LL(1), LALR(1)

Trevor Jenkins cleared up much with his posting of p410 from
``The Theory and Practice of Compiler Writing'', but the diagram
is a bit misleading (only relevant portions shown):


> LALR(1) | Extended Prec.
> +--------+ | |
> | SLR(1) +--------+ |
> | | | |
> | +---------------+| |
> LL(1) | Simple
> LR(0) Precedence


There is no strict ordering between LALR(1) and LL(1) as there are
grammars that LALR(1), but not LL(1) and at least one that is LL(1),
but not LALR(1); i.e. LALR(1) is not strictly stronger than LL(1) as
the diagram would have us believe. For example,


%token A B
%%
s: A a
  | B b
  ;


a: c A
  | d B
  ;


b: c B
  | d A
  ;


c: e
  ;


d: e
  ;


e:
  ;
%%


This is not "yaccable" as you get:


7: reduce/reduce conflict (red'ns 7 and 8 ) on A
7: reduce/reduce conflict (red'ns 7 and 8 ) on B
state 7
                c : e_ (7)
                d : e_ (8)


                . reduce 7


Also, when you let me put actions in a grammar anywhere I want, LR(k)
and LL(k) become equally strong in the worst case.


Terence Parr
Postdoctoral slave
U of MN, AHPCRC
Peoples Arctic Socialist Republic of Minnesota
--

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