野牛语法偶尔通过,偶尔失败



我第一次广泛使用Bison语法。我已经设置好了语法,还有一个用来关联结果的小测试套件。

偶尔,测试套件会通过:

Reducing stack by rule 101 (line 613):
   $1 = nterm mathenv ()
-> $$ = nterm closedTerm ()
Stack now 0 5 3
Entering state 120
Reading a token: Next token is token ENDMATH ()
Reducing stack by rule 28 (line 517):
   $1 = nterm closedTerm ()
-> $$ = nterm compoundTerm ()
Stack now 0 5 3
Entering state 119
Reducing stack by rule 12 (line 333):
   $1 = nterm compoundTerm ()
-> $$ = nterm compoundTermList ()
Stack now 0 5 3
Entering state 198
Next token is token ENDMATH ()
Shifting token ENDMATH ()
Entering state 325
... continues to completion ...

偶尔不会:

Reducing stack by rule 101 (line 613):
   $1 = nterm mathenv ()
-> $$ = nterm closedTerm ()
Stack now 0 5 3
Entering state 120
Reading a token: Next token is token MN ()
Reducing stack by rule 28 (line 517):
   $1 = nterm closedTerm ()
-> $$ = nterm compoundTerm ()
Stack now 0 5 3
Entering state 119
Reducing stack by rule 12 (line 333):
   $1 = nterm compoundTerm ()
-> $$ = nterm compoundTermList ()
Stack now 0 5 3
Entering state 198
Next token is token MN ()
Shifting token MN ()
Entering state 11
... errors eventually ...
Now at end of input.
Line: 9 Error: syntax error at token 

ENDMATH是要转移到的正确标记,但有时MN是确定的。每当我进行测试时,我都会得到不一致的结果。这种"随机"的歧义是正常的吗?是什么原因造成的?我应该定义一些%precedence规则吗?

y.output的顶部,我确实看到了一些状态冲突,比如

State 0 conflicts: 3 shift/reduce
State 120 conflicts: 2 shift/reduce
State 127 conflicts: 2 shift/reduce
State 129 conflicts: 2 shift/reduce
State 154 conflicts: 1 shift/reduce
State 207 conflicts: 3 shift/reduce
State 265 conflicts: 109 shift/reduce
State 266 conflicts: 109 shift/reduce
State 267 conflicts: 109 shift/reduce
State 268 conflicts: 109 shift/reduce
State 269 conflicts: 109 shift/reduce
State 342 conflicts: 2 shift/reduce
State 390 conflicts: 109 shift/reduce
State 391 conflicts: 109 shift/reduce
State 396 conflicts: 1 shift/reduce
State 397 conflicts: 1 shift/reduce

消除所有这些冲突是否可取?注意,状态120被列为具有冲突,并且是正好在该随机错误发生之前的状态。

语法冲突意味着语法不是LALR(1)。这可能是由于语法不明确,也可能是因为语法需要多个前瞻性标记。无论何时发生冲突,bison都会根据您的优先级指令选择一个可能的操作(shift或reduce)来解决冲突。这就产生了一个解析器,它可以识别(解析)语法所描述的语言的某个子集。

如果冲突纯粹是由于歧义引起的,那么这可能只会消除歧义解析,而根本不会减少语言。对于这种情况,使用优先级规则来解决歧义是处理问题的正确方法,因为它为您提供了解析所需语言的语法。

如果冲突是由于需要更多的前瞻性,那么优先级规则通常没有帮助。您需要通过重新安排语法以不需要前瞻性或使用其他技术(技巧)来解决问题,例如让lexer根据输入或其他信息中的进一步前瞻性插入额外的合成令牌。

在您的案例中,直接的问题似乎出现在lexer中——在一个案例中,它返回令牌ENDMATH,而在另一个案例则返回MN。语法中也可能存在与y.output中看到的冲突有关的歧义或前瞻性问题,但乍一看,这些问题似乎完全独立于lexer的问题。

相关内容

  • 没有找到相关文章

最新更新