4.10 The following EBNF grammar generates a subset of the UNIX shell command language:
Script ::= Command*
Command ::= Filename Argument* eol
| Variable = Argument eol
| if Filename Argument* then eol
Command*
else eol
Command*
fi eol
| for Variable in Argument* eol
do eol
Command*
od eol
Argument ::= Filename | Literal | Varialbe
The start symbol is Script. The token eol corresponds to an end-of-line.
Construct a recursive-descent parser for this language. Treat filenames, literals, and variables as single tokens.
Sol.
private void parseScript ( ) {
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Variable
|| currentToken.kind == Token.if
|| currentToken.kind == Token.for)
parseCommand ( );
}
private void parseCommand ( ) {
switch (currentToken.kind) {
case Token.Filename: {
acceptIt ( );
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Literal
|| cuurentToken.kind == Token.Variable)
parseArgument ( );
accept(Token.eol)
}
break;
case Token.Variable: {
acceptIt ( );
accept(Token.equal);
parseArgument ( );
accept(Token.eol);
}
break;
case Token.if: {
acceptIt ( );
accept(Token.Filename);
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Literal
|| cuurentToken.kind == Token.Variable)
parseArgument ( );
accept(Token.then);
accept(Token.eol);
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Variable
|| currentToken.kine == Token.if
|| currentToken.kind == Token.for)
parseCommand ( );
accept(Token.else);
accept(Token.eol);
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Variable
|| currentToken.kine == Token.if
|| currentToken.kind == Token.for)
parseCommand ( );
accept(Token.fi);
accept(Token.eol);
}
break;
case Token.for: {
acceptIt( );
accept (Token.Variable);
accept (Token.in);
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Literal
|| cuurentToken.kind == Token.Variable)
parseArgument ( );
accept(Token.eol);
accept(Token.do);
accept(Token.eol);
while (currentToken.kind == Token.Filename
|| currentToken.kind == Token.Variable
|| currentToken.kine == Token.if
|| currentToken.kind == Token.for)
parseCommand ( );
accept(Token.od);
accept(Token.eol);
}
break;
default :
report a syntactic error
}
private void parseArgument ( ); {
switch (currentToken.kind) {
case Token.Filename:
acceptIt ( );
break;
case Token.Literal:
acceptIt ( );
break;
case Token.Variable:
acceptIt ( );
break;
default:
report a syntactic error
}
4.17 The Mini-Triangle scanner (Example 4.21) stores the spellings of separators, including comments, only to discard them later. Modify the scanner to avoid this inefficiency.
Sol.
We only need to modify the scanSeparator where take/takeIt are changed to taking nothing.
private void scanSeparator ( ) {
switch (currentChar) {
case ‘!’: {
currentChar = next source character;
while (
isGraphic (currentChar))
currentChar = next source character;
if (currentChar == ‘\n’)
currentChar = next source character;
else
report a lexical error
}
break;
case ‘ ’: case ‘\n’ :
currentChar = next source character;
break;
}
}
5.8 Consider the following Triangle record types:
type T1 = record i: Integer; c: Char end;
type T2 = record j: Integer; h: Char end;
type T3 = record c: Char; i: Integer end
No two of these types are equivalent, since a Triangle record type is characterized by the identifiers, types, and order of its fields. The typeDecoter class’s equals method tests whether the two type ASTs are structurally identical.
Suppose, hypothetically, that two alternative ways of characterizing a Triangle record type are being considered. In each case, describe how the equals method would be modified.
(a) A record type is to be characterized only by the types and order of its fields (ignoring their identifiers). Thus types T1 and T2 (but not T3) are to be equivalent.
(b) A record type is to be characterized only by the identifiers and types of its fields (ignoring their order). Thus types T1 and T3 (but not T2) are to be equivalent.
Sol.
(a) Eliminate identifiers from ASTs or remove spelling check from the equals methods.
(b) Reconstruct ASTs so that record fields are in the order of identifiers, then apply equals methods.