Section notes: Week 5

CS 164, Fall 2005

Exam prep

• What's the muddiest point for you in the course?
• Any questions about material for the exam?
• My recommendations for preparation:
  • Do the reading and review the lecture slides
  • Try old exams (available on the web page)
  • Start assignment 3 (look at the recdec315 codes)
  • Ask questions: of each other, of the professor and me, on the newsgroup

LL(1) parsing

• Example: The multiples of 5 DFA
  • Deriving the DFA
  • Writing an LL(1) grammar
  • Writing an LR(0) grammar
• Example: if, in, the, then
  • Writing a grammar
  • First, follow, and null
  • Parse tables
  • Left factoring
• Example: Nested comment parsing
  • Writing a grammar
  • Building the parse table
  • Right recursion
• Strategic comments:
  • Automation of LL(1) parsing
  • Why LL(1) or LR(1)?

Exercises

Nickle rational numbers can be written as int.fixed{repeat}. For example, the fraction 4/3 would be written as 1.{3}. The integer part is not optional, so 1/3 is written 0.{3}, not .{3}.

• Write a regular expression for Nickle rational numbers.
• Construct a finite state machine to recognize Nickle numbers.
• Write an LL(1) grammar for Nickle rational numbers.

Write a Lisp function to evaluate simple numerical expressions that satisfy the following grammar (digits, +, and - are the terminal symbols.

  S -> S + I | S - I | I
  I -> 0 | N R
  R -> D R | epsilon
  N -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  D -> 0 | N

Question for next time

The program recdec315s.cl is an example of a hand-written LL(1) parser that produces a useful abstract syntax tree. The MJ grammar I came up with has 76 productions, and I didn't feel like writing all the Lisp functions by hand. So I wrote a tool, make-ll1, which (similar to the wrapper from make-lalr) defines a macro def-ll1 to take a list of production forms like (lhs (rhs) augment) and produce an augmented LL(1) parse table. Using make-ll1, my parser to produce ASTs for grammar 3.15 looks like this:

;; Define an LL(1) parser
(def-ll1 *g315-table*

  ;; Statement
  (S  (E eof)     %0)

  ;; Left-factored sum list
  (E  (T Ep)      (sum-tree %0 %1))
  (Ep (+ T Ep)    `(+ ,%1 . ,%2))
  (Ep (- T Ep)    `(- ,%1 . ,%2))
  (Ep ()          nil)

  ;; Left-factored product list
  (T  (F Tp)      (sum-tree %0 %1))
  (Tp (* F Tp)    `(* ,%1 . ,%2))
  (Tp (/ F Tp)    `(/ ,%1 . ,%2))
  (Tp ()          nil)

  ;; Terminals and parened exprs
  (F  (id)         %0)
  (F  (num)        %0)
  (F  (#\( E #\))  %1))

What do you think sum-tree looks like? An alternate way to get the correct associativity is to pass around lambda functions corresponding to partially-evaluated trees; can you think how you might write that? Compare this parser to the sample LALR(1) parsers in jy.lisp. Which do you prefer, and why?