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<out boolean isConst> (. boolean alsoConst; .)
= ( "+" Term<out isConst>
| "-" Term<out isConst>
| Term<out isConst>
)
{ AddOp Term<out alsoConst> (. isConst = isConst && alsoConst; .)
} .
Term<out boolean isConst> (. boolean alsoConst; .)
= Factor<out isConst>
{ MulOp Factor<out alsoConst> (. isConst = isConst && alsoConst; .)
} .
Factor<out boolean isConst>
= Designator<out isConst>
| number (. isConst = true; .)
| "(" Expression<out 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, 2008 */
static String thisName, maxName;
static int maxLength = 0;
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
TOKENS
nonterminal = letter {letter | digit } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF (. int maxRHS; .)
= { Production<out maxRHS> (. if (maxRHS > maxLength) maxName = thisName; .)
} (. IO.writeLine("Longest production was for "
+ maxName); .)
EOF .
Production<out int maxRHS>
= SYNC nonterminal (. thisName = token.val; .)
WEAK "="
Expression<out maxRHS>
SYNC "." .
Expression<out int expLength> (. int altLength; .)
= Term<out expLength>
{ WEAK "|" Term<out altLength> (. if (altLength > expLength)
expLength = altLength; .)
} .
Term<out int termLength> (. int N; termLength = 0; .)
= [ Factor<out termLength>
{ Factor<out N> (. termLength += N; .)
}
] .
Factor<out int factorLength> (. factorLength = 0; .)
= nonterminal (. factorLength = 1; .)
| terminal (. factorLength = 1; .)
| "[" Expression<out factorLength> "]"
| "(" Expression<out factorLength> ")"
| "{" Expression<out 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, 2008 */
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} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF (. Prod bigProd = new Prod(), nextProd; .)
= { Production<out nextProd> (. if (nextProd.maxRHS > bigProd.maxRHS)
bigProd = nextProd; .)
} (. IO.writeLine("Longest production was for "
+ bigProd.name); .)
EOF .
Production<out Prod p> (. p = new Prod(); .)
= SYNC nonterminal (. p.name = token.val; .)
WEAK "="
Expression<out p.maxRHS>
SYNC "." .
Expression<out int expLength> (. int altLength; .)
= Term<out expLength>
{ WEAK "|" Term<out altLength> (. if (altLength > expLength)
expLength = altLength; .)
} .
Term<out int termLength> (. int N; termLength = 0; .)
= [ Factor<out termLength>
{ Factor<out N> (. termLength += N; .)
}
] .
Factor<out int factorLength> (. factorLength = 0; .)
= nonterminal (. factorLength = 1; .)
| terminal (. factorLength = 1; .)
| "[" Expression<out factorLength> "]"
| "(" Expression<out factorLength> ")"
| "{" Expression<out factorLength> "}"
.
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.
Attributed it would look like this:
COMPILER SABCTV $CN
/* "Bob, Bob" - check over-exposure of Peter Terry on SABC TV
A very simple problem can be solved in a very simple way! */
static boolean justSeenPeter = false;
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
SABCTV = { Programme } "Closedown" .
Programme = "Announcement" { QualityShow } "Reminder" .
QualityShow
= ( ( "Frasier" | "MyFamily" ) (. justSeenPeter = false; .)
| ( "PopIdols" | "Generations" ) (. justSeenPeter = true; .)
) { Advert } .
Advert
= "CTMTiles" (. if (justSeenPeter) SemError("Peter over exposed!");
justSeenPeter = true; .)
| ( "VodaCom" | "Nando's"
| "LGDigital" | "Domestos" ) (. justSeenPeter = false; .) .
END SABCTV.
The alternative below forbids PopIdols or Generations to follow a CTM advert. Not quite what was asked!
QualityShow
= ( ( "Frasier" | "MyFamily" ) (. justSeenPeter = false; .)
| ( "PopIdols" | "Generations" ) (. if (justSeenPeter) SemError("Peter over exposed!");
justSeenPeter = true; .)
) { Advert } .
You might like to think carefully about what the following alternative would allow or forbid:
QualityShow (. justSeenPeter = false; .)
= ( ( "Frasier" | "MyFamily" )
| ( "PopIdols" | "Generations" ) (. if (justSeenPeter) SemError("Peter over exposed!");
justSeenPeter = true; .)
) { Advert } .