6 Oct 2003 21:29:21 -0400

Related articles |
---|

Comparative studies of Generalized LR and LL parsing? noemails@replyToTheGroup.nospam.org (Kunle Odutola) (2003-10-04) |

Re: Comparative studies of Generalized LR and LL parsing? daw@mozart.cs.berkeley.edu (2003-10-06) |

Re: Comparative studies of Generalized LR and LL parsing? haberg@matematik.su.se (2003-10-06) |

Re: Comparative studies of Generalized LR and LL parsing? cfc@world.std.com (Chris F Clark) (2003-10-06) |

Re: Comparative studies of Generalized LR and LL parsing? oliver@zeigermann.de (Oliver Zeigermann) (2003-10-27) |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 6 Oct 2003 21:29:21 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 03-10-016 |

Keywords: | parse, LL(1), LR(1) |

Posted-Date: | 06 Oct 2003 21:29:21 EDT |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.