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.


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


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




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


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




parameterDeclaration1
    parameterDeclaration -> '...';


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.