yacc - BNF：输入错误的非终结符

Question

我正在为国际象棋代数符号开发 BNF，并遇到了一个有趣的案例，输入到错误的非终端。

我的开始 BNF 规则如下（请注意，这故意不包括 castling 或 notes）：

algebraic_notation : piece start_position capture end_position promotion

piece, start_position, capture, 和promotion可以为空，因此允许像 'd4' 这样的移动。问题是，当输入这样的移动时，输入 ('d4') 被 采用start_position，从而导致错误 b/c 没有更多的输入end_position，不能为空。

显而易见的破解/解决方法是允许end_position为空，然后检查我们是否有任何输入并采取相应的行动。

这确实有效，但我想知道是否有办法解决这个问题。如果导致整个表达式不匹配，输入是否可能不转到第一个匹配符号？

另一个问题是这是否是 BNF 的标准行为，还是我正在使用的 yaccer 的问题：PLY v 3.3。

尝试使用 flex/bison 并得到了同样的结果。所以它似乎并不特定于 PLY。

以下是完整性的所有相关规则：

algebraic_notation : piece start_position capture end_position promotion

piece : KING
        | QUEEN
        | BISHOP
        | KNIGHT
        | ROOK
        | pawn

pawn : empty

start_position : FILE
                | NUMBER
                | FILE NUMBER
                | empty

end_position : FILE NUMBER
                | empty                 // this line is the hack/workaround

capture : CAPTURE
        | empty

promotion : EQUAL QUEEN
            | EQUAL ROOK
            | EQUAL KNIGHT
            | EQUAL BISHOP
            | empty

empty : 

Answer 1

问题是您忽略了从解析器生成器获得的移位/减少冲突。虽然 yacc/bison（可能是 PLY）会为您解决错误，但该解决方案可能无法满足您的需求，并且可能导致解析器解析您尝试解析的语言以外的语言。

每当您从 LR 解析器生成器中获得 shift/reduce（或 reduce/reduce）冲突时，您确实需要了解冲突是什么（以及为什么会发生）才能知道是否可以忽略它或是否需要修复它。因此，让我们通过摆脱“hack”（这显然是错误的，而不是您想要解析的东西）以及无用的“empty”规则（只会混淆事物）来修复您的语法：

%token FILE NUMBER
%%
algebraic_notation : piece start_position capture end_position promotion
piece : 'K' | 'Q' | 'B' | 'N' | 'R' | /*pawn*/
start_position : FILE | NUMBER | FILE NUMBER | /*empty*/
end_position : FILE NUMBER
capture : 'x' | /*empty*/
promotion : '=' 'Q' | '=' 'R' | '=' 'N' | '=' 'B' | /*empty*/

现在，当您通过 'bison -v' 运行它时（总是使用 -v 来获取详细的输出文件——我不确定 PLY 的等价物是什么），您会收到有关 shift/reduce 冲突的消息，如果您看在.output文件中你可以看到它是什么：

state 7

    1 algebraic_notation: piece . start_position capture end_position promotion

    FILE    shift, and go to state 9
    NUMBER  shift, and go to state 10

    FILE      [reduce using rule 11 (start_position)]
    $default  reduce using rule 11 (start_position)

    start_position  go to state 11

这告诉您，在看到 a 之后piece，当下一个标记是 时FILE，它不知道它应该转移（将FILE视为 （的一部分）start_position）还是减少（给出一个空的start_position）。那是因为它需要更多的前瞻性来查看是否有第二个位置可以用作end_position知道要做什么，所以简单地忽略冲突将导致解析器无法解析许多有效的东西（基本上，任何带有空start_position和的东西capture） .

解决涉及像这样的空产生式（或几乎任何涉及空产生式的冲突）的前瞻相关的移位减少冲突的最佳方法是分解语法 - 摆脱空规则并复制任何规则使用和不使用非终端。就您而言，这为您提供了规则：

algebraic_notation : piece capture end_position promotion
algebraic_notation : piece start_position capture end_position promotion
start_position : FILE | NUMBER | FILE NUMBER 

（其他规则不变）这样你仍然有一个移位减少冲突：

state 7

    1 algebraic_notation: piece . capture end_position promotion
    2                   | piece . start_position capture end_position promotion

    FILE    shift, and go to state 9
    NUMBER  shift, and go to state 10
    'x'     shift, and go to state 11

    FILE  [reduce using rule 14 (capture)]

    start_position  go to state 12
    capture         go to state 13

