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

"Mark F." <Mark.Felzer@gmail.com>
21 Apr 2006 23:47:48 -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: "Mark F." <Mark.Felzer@gmail.com>
Newsgroups: comp.compilers
Date: 21 Apr 2006 23:47:48 -0400
Organization: Compilers Central
Keywords: parse, question, comment
Posted-Date: 21 Apr 2006 23:47:48 EDT

Hey guys,


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


As I understand it a top-down parser..will start with the first input
symbol of the program file,check if its a terminal/nonterminal, then
it expands it..looking for the next predicted symbol. 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?




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


Post a followup to this message

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