Friday, March 26, 2010

parsing with pattern matching

Parsing with pattern matching is pretty sweet.

Here's a test grammar:

# test a simple predicate language
expr: predicate | atom
list: expr ("," expr)*
predicate: NAME "(" list ")"
atom: NAME | NUMBER | STRING


And the pattern-matching code to parse it into an AST:

(datatype atom
  (:name string)
  (:number int)
  (:string string)
  )

(datatype expr
  (:pred string (list (expr)))
  (:atom (atom))
  )

(define p-atom
  (item:t 'NAME x)   -> (atom:name x)
  (item:t 'NUMBER x) -> (atom:number (string->int x))
  (item:t 'STRING x) -> (atom:string x)
  _ -> (error "p-atom")
  )

(define p-list3
  (list:cons (item:t 'comma _) 
  (list:cons x 
  (list:nil))) -> (p-expr x)
  _ -> (error "p-list3")
  )

(define p-list2
  (item:nt 'list_c_1_s1 (list:cons x y)) -> (list:cons (p-list3 y) (p-list2 x))
  (item:nt 'list_c_1_s1 (list:nil))      -> (list:nil)
  _ -> (error "p-list2")
  )

(define p-list
  (item:nt 'list (list:cons expr 
                 (list:cons rest 
                 (list:nil)))) -> (list:cons (p-expr expr) (p-list2 rest))
  _ -> (error "p-list")
  )

(define p-expr2
  (item:nt 'predicate
           (list:cons (item:t 'NAME name)
           (list:cons _ ;; lparen
           (list:cons args
           (list:cons _ ;; rparen
           (list:nil))))))
  -> (expr:pred name (p-list args))

  (item:nt 'atom (list:cons x (list:nil))) -> (expr:atom (p-atom x))
  y -> (error y)
  )

(define p-expr
  (item:nt 'expr (list:cons x (list:nil))) -> (p-expr2 x)
  _ -> (error "p-expr")
  )

The patterns are a little noisy due to my lack of a special syntax for lists. I'm still on the fence about whether that's a good idea.

No comments:

Post a Comment