C++ Bison解析器转移减少冲突

发布于04月23日

我是Bison的新手，我正在try 编写一个解析器.我已经用Flex写了一个 scanner .我为解析器想出了以下语法:

%token NUMBER
%token IDENTIFIER

%start Program

%%

Program: Stats;

Stats: Stats Stat ";"
    | /* Epsilon */
    ;

Stat: "var" IDENTIFIER ":=" Expr
    | Lexpr ":=" Expr
    | Expr;

Lexpr: IDENTIFIER
    | "head" Expr
    | "tail" Expr;

Expr: Term
    | UnaryOperatorChain Term;

UnaryOperatorChain: UnaryOperatorChain UnaryOperator
    | UnaryOperator;

UnaryOperator: "head" | "tail" | "not" | "islist";

Term:
    "(" Expr ")"
    | NUMBER
    | IDENTIFIER;

%%

我得到这个错误: 14 shift/reduce conflicts shift/reduce conflict on token "head"

我认为问题在于解析器无法区分Lexpr和Expr，因此不知道使用哪个规则.我try 了几个小时重新排列语法，但似乎没有任何效果.提前感谢:)

推荐答案

以bison -v运行会生成扩展名为.output的文件.这可以帮助您找到冲突的原因.就您的情况而言，它以:

State 7 conflicts: 7 shift/reduce
State 8 conflicts: 7 shift/reduce

稍后，对于状态7(类似于状态8):

State 7

    8 Lexpr: "head" • Expr
   14 UnaryOperator: "head" •

    NUMBER      shift, and go to state 4
    IDENTIFIER  shift, and go to state 19
    "head"      shift, and go to state 20
    "tail"      shift, and go to state 21
    "not"       shift, and go to state 9
    "islist"    shift, and go to state 10
    "("         shift, and go to state 11

    NUMBER      [reduce using rule 14 (UnaryOperator)]
    IDENTIFIER  [reduce using rule 14 (UnaryOperator)]
    "head"      [reduce using rule 14 (UnaryOperator)]
    "tail"      [reduce using rule 14 (UnaryOperator)]
    "not"       [reduce using rule 14 (UnaryOperator)]
    "islist"    [reduce using rule 14 (UnaryOperator)]
    "("         [reduce using rule 14 (UnaryOperator)]

    Expr                go to state 22
    UnaryOperatorChain  go to state 15
    UnaryOperator       go to state 16
    Term                go to state 17

状态7对应于由前两行中的两个项目组成的项目集.在这两个项目中，您刚刚阅读了令牌"head".以下几行表明Bison不知道在以下情况下该做什么，例如，随后是令牌NUMBER，或者令牌IDENTIFIER，等等.

它可以转移并进入状态4，其中包含项19 Term: NUMBER •，从而继续执行规则8中head之后的表达;或
它可以通过规则14来减少，该规则规定head是一元运算符.

这是在告诉你你的表达语言是模棱两可的.有了经验，您应该已经能够找到歧义的原因.如果没有，再次运行bison -Wcounterexamples也可以帮助您:

  First example: Stats "head" • "head" Term ":=" Expr ";" $end
  Shift derivation
    $accept
    ↳ 0: Stats                                                                     $end
         ↳ 2: Stats Stat                                                       ";"
                    ↳ 5: Lexpr                                       ":=" Expr
                         ↳ 8: "head" Expr
                                     ↳ 11: UnaryOperatorChain   Term
                                           ↳ 13: UnaryOperator
                                                 ↳ 14: • "head"
  Second example: Stats "head" • "head" Term ";" $end
  Reduce derivation
    $accept
    ↳ 0: Program                                                                      $end
         ↳ 1: Stats
              ↳ 2: Stats Stat                                                     ";"
                         ↳ 6: Expr
                              ↳ 11: UnaryOperatorChain                       Term
                                    ↳ 12: UnaryOperatorChain   UnaryOperator
                                          ↳ 13: UnaryOperator  ↳ 14: "head"
                                                ↳ 14: "head" •

这告诉您Bison无法决定如何解析字符串前置(例如head head id).(事实上，作为反例，即使是head id也适用.)请记住，Bison只能解析LALR(1)语法，即带有一个前瞻符号.当第一个head被读取并且第二个head是先行符号时，Bison需要确定这是Lexpr的一部分(后面会跟着:=)还是Expr的一部分(后面会跟着;).当稍后找到(或没有)标记:=时，两者之间的差异将变得明显.但是，为了看到这个标记，我们需要任意数量的前瞻符号，因为Lexpr中head后面的Expr的大小可以任意大.

因此，这里的问题是Lexpr和Expr生成的语言的公共子集，在Stat的两个替代规则中.

恐怕这个问题没有简单的解决方案.您必须重新构建语法并消除歧义.我认为你应该try 一下，所以我不会给任何剧透.提示:只要看到像head tail head head ...这样的开头，尽量避免决定你有哪种表情.

C++ Bison解析器转移减少冲突

推荐答案

C++相关问答推荐

C限制限定符是否可以通过指针传递？

如何启用ss(另一个调查套接字的实用程序)来查看Linux主机上加入的多播组IP地址？

C如何显示字符串数组中的第一个字母

以前版本的tty_ldisc_ops.ioctl()是否也需要文件参数？

ATmega328P EEPROM未写入

如何在C中使printf不刷新标准输出？

函数内的局部字符指针

在CLANG中调试预处理器宏

为什么此共享库没有预期的依赖项？

什么是.c.h文件？

每次除以或乘以整数都会得到0.0000

当b是无符号字符时，int a=(b<；<；2)>；>；2；和int a=b&；0x3F；之间有什么区别？

为什么编译器不能简单地将数据从EDI转移到EAX？

如何对现有的双向循环链表进行排序？

Valgrind正在使用一个Fexecve电话报告不可能发生的事情

如何使用空元素块声明指针数组

哪个首选包含第三个库S头文件？#INCLUDE；文件名或#INCLUDE<；文件名&>？

函数指针作为函数参数 - 应该使用 const 吗？

一元运算符

int 与 size_t 与 long