Re: Comparative studies of Generalized LR and LL parsing?

Oliver Zeigermann <oliver@zeigermann.de>
27 Oct 2003 16:11:39 -0500

          From comp.compilers

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)
| List of all articles for this month |

From: Oliver Zeigermann <oliver@zeigermann.de>
Newsgroups: comp.compilers
Date: 27 Oct 2003 16:11:39 -0500
Organization: T-Online
References: 03-10-016 03-10-031
Keywords: parse
Posted-Date: 27 Oct 2003 16:11:39 EST

Hi Chris,


I am normally deterred by long postings, but yours was pretty
interesting. I am no friend of abstract and mathematical defintions as
well, but prefer analogies and comparisons. In


http://www.cs.vu.nl/~dick/PTAPG.html


parsing is compared and related to search all the time. E.g. LR tables
are seen as a way to record search information for faster processing
(besides this book is *very* worth reading).


I think what you call "parallel" can be compared to the paths of a
search graph. As mentioned above LR parsing is some sort of recording of
such a search combining the "parallel" branches of the search. This is
not possible all kinds of searches, so not every context free grammar is LR.


In deterministic LL parsing it is hard for me to find any kind of
search. Is there anything in computing first/follow sets?


But when you consider non-deterministic LL parsing using a backtracking
mechanism, there you have your depth-first search again. Even though I
can not proove it and am actually not an expert in compiler theory,
backtracking LL should parse all languages you can describe with an
LR-grammar (even though at exponential cost).


This is just my imprecise and figurative view of things, so experts
please forbear with me.


Oliver


Post a followup to this message

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