[LLVMdev] LLVM / C--

[Guillaume FORTAINE]

>Neither C-- nor LLVM provide this.  Why do you need a GLR parser 
>specifically?

http://www.cs.berkeley.edu/~smcpeak/elkhound/

Parsing with arbitrary context-free grammars has two key advantages: (1) 
unbounded lookahead, and (2) support for ambiguous grammars. Unbounded 
lookahead is achieved by allowing multiple potential parses to coexist for as 
long as necessary. Similarly, ambiguity is handled by letting potential 
parses be coalesced, with special action taken to handle the ambiguous region 
of the input. In general, by using the GLR algorithm, Elkhound avoids the 
difficulty of trying to make a language grammar fit the LALR(1) restrictions.


http://en.wikipedia.org/wiki/GLR_parser

Advantages
When implemented carefully, the GLR algorithm has the same time complexity as 
the CYK algorithm and Earley algorithm -- O(n3). However, GLR carries two 
additional important advantages:
The time required to run the algorithm is proportional to the degree of 
nondeterminism in the grammar -- on deterministic grammars the GLR algorithm 
runs in O(n) time (this is not true of the Earley and CYK algorithms)
The GLR algorithm is "on-line" -- that is, it consumes the input tokens in a 
specific order and performs as much work as possible after consuming each 
token.
Since most programming languages are deterministic or "almost deterministic", 
in practice the GLR algorithm often performs markedly better than others.


In short : to have cutting-edge stuff and to forget bison another GNU tool ...

Best Regards,

				Guillaume