基本上，我们只是将冲突移了一步，现在出现了空capture规则的问题。因此，我们也将其分解：

algebraic_notation : piece end_position promotion
algebraic_notation : piece capture end_position promotion
algebraic_notation : piece start_position end_position promotion
algebraic_notation : piece start_position capture end_position promotion
capture : 'x'

现在野牛报告不再有冲突，所以我们可以有理由相信它会按照我们想要的方式解析。您可以通过摆脱规则并在规则中使用文字来进一步简化capture它。我个人更喜欢这个，因为我认为避免不必要的间接更清楚：'x'algebraic_notation

%token FILE NUMBER
%%
algebraic_notation : piece end_position promotion
algebraic_notation : piece 'x' end_position promotion
algebraic_notation : piece start_position end_position promotion
algebraic_notation : piece start_position 'x' end_position promotion
piece : 'K' | 'Q' | 'B' | 'N' | 'R' | /*pawn*/
start_position : FILE | NUMBER | FILE NUMBER
end_position : FILE NUMBER
promotion : '=' 'Q' | '=' 'R' | '=' 'N' | '=' 'B' | /*empty*/

Answer 2

我没有使用 PLY，并且没有看到您尝试过的完整 flex/bison 文件，我可能会选择一个非问题，但在我看来，您并没有让解析器知道当前不会再出现algebraic_notation规则。您没有说您如何知道输入 'd4' 与 start_position 匹配，但如果解析器知道它具有规则的所有标记，并且唯一的非空标记是 end_position，则它必须匹配 'd4'那。

引入一个标记一行结束的令牌怎么样，比如 EOL。所以你的第一条规则变成：

algebraic_notation : piece start_position capture end_position promotion EOL

并且解析器现在看到令牌“d4”后跟 EOL——这会改变行为吗？

Answer 3

这个问题很好地说明了一个问题是计算机科学理论，即从语法中删除 epsilon（或空）产生式。国际象棋符号的歧义问题可以通过简化语法以删除空产生式来解决（对于 yacc 或 PLY）。SO/SE 和其他站点上都有很多关于此的材料。我为感兴趣的读者附加了参考书目。

通过对规则进行无意识的转换以删除盲/空/ε产生式，我们得到以下CFG：

algebraic_notation : piece start_position capture end_position promotion
                   | piece start_position capture end_position 
                   | piece start_position capture promotion
                   | piece start_position end_position promotion
                   | piece capture end_position promotion
                   | piece start_position capture
                   | piece start_position end_position
                   | piece capture end_position
                   | piece start_position promotion
                   | piece capture promotion
                   | piece end_position promotion
                   | piece promotion
                   | piece end_position 
                   | piece capture 
                   | piece start_position 
                   | piece 
                   | start_position capture end_position promotion
                   | start_position capture end_position
                   | start_position capture promotion
                   | start_position end_position promotion
                   | capture end_position promotion
                   | start_position capture
                   | start_position end_position
                   | capture end_position
                   | end_position promotion
                   | start_position 
                   | capture 
                   | end_position
                   | promotion
piece : KING
        | QUEEN
        | BISHOP
        | KNIGHT
        | ROOK

start_position : FILE
                | NUMBER
                | FILE NUMBER

end_position : FILE NUMBER

capture : CAPTURE

promotion : EQUAL QUEEN
            | EQUAL ROOK
            | EQUAL KNIGHT
            | EQUAL BISHOP

（这可以通过删除那些在国际象棋符号中不可能出现的组合来简化，但这是给读者的练习）。

参考书目

最好的书可能是：

• Hopcroft & Ullman 介绍自动机理论、语言和计算

• Aho & Ullman解析、翻译和编译理论

或者只是转到 Jeff Ullman 课堂上的幻灯片：

• CFG 的范式

或者一堆关于 SO/SE 的相关问题：

• https://math.stackexchange.com/questions/563363/removing-epsilon-productions-from-a-context-free-grammar

• 从上下文无关语法中删除 epsilon 产生式

• 将语法转换为乔姆斯基范式？

Answer 4

如果你包裹start_position capture end_position到一个中间块，并FILE NUMBER从 start_pos 中删除，会发生什么情况：

middle: start_pos capture end_pos
      | end_pos capture end_pos
      | capture end_pos

start_pos : FILE
      | NUMBER
      | empty

end_pos : FILE NUMBER

capture : CAPTURE
      | empty