Re: Types of grammars.

"Luke" <Luke@comodo.techi.com.force9.net> asked:
> Could somebody please tell me how all the grammars fit together? i.e. Is an
> LL(k) grammar a subset of LR(k)?
1) All LL(k) grammars are LL(k+1) grammars.
2) All LR(k) grammars are LR(k+1) grammars.
3) All LALR(k) grammars are LALR(k+1) grammars.
4) All LALR(k) grammars are LR(k) grammars.
5) All LL(k, for any k) grammars are LR(1) grammars.
6) All LR(0) grammars are LALR(1) grammars.
But
7) There are LL(k) grammars which are not LALR(1) grammars,
      nor LR(0) grammars. (The LR(0) method throws away left context the
      LL(k) grammars preserve, and the LALR method does not restore all
      of it, but the LR(1) method does.)


> Also, when building LR state diagrams, are the epsilon productions also
> included?
>
> i.e.
> stmt -> .expr '+' expr
> stmt -> .E
> Where E == epsilon.


Yes, but you should think of the dot as being pushed through the
epsilon and ending up at the end of the rule, which means there will
be some reduce actions (or conflicts) in that state. Does that make
any more sense?


Epsilon is an important concept, but in this case it is confusing,
which is why I prefer a more yacc-like notation without any epsilons,
but with terminating semi-colons and with empty rules allowed.


Thus, your example would be written:


        stmt : .expr '+' expr ;
        stmt : .;


In this notation, when you get the dot to the semi-colon, it means
there are reduce transitions.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
--

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