Re: Comparative studies of Generalized LR and LL parsing?

Kunle asked:
> Is there such a thing as "Generalized LL" parsing and, have there
> been any useful comparisons of "Generalized LR" and "Generalized LL"
> parsing?.


Part of the reason you don't hear about GLL parsing, is that the term
isn't (to my knowledge) attached to any specific parsing method (at
least not in common usage). The term GLR parsing *is* commonly
attached to the work of Lang, Tomita, et seq.


Moreover, the concept behind GLR parsing doesn't *exactly* apply to LL
parsing. There aren't run-time structures that one can build that
allow one to simulate running multiple LL parsers in parallel and then
combining the results. More importantly, one cannot create these
non-existent structures by modifying the output of an LL parser to
handle problem cases by simulating such parallelism. If one could,
then there would be an obvious candiate for GLL parsing.


That's a rough model of what GLR parsing does. It simulates Earley
parsing, which can be viewed as a kind of running many LR parsers in
parallel, by modifying the output of a normal LR parser to generate a
data sructure that effectively models running multiple LR parsers in
parallel. (In fact, to my mind GLR parsing makes the correspondence
between parallel LR parsers and Earley parsing clear.)


In some ways, LR parsing itself operates analogously to LL parsing to
the way that GLR parsing generalizes LR parsing--that is, it is
possible to model LR parsing as running a series or LL parsers in
parallel, in a similar way to the one in which GLR parsing models
running LR parsers in parallel. Note, some of the difficulties in LR
parsing has compared to LL parsing (handling inherited attributes, for
example) are direct results of that parallelism.


Note, to a lesser degree (at least to my mind), LL(infinite) parsing,
the kind done by ANTLR and RDP, models some of the aspects of what one
might call GLL parsing (and is clearly in the LL family)--however,
LL(infinite) parsing is not a parallelization of LL parsing, just a
way of easing the lookahead restrictions by deferring them. (LR
parsing can also be seen as a way of easing lookahead restrictions,
but it does so by parallelizing the parsing steps (e.g. the set of LR
items are effectively a set of LL parsers running in parallel).)


Recent offline/personal discussions between Terence Parr and myself
have explored that point and are converging on a model that describes
both LL and LR parsing in an easy to understand way, so that it is
easy to see how LR parsing is just a generalization of LL parsing, and
how there are interim steps between the two parsing methodologies that
are more LL like. Terence, in particular, has come up with a view of
extending LL lookahead from the LL(infinite) case to LL(regular) by
making an FSA that looks a lot like the set-of-items constructions used
in LR parsing. An older paper by one of Nigel Horspool's students,
shows how to model LL parsing with LR tables. It doesn't take much to
combine these views into a coherent unifying model that combines LL
and LR parsing.


Next to that, the closest correspondence I can think of is
"Generalized Left Corner parsing" and that has been studied and used
fruitfully by Computational Linguists.


At this point, I will shut-up, as my knowledge of the technique (GLC
parsing) is somewhat limited, and what I would say next could easily
be erroneous and misleading....


Of course, some would take umbrage at what I've already said and
described as erroneous and misleading! My view of the different
models of parsing as paralellizations is not widely accepted and
certainly requires some liberties in the descriptions.


My apologies for such a long reply.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
19 Bronte Way #33M voice : (508) 435-5016
Marlboro, MA 01752 USA fax : (508) 251-2347 (24 hours)

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