CODEWITHSUNDEEP
parsinggrammar
schweizbolt
schweizbolt

Reputation: 3

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

Upvotes: 0

Views: 155

Answers (2)

Slimane Oulad-Naoui
Slimane Oulad-Naoui

Reputation: 1

The grammar is not LL. The two productions (alternatives) of non-terminal A share the same prefix, which is not accepted in LL parsing, i.e, the grammar should be factorized first.

Upvotes: 0

ggorlen
ggorlen

Reputation: 56925

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

Upvotes: 2

Related Questions