Удаление свёртка/свёртка

Question

Я создал компилятор для языка, который имеет следующую грамматику, как определено ML-Yacc (Начиная символ «программа», которая определяется в нижней части):

%nonassoc  FUN VAR ASSIGN PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVIDEASSIGN 
%right   ELSE 
%left   OR 
%left   AND 
%nonassoc  EQ NEQ GT LT GE LE 
%left   PLUS MINUS 
%left   TIMES DIVIDE 
%left   UNARY 
%left   LPAREN 

%% 

const: INT                
    | FLOAT                
    | BOOL               
    | STRING              

ty: ID               
    | FUN LPAREN typeList RPAREN ARROW ty       

typeList: typeList'              
     |                

typeList': ty COMMA typeList'            
     | ty               

exp: primaryExp              
    | callExp               
    | boolExp               
    | opExp               
    | assignExp              

assignExp: ID ASSIGN exp              
     | ID PLUSASSIGN exp             
     | ID MINUSASSIGN exp           
     | ID TIMESASSIGN exp           
     | ID DIVIDEASSIGN exp           

tyargs: LT typeList' GT             

callExp: exp LPAREN expList RPAREN          

boolExp: exp AND exp               
     | exp OR exp             

opExp: ID PLUSPLUS              
    | ID MINUSMINUS              
    | PLUSPLUS ID             
    | MINUSMINUS ID              
    | exp PLUS exp             
    | exp MINUS exp              
    | MINUS exp %prec UNARY            
    | BANG exp %prec UNARY           
    | exp TIMES exp              
    | exp DIVIDE exp            
    | exp EQ exp             
    | exp NEQ exp             
    | exp GT exp             
    | exp LT exp             
    | exp GE exp             
    | exp LE exp             

expList: expList'              
     |                 


expList': exp COMMA expList'             
     | exp               

primaryExp: ID                
      | const               
      | lambdaExp              
      | LPAREN exp RPAREN                         

varDecl: ty ID ASSIGN exp            
     | ty ID               
     | VAR ID ASSIGN exp            


expStat: exp SEMICOLON             
     | SEMICOLON              


statList: stat statList             
     |                

compoundStat: LBRACE statList RBRACE            

selectionStat: IF LPAREN exp RPAREN stat ELSE stat        
      | IF LPAREN exp RPAREN stat           


jumpStat: RETURN exp               
     | RETURN               
     | BREAK               

iterationStat: WHILE LPAREN exp RPAREN stat         
      | FOR LPAREN SEMICOLON SEMICOLON RPAREN stat     
      | FOR LPAREN SEMICOLON SEMICOLON exp RPAREN stat    
      | FOR LPAREN SEMICOLON exp SEMICOLON RPAREN stat    
      | FOR LPAREN SEMICOLON exp SEMICOLON exp RPAREN stat   
      | FOR LPAREN varDecl SEMICOLON SEMICOLON RPAREN stat   
      | FOR LPAREN varDecl SEMICOLON SEMICOLON exp RPAREN stat  
      | FOR LPAREN varDecl SEMICOLON exp SEMICOLON RPAREN stat  
      | FOR LPAREN varDecl SEMICOLON exp SEMICOLON exp RPAREN stat 
      | FOR LPAREN exp SEMICOLON SEMICOLON RPAREN stat    
      | FOR LPAREN exp SEMICOLON SEMICOLON exp RPAREN stat   
      | FOR LPAREN exp SEMICOLON exp SEMICOLON RPAREN stat   
      | FOR LPAREN exp SEMICOLON exp SEMICOLON exp RPAREN stat  

stat: expStat               
    | compoundStat             
    | selectionStat             
    | iterationStat             
    | jumpStat SEMICOLON            
    | varDecl SEMICOLON                 

declList: declList'              
     |                

declList': varDecl COMMA declList'           
     | varDecl                           

functionDecl: FUN ID LPAREN declList RPAREN ARROW ty compoundStat   

lambdaExp: LPAREN declList RPAREN ARROW ty compoundStat     

declarations: varDecl SEMICOLON declarations          
      | functionDecl declarations          
      |                

program: declarations             

и эта грамматика хорошо, но теперь я хочу представить параметрический полиморфизм и, таким образом, добавили следующие спектакли в грамматике:

tyargs: LT typeList' GT 

ty: ID tyargs 

callExp: exp tyargs LPAREN expList RPAREN 

idList: ID COMMA idList             
     | ID 

tyvars: LT idList GT 

functionDecl: FUN ID tyvars LPAREN declList RPAREN ARROW ty compoundStat 

и теперь я получаю следующие 2 свёртка/свёртка, которые я не знаю, как решить

error: state 75: reduce/reduce conflict between rule 46 and rule 5 on GT 
error: state 75: reduce/reduce conflict between rule 46 and rule 5 on COMMA 

Может ли кто-нибудь сказать мне, как я удалю эти 2 конфликта?

EDIT: Вот полный вывод .desc от mlyacc http://pastebin.com/2w26ytuV. Не то, чтобы этот показатель также показывал 2 доброкачественных ошибки сдвига/уменьшения

Answer 1

Ну, никто не ответил, но вы сделали грамматику славной двусмысленностью. Есть два возможных производств для:

LT ID GT 
ID LT ID GT 

принять некоторые примеры:

<a> 
b<a> 

таковы, чтобы быть tyargs или tyvars или начало callExp? Ваша грамматика говорит, что они могут быть обоими. Поэтому довольно сложно анализировать такие инструменты, как ml-yacc, без внесения каких-либо изменений в язык или правила, которые вы используете.

У вас возникнут проблемы с составлением его с помощью ml-yacc, не объясняя структуру языка немного больше. Кто-то может показать вам лучший способ структурирования правил грамматики, чтобы оставаться в пределах ограничений таких инструментов.

Answer 2

Проблема в том, что с новыми правилами грамматика требует произвольного вида, чтобы рассказать разницу между varDecl и expStmt. Это происходит от , являющегося как двоичным оператором для выражений, так и указанием начала списка tyargs для параметризованного типа.

Одним из возможных решений было бы ввести новое ключевое слово для обозначения параметризованного типа или функции (например, в FUN ключевое слово в настоящее время используется, чтобы ввести тип функции), что позволило бы парсер знать заранее, будет ли лечить LT как оператор или список параметров типа. Таким образом, вы бы вместо того, чтобы добавить новые правила, как:

ty: TYPE ID tyargs 

callExpr: CALL ID tyargs LPAREN expList RPAREN 

Другая возможность заключается в том, чтобы использовать обратную связь лексического анализатора с помощью таблицы символов - имеют лексер распознавать идентификаторы, которые требуют параметров типа (путем поиска имен в таблице символов) и вернуть для них другой токен.

Третья возможность заключается в том, чтобы использовать более сильный парсер генератор, который может иметь дело с большим количеством опережающего просмотра, такие как %glr-parser вариант бизона или btyacc