Search code examples
bisoncontext-free-grammarshift-reduce-conflictambiguous-grammar

Resolve ambiguity from grammar for C initialization list

I cannot seem to resolve the ambiguity contained in the following rule:

InitializerList_a →,[Initializer][InitializerList_a]

It is causing a shift/reduce conflict in my parser (I'm using Bison). The following is its closure:

InitializerList_a → ε

Initializer → [Constant]

Initializer → {[InitializerList][Initializer_a]

Initializer_a → }

Initializer_a → ,}

InitializerList → [Initializer][InitializerList_a]

Any help would be appreciated. I can post the bison output file if needed.

Here is the same grammar written in a more readable way:

L → IT

T → ,IT | ε

I → [Constant] | {LA

A → } | ,}

where [Constant] is a terminal
Solution

  • This should cover it. YACC like grammars prefer head recursion over tail recursion in the grammar.

    %start I
%token CONSTANT
%%
I: CONSTANT | '{' L '}' ;
L: J | J ',' ;
J: I | J ',' I ;