Work Note 3, DM546, Spring 2017

Lecture February 7

• The tool bison.
• Abstract Syntax Trees.

Exercises February 10

• 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 transparency 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