ac abc aca abca acaa abcaa acaaa abcaaa ...As a regular expression: a c a* | a b c a*
b) The problem:
There is a FIRST() conflict between the two productions for the non-terminal S:
S -> a T S -> a b TThere is left recursion in this production for the non-terminal T:
T -> T aThe grammar is ambiguous, since a T can either be expanded to a c directly, or to a U, which can then in turn be expanded to the same c.
T -> c | U U -> c
c) Bottom-up parsers, such as the ones generated by Bison, can handle grammars with FIRST() conflicts and the left recursion, so those are no longer a problem. The ambiguity, however, is still a problem. It doesn't matter how well a parser can handle ambiguity, since the same input can be interpreted in different ways, and the parser has no way to know which interpretation is the correct or intended one.
The first L in all of the names means that the tokens in the input are read from left to right.
The number within parentheses is how many tokens lookahead the parser uses.
The second letter L means leftmost derivation, and is what top-down parsers do. Let's say that the start symbol in a grammar is S, and there is a production S -> T U. An LL parser will apply that production to create a node for the S non-terminal, and then continue to parse a T. We can say that it expands S to T U, and it then starts to expand the leftmost part, T.
The second letter R means rightmost derivation in reverse, and is what top-down parsers do. An LR parser will wait until it has parsed a complete T, and then parse a complete U, before finally creating a node for S. We can say that it reduces T U to S, which is why we say that it is a derivation in reverse. Instead of using the production S -> T U to expand S to T U, it uses it in reverse to reduce T U to S.