Compilers - Grammar classification

Author

Grammar classification

Ehsan Akhgari

2005-12-11, 7:19 pm

Hi all,

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

So far I know that if an LL(1) grammar has any lambda productions it's
not LR(0), and if it has some non-terminal symbols which only produce
lambda strings, then it might not be SLR(1) as well. But I have not
been able to find any grammar of the latter form. I've performed a lot
of trial and error, to no avail. I prefer to have a clue how to
organize my trials in a systematic manner, but I have no such clue as
well.

Can anyone guide me in the right direction, or provide a sample LL(1)
grammar which is not SLR(1)?

Thanks in advance,
Ehsan

Chris F Clark

2005-12-15, 3:58 am

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

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)

Sponsored Links