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' -> A1. A -> a B b2. B -> b3. 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=falseB { b } epsilon=trueS' { 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?
Is this grammar LALR(1)
formal grammars;parsers