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

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
.