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?

Était-ce utile?

La 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.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top