Re: LL Parser problem

On 15 Aug 2004 22:20:08 -0400, Chris F Clark <cfc@shell01.TheWorld.com>
wrote:


>> It seems to raise a bigger question, to my mind. Are, perhaps, all
>> these limited grammar parsers (parser generators) -- LL(1), LL(k),
>> LALR, and so on -- losing their relevance these days (at least with
>> regards to programming language compilers and similar tools)?
>
> Actually, I would say the opposite is true. A serious number of
> parser generators have been extended with some form of backtracking
> and/or other infinite lookahead mechanism. Here are just the examples
> off the top of my head--predicates (or "lookahead" declarations):
> ANTLR, JavaCC, Yacc++; backtracking: BTYACC, meta-S, PEG (Brian Ford's
> recent work); Lang/Tomita parsing: ASDL, Bison. In fact, if one wants
> to do backtracking parser, it is almost always easier to do it in a
> grammar based scheme or a functional (FP) language. Why, because one
> wants to interpret the grammar and back back up easily. It is hard to
> back up in an imperative language. Thus, you want something where the
> "state" is small and easily managed, so that backing the state back up
> is also easy.


My phraseology was poor (sorry).


I didn't mean to suggest that parser generators are losing their
relevance, but rather that /limited grammar/ parser generators are
losing their relevance (compared to backtracking parser generators,
whose grammars are not limited, as such).


I agree with the idea of using a language which supports backtracking
(or can be programmed to support it neatly). In a way, that's what a
parser generator is.


It's not actually that difficult to backtrack in an imperative
language. You only need to place 'mark', 'rewind', and 'unmark'
operations in the appropriate places. But it is much neater and
easier if these operations are done intrinsically.


--
Nick Roberts

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