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

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

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