试图在语法中找到 Shift/Reduce 冲突

Question

我有以下语法 (Yacc)，这是一个简单的 C 编译器的开始，我从一个简单的 if 语句开始：

S : E
  ;

E : COND_NO_ELSE
  ;

COND_NO_ELSE : IF BOOL_EXP BLOCK
;

BLOCK : LC EXP RC

BOOL_EXP : LP EXP BOOL_OP EXP RP
     ;

BOOL_OP : LT_OP
     | GT_OP
     | LE_OP
     | GE_OP
     | EQ_OP
     | NE_OP
     ;

MATH_OP : PLUS_OP
    ;

EXP : IDENTIFIER
    | EXP MATH_OP EXP
    ;

相关规则的词法分析器扫描器如下：

"="       { yylval.string = strdup(yytext); return ASSIGN;}
"+"       { yylval.string = strdup(yytext); return PLUS_OP;}
"-"       { yylval.string = strdup(yytext); return MINUS_OP;}
"*"       { yylval.string = strdup(yytext); return MULTIPLY_OP;}
"/"       { yylval.string = strdup(yytext); return DIV_OP;}
"%"       { yylval.string = strdup(yytext); return MOD_OP;}

"<"       { yylval.string = strdup(yytext); return LT_OP;}
">"       { yylval.string = strdup(yytext); return GT_OP; }
"<="       { yylval.string = strdup(yytext); return LE_OP; }
">="       { yylval.string = strdup(yytext); return GE_OP; }
"=="       { yylval.string = strdup(yytext); return EQ_OP; }
"!="       { yylval.string = strdup(yytext); return NE_OP; }
"("       { yylval.string = strdup(yytext); return LP; }
")"       { yylval.string = strdup(yytext); return RP; }
"{"       { yylval.string = strdup(yytext); return LC; }
"}"       { yylval.string = strdup(yytext); return RC; }
if { return IF; }

我知道当我添加 MATH_OP 时冲突开始了（我有所有数学运算符并且有 5 个冲突，除了 PLUS_OP 之外的所有都被删除并得到 1 shift/reduce冲突）。

我按照建议 here, and checked this 问题对输出文件使用了 -v 标志，但它不太像我的语法...

如何找到冲突？

Answer 1

你的语法包括产生式：

EXP : EXP MATH_OP EXP

这本质上是模棱两可的。假设您有两个运算符：

1 + 2 * 3

很明显，上面的是EXP MATH_OP EXP（因为没有别的选择），而是那个

[EXP: 1 + 2] [MATH_OP *] [EXP: 3]

或者是

[EXP: 1] [MATH_OP +] [EXP: 2 * 3]

这两个解析显然有不同的语义，语法允许两者。

即使您只有一个运算符，也会存在歧义（实际上，同样的歧义），尽管碰巧使用 + 的通常定义，评估将是相同。（与单个运算符 - 不同，这会使歧义稍微清楚一些。）

创建算术表达式的 yacc/bison 文法有两种常规策略：

明确指出表达式的解析方式。 (Example from Wikipedia).
使用优先声明隐式限制解析。 (Example from bison manual.)

第一种策略比较冗长但更灵活；如果您正在尝试了解 LR 解析的工作原理，可能会更好，因为它是显式的。第二种策略更紧凑，可以说更容易阅读（因为许多临时读者比上下文无关语法更能理解运算符优先级列表），但要详细了解它是如何工作的。

在这两种情况下，您都不能像 MATH_OP 那样将所有运算符都集中到一个非终结符中，因为具有不同优先级的运算符在语法上是不同的。

您还将在此站点中找到许多相关问题和答案。

顺便说一句，将 + 之类的纯句法标记的字符串值传递给解析器的情况很少见。解析器不需要那个值，因为它已经知道标记类型，所以 strdup() 是不必要的开销，相应的 free() 使语法动作混乱（而且，把它放在哪里并不明显） .如果您认为您需要字符串来跟踪语法操作，请查看 bison's debug facilities，它比在整个解析器中散布 printfs 更容易使用和更可靠。如果您根本不使用运算符的语义值，那么您显然不需要去复制字符串然后释放或泄漏内存的麻烦。

试图在语法中找到 Shift/Reduce 冲突

Trying to find Shift/Reduce conflict in Grammar

grammar

parsing

yacc

compilation

bison