[plt-scheme] BNF parser generator

From: David Herman (dherman at ccs.neu.edu)
Date: Fri Jan 16 01:08:41 EST 2004

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



Posted on the users mailing list.