Re: Comparative studies of Generalized LR and LL parsing?

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

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