Re: understanding the intuition behind LL(k) parsers and LR(k) parsers

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
23 Apr 2006 10:05:53 -0400

          From comp.compilers

Related articles
understanding the intuition behind LL(k) parsers and LR(k) parsers Mark.Felzer@gmail.com (Mark F.) (2006-04-21)
Re: understanding the intuition behind LL(k) parsers and LR(k) parsers tom@infoether.com (Tom Copeland) (2006-04-22)
Re: understanding the intuition behind LL(k) parsers and LR(k) parsers cfc@shell01.TheWorld.com (Chris F Clark) (2006-04-23)
Re: understanding the intuition behind LL(k) parsers and LR(k) parsers max@gustavus.edu (Max Hailperin) (2006-04-23)
Re: understanding the intuition behind LL(k) parsers and LR(k) parsers DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-04-23)
Re: understanding the intuition behind LL(k) parsers and LR(k) parsers pbmann@gmail.com (2006-04-28)
Re: understanding the intuition behind LL(k) parsers and LR(k) parsers pbmann@gmail.com (2006-05-01)
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 23 Apr 2006 10:05:53 -0400
Organization: Compilers Central
References: 06-04-124
Keywords: parse
Posted-Date: 23 Apr 2006 10:05:53 EDT

"Mark F." wrote:


> Maybe you can help me visualize the basic idea behind the two
> approaches to AST tree generation.


Just an idea:


A top-down parser starts thinking about possible alternatives, *before*
inspecting an input symbol. He will immediately know, when only one or
zero alternatives remain, whereupon all read symbols can be discarded.


As a scout, he'll know where he is, but not where to go.




A bottom-up parser reads input symbols and determines the possible
alternatives *afterwards*, from what he already has read. If not a
single alternative remains, it continues reading, hoping that further
symbols will make sense later.


As a scout, he'll know where to go, but not which way.


DoDi


Post a followup to this message

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