Rewrite the following grammars so as to eliminate the Wirth meta-brackets { } and [ ] and hence (or otherwise) test the grammars for being LL(1) compliant. If they are not LL(1) compliant, can you find equivalent LL(1) compliant grammars?
You can find the sources for these grammars in the file tut31.zip.
COMPILER Course
/* Grammar describing history of a university course */
PRODUCTIONS
Course = Introduction Section { Section } Conclusion .
Introduction = "lecture" [ "handout" ] .
Section = { "lecture" | "practical" "test" | "tutorial" | "handout" } "test" .
Conclusion = [ "panic" ] "examination" .
END Course.
Change the PRODUCTIONS section to read
PRODUCTIONS
Course = Introduction Section MoreSections Conclusion .
MoreSections = Section MoreSections | e .
Introduction = "lecture" OptionalHandout .
OptionalHandout = "handout" | e .
Section = Subsections "test" .
Subsections = Delivery Subsections | e
Delivery = "lecture" | "practical" "test" | "tutorial" | "handout"
Conclusion = OptionalPanic"examination" .
OptionalPanic = "panic" | e .
END Course.
The grammar is non LL(1). OptionalHandout is nullable, and
FIRST(OptionalHandout) = { "handout" }
FOLLOW(OptionalHandout) = FIRST(Section)
= { "lecture" , "practical" "test" , "tutorial" , "handout" }
The other nullable non-terminals do not raise any problems.
COMPILER RE
/* Regular expression grammar */
CHARACTERS
control = CHR(0) .. CHR(31) .
noquote1 = ANY - control - "'" .
noquote2 = ANY - control - '"' .
meta = "()*,.;[]-?+" .
simple = ANY - control - "'" - '"' - meta .
backslash = CHR(92) .
TOKENS
atomic = simple .
escaped = "'" noquote1 "'" | '"' noquote2 '"' .
COMMENTS FROM backslash TO backslash
IGNORE control
PRODUCTIONS
RE = { Expression ";" } EOF .
Expression = Term { "|" Term } .
Term = Factor { [ "." ] Factor } .
Factor = Element [ "*" | "?" | "+" ] .
Element = Atom | Range | "(" Expression ")" .
Range = "[" OneRange { OneRange } "]" .
OneRange = Atom [ "-" Atom ] .
Atom = atomic | escaped .
END RE.
Change the PRODUCTIONS section to read
PRODUCTIONS
RE = Expressions EOF .
Expressions = Expression ";" Expressions | e .
Expression = Term MoreTerms .
MoreTerms = "|" Term MoreTerms | e .
Term = Factor MoreFactors .
MoreFactors = OptionalDot Factor MoreFactors | e .
OptionalDot = "." | e .
Factor = Element OptionalSuffix .
OptionalSuffix = "*" | "?" | "+" | e .
Element = Atom | Range | "(" Expression ")" .
Range = "[" OneRange MoreRanges "]" .
MoreRanges = OneRange MoreRanges | e .
OneRange = Atom OptionalAtom .
OptionalAtom = "-" Atom | e .
Atom = atomic | escaped .
END RE.
This is an LL(1) grammar. The full analysis is easy enough to do.
COMPILER Play
/* Grammar for Shakespearian play */
PRODUCTIONS
Play = Act Act Act "interval" Act Act .
Act = Scene { Scene } .
Scene = { "speech" } "entry" { Action } .
Action = "speech" | "entry" | "exit" | "death" | "gesticulation" .
END Play.
Change the PRODUCTIONS section to read
PRODUCTIONS
Play = Act Act Act "interval" Act Act .
Act = Scene MoreScenes .
MoreScenes = Scene MoreScenes | e .
Scene = Speeches "entry" Actions .
Speeches = "speech" Speeches | e .
Actions = Action Actions | e .
Action = "speech" | "entry" | "exit" | "death" | "gesticulation" .
END Play.
Here MoreScenes, Speeches and Actions are nullable
FIRST(MoreScenes) = { "speech", "entry" }
FOLLOW(MoreScenes) = FOLLOW(Act)
= First(Act) U { "interval" }
= FIRST(Scene) U { "interval" } = { "speech", "entry", "interval" }
so the grammar is non-LL(1).
FIRST(Speeches) = { "speech" }
FOLLOW(Speeches) = { "entry" }
so no problem there
FIRST(Actions) = { "entry", "speech", "exit", "death", "gesticulation" }
FOLLOW(Actions) = Follow(Scene) = { "interval", "entry", "speech" }
so the grammar is non-LL(1) there as well.
Ignoring any LL(1) problems - how would you attribute this last grammar to check that there were no actors left on the stage at the end of every act?
The only way to "fix" this probably is to have some sort of extra visual cue - like curtains or lights being raised and lowered to mark one scene or act from another.
Clearly this won't work, properly, but the idea would be
COMPILER Play
/* Grammar for Shakespearian play */
int onStage = 0; /* can get away with a global count */
PRODUCTIONS
Play
= Act Act Act "interval" Act Act .
Act (. onStage = 0; .)
= Scene { Scene } (. if (onstage > 0) SemError("some actors are still on stage"); .)
.
Scene
= { "speech" } "entry" (. onstage++; .)
{ Action } .
Action
= "speech"
| "entry" (. onstage++; .)
| "exit" (. onstage--;
if (onStage < 0) SemError("more actors have left than have entered"); .)
| "death"
| "gesticulation" .
END Play.