野牛語法無法修復轉變/減少衝突

Question

我有以下的野牛語法：

%error-verbose 
%{ 
#include "node.h" 
NBlock *programBlock; 

#define YYDEBUG 1 

extern int yylex(); 
void yyerror(const char *s) { printf("Error: %s\n", s); } 
%} 

%union { 
    Node *node; 
    NBlock *block; 
    NBody *body; 
    NHeader *header; 
    NExpression *expression; 
    NStatement *statement; 
    NIdentifier *identifier; 
    NVariableDeclaration *variableDeclaration; 
    NDoWhileStatement *doWhileStatement; 
    NWhileStatement *whileStatement; 
    NIfStatement *ifStatement; 
    NForStatement *forStatement; 
    std::vector<NVariableDeclaration*> *variableDeclarations; 
    std::vector<NExpression*> *expressions; 
    std::vector<NStatement*> *statements; 
    std:string *string; 
    int token; 
} 

/* 
The %token directive is used to associate a type to a terminal symbol. 
%token <type> 'terminal_list' 
associates the specific type <type> to each terminal in 'terminal_list'. 
The type <type> is the same used in the %union declaration 
*/ 

%token <string> TIDENTIFIER TINTEGER TDOUBLE 
%token <token> TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL 
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT 
%token <token> TPLUS TMINUS TMUL TDIV TDO TDOUBLE_TYPE TINT_TYPE 
%token <token> TELSE TFOR TIF TSEMICOLON TTHEN TWHILE 

/* 
The %type directive is used to associate a type to a nonterminal symbol. 
%type <type> nonterminal_list 
associates the specific type <type> to each nonterminal in 'nonterminal_list'. 
The type <type> is the same used in the %union declaration 
*/ 

%type <expression> expression term factor 
%type <block> program body header tail statements 
%type <statement> statement forStatement ifStatement doWhileStatement whileStatement variableDeclaration 
%type <token> comparison 
%type <string> identifier_type 

/* 
Operator precedence for mathematical operators 
*/ 

%left TPLUS TMINUS 
%left TMUL TDIV 
%left TCEQ TCNE TCLT TCLE TCGT TCGE 

/* 
Start grammar symbol 
*/ 

%start program 

%% 

program:    TLBRACE body TRBRACE { printf("Reduce body to program\n"); } 
         ; 

body:     header TLBRACE block TRBRACE tail { printf("Reduce header block tail to body\n"); } 
         ; 

header:     TLBRACE variableDeclarations TRBRACE { printf("Reduce variableDeclarations to header\n"); } 
         | TLBRACE TRBRACE { printf("Reduce empty to header\n"); } 
         ; 

variableDeclarations: variableDeclaration TSEMICOLON { printf("Reduce variable declaration to header\n"); } 
         | variableDeclarations variableDeclaration TSEMICOLON { printf("Reduce variable declaration list to header\n"); } 
         ; 

tail:     TLBRACE statements TRBRACE { printf("reduce statement list to tail\n"); } 
         | TLBRACE TRBRACE { printf("Reduce empty to tal\n"); } 
         ;     

statements:    statement TSEMICOLON { printf("Reduce statement to statement list\n"); } 
         | statements statement TSEMICOLON { printf("Reduce statement list to statement list\n"); } 
         ; 

statement:    ifStatement { printf("Reduce if to statement\n"); }; 
         | forStatement { printf("Reduce for to statement\n"); }; 
         | doWhileStatement { printf("Reduce doWhile to statement\n"); }; 
         | whileStatement { printf("reduce while to statement\n"); } 
         | TIDENTIFIER TEQUAL expression { printf("Reduce assignment to expression\n"); } 
         ; 

forStatement:   TFOR TLPAREN expression TSEMICOLON expression TSEMICOLON expression TRPAREN block { printf("Reduce for to for statement\n"); } 
         ; 


ifStatement:   TIF expression TTHEN block { printf("Reduce if to if statement\n"); } 
         | TIF expression block TELSE block { printf("Reduce ifelse to if statement\n"); } 
         ; 

