21 Apr 2006 23:47:48 -0400

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) |

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.