CODEWITHSUNDEEP
parsingll-grammar
dv1729
dv1729

Reputation: 1057

LL(1) parsing conflict

I'm writing a LL(1) parser for a very simple grammar. Yet I've found conflicts when trying to build the parsing table.

I'm surprised since the grammar seems simple. I don't know if I have a problem with the parser or with my understanding of LL(1) parsing. Maybe the grammar is not LL(1) in the end.

The grammar is:

1: S         -> begin list
2: list      -> id    listPrime
3: listPrime -> id    listPrime
4:            | ε

My code runs into two conflicts, both for deriving listPrime, one with the terminal symbol id and one with the EOF. In both cases rule 3 clashes against rule 4.

My computed FIRST and FOLLOW sets are:

first:
   { S: Set { 'begin' },
     list: Set { 'id' },
     listPrime: Set { 'id', 'eps' } },

follow:
   { S: Set { 'EOF' },
     list: Set { 'EOF', 'id' },
     listPrime: Set { 'EOF', 'id' } } }

Upvotes: 1

Views: 701

Answers (1)

rici
rici

Reputation: 241721

The grammar is LL(1). Your FOLLOW sets are computed incorrectly, which can easily be verified: there is no derivation in which list or listPrime is followed by a token other than EOF.

Upvotes: 2

Related Questions