Re: LL Parser problem

SM Ryan <wyrmwif@tsoft.org> wrote:
> If you have two different derivations
>
> Z -> X -> A<B>
> and Z -> Y -> A<B
>
> where B has an unbounded expansion, then it isn't LL(k). To be LL(k) you
> have to be able choose X or Y by left context + at most k symbols. In
> this case you have traverse the entire expansion of B which can be more
> than k symbols.


Nick Roberts replied:
> I humbly suggest, if you have the option, that you switch to using a
> backtracking parser (as hinted at by your own comment). It may not be
> so quick, but I suspect that's not likely to be a problem.


A backtracking parser is not needed for this case, an [LA]LR one will
do. There isn't a "grammatical" LL solution (that is a solution that
can be done, just in an LL grammar, with no outside help, e.g. from
the lexer), as this is the if-then-else problem. However, like the
if-then-else problem, one can probably solve it in an LL grammar /
parser by accepting a slightly bigger language. It will be a little
messy though. However, like most "expression" problems, a simpler
solution is to use an LR-like parser generator or a precedence one.
My guess is that's what the original AREV folks did.


Nick Roberts also replied:
> 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.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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