UP | HOME

Summary: PLAI Ch.2 — Everything (We Will Say) About Parsing

Table of Contents

Key Claims

  • PLAI deliberately minimises the treatment of parsing, exploiting Lisp's s-expression syntax to sidestep most parsing complexity.
  • read (Racket) converts parenthesised input into a tree of s-expressions unambiguously; quotation 'expr is its shorthand.
  • A parser in PLAI is a thin function from s-expressions to a typed AST (ArithC here). It is separate from the interpreter.
  • The resulting "bicameral" two-level design (s-expression reader + typed parser) cleanly separates surface syntax from internal representation.
  • In Common Lisp / tolk, Lisp's built-in reader plays the same role as Racket's read; ematch with quasiquote patterns replaces cond on s-expression predicates.

Summary

Chapter 2 argues that parsing is a distraction from the study of language semantics. PLAI exploits Racket's s-expression reader (read) as a free, unambiguous first parsing phase, leaving only a thin second phase to convert s-expressions into typed AST nodes.

The two-level (bicameral) design

  1. Lower level (reader): read / quotation turns character streams into s-expressions. No ambiguity because fully-parenthesised input is unambiguous.
  2. Upper level (parser): A function parse : s-expression → ArithC converts s-expressions into properly typed AST nodes, doing rudimentary well-formedness checking.
(define-type ArithC
  [numC (n : number)]
  [plusC (l : ArithC) (r : ArithC)]
  [multC (l : ArithC) (r : ArithC)])

(define (parse [s : s-expression]) : ArithC
  (cond
    [(s-exp-number? s) (numC (s-exp->number s))]
    [(s-exp-list? s)
     (let ([sl (s-exp->list s)])
       (case (s-exp->symbol (first sl))
         [(+) (plusC (parse (second sl)) (parse (third sl)))]
         [(*) (multC (parse (second sl)) (parse (third sl)))]
         [else (error 'parse "invalid list input")]))]
    [else (error 'parse "invalid input")]))

Tolk / Common Lisp correspondence

In tolk, the s-expression is a native Lisp value (no s-exp->list casting needed). The parser uses ematch with quasiquote patterns: 

(defmethod parse (sexp)
  (ematch sexp
    ((type number) (make-instance 'num :n sexp))
    (`(+ ,l ,r) (make-instance 'plus :l (parse l) :r (parse r)))
    (`(* ,l ,r) (make-instance 'mult :l (parse l) :r (parse r)))))

The typed s-expression type in plai-typed — which requires explicit casts via s-exp->number, s-exp->symbol etc. — has no counterpart in Common Lisp, where values carry their types at runtime and pattern matching is direct.

Related