Re: LL Parser problem

"Nick Roberts" <>
23 Aug 2004 12:11:02 -0400

          From comp.compilers

Related articles
LL Parser problem (2004-08-09)
Re: LL Parser problem (2004-08-10)
Re: LL Parser problem (SM Ryan) (2004-08-11)
Re: LL Parser problem (Nick Roberts) (2004-08-13)
Re: LL Parser problem (Chris F Clark) (2004-08-15)
Re: LL Parser problem (Nick Roberts) (2004-08-23)
Re: LL Parser problem (Richard Pennington) (2004-08-25)
Re: LL Parser problem (2004-09-03)
Re: LL Parser problem (Chris F Clark) (2004-09-07)
| List of all articles for this month |

From: "Nick Roberts" <>
Newsgroups: comp.compilers
Date: 23 Aug 2004 12:11:02 -0400
Organization: Compilers Central
References: 04-08-060 04-08-063 04-08-082 04-08-101
Keywords: parse, LL(1)
Posted-Date: 23 Aug 2004 12:11:01 EDT

On 15 Aug 2004 22:20:08 -0400, Chris F Clark <>

>> 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

Post a followup to this message

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