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

Chris F Clark <cfc@shell01.TheWorld.com>
23 Apr 2006 10:00:02 -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: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 23 Apr 2006 10:00:02 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 06-04-124
Keywords: parse
Posted-Date: 23 Apr 2006 10:00:02 EDT

Your intuition for bottom-up parsers is interesting but flawed. It is
not the exact reverse of LL; one doesn't start with the last terminal,
but rather the first.


The best "intuition" of a bottom-up parser is to imagine the finished
parse (derivation) tree, like I show in ASCII art below. Now, start
at the bottom-left corner and walk acroos the leaves (terminals).
Each time, you have walked across enough leaves, that you have found
all the leaves, for some non-terminal, you build that non-terminal,
working your way up the tree.


program
  |
  +------...
  |
stmt
  |
  +---+---+----+
  | | | |
  A = expr ;
                  |
                  +----+----+
                  | | |
                  B * C


With the example, you start with A, then =, then B, *, and C. Once
you have reached C, you can build an expr. Then at ;, you can build a
stmt. When you have seen everything, you can build a program
non-terminal and you are done.


Note, this is vastly simplified and details have been swept under the
rug, but it does give the right intuitive feel for LR parsing.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------



Post a followup to this message

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