doWhileStatement:  TDO block TWHILE expression { printf("reduce dowhile to while statement\n"); } 
         ; 

whileStatement:   TWHILE block expression { printf("Reduce while to while statement\n"); } 
         ; 

block:     TLBRACE statements TRBRACE { printf("Reduce statement list to block\n"); } 
         | TLBRACE TRBRACE { printf("Reduce empty to block\n"); } 
         ; 

variableDeclaration: identifier_type TIDENTIFIER { printf("reduce uninitialized identifier to variable declaration\n"); } 
         | identifier_type TIDENTIFIER TEQUAL expression { printf("Reduce initialized identifier to variable declaration\n"); } 
         ; 

identifier_type:  TINT_TYPE { printf("Reduce int to identifier type\n"); } 
         | TDOUBLE_TYPE { printf("Reduce double to identifier type\n"); } 
         | { printf("Reduce empty to identifier type\n"); } 
         ; 



expression:    term { printf("Reduce term to expresson\n"); } 
         | expression comparison expression { printf("Reduce comparison to expression\n"); } 
         | expression TPLUS term { printf("Reduce addition to expression\n"); } 
         | expression TMINUS term { printf("Reduce subtraction to expression\n"); } 
         ; 

term:     factor { printf("Reduce factor to term\n"); } 
         | term TMUL factor { printf("Reduce multiplication to term\n"); } 
         | term TDIV factor { printf("Reduce division to term\n"); } 
         ; 

factor:     TLPAREN expression TRPAREN { printf("Reduce nested expression to expression\n"); } 
         | TMINUS factor { printf("Reduce -factor to factor\n"); } 
         | TIDENTIFIER { printf("Reduce identifier to factor\n"); } 
         | TINTEGER { printf("Reduce integer to numeric\n"); } 
         | TDOUBLE { printf("Reduce double to numeric\n"); } 
         ; 

comparison:    TCEQ { printf("Reduce eq to comparison\n"); } 
         | TCNE { printf("Reduce ne to comparison\n"); } 
         | TCLT { printf("Reduce lt to comparison\n"); } 
         | TCLE { printf("Reduce le to comparison\n"); } 
         | TCGT { printf("reduce gt to comparison\n"); } 
         | TCGE { printf("Reduce ge to comparison\n"); } 
         ; 

，我得到8位移位/減少，我不知道如何解決衝突。

以下是我使用--report = all參數生成的parser.output文件的一個部分。它是由8個轉變影響了狀態/減少衝突：

State 79 

    29 expression: expression . comparison expression 
    29   | expression comparison expression . [TCEQ, TCNE, TCLT, TCLE, TCGT, TCGE, TRPAREN, TLBRACE, TPLUS, TMINUS, TSEMICOLON, TTHEN] 
    30   | expression . TPLUS term 
    31   | expression . TMINUS term 
    40 comparison: . TCEQ 
    41   | . TCNE 
    42   | . TCLT 
    43   | . TCLE 
    44   | . TCGT 
    45   | . TCGE 

    TCEQ shift and go to state 56 
    TCNE shift and go to state 57 
    TCLT shift and go to state 58 
    TCLE shift and go to state 59 
    TCGT shift and go to state 60 
    TCGE shift and go to state 61 
    TPLUS shift and go to state 62 
    TMINUS shift and go to state 63 

    TCEQ  [reduction with rule 29 (expression)] 
    TCNE  [reduction with rule 29 (expression)] 
    TCLT  [reduction with rule 29 (expression)] 
    TCLE  [reduction with rule 29 (expression)] 
    TCGT  [reduction with rule 29 (expression)] 
    TCGE  [reduction with rule 29 (expression)] 
    TPLUS  [reduction with rule 29 (expression)] 
    TMINUS [reduction with rule 29 (expression)] 
    $default reduction with rule 29 (expression) 

    comparison go to state 64 

如果我沒有理解好這個問題是解析器不知道，如果上閱讀文字的另一PICE或立即減少了規則表達式會：表達式比較表達。

我會說立即減少是正確的。但如果我這是正確的，那麼我該如何強制立即減少轉移？

Answer 1

