|Grammar to automation translation at runtime (NOT at compile time)? email@example.com (2003-05-14)|
|Re: Grammar to automation translation at runtime (NOT at compile time) firstname.lastname@example.org (Sreenivas Viswanadha) (2003-05-18)|
|Re: Grammar to automation translation at runtime (NOT at compile time) email@example.com (Vladimir Makarov) (2003-05-18)|
|From:||Vladimir Makarov <firstname.lastname@example.org>|
|Date:||18 May 2003 01:30:49 -0400|
|Organization:||Red Hat, Inc.|
|Posted-Date:||18 May 2003 01:30:49 EDT|
Soumen Sarkar wrote:
> Currently the parser generator technology allows grammar to automation
> translation in compile time only. For example if I have to validate a
> text stream that I am receiving, I can not load a grammar file
> dynamically and validate the text stream.
Year ago I wrote Earley parser which can do that (you can use grammars
from files or form it in run time). It is designed as an abstract
data and implemented on C and C++. I spent much time to design and
implement it fast and using few memory. E.g. it parses 6,000 lines of
C code for 0.1 sec on 2.5GHz P4 or 0.35 sec on 550Mhz P3 and consumes
1MB of dynamic memory for this. This times includes all (processing
ANSI C grammar, lexical analysis and Earley parser work itself).
As Earley parser it can parse ambiguous grammar too. The description
is similar to YACC one but instead of actions there are simple
translations. So the output of its work can be abstract tree. For
ambiguous grammar it can give all abstract trees (in compact form by
reusing similar subtrees) or only one abstract tree (it can be chosen
random or based on rule costs). It also can do a minimal cost
recovery from syntactic errors.
Honestly, I don't see necessity of usage of other compiler compilers
for the most projects (except industrial compilers). And I don't use
them although long ago I wrote another compiler compiler MSTA faster
than YACC and Bison.
Earley parser is a part of COCOM toolset (see directory AMMUNITION).
You can find the toolset on
The earley parser documentation is on
The mentioned test (#41) is in file earley.tst.
The parser is distributed under GPL (not LGPL)
Usually I use earley parser in interpreter of DINO language for my
Return to the
Search the comp.compilers archives again.