我是
Bison
的新手,我正在尝试编写一个解析器。我已经用 Flex 编写了一个扫描仪。我为解析器想出了以下语法:
%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,因此不知道使用哪个规则。我尝试了几个小时来重新安排我的语法,但似乎没有任何效果。预先感谢:)
使用
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
时该怎么办。
19 Term: NUMBER •
,从而继续执行规则 8 中head
后面的表达式;或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
(后面会跟一个 ;
)。当稍后找到(或未找到)标记 :=
时,两者之间的差异将变得明显。但是,为了看到这个标记,我们需要任意数量的前瞻符号,因为 Expr
中 head
后面的 Lexpr
的大小可以是任意大。
所以,这里的问题是
Lexpr
和 Expr
生成的语言的公共子集,在 Stat
的两个替代规则中。
恐怕没有简单的解决方案。你必须重构你的语法并消除歧义。