BNF：输入到错误的非终结符

Question

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

我开始BNF规则如下（注意，这故意不包括易位或笔记）：

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 /野牛，并得到同样的东西。所以它看起来并不特定于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

我没有使用PLY，没有看到你试过我可能会在一个非问题是捡了完全屈曲/野牛文件，但它在我看来，你并没有给解析器一个想法，即现在的规则没有更多的东西。你没有说你知道输入'd4'是否与start_position相匹配，但是如果解析器知道它具有规则的所有标记，并且唯一的非空标记是end_position，那么它必须匹配'd4'那。

如何引入标记行结束的令牌，如EOL。所以，你的第一条规则变为：

algebraic_notation : piece start_position capture end_position promotion EOL 

和解析器现在看到令牌“D4”，然后EOL - 这是否改变行为？

Answer 2

，如果你换start_position capture end_position成中间块，并从START_POS删除FILE NUMBER，对这样的事情会发生什么：

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 

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 & UllmanIntroduction to Automata Theory, Languages, and Computation

• 阿霍&厄尔曼解析，翻译理论，和编译

或者只是去从杰夫·厄尔曼的类幻灯片：

• Normal Forms for CFG's

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

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

• Removing epsilon production from context-free grammar

• Converting grammar to Chomsky Normal Form?

Answer 4

的问题是，你忽略移位/减少冲突你从你的解析器发生器获得。虽然yacc/bison（可能是PLY）会为您解决错误，但是该解决方案可能无法达到您想要的效果，并且可能会导致解析器解析除您正在尝试解析的语言之外的语言。

无论您何时从LR解析器生成器发生移位/减少（或减少/减少）冲突，您都需要了解冲突是什么（以及为什么会发生），以了解是否可以忽略它或者是否需要要解决这个问题。所以让我们通过摆脱“黑客”（这显然是错误的，而不是要分析的东西），以及无用的“空”规则的修正你的语法（这只会带来混乱）：

%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的等价物是什么）时，你会看到关于转换/减少冲突的消息，并且如果你看在.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 

这是告诉你，看到piece，当一个令牌是后，它不知道它是否应该移位（将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规则的问题。因此，我们认为unfactor以及：

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规则并在algebraic_notation规则中使用文字'x'来简化它。我个人更喜欢这个，因为我认为它是更清晰的，以避免不必要的间接：

%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*/