[plt-scheme] BNF parser generator
I've written a little parser generator for BNF grammars that turned out
pretty well. It's similar to Dorai Sitaram's implementation of regular
expressions (i.e., the two-continuation backtracking model).
http://www.ccs.neu.edu/home/dherman/code/grammar.ss
As an example, here's a grammar for a miniature regular expression
language:
;; --
(define regexp-grammar
(grammar Regexp
[Regexp (alt (seq (lambda (left bar right)
`(:or ,left ,right))
Pieces "|" Regexp)
Pieces)]
[Pieces (alt (seq (lambda (fst snd)
(match snd
[`(:seq . ,seq) `(:seq ,fst , at seq)]
[_ `(:seq ,fst ,snd)]))
Piece Pieces)
Piece)]
[Piece (alt (seq (lambda (atom star)
`(:star ,atom))
Atom "*")
Atom)]
[Atom (alt (seq (lambda (lp body rp)
`(:sub ,body))
"(" Regexp ")")
(not-in "()*|"))]))
;; --
Take a look at the code if you're interested -- I think it's a nice
example of combinators, continuations, and even (though not explicit)
monadic style.
Dave