时间戳

首页 > 解决方案 > 警告：Bison 中的“由于冲突，解析器中的规则无用”

parsing - 警告：Bison 中的“由于冲突，解析器中的规则无用”

问题描述

我正在尝试制作一个 C 词法分析器，但我有一些警告：

rule useless in parser due to conflicts: sentenceList: sentenceList sentence
rule useless in parser due to conflicts: sentSelection: IF '(' expression ')' sentence
rule useless in parser due to conflicts: sentSelection: IF '(' expression ')' sentence ELSE sentence
rule useless in parser due to conflicts: sentSelection: SWITCH '(' expression ')' sentence
rule useless in parser due to conflicts: sentIteration: WHILE '(' expression ')' sentence
rule useless in parser due to conflicts: sentIteration: FOR '(' expression ';' expression ';' expression ')' sentence

这是警告来自的代码部分：

input:    /* nothing */
        | input line
;

line:     '\n'
        | sentence '\n' 
;
sentence :       sentComposed
                |sentSelection
                |sentExpression
                |sentIteration
;

sentComposed:     statementsList
                 |sentenceList
;

statementsList:      statement
                   | statementsList statement
;

sentenceList:    sentence
                |sentenceList sentence
;

sentExpression: expression ';'
              |';'
;

sentSelection: IF '(' expression ')' sentence
              |IF '(' expression ')' sentence ELSE sentence
              |SWITCH '(' expression ')' sentence
;

sentIteration: WHILE '(' expression ')' sentence
              |DO sentence WHILE '(' expression ')' ';' 
              |FOR '(' expression ';' expression ';' expression ')' sentence
;

statement: DATATYPE varList                
;

varList:     aVar
            |varList ',' aVar
;

aVar:     variable inicial                           
;

variable: IDENTIFIER                                 
;

initial: '=' NUM                                         
;

我刚刚添加了更多信息 大写字母中的每个单词都是标记。如果您需要任何其他信息，请告诉我

标签： parsingbisonyacclexical-analysisgnuwin32

解决方案

这是您的语法的相当简化（但完整）的摘录。我已经声明expression为终端，以避免必须定义它：

%token expression IF
%%
sentence :       sentComposed
                |sentSelection
                |sentExpression
sentComposed:    sentenceList
sentenceList:    sentence
                |sentenceList sentence
sentExpression:  expression ';'
                |';'
sentSelection:   IF '(' expression ')' sentence

当我通过野牛运行它时，它报告：

ez.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
ez.y: warning: 8 reduce/reduce conflicts [-Wconflicts-rr]

这些冲突是实际问题，如以下警告所示（“由于冲突”）：

ez.y:8.18-38: warning: rule useless in parser due to conflicts [-Wother]
                 |sentenceList sentence
                  ^^^^^^^^^^^^^^^^^^^^^
ez.y:11.18-47: warning: rule useless in parser due to conflicts [-Wother]
 sentSelection:   IF '(' expression ')' sentence
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

当 bison 在语法中发现冲突时，它会根据一个简单的过程来解决它：

  • shift-reduce 冲突以有利于转移的方式解决
  • 减少-减少冲突的解决有利于语法中较早发生的产生式。

一旦这样做了，可能会证明某些产品永远无法使用，因为它已从可能已减少的每个上下文中消除。这是语法有问题的明显迹象。[注1]

这里的基本问题是，这sentComposed意味着可以将语句串在一起以形成更长的语句。那么如果你写会发生什么：

IF (e) statement1 statement2

可能statement1 statement2是打算将其简化为sentComposed作为 目标的单个IF语句，因此仅当e为真时才执行这两个语句。或者它可能是sentComposed由IF带有 target 的语句组成statement1，然后是statement2. 在 C 语言中，区别在于：

if (e) { statement1; statement2; }

和

{ if (e) { statement1; } statement2; }

所以这是一个真正的模棱两可，你可能需要重新考虑没有大括号才能解决它。

但这不是唯一的问题。你也有一堆减少减少冲突。这些以更简单的方式出现，因为上述语法的一部分是以下循环：

sentence:     sentComposed
sentComposed: sentenceList
sentenceList: sentence

这个循环意味着你的语法允许一个单一sentence的包含在任意数量的单位减少中。你当然不是故意的；我确定您的意图是sentComposed仅在实际必要时使用。但是野牛不知道你的意图；它只知道你说什么。

同样，当您弄清楚您实际上想要如何识别 a 的边界时，您可能会解决这个问题sentComposed。

笔记：

  1. 在某些情况下，冲突实际上并不是问题。例如，这两个产生式之间存在 shift-reduce 冲突；所谓的“dangling-else”歧义：

    sentSelection: IF '(' expression ')' sentence
              |IF '(' expression ')' sentence ELSE sentence

    在嵌套IF语句中：

    IF (e) IF (f) s1 ELSE s2

    目前尚不清楚ELSE应该适用于内部还是外部IF。如果它适用于内部IF，则必须将其转移以允许第二次产生 for sentSelection。如果它适用于外部IF，则必须首先执行归约以完成内部（else-less）IF，然后再转移ELSE到外部IF。Bison 的默认操作（“首选移位”）在这种情况下完全正确，即ELSE立即移位。（事实上​​，这就是为什么默认选择为“首选班次”的原因）。

推荐阅读