8

I am learning now about parsers on my Theory Of Compilation course. I need to find an example for grammar which is in LL(1) but not in LALR. I know it should be exist. please help me think of the most simple example to this problem.

Cœur
  • 37,241
  • 25
  • 195
  • 267
Yotam Madem
  • 375
  • 2
  • 12
  • 2
    Are you sure it's not a trick question, or possibly you have it reversed. I was under the impression (from my compilers course last semester) that LL(1) was a subset of LALR, and thus, all LL(1) grammars are LALR. I could be misremembering, let me dig out my dragon book. – jpm Jun 27 '11 at 00:05

2 Answers2

15

Some googling brings up this example for a non-LALR(1) grammar, which is LL(1):

S ::= '(' X 
    | E ']' 
    | F ')'
X ::= E ')' 
    | F ']'
E ::= A
F ::= A
A ::= ε

The LALR(1) construction fails, because there is a reduce-reduce conflict between E and F. In the set of LR(0) states, there is a state made up of

E ::= A . ;
F ::= A . ;

which is needed for both S and X contexts. The LALR(1) lookahead sets for these items thus mix up tokens originating from the S and X productions. This is different for LR(1), where there are different states for these cases.

With LL(1), decisions are made by looking at FIRST sets of the alternatives, where ')' and ']' always occur in different alternatives.

Gunther
  • 5,146
  • 1
  • 24
  • 35
1

From the Dragon book (Second Edition, p. 242):

The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive or LL methods. For a grammar to be LR(k), we must be able to recognize the occurrence of the right side of a production in a right-sentential form, with k input symbols of lookahead. This requirement is far less stringent than that for LL(k) grammars where we must be able to recognize the use of a production seeing only the first k symbols of what the right side derives. Thus, it should not be surprising that LR grammars can describe more languages than LL grammars.

jpm
  • 3,165
  • 17
  • 24
  • 4
    Second, this answer does not contradicts the assumption that there is a grammar in LL(1) which is not in LALR. that is because as you may know, LALR < LR(1). in the lectures slides that we learn from, there is a schematic picture of relations between the grammar classes, and it can be seen very easily that LALR does not contain LL(1). they indeed have a big intersection but one does not contain an other. look at page 7 of the following lecture: http://www.cs.technion.ac.il/%7Eyahave/courses/tocs2011/compilers-lec04.pdf and see what I mean. – Yotam Madem Jun 27 '11 at 11:51
  • Ah, that's right. As Gunther points out in his answer, LALR loses some generality from CLR because it mixes states. – jpm Jun 27 '11 at 18:14