1. The simple grammar below describes railway trains (it is similar to one discussed in a previous prac test):
How would you add actions and attributes to the grammar so that it will
(a) Parse the data file (b) Count and report on the number of locomotives, trucks, and passenger coaches in each valid train (c) In the interests of safety, satisfy a regulation to the effect that fuel trucks may not be marshalled immediately behind the locomotives, or immediately in front of a passenger coach.
COMPILER Train $CNX
/* Grammar for railway trains with simple safety regulations
P.D. Terry, Rhodes University, 2000 */
#include "misc.h"
enum KINDS {SafeTruck, FuelTruck, Loco};
bool Safe;
int Trucks, Locos, Coaches;
KINDS LastKind;
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
Train = { OneTrain } EOF .
OneTrain
= (. Trucks = Locos = Coaches = 0;
Safe = TRUE; .)
LocoPart GoodsPart HumanPart (. printf("%d locos %d trucks %d coaches -", Locos, Trucks, Coaches);
printf(" safety regulations ");
if (Safe) printf("obeyed\n");
else printf("contravened\n"); .)
SYNC "." .
LocoPart
= "loco" (. Locos++; LastKind = Loco; .)
{ "loco" (. Locos++; .)
} .
GoodsPart = Truck { Truck } .
HumanPart
= "guard" (. Trucks++; .)
| (. if (LastKind == FuelTruck) Safe = FALSE; .)
{ "coach" (. Coaches++; .)
} "brake" (. Coaches++; .) .
Truck
= (. Trucks++ .)
( "coal" | "open" | "cattle" ) (. LastKind = SafeTruck; .)
| "fuel" (. if (LastKind == Loco) Safe = FALSE;
LastKind = FuelTruck; .) .
END Train.
2. Consider the by now rather hackneyed grammar for expressions which has been written out again below. How would you add attributes so that a parser, after recognising an Expression, would be able to determine whether that Expression was a "constant expression" (meaning that in principle it could be evaluated at compile time) or was a "variable expression" (meaning that it could not be evaluated until run time)? Assume that the Designator production can be attributed so that it returns the result of searching the symbol table to determine whether the associated identifier denotes a variable or a constant.
Expression<bool &isConst>
= (. bool alsoConst; .)
( "+" Term<isConst>
| "-" Term<isConst>
| Term<isConst>
) { AddOp
Term<alsoConst> (. isConst = isConst && alsoConst; .)
}
.
Term<bool &isConst>
= (. bool alsoConst; .)
Factor<isConst>
{ MulOp
Factor<alsoConst> (. isConst = isConst && alsoConst; .)
}
.
Factor<bool &isConst>
= Designator<isConst>
| number (. isConst = true; .)
| "(" Expression<isConst> ")"
.
3. Consider the familiar grammar below for describing a set of EBNF productions. How could you add attributes to this grammar so that it could determine which non-terminal had the longest right hand side (in terms of the number of terminals and non terminals in any one of its alternatives)?
COMPILER EBNF $CXN
/* Describe simple EBNF productions and find which has the longest right side
P.D. Terry, Rhodes University, 2000 */
#include <stdio.h>
#include <string.h>
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
IGNORE CHR(9) .. CHR(13)
TOKENS
nonterminal = letter {letter | digit } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
PRODUCTIONS
EBNF
= (. char Name[50], LongestName[50];
int Length, LongestLength = 0; .)
{ Production<Name, Length>
(. if (Length > LongestLength) {
LongestLength = Length;
strcpy(LongestName, Name);
} .)
} (. printf("Longest production was for %s\n", LongestName); .)
EOF .
Production<char Name[], int &LongestRHS>
= SYNC nonterminal (. LexString(Name, 50); .)
WEAK "="
Expression<LongestRHS> SYNC "." .
Expression<int &ExpLength>
= (. int AltLength; .)
Term<ExpLength>
{ WEAK "|" Term<AltLength> (. if (AltLength > ExpLength)
ExpLength = AltLength; .)
} .
Term<int &TermLength>
= (. int N; TermLength = 0; .)
[ Factor<TermLength> { Factor<N> (. TermLength += N; .)
} ] .
Factor<int &FactorLength>
=
nonterminal (. FactorLength = 1; .)
| terminal (. FactorLength = 1; .)
| "[" Expression<FactorLength> "]"
| "(" Expression<FactorLength> ")"
| "{" Expression<FactorLength> "}" .
END EBNF.