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.
As some of you may know, my brother Peter occasionally brightens up your TV screens with good advice as to how to keep your bathroom walls beautiful with tiles from CTM. (I suspect he may teach you more useful skills than I do!); he also has been known to appear occasionally in "Generations" and "PopIdols". What you may not know is that he worked for State Theatre in Pretoria, which folded up a few years ago, so he is dependent more than ever before on how the SABC treat him.
The SABC fear that he may be suffering from over-exposure and have asked me to extend/write a system to allow them to check that he never appear in two advertisements in a row (that is, that any CTM adverts must be separated by at least one other advert), and that no CTM advert immediately follows a screening of "Generations" or "PopIdols".
I have got as far as the following grammar. How do I add the attributes and actions to produce a system that I can sell to the SABC for Big Bucks?
COMPILER SABCTV $CN
/* Save Peter Terry from over exposure on SABC TV */
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
SABCTV = { Programme } "Closedown" .
Programme = "Announcement" { QualityShow }
"Reminder" /* you know it's the right thing to do */ .
QualityShow = ( "Frasier" | "PopIdols" | "MyFamily" | "Generations" ) { Advert } .
Advert = "CTMTiles" | "Domestos" | "VodaCom" | "Nando's" | "LGDigital" .
END SABCTV.
Written out ready to attribute:
COMPILER SABCTV $CN
/* Save Peter Terry from over exposure on SABC TV */
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
SABCTV
= { Programme
}
"Closedown"
.
Programme
= "Announcement"
{ QualityShow
}
"Reminder"
.
QualityShow
= (
"Frasier"
| "PopIdols"
| "MyFamily"
| "Generations"
)
{ Advert
}
.
Advert
= "CTMTiles"
| "Domestos"
| "VodaCom"
| "Nando's"
| "LGDigital"
.
END SABCTV.