COMS W4115
Programming Languages and Translators
Lecture 10: Implementing a Parser with Yacc
February 23, 2015

Lecture Outline

  1. Issues arising in implementing a parser with Yacc
  2. Shift/reduce conflicts
  3. Using Yacc to generate LALR(1) parsers
  4. Using Yacc with ambiguous grammars
  5. Error recovery in Yacc

1. Issues Arising in Implementing a Parser with Yacc

2. Shift/Reduce Conflicts

3. Using Yacc with Ambiguous Grammars

4. The "Dangling-Else" Ambiguity

5. Error Recovery in Yacc

6. Practice Problems

    Consider the following grammar G:
  1. What language does G generate?
  2. Construct an SLR(1) parsing table for G.
  3. Explain why the parsing action conflicts arise in the parsing table.
  4. Construct an equivalent LALR(1) grammar for L(G).
  5. Show that your grammar is LALR(1) by using yacc to construct an LALR(1) parsing table for it.
  6. Is your grammar LL(1)?

7. Reading



aho@cs.columbia.edu