Announce: D Parser (a scannerless GLR parser)

John Plevyak <>
22 Mar 2003 15:57:29 -0500

          From comp.compilers

Related articles
Announce: D Parser (a scannerless GLR parser) (John Plevyak) (2003-03-22)
Re: Announce: D Parser (a scannerless GLR parser) (Ron Pinkas) (2003-03-24)
| List of all articles for this month |

From: John Plevyak <>
Newsgroups: comp.compilers
Date: 22 Mar 2003 15:57:29 -0500
Organization: Prodigy Internet
Keywords: parse, tools, available
Posted-Date: 22 Mar 2003 15:57:29 EST

Coming on the heals of the recent discussion of GLR parsing I would
like to announce the availability of D Parser v1.0, a scannerless
GLR parser generator based on the Tomita algorithm.

It implements a novel solution to the right epsilon problem pointed
out in the previously mentioned "Tomita-Syle Generalized LR Parsers"
paper by Elizabeth Scott, Adrian Johnstone, and Shamsa Sadaf Hussain
which doesn't require changing the parsing tables (since that
complicates handing of actions). Other than that, the core is
essentially the same as the algorithm which they prove correct in that

It is intended to be simple, flexible, extensible and above all

Here is a partial list of features:

          * Really simple!
          * EBNF-style grammars
          * Regular expression terminals
          * Priorities and associativities for token and rules
          * Built-in error recovery
          * Partial parses
          * Speculative actions (for semantic disambiguation)
          * Optional auto-building of parse tree
          * Final actions as you go, or on the complete parse tree
          * Includes a symbol table built for ambiguous parsing
          * Left-epsilon rule actions are invoked the 'correct' number of times
          * Support for parsing starting with any non-terminal
          * Recursive parsing
          * Whiltespace can be specified as a subgrammar
          * Supports external (C call interface) tokenizers and external
terminal scan
          * Can build tokenizers, either unified or over a subset of states
          * Good asymptotically efficiency
          * Comes with an full unambiguous ANSI-C grammar complete and ready
to run in
    about 200 lines
          * Comes with full source, so if it doesn't do what you want you can
make it!
          * Portable C for easy compilation and linking
          * BSD licence, so you can included it in your application without
worrying a
bout licensing

While I have tested this release against all the examples I could
find in the literature of problematic grammars, it is still a
v1.0 release.

I would appreciate any comments, feedback, patches, etc.


John Plevyak (jplevyak at acm dot org)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.