Question

Can someone please confirm for me if the following BNF grammar is LL(1):

S ::= A B B A
A ::= a
A ::=
B ::= b
B ::=

where S is the start symbol and non terminals A and B can derive to epsilon. I know if there are 2 or more productions in a single cell in the parse table, then the grammar isn't LL(1). But if a cell already contains epsilon, can we safely replace it with the new production when constructing the parse table?

Was it helpful?

Solution

This grammar is ambiguous, and thus not LL(1), nor LL(k) for any k.

Take a single a or b as input, and see that it can be matched by either of the A or B references from S. Thus there are two different parse trees, proving that the grammar is ambiguous.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top