解決移位/減少衝突

Question

我使用PLY解析this語法。我爲鏈接規範中使用的EBNF實現了一個metagrammar，但PLY報告了多個shift/reduce衝突。

語法：

Rule 0  S' -> grammar 
Rule 1  grammar -> prod_list 
Rule 2  grammar -> empty 
Rule 3  prod_list -> prod 
Rule 4  prod_list -> prod prod_list 
Rule 5  prod -> id : : = rule_list 
Rule 6  rule_list -> rule 
Rule 7  rule_list -> rule rule_list 
Rule 8  rule -> rule_simple 
Rule 9  rule -> rule_group 
Rule 10 rule -> rule_opt 
Rule 11 rule -> rule_rep0 
Rule 12 rule -> rule_rep1 
Rule 13 rule -> rule_alt 
Rule 14 rule -> rule_except 
Rule 15 rule_simple -> terminal 
Rule 16 rule_simple -> id 
Rule 17 rule_simple -> char_range 
Rule 18 rule_group -> (rule_list) 
Rule 19 rule_opt -> rule_simple ? 
Rule 20 rule_opt -> rule_group ? 
Rule 21 rule_rep0 -> rule_simple * 
Rule 22 rule_rep0 -> rule_group * 
Rule 23 rule_rep1 -> rule_simple + 
Rule 24 rule_rep1 -> rule_group + 
Rule 25 rule_alt -> rule | rule 
Rule 26 rule_except -> rule - rule_simple 
Rule 27 rule_except -> rule - rule_group 
Rule 28 terminal -> SQ string_no_sq SQ 
Rule 29 terminal -> DQ string_no_dq DQ 
Rule 30 string_no_sq -> LETTER string_no_sq 
Rule 31 string_no_sq -> DIGIT string_no_sq 
Rule 32 string_no_sq -> SYMBOL string_no_sq 
Rule 33 string_no_sq -> DQ string_no_sq 
Rule 34 string_no_sq -> + string_no_sq 
Rule 35 string_no_sq -> * string_no_sq 
Rule 36 string_no_sq -> (string_no_sq 
Rule 37 string_no_sq ->) string_no_sq 
Rule 38 string_no_sq -> ? string_no_sq 
Rule 39 string_no_sq -> | string_no_sq 
Rule 40 string_no_sq -> [ string_no_sq 
Rule 41 string_no_sq -> ] string_no_sq 
Rule 42 string_no_sq -> - string_no_sq 
Rule 43 string_no_sq -> : string_no_sq 
Rule 44 string_no_sq -> = string_no_sq 
Rule 45 string_no_sq -> empty 
Rule 46 string_no_dq -> LETTER string_no_dq 
Rule 47 string_no_dq -> DIGIT string_no_dq 
Rule 48 string_no_dq -> SYMBOL string_no_dq 
Rule 49 string_no_dq -> SQ string_no_dq 
Rule 50 string_no_dq -> + string_no_dq 
Rule 51 string_no_dq -> * string_no_dq 
Rule 52 string_no_dq -> (string_no_dq 
Rule 53 string_no_dq ->) string_no_dq 
Rule 54 string_no_dq -> ? string_no_dq 
Rule 55 string_no_dq -> | string_no_dq 
Rule 56 string_no_dq -> [ string_no_dq 
Rule 57 string_no_dq -> ] string_no_dq 
Rule 58 string_no_dq -> - string_no_dq 
Rule 59 string_no_dq -> : string_no_dq 
Rule 60 string_no_dq -> = string_no_dq 
Rule 61 string_no_dq -> empty 
Rule 62 id -> LETTER LETTER id 
Rule 63 id -> LETTER DIGIT id 
Rule 64 id -> LETTER 
Rule 65 id -> DIGIT 
Rule 66 rest_of_id -> LETTER rest_of_id 
Rule 67 rest_of_id -> DIGIT rest_of_id 
Rule 68 rest_of_id -> empty 
Rule 69 char_range -> [ UNI_CH - UNI_CH ] 
Rule 70 empty -> <empty> 

衝突：

id : LETTER LETTER id 
      | LETTER DIGIT id 
      | LETTER 
      | DIGIT 

。

