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
=
( "+" Term
| "-" Term
| Term
) { AddOp
Term
} .
Term
= Factor
{ MulOp
Factor
} .
Factor
=
Designator
| number
| "(" Expression
")" .
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)?
COMPILER EBNF $CN
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
TOKENS
nonterminal = letter {letter | lowline } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF
=
{ Production
}
EOF .
Production
=
SYNC nonterminal
WEAK "="
Expression
SYNC "." .
Expression
=
Term
{ WEAK "|" Term
} .
Term
=
[ Factor
{ Factor
}
] .
Factor
=
nonterminal
| terminal
| "[" Expression "]"
| "(" Expression ")"
| "{" Expression "}" .
END EBNF.
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 check a set of productions to determine whether any non-terminals had not been defined, and whether any non-terminals could not possibly be reachable?
COMPILER EBNF $CN
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
TOKENS
nonterminal = letter {letter | lowline } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF
=
{ Production
}
EOF
.
Production
= SYNC nonterminal
WEAK "="
Expression
SYNC "." .
Expression
= Term
{ WEAK "|" Term
} .
Term
= [ Factor
{ Factor
}
] .
Factor
=
nonterminal
| terminal
| "[" Expression "]"
| "(" Expression ")"
| "{" Expression "}" .
END EBNF.