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

Tom Copeland <tom@infoether.com>
22 Apr 2006 10:01:10 -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: Tom Copeland <tom@infoether.com>
Newsgroups: comp.compilers
Date: 22 Apr 2006 10:01:10 -0400
Organization: Compilers Central
References: 06-04-124
Keywords: parse

On Fri, 2006-04-21 at 23:47 -0400, Mark F. wrote:


> .... A bottom up parser has to start with some kind of "last
> terminal" then build the tree in upward direction. Intuitively where
> would the bottom-up parser start if presented an input file. How
> does it find this starting point, of the parse. It has to be the
> deepest part of the tree. But how do you detect this, without
> expending the tree first from top-bottom? Is my thinking faulted?


> [Bottom up parsers use a state machine, like the one in a DFA regular
> expression matcher. The states implicitly encode all of the possible
> matches, and when the parser gets to a state where there's one complete
> match, you reduce the rule. -John]


For notes on a particular implementation of a bottom up tree builder,
check out the JJTree documentation:


https://javacc.dev.java.net/doc/JJTree.html


It talks about ways to customize the node tree as it's constructed; lots
of good stuff there.


Yours,


tom


Post a followup to this message

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