CODEWITHSUNDEEP
parsingcontext-free-grammarparser-generator
AltF4
AltF4

Reputation: 86

Eliminate indirect First-First conflicts in LL 1 grammar

I am trying to write a LL(1) parser generator and I am running into a issue with grammars which I know to be LL(1) but I cannot factor them properly.

For example consider the grammar:

S -> As Ao
As -> a As
As -> Ɛ
Ao -> a
Ao -> Ɛ

Now this grammar has a first-follow conflict in As so I perform Ɛ elimination and have: 

S -> As Ao
S -> Ao
As -> a As
As -> a
Ao -> a
Ao -> Ɛ

Which has a first-first conflicts in S and As. Resolving the conflict in As produces:

S -> As Ao
S -> Ao
As -> a As'
As' -> As
As' -> Ɛ 
Ao -> a
Ao -> Ɛ

Which has a first-follow conflict in As' which when eliminated simply cycles. Further, the conflict in S cannot be solved via left factorization

I believe the issue is that As Ao == As if I knew how to prove this I believe the issue would go away as the initial grammar could be transformed to:

S -> As
As -> a As
As -> Ɛ

Is there standard techniques for resolving such conflicts?

edit: I realize the grammar above is ambiguous. The grammar I am really interested in parsing is:

S -> a As Ao
As -> , a AS
As -> Ɛ
Ao -> ,
Ao -> Ɛ

I.e. a comma separated list of a with an optional trailing comma.

Upvotes: 0

Views: 830

Answers (1)

rici
rici

Reputation: 241911

The original grammar is ambiguous, so no deterministic parser can be produced.

Of course, you can eliminate the ambiguities easily enough, since the language is just "zero or more as":

S  ⇒ As
As ⇒ a As
As ⇒ Ɛ

But presumably the question is a simplification of some more complicated grammar in which Ao is not the same as a, but in which FIRST(As) and FIRST(Ao) have some common element.

In general, it is difficult to write LL(1) grammars for such languages, and it is indeed possible that such a grammar does not exist for the language. In order to answer the question in more detail, it would be necessary to understand what is meant by the claim that the grammar is known to be LL(1).

Upvotes: 1

Related Questions