Search code examples
parsinggrammar

Can anyone explain why this grammar cannot be parsed by an LL(1) parser?

I am struggling to understand why an LL(1) parser would not be able to parse this.

A ::= B PLUS A | B

B ::= NUM | ID
Solution

  • A ::= B PLUS A | B has to look ahead to figure out which rule to use. The B is ambiguous.

    You could add a new rule A' that goes to epsilon to remove the ambiguity:

    A  ::= B A'
A' ::= PLUS A | epsilon
B  ::= NUM | ID