您的語法不明確 - 類似1 < 2 < 3的輸入可以解析爲(1 < 2) < 3或1 < (2 < 3)。

有對付這種兩種方式 - 要麼添加%left/%right/%nonassoc指令使用野牛的內部優先級處理，或引進的規則，其他級別來處理它。

現在您的其他運營商（*/+-）你正在做的這兩個 - 這通常是一個錯誤，你想要做的只是一個或另一個。但是如果你做做做這兩個，額外的規則將優先，優先指令將被忽略，有時會引起驚人的問題。

像這樣的關係的「正常」處理就是說你不能有多個關係（1 < 2 < 3是一個語法錯誤，不應該被解析爲向左或向右遞歸）。倒是改變你表達規則：

expression:   add_expression 
        | add_expression comparison add_expression 
        ; 
add_expression:  term 
        | add_expression TPLUS term 
        | add_expression TMINUS term 
        ; 

使用優先指令，擺脫term，factor和comparison（移動它們全部納入expression並添加：

%nonassoc TCEQ TCNE TCLT TCLE TCGT TCGE 
%left TPLUS TMINUS 
%left TMUL TDIV 

Answer 2

問題是關聯規則（如%left指令）不通過語法間接工作。如果您廢除comparison規則並將所有比較運算符都拉入expression規則中，問題就會消失。 （我使用Bison v2.4.1驗證了這一點。）

這可能不方便，因爲它會使expression比您想要的更冗長。解決方法是將決定推回給掃描儀。將COMPARISON定義爲單個令牌，並通過yylval作爲單獨的枚舉類型傳遞比較的風格，因此它可用作$n。

Answer 3

臨屋你的答案。這裏是完整的Bison語法：

%error-verbose 
%{ 
#include "node.h" 
#include <iostream> 
#include <string> 
NBlock *programBlock; 

#define YYDEBUG 1 

extern int yylex(); 
void yyerror(const char *) { printf("Error: %s\n", s); } 
%} 

%union { 
    Node *node; 
    NBlock *block; 
    NBody *body; 
    NHeader *header; 
    NExpression *expression; 
    NStatement *statement; 
    NIdentifier *identifier; 
    NVariableDeclaration *variableDeclaration; 
    NDoWhileStatement *doWhileStatement; 
    NWhileStatement *whileStatement; 
    NIfStatement *ifStatement; 
    NForStatement *forStatement; 
    std::vector<NVariableDeclaration*> *variableDeclarations; 
    std::vector<NExpression*> *expressions; 
    std::vector<NStatement*> *statements; 
    std:string *string; 
    int token; 
} 

%token <string> TIDENTIFIER TINTEGER TDOUBLE 
%token <token> TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL 
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT 
%token <token> TPLUS TMINUS TMUL TDIV TDO TDOUBLE_TYPE TINT_TYPE 
%token <token> TELSE TFOR TIF TSEMICOLON TTHEN TWHILE TLSQUARE TRSQUARE 

%type <expression> expression term factor 
%type <block> program body header tail 
%type <statements> statements 
%type <statement> statement 
%type <forStatement> forStatement 
%type <ifStatement> ifStatement 
%type <doWhileStatement> doWhileStatement 
%type <whileStatement> whileStatement 
%type <variableDeclaration> variableDeclaration 
%type <token> comparison 
%type <string> identifier_type 
%type <variableDeclarations> variableDeclarations 

/* 
Start grammar symbol 
*/ 

%start program 

%% 

program:    TLBRACE body TRBRACE { printf("Reduce body to program\n"); } 
         ; 

body:     header TLBRACE block TRBRACE tail { printf("Reduce header block tail to body\n"); } 
         ; 

header:     TLBRACE variableDeclarations TRBRACE { printf("Reduce variableDeclarations to header\n"); } 
         | TLBRACE TRBRACE { printf("Reduce empty to header\n"); } 
         ; 

variableDeclarations: variableDeclaration TSEMICOLON { printf("Reduce variable declaration to header\n"); } 
         | variableDeclarations variableDeclaration TSEMICOLON { printf("Reduce variable declaration list to header\n"); } 
         ; 

