Re: Grammar classification

Ehsan asked:
> I'm looking for characteristics of an LL(1) grammar which is also
> LALR(1) but not SLR(1).


I'm not going to give a direct example as this is a typical homework
problem and learning to solve it is part of truly understanding the
different language classes. However, I will show you how to construct
such a grammar, since you also asked for pointers in the right
direction.


Ok, you know that grammars that have non-terminals with epsilon rules
can be used to generate problem cases. Here is one in yacc notation.


a: /* empty */ ;


The next thing you should know that it is "conflicts" (two rules that
can be used in the same context) that generate the same string which
are problems for LR techniques. So, we need another such rule:


b: /* empty */ ;


Now, we need them to be used in the same context:


goal: beforea a aftera | beforeb b afterb;


Now, you just need to figure out what the rules for beforea, beforeb,
and aftera, and afterb need to be.


The first hint is that to be a conflict the left context of a and b
must be "the same" at least for one case. What if anything needs to
be true of the right context?


The second hint is that the SLR technique merges lookahead regardless
of left context. Thus, if you have a more complicated rule, like the
one below, you can "confuse" the technique with mixing and matching
the 1 and 2 items, i.e. aftera1 gets confused with afterb2 rather than
afterb1.


goal: beforea1 a aftera1 | beforeb1 b afterb1;
        | beforea2 a aftera2 | beforeb2 b afterb2;


If you've got that right, what does the LALR algorithm do with the
lookaheads and how does it differ? Is your problem grammar LALR? If
not, can you see a ways to make a similar one which is not SLR, but is
LALR? If it is LALR, can you see a way to make a grammar which is not
LALR also, but is still LL?


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.