Yacc语法：解决Shift/Reduce和Reduce/Reduce冲突

Question

我正在为特定的 DSL 语言开发一个解析器。下面是一个有效的（但不完整的）语法：

%{
package main
%}

//%type<stmts> stmts
%type<stmt> stmt
//%type<stmt_if> stmt_if
//%type<exprs> exprs
//%type<compstmt> compstmt

%union {
    token Token
    terminal                   Token
    //terms                  Token
    stmt_if statement // оператор Если
    stmts   statements
    stmt    statement
    compstmt    statements
}

%token<token> Directive Identifier Procedure Var EndProcedure If Then ElseIf Else EndIf For Each In To Loop EndLoop Break Not
%token<token> Continue Try Catch EndTry Number String Array Function EndFunction Return Throw NeEq Or And True False Undefind Export

%right '='
%left Or
%left And
%left Identifier
//%nonassoc NeEq '>' '<'
%nonassoc NeEq
%left '>' '<'
%left '+' '-'
%left '*' '/' '%'



%%

main: opt_directive invoke {}
;

opt_directive: /* none */
| Directive EOL {}
;

opt_export: /* none */
| Export {}
;


invoke: Function Identifier '(' exprs ')' opt_export opt_stmt EndFunction opt_terms {}
        | Procedure Identifier '(' exprs ')' opt_export opt_stmt EndProcedure opt_terms {}
;

opt_stmt : opt_terms{}
    | stmts opt_terms{}
;
    
stmts :  stmt {}
        | EOL stmt {}
        | stmts terminals stmt{}
    //| stmts semi stmt {}
;

stmt : Return expr {}
    | Throw throw_terms {}
    | Break {  }
    | Continue {  }
    | expr {}
    | stmt_if {}
;

throw_terms : terminal {}
    | String terminal {}
;


stmt_if : If expr Then opt_stmt EndIf terminal
        {

        }
;


expr : Identifier {}
    | '(' expr ')' { }
    | expr '+' expr { }
    | expr '-' expr { }
    | expr '*' expr { }
    | expr '/' expr { }
    | expr '%' expr {}
    | String {}
    | Number { }
    | True { }
    | False { }
    | Undefind {}
    | expr '>' expr { }
    | expr '<' expr{}
    | expr '=' expr {}
    | Identifier  '=' expr {}
    | expr NeEq expr {}
    | expr And expr { }
    | expr Or expr {}
    | Identifier '(' exprs ')' {}
;

exprs : { }
    | expr {}
    | exprs ',' opt_terms expr {}
;    

opt_terms : /* none */
    | terminals
;

terminals : terminal { }
    | terminals terminal { }
;

terminal : semi { }
        | EOL { }
;

EOL : '\n';
semi: ';';

%%

如果我将

terminal

规则中的

terminals

更改为

stmt_if

，则会发生冲突

stmt_if : If expr Then opt_stmt EndIf terminals
        {

        }
;

我需要使用

terminals

因为语言语法允许这样的语句：

If 1 = 1 Then
// ...
EndIf;

以及：

If 1 = 1 Then
// ...
EndIf
;

我不明白为什么这里存在歧义，因为“终端”应该容纳可选的换行符和分号。如何编写允许在末尾有多个空格和分号而不会产生歧义的规则？

预先感谢您的帮助！

Answer 1

基本问题是，通过同时拥有

terminals

和

stmt_if

的

stmts

部分，它是不明确的，因为任何给定终端应该与 which 关联。由于

terminals

只能位于 stmt 中的

 两个 

stmts

 之间（不在末尾），因此变得更加复杂，因此末尾的任何 

terminals

 都必须与 

stmt_if

 相关联（或者如果最后一个 

stmt

 不是 

stmt_if

，则会导致错误。

现在就您的情况而言，您可能不关心任何给定终端与哪个 stmt 或 stmts 关联，因为您只是将它们扔掉。你真正关心的是在应该允许的地方允许它们，在不应该的地方不允许它们（从你的语法中并不清楚这些是什么——如果在函数或过程中的最后一个

stmt

之后不允许它们）除非那是一个“如果”？这就是你目前正在做的事情）

最简单的解决方法是在语法中选择一个位置来放置它们并（仅）将它们放在那里。例如，您可以将它们放入

stmt

 规则中 - 每种 

stmt

 都以 

terminals

 或 

opt_terminals

 结尾（取决于该语句是否需要至少一个终端）。但这会在过程/函数体的末尾允许您可能不想要的额外终端。