1. 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<^boolean isConst> (. boolean alsoConst; .)
= ( "+" Term<^isConst>
| "-" Term<^isConst>
| Term<^isConst>
)
{ AddOp Term<^alsoConst> (. isConst = isConst && alsoConst; .)
} .
Term<^boolean isConst> (. boolean alsoConst; .)
= Factor<^isConst>
{ MulOp Factor<^alsoConst> (. isConst = isConst && alsoConst; .)
} .
Factor<^boolean isConst>
= Designator<^isConst>
| number (. isConst = true; .)
| "(" Expression<^isConst> ")"
.
2. 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)?
Two solutions follow. In the first one we simply use some static fields in the Parser class to record the quantities of interest:
import Library.*;
COMPILER EBNF $CN
/* Describe simple EBNF productions and find which has the longest right side
P.D. Terry, Rhodes University, 2003 */
static String thisName, maxName;
static int maxLength = 0;
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 (. int maxRHS; .)
= { Production<^maxRHS> (. if (maxRHS > maxLength) maxName = thisName; .)
} (. IO.writeLine("Longest production was for "
+ maxName); .)
EOF .
Production<^int maxRHS>
= SYNC nonterminal (. thisName = token.str; .)
WEAK "="
Expression<^maxRHS>
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> (. factorLength = 0; .)
= nonterminal (. factorLength = 1; .)
| terminal (. factorLength = 1; .)
| "[" Expression<^factorLength> "]"
| "(" Expression<^factorLength> ")"
| "{" Expression<^factorLength> "}"
.
END EBNF.
In the second solution we show how one can arrange for parsing methods to return objects that encapsulate the quantities of interest:
import Library.*;
COMPILER EBNF $CN
/* Describe simple EBNF productions and find which has the longest right side
P.D. Terry, Rhodes University, 2003 */
static class Prod {
public String name = "";
public int maxRHS = 0;
}
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 (. Prod bigProd = new Prod(), nextProd; .)
= { Production<^nextProd> (. if (nextProd.maxRHS > bigProd.maxRHS)
bigProd = nextProd; .)
} (. IO.writeLine("Longest production was for "
+ bigProd.name); .)
EOF .
Production<^Prod p> (. p = new Prod(); .)
= SYNC nonterminal (. p.name = token.str; .)
WEAK "="
Expression<^p.maxRHS>
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> (. factorLength = 0; .)
= nonterminal (. factorLength = 1; .)
| terminal (. factorLength = 1; .)
| "[" Expression<^factorLength> "]"
| "(" Expression<^factorLength> ")"
| "{" Expression<^factorLength> "}"
.
END EBNF.