You can find the source for these grammars on the WWW page in the file TUT4.ZIP.
Are the following grammars LL(1) compliant? If not, why not?
COMPILER A $TF
PRODUCTIONS
A = B ( "x" | "z" ) ( "w" | "z" ) B .
B = "x" B "z" | { "y" } .
END A.
COMPILER S $FT
PRODUCTIONS
S = A | B .
A = C D | E "f" .
B = "d" | "e" .
C = [ "a" | "b" ] .
D = [ "c" | "e" ] .
E = "f" | "g" .
END S.
COMPILER Z $TF
PRODUCTIONS
Z = B C | D E .
B = [ E ] .
C = "x" E .
D = E { Z } ( E | "w" ) .
E = "y" | "z" .
END Z.
The following describes a silly computer language. Study it carefully and decide whether it is LL(1) compliant. If not, explain why, and make suggestions as to how it might be slightly modified in that case so that a recursive descent parser could be constructed for it.
COMPILER Block $TF
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
TOKENS
identifier = letter { letter } .
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Block = "BEGIN" StatementSequence "END" .
StatementSequence = Statement { ";" Statement } .
Statement = [ Block | Declaration | Assignment
| WhileStatement | DoStatement | IfStatement ].
Declaration = identifier { "," identifier } ":" Type .
IfStatement = "IF" Expression
[ "THEN" ] StatementSequence
[ "ELSE" StatementSequence ] .
Expression = identifier . /* for illustration only */
WhileStatement = "WHILE" Expression "DO" StatementSequence "END" .
DoStatement = "DO" StatementSequence "WHILE" Expression .
Assignment = identifier ":=" Expression .
Type = "INTEGER" | "BOOLEAN" | "CHAR" .
END Block.
Would it perhaps have been wiser to try to write the grammar with the following alternative for IfStatement?
IfStatement = "IF" Expression
( Statement | "THEN" Statement "ELSE" Statement ) .
As a more interesting example of applying an analysis to a grammar expressed in EBNF, let us consider how we might describe the theatrical production of a Shakespearian play with five acts. In each act there may be several scenes, and in each scene appear one or more actors, who gesticulate and make speeches to one another (for the benefit of the audience, of course). Actors come onto the stage at the start of each scene, and come and go as the scene proceeds - to all intents and purposes between speeches - finally leaving at the end of the scene (in the Tragedies some may leave dead, but even these usually revive themselves in time to go home). Plays are usually staged with an interval between the third and fourth acts.
Actions like "speech", "entry" and "exit" are really in the category of the lexical terminals which a scanner (in the person of a member of the audience) would recognize as key symbols while watching a play.
Analyse this grammar in detail. If it proves out to be non-LL(1), try to find an equivalent that is LL(1), or argue why this should be impossible.