how to solve shift reduce / reduce reduce conflict??

"이주현" <hihihi@icu.ac.kr>
23 May 2003 01:36:59 -0400

From comp.compilers

Related articles
*how to solve shift reduce / reduce reduce conflict?? hihihi@icu.ac.kr (이주현)* (2003-05-23)**

| List of all articles for this month |

From:	"이주현" <hihihi@icu.ac.kr>
Newsgroups:	comp.compilers
Date:	23 May 2003 01:36:59 -0400
Organization:	Korea Research Environment Open Network
Keywords:	C++, parse, question
Posted-Date:	23 May 2003 01:36:59 EDT

I'm translating C++ grammar into yacc code.
And I met reduce-reduce conflicts and shift-reduce.
So I'm looking for reduce conflict solution.
I have known some technique (inline and adding production).

But, I need another technique to solve reduce conflict.

Because C++ grammar is some heavy and complex and inline technique make a
number of production large.

ex1) For this example, if i use inline technique, it makes code complex..
and another solution is what?

prog0
prog -> TEMPLATE '<' templateParameterList '>' CLASS '=' idExpression;

templateParameterList0
templateParameterList -> templateParameter;
templateParameterList1
templateParameterList -> templateParameterList ',' templateParameter;

templateParameter0
templateParameter -> typeParameter;
templateParameter1
templateParameter -> parameterDeclaration;

parameterDeclarationList0
parameterDeclarationList -> parameterDeclaration ;
parameterDeclarationList1
parameterDeclarationList -> parameterDeclarationList ','
parameterDeclaration ;

parameterDeclaration0
parameterDeclaration -> ID;
parameterDeclaration1
parameterDeclaration -> '...';

typeParameter0
typeParameter -> CLASS;

idExpression0
idExpression -> ID;

I said that this method is inline technique.

ex2)

prog0
prog -> className;

templateId0
templateId -> templateName '<' '>' ;
templateId1
templateId -> templateName '<' templateArgumentList '>' ;

className0
className -> templateId;
className1
className -> ID;

templateName0
templateName -> ID;

* This is a conflict between className and templateName.
If a token is ID, parser can't detemine whether className production or
templateName.

==> Solution
replace templateName with ID and remove templateName production

templateId0
templateId -> ID '<' '>' ;
templateId1
templateId -> ID '<' templateArgumentList '>' ;

==> using inline technique for ex1...
i) duplicate templateParameter1 production and replace parameterDeclaration
with ID
ii) remove parameterDeclaration0 production

step1)

templateParameter0
    templateParameter -> typeParameter;
templateParameter1
    templateParameter -> parameterDeclaration ;
templateParameter2
    templateParameter -> ID;

parameterDeclaration1
parameterDeclaration -> '...';

parameterDeclarationList0
    parameterDeclarationList -> parameterDeclaration ;
parameterDeclarationList1
    parameterDeclarationList -> parameterDeclarationList ','
parameterDeclaration ;
parameterDeclarationList2
    parameterDeclarationList -> ID ;
parameterDeclarationList3
    parameterDeclarationList -> parameterDeclarationList ',' ID ;

step2)
i) duplicate parameterDeclarationList1 and parameterDeclarationList3
production
and replace parameterDeclarationList with ID
ii) remove parameterDeclarationList2 production

parameterDeclarationList0
    parameterDeclarationList -> parameterDeclaration ;
parameterDeclarationList1
    parameterDeclarationList -> parameterDeclarationList ','
parameterDeclaration ;
parameterDeclarationList3
    parameterDeclarationList -> parameterDeclarationList ',' ID ;
parameterDeclarationList4
    parameterDeclarationList -> ID ',' parameterDeclaration ;
parameterDeclarationList5
    parameterDeclarationList -> ID ',' ID ;

step3)
i) duplicate templateParameterList0 and templateParameterList1 production
and replace templateParameter with ID
ii) remove templateParameter2 production

templateParameterList0
    templateParameterList -> templateParameter;
templateParameterList1
    templateParameterList -> templateParameterList ',' templateParameter;
templateParameterList2
    templateParameterList -> ID;
templateParameterList3
    templateParameterList -> templateParameterList ',' ID;

templateParameter0
templateParameter -> typeParameter;
templateParameter1
templateParameter -> parameterDeclaration ;

step4)
i) duplicate templateParameterList1 and templateParameterList3 production
and replace templateParameter with ID
ii) remove templateParameterList2 production

templateParameterList0
    templateParameterList -> templateParameter;
templateParameterList1
    templateParameterList -> templateParameterList ',' templateParameter;
templateParameterList3
    templateParameterList -> templateParameterList ',' ID;
templateParameterList4
    templateParameterList -> ID ',' templateParameter;
templateParameterList5
    templateParameterList -> ID ',' ID;

prog0
prog -> TEMPLATE '<' templateParameterList '>' CLASS '=' idExpression;
prog1
prog -> TEMPLATE '<' ID '>' CLASS '=' idExpression;

==> orderly listing...
templateParameterList5 and parameterDeclarationList5 production is same.
like these productions, enlarge productions.
so, I need another technique.