Note 3, DM546, fall 2019
Lecture February 11
-
The tool
bison.
-
Abstract Syntax Trees.
Background material: Appel Chapters 4, Bison documentation.
With regards to literature and material on bison, see the literature page.
Exercises February 15
-
Appel 3.1, 3.3 a-c, 3.10, 3.15.
-
We have considered grammars with rules for
'+', '-', '*', '/', id, num and parentheses.
Expand these grammars with boolean operators (and, or, not) and
comparisons (==, <=, etc.)
in such a way that you get the usual precedens and associativity.
Use the slide introducing an unambiguous grammar for expressions
as your starting point.
-
Show that the grammar below is LR(1), but not LALR(1), i.e., it works
making an LR(1) parser table, but something goes wrong when you make
the transition to an LALR(1) table.
Recall that the |-shorthand used below indicates four S-productions.
Remember first to introduce a new nonterminal and an eof-symbol ($).
- S → a E a | b E b | a F b | b F a
- E → e
- F → e