Section notes: Week 6

CS 164, Fall 2005

Administravia

• Section evaluations?
• Exam follow-up questions?
• HW (for next week's section): Extend the LALR(1) parser for the RPN language from today's class to include - and swap operations. Include augments.

Example: RPN parsing

Consider a simple stack-based calculator language (like RPN for HP calculators):

  S -> S S +
  S -> S S *
  S -> int

We can rewrite this as an LL(1) grammar (what do S1 and S0 represent?):

  S1 -> int S0
  S0 -> S1 F S0
  S0 ->
  F  -> +
  F  -> *

• How would you augment the LR(1) grammar to evaluate expressions?
• How would you augment the LL(1) grammar to evaluate expressions?
• Can you write a recursive-descent evaluator?
• What does an LR(0) state table look like?
• Example trace: 1 4 * 1 + 7 1 2 + *

Example: expressions

Why might we not like the parse tree from this grammar?

  E -> T + E
  E -> T - E
  E -> T
  F -> int

What augments would we use for this grammar?

  E -> E + T
  E -> T
  T -> T * F
  T -> F
  F -> int

What is the parse tree for 2 * 3 - 4 + 5 * 5?

A trickier example

  P  -> DS ES
  DS -> DS D
  DS ->
  ES -> ES E
  ES -> 
  D -> id id ;
  E -> id = id ;

Is this grammar LR(1)?

Question for next time

Consider the grammar G1 from jy.lisp, which describes simple expressions. Can you extend G1 so that it not only supports subtraction (a - b), but also negation (-a)?