state 4 

    (62) id -> LETTER . LETTER id 
    (63) id -> LETTER . DIGIT id 
    (64) id -> LETTER . 

    ! shift/reduce conflict for LETTER resolved as shift 
    ! shift/reduce conflict for DIGIT resolved as shift 
    LETTER   shift and go to state 10 
    DIGIT   shift and go to state 9 
    |    reduce using rule 64 (id -> LETTER .) 
    -    reduce using rule 64 (id -> LETTER .) 
    (    reduce using rule 64 (id -> LETTER .) 
    SQ    reduce using rule 64 (id -> LETTER .) 
    DQ    reduce using rule 64 (id -> LETTER .) 
    [    reduce using rule 64 (id -> LETTER .) 
    $end   reduce using rule 64 (id -> LETTER .) 
    )    reduce using rule 64 (id -> LETTER .) 
    :    reduce using rule 64 (id -> LETTER .) 
    ?    reduce using rule 64 (id -> LETTER .) 
    *    reduce using rule 64 (id -> LETTER .) 
    +    reduce using rule 64 (id -> LETTER .) 

    ! LETTER   [ reduce using rule 64 (id -> LETTER .) ] 
    ! DIGIT   [ reduce using rule 64 (id -> LETTER .) ] 

id規則應該保證產品的ID以字母開頭。

下一頁衝突：

rule_alt  : rule '|' rule 

。

state 113 

    (25) rule_alt -> rule | rule . 
    (25) rule_alt -> rule . | rule 
    (26) rule_except -> rule . - rule_simple 
    (27) rule_except -> rule . - rule_group 

    ! shift/reduce conflict for | resolved as shift 
    ! shift/reduce conflict for - resolved as shift 
    (    reduce using rule 25 (rule_alt -> rule | rule .) 
    SQ    reduce using rule 25 (rule_alt -> rule | rule .) 
    DQ    reduce using rule 25 (rule_alt -> rule | rule .) 
    LETTER   reduce using rule 25 (rule_alt -> rule | rule .) 
    DIGIT   reduce using rule 25 (rule_alt -> rule | rule .) 
    [    reduce using rule 25 (rule_alt -> rule | rule .) 
    )    reduce using rule 25 (rule_alt -> rule | rule .) 
    $end   reduce using rule 25 (rule_alt -> rule | rule .) 
    |    shift and go to state 76 
    -    shift and go to state 74 

    ! |    [ reduce using rule 25 (rule_alt -> rule | rule .) ] 
    ! -    [ reduce using rule 25 (rule_alt -> rule | rule .) ] 

連接到smiliar之一：

rule_except  : rule '-' rule_simple 
       | rule '-' rule_group 

如何解決這些？

Answer 1

你真的應該認真思考使用通常的掃描/解析器架構。否則，你將不得不找到一種方法來處理空白。

事實上，你似乎完全忽略了空格。這意味着解析器無法看到three consecutive identifiers之間的空白。它會看到它們以asoupofundifferentiatedletters的形式一起運行，並且無法知道最初的意圖是什麼。這使得你的語法模糊不清，因爲在語法中，兩個標識符可以在假設某事物會使它們彼此區分的情況下相互跟隨。模糊的語法總是會導致LR衝突。

讓詞法分析器識別的標識符（以及其他多字符標記）爲，使得更容易。否則，您將不得不重寫語法以識別允許空格的所有位置（例如圍繞(identifer1|identifier2)中的標點符號）或需要（例如two identifiers）。使用正則表達式也將刪除其他問題你的語法和識別掃描儀

識別標識：

id -> LETTER LETTER id 
id -> LETTER DIGIT id 
id -> LETTER 

這些規則要求id是一個奇數個字符，其中數字只出現在連位置。因此a1b將是id，但不是ab1或ab或a1。我相信那不是你的意思。

您似乎試圖避免左遞歸。相反，你應該擁抱左遞歸。自下而上的解析器，如PLY，喜歡左遞歸。 （他們處理權遞歸，但過度的解析器堆棧使用成本），所以，你真正想要的是：

id: LETTER | id LETTER | id DIGIT 

有在類似的變化是必要的語法等地。

另一個衝突是由您對運算符優先級的非正統處理引起的，這可能也是您嘗試避免左遞歸的結果。與代數運算符一樣，EBNF運算符可以用簡單的優先級方案進行分析。但是，使用優先級聲明（%left和朋友）將因「不可見」串聯運算符而變得複雜。通常，您會發現使用明確的優先級比標準expr/factor/term代數語法更容易。在你的情況下，相當於將是這樣的：

item: id 
    | terminal 
    | '(' rule ')' 
term: item 
    | item '*' 
    | item '+' 
    | item '?' 
seq : term 
    | seq term 
alt : seq 
    | alt '|' seq 
except: term '-' term 
rule: alt 
    | except 

的except在上述對應於缺乏對-操作的優先級信息的處理。這是通過有效地禁止任何-和|運營商的混合而沒有明確的括號來表達的。

你還會發現，你有移進/歸約衝突在這裏：

# The following will create a problem 
prod: id "::=" rule 
prod_list 
    : prod 
    | prod_list prod 

（注：事實上，我寫了左遞歸不會產生問題）

那不是模棱兩可的，但它不是從一個單一的向前標記進行從左到右的解析。它需要兩個令牌，因爲您不知道id是否是當前正在分析的序列的一部分，或者直到您在id之後看到該令牌之後纔開始新的生產：如果它是::=，那麼id是新生產的開始，不應該轉移到現行規則中。通常解決這個問題的方法是在詞法分析器中進行破解：詞法分析器包含一個函數，該函數保留一個額外的前瞻符號，以便它可以發出id ::=作爲definition類型的單個符號。在其他SO問題中，有許多針對各種LR解析器的黑客示例。

---

說了這麼多，我真的不明白爲什麼你想爲EBNF構建一個解析器來解析XML。從EBNF構建工作解析器基本上就是PLY所做的，除了它不實現「E」部分，因此您必須重寫使用?,*,+和-運算符的規則。這可以自動處理，儘管-運算符通常是非平凡的，但它不會很簡單。恕我直言，將BNF規則改寫成BNF，然後使用PLY將會更容易。但是如果你正在尋找一個挑戰，那就去做吧。

Answer 2

首先，你顯然非常地冷靜地翻譯語法。您需要標記輸入流。

通常情況下，類似的ID將是由詞法分析器可以看出端倪終端，而不是解析爲語法

id : LETTER LETTER id 
     | LETTER DIGIT id 
     | LETTER 
     | DIGIT 

它看起來像一切的一部分，你必須下終端不應該成爲語法的一部分。

其次，你在你的語法中使用了正確的遞歸。雖然LALR可以同時使用左遞歸和右遞歸，但您可以使用左遞歸獲得更小的表。

假設你有輸入字符串AA

如果你堅持解析標識符，你會更多的東西一樣

id : id LETTER 
    | id DIGIT 
    | LETTER 

最後，按住Shift鍵並減少衝突不一定基於想要的。它們經常出現在數字表達式中，由運算符先例來解決。

減少 - 減少衝突總是不好的。