I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3.

0. S' -> A
1. A -> a B b
2. B -> b
3. B -> 

This recognizes ab and aab. It is my assumption that with one symbol of look-ahead, I would know whether to reduce using rule 3 or shift using rule 2. That is, when scanning ab, I need to reduce using rule 3 to get a B onto my stack. But when the input is abb I want to just shift the first b, then reduce it by rule 2.

As I work through creating a LALR(1) parsing table, I get the following:

 , $ , a , b , A , B 
0,   , s2,   , g1,   ,
1, a ,   ,   ,   ,   ,
2,   ,   , s5,   , g3,
3,   ,   , s4,   ,   ,
4, r1,   ,   ,   ,   ,
5,   ,   , r2,   ,   ,

The issue is that there is an ambiguity on state [2, b] A 'reduce by 3' was rejected. Of course, this is why I chose the grammar.

I calculated first and follow as:

**************
* First sets *
**************
A { a } epsilon=false
B { b } epsilon=true
S' { a } epsilon=false

***************
* Follow sets *
***************
S' { $ }
    A { $ }
B { b }

Anyway, I have implemented this as best I know how and the ambiguity remains. Am I doing something wrong? Am I expecting too much from LALR(1)?

EDIT - one possible place where I am confused could be when 'lookahead' occurs. If the lookahead symbol is only used to make a decision on whether a reduction should occur, then to be successful we require enough information after we shift the first a. Basically, if we see two b's coming, we can infer our only chance of success is to shift the first one and then reduce it to B. If there is only one B, we'll need to reduce the epsilon to get a B onto the stack. Then we'll be set up to successfully reduce aBb. By this metric, this would be an LALR(2) grammar. Does this make sense (in the scope of LALR(k) parsers,) or am I just wrong?

A simpler way to see that this grammar is not LALR(1) is to look at the LR(1) item sets:

  1. $S' \rightarrow \bullet A,\enspace \$$
    $A \rightarrow \bullet aBb,\enspace \$$
  2. $S' \rightarrow A\bullet ,\enspace \$$
  3. $A \rightarrow a\bullet Bb,\enspace \$$
    $B \rightarrow \bullet b,\enspace b$
    $B \rightarrow \bullet ,\enspace b$
  4. $A \rightarrow aB\bullet b,\enspace \$$
  5. $B \rightarrow b\bullet ,\enspace b$
  6. $A \rightarrow aBb\bullet ,\enspace \$$

You can see that in state 3 the shift/reduce conflict remains, even in LR(1). This grammar is not LR(1), and thus not LALR(1).

You should first change your Grammar by replacing values of B and then create a parser

0. S' -> A
1. A -> a b | a b b

or

0. S' -> A
1. A -> a b | a B b
2. B -> b

For more, this may help

  • 1
    Thanks for your response. The point of the question is not to construct a grammar that recognizes two strings. It is instead to gain insight into the nature of the given grammar. – Tony Ennis Dec 29 '14 at 14:21

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.