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