Bison 减少/减少与强制转换和表达式括号的冲突

Question

我正在用 bison 构建语法，并且我已将最后一个 reduce/reduce 错误缩小到以下测试用例：

%{
#include <stdio.h>
#include <string.h>

extern yydebug;

void yyerror(const char *str)
{
  fprintf(stderr, "Error: %s\n", str);
}

main()
{
  yydebug = 1;
  yyparse();
}
%}

%right '='
%precedence CAST
%left '('

%token AUTO BOOL BYTE DOUBLE FLOAT INT LONG SHORT SIGNED STRING UNSIGNED VOID

%token IDENTIFIER

%start file

%debug

%%

file
  : %empty
  | statement file
  ;

statement
  : expression ';'
  ;

expression
  : expression '=' expression
  | '(' type ')' expression %prec CAST
  | '(' expression ')'
  | IDENTIFIER
  ;

type
  : VOID
  | AUTO
  | BOOL
  | BYTE
  | SHORT
  | INT
  | LONG
  | FLOAT
  | DOUBLE
  | SIGNED
  | UNSIGNED
  | STRING
  | IDENTIFIER
  ;

据推测，问题在于它在表达式中看到时无法区分类型和表达式之间的区别(IDENTIFIER)。

输出：

fail.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
fail.y:64.5-14: warning: rule useless in parser due to conflicts [-Wother]
   | IDENTIFIER
     ^^^^^^^^^^

我能做些什么来解决这个冲突？

Answer 1

如果语法仅限于 OP 中显示的产生式，则消除冲突会相对容易，因为语法是明确的。唯一的问题是它是 LR(2) 而不是 LR(1)。

OP中的分析是完全正确的。当解析器看到时，例如：

( identifier1 · )

（其中·标记当前点，因此前瞻标记为)），无法知道它是否是

( identifier1 · ) ;
( identifier1 · ) = ...
( identifier1 · ) identifier2
( identifier1 · ) ( ...

在前两种情况下，identifier1必须简化为expression，因此( expression )可以随后简化为expression，而在后两种情况下， identifier1必须简化为 ，type以便( type ) expression随后可以简化为expression。如果解析器可以在未来看到一个令牌，则可以做出决定。

因为对于任何 LR(k) 文法，都有一个 LR(1) 文法可以识别相同的语言，所以显然有一个解决方案；一般的方法是推迟减少，直到一个令牌前瞻足以区分。一种方法是：

cast_or_expr   : '(' IDENTIFIER ')'
               ;
cast           : cast_or_expr
               | '(' type ')'
               ;
expr_except_id : cast_or_expr
               | cast expression %prec CAST
               | '(' expr_except_id ')'
               | expression '=' expression
               ;
expression     : IDENTIFIER
               | expr_except_id
               ;

（语法的其余部分是相同的，除了IDENTIFIER从 的产生式中删除type。）

这适用于没有符号既可以是前缀又可以是中缀运算符（如-）并且没有运算符可以省略（实际上，就像在函数调用中一样）的语法。特别是，它不适用于 C，因为它会留下歧义：

( t ) * a   // product or cast?
( t ) ( 3 ) // function-call or cast?

这些是语法中真正的歧义，只能通过知道t是类型名还是变量/函数名来解决。

C 解析器的“通常”解决方案是通过在扫描器和解析器之间共享符号表来解决歧义；由于typedef类型别名声明必须出现在第一次使用符号作为适用范围内的类型名之前，因此可以在扫描标记之前知道标记是否已用typedef. 更准确地说，如果没有看到 typedef，则可以假定该符号不是类型，尽管它可能完全未声明。

通过使用 GLR 语法和语义谓词，可以将逻辑限制为解析器。有些人觉得这样更优雅。