27 Oct 2003 16:11:39 -0500

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: | 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.