tail:     TLBRACE statements TRBRACE { printf("reduce statement list to tail\n"); } 
         | TLBRACE TRBRACE { printf("Reduce empty to tal\n"); } 
         ;     

statements:    statement TSEMICOLON { printf("Reduce statement to statement list\n"); } 
         | statements statement TSEMICOLON { printf("Reduce statement list to statement list\n"); } 
         ; 

statement:    ifStatement { printf("Reduce if to statement\n"); }; 
         | forStatement { printf("Reduce for to statement\n"); }; 
         | doWhileStatement { printf("Reduce doWhile to statement\n"); }; 
         | whileStatement { printf("reduce while to statement\n"); } 
         | TIDENTIFIER TEQUAL expression { printf("Reduce assignment to expression\n"); } 
         | TIDENTIFIER TLSQUARE TINTEGER TRSQUARE TEQUAL expression { printf("Reduce array assignment to expression\n"); } 
         ; 

forStatement:   TFOR TLPAREN expression TSEMICOLON expression TSEMICOLON expression TRPAREN block { printf("Reduce for to for statement\n"); } 
         ; 


ifStatement:   TIF expression TTHEN block { printf("Reduce if to if statement\n"); } 
         | TIF expression TTHEN block TELSE block { printf("Reduce ifelse to if statement\n"); } 
         ; 

doWhileStatement:  TDO block TWHILE expression { printf("reduce dowhile to while statement\n"); } 
         ; 

whileStatement:   TWHILE block expression { printf("Reduce while to while statement\n"); } 
         ; 

block:     TLBRACE statements TRBRACE { printf("Reduce statement list to block\n"); } 
         | TLBRACE TRBRACE { printf("Reduce empty to block\n"); } 
         ; 

variableDeclaration: identifier_type TIDENTIFIER { printf("Reduce uninitialized identifier to variable declaration\n"); } 
         | identifier_type TIDENTIFIER TLSQUARE TINTEGER TRSQUARE { printf("Reduce array to variable declaration\n"); } 
         | identifier_type TIDENTIFIER TEQUAL expression { printf("Reduce initialized identifier to variable declaration\n"); } 
         | identifier_type TIDENTIFIER TLSQUARE TINTEGER TRSQUARE TEQUAL expression { printf("Reduce initialized array to variable declaration\n"); } 
         ; 

identifier_type:  TINT_TYPE { printf("Reduce int to identifier type\n"); } 
         | TDOUBLE_TYPE { printf("Reduce double to identifier type\n"); } 
         | { printf("Reduce empty to identifier type\n"); } 
         ; 


expression:    add-expression { printf("Reduce add-expression to expression\n"); } 
         |add-expression comparison add-expression { printf("Reduce add-expression comparison add-expression to expression\n"); } 


add-expression:   term { printf("Reduce term to expresson\n"); } 
         | add-expression TPLUS term { printf("Reduce addition to expression\n"); } 
         | add-expression TMINUS term { printf("Reduce subtraction to expression\n"); } 
         ; 

term:     factor { printf("Reduce factor to term\n"); } 
         | term TMUL factor { printf("Reduce multiplication to term\n"); } 
         | term TDIV factor { printf("Reduce division to term\n"); } 
         ; 

factor:     TLPAREN expression TRPAREN { printf("Reduce nested expression to expression\n"); } 
         | TMINUS factor { printf("Reduce -factor to factor\n"); } 
         | TIDENTIFIER { printf("Reduce identifier to factor\n"); } 
         | TINTEGER { printf("Reduce integer to numeric\n"); } 
         | TDOUBLE { printf("Reduce double to numeric\n"); } 
         ; 

comparison:    TCEQ { printf("Reduce eq to comparison\n"); } 
         | TCNE { printf("Reduce ne to comparison\n"); } 
         | TCLT { printf("Reduce lt to comparison\n"); } 
         | TCLE { printf("Reduce le to comparison\n"); } 
         | TCGT { printf("reduce gt to comparison\n"); } 
         | TCGE { printf("Reduce ge to comparison\n"); } 
         ;