奇怪移位/減少不含糊衝突（我認爲）語法

所以在我的語言，我想有斑點的語法表達：奇怪移位/減少不含糊衝突（我認爲）語法

myObject.myProperty 
myObject.myProperty.subProperty

而且我要聲明

Object myObject = 1

此外，對象類型可以命名空間：

Object.SubObject mySubObject = 1

的簡化語法如下：

program: 
    declaration; 
    | expression; 

declaration: 
    TOKEN_IDENTIFIER TOKEN_IDENTIFIER '=' TOKEN_INTEGER; 
    | TOKEN_IDENTIFIER '.' TOKEN_IDENTIFIER TOKEN_IDENTIFIER '=' TOKEN_INTEGER; 

expression: 
    TOKEN_IDENTIFIER; 
    | expression '.' TOKEN_IDENTIFIER;

不幸的是，用Bison編譯這個語法給出了一個shift-reduce衝突。看看狀態機的輸出，在我看來，Bison解釋它的方式是錯誤的。下面是狀態1，這是讀取所述第一標識符之後的狀態：

State 1 

    3 declaration: "identifier" . "identifier" '=' "integer" 
    4   | "identifier" . '.' "identifier" "identifier" '=' "integer" 
    5 expression: "identifier" . 

    "identifier" shift, and go to state 5 
    '.'   shift, and go to state 6 

    "end of code" reduce using rule 5 (expression) 
    '.'   [reduce using rule 5 (expression)]

和狀態6（讀取點陣當默認移位狀態）僅表示一個聲明：

State 6 

    4 declaration: "identifier" '.' . "identifier" "identifier" '=' "integer" 

    "identifier" shift, and go to state 10

它在我看來，在狀態1中，讀點時不應該有減少的可能性。它應該向前看，如果它看到兩個標識符之後（兩者之間沒有點），它應該轉換到僅聲明狀態，但是如果它看到第二個點或代碼結束，它將減少到表達式。事實上，聲明的規則是兩個標識符可以並排找到而沒有點之間的唯一實例應該消除語法歧義，因此不存在移位減少錯誤。

我試過這與ielr和canonical-lr具有相同的結果（不知道這是否應該重要）。

任何想法？我的解釋是它應該如何工作不正確？

來源

2017-02-24 Anthony Johnson

這是告訴你的是，如果我們看到了'TOKEN_IDENTIFIER''。 TOKEN_IDENTIFIER'，它不知道，在你之外提供其他提示，是否應該減少，返回一個「表達式」，或者換入另一個標記，因爲它被看作是「聲明」的第一部分。一些額外的語法，例如要求「表達式」和「聲明」以分號或某物結尾，這將有助於減少歧義......用你當前的規則，「xy a」可以是一個表達式，（'xy ab'）或者聲明的開頭...... – twalberg

在這個語法中，我不提供遞歸到多個語句中，所以語法不能有多個語句。甚至當我添加';'定界符，我仍然得到轉變/減少衝突。 –

環顧四周，我相信我遇到的問題與http://stackoverflow.com/questions/19335353/a-yacc-shift-reduce-conflict-on-an- unambiguous-grammar一樣，那是的，它是一個明確的語法，但也許它是一個LR（2），野牛不處理。我認爲ielr選項應該解決這個問題。關於如何調整語法的任何想法，因此它是LR（1）。 –

它應該向前看，如果它看到兩個標識符緊跟在對方後面，

LALR（1）中的1表示「一個向前的標記」。因此，解析不會在前瞻中看到兩個標識符，因爲它只能看到一個標識符。

我認爲ielr選項應該解決這個問題。

沒有。解析器是LR（1）（差不多）。並且canonical-lr是LR（1）（精確地）。在所有情況下，它都是相同的1。

簡單的解決方案是使用GLR解析器（%glr-parser），該解析器不限於一個前瞻標記，因爲它根本不使用前瞻。相反，它會並行地維護所有可能的解析堆棧，直到它找到一種方法來確定哪一個是有效的，或者它知道解決不明確性是不可能的。很明顯，保留多個堆棧會導致性能損失，但它可能不會成爲編譯器的瓶頸。 GLR解析器可以在不修改的情況下使用任何明確的語法，並且在大多數情況下，不需要修改解析器操作，因此它通常是一個不錯的選擇。

否則，你可以添加一個「看似多餘的」生產（這句話來自於流行的編譯文本）：

expression: TOKEN_IDENTIFIER 
      | compound_expression 
compound_expression 
      : TOKEN_IDENTIFIER '.' TOKEN_IDENTIFIER 
      | compound_expression '.' TOKEN_IDENTIFIER

這種解決方案並不總是很好地擴展到更復雜的語法，雖然。

來源

2017-02-24 20:21:50 rici

在LALR（1）解析器中處理這類事情的正常方式是將導致衝突的表達式和聲明之間的共同事物分解出來。在你的情況下，這是一個可選的作用域名稱，可以是聲明中的類型名稱，也可以是表達式中的字段引用。所以你重構，作爲

name: TOKEN_IDENTIFIER 
    | name '.' TOKEN_IDENTIFIER 

declaration: name TOKEN_IDENTIFIER '=' expression 

expression: name 
      | ... other expression rules

這部作品的原因是，它現在可以只識別name一開始並不太在乎它是否是一個declaration的開始或expression - 這一決定被推遲，直到它在完整的name之後看到下一個令牌。

請注意，如果您有一條允許兩個連續表達式之間沒有標記的規則，則這仍然會失敗。

此外，這種語法從原始語法略有不同，因爲它允許在一個聲明如

Object.SubObject.SubSubObject mySubSubObject = 1

而你的語法只允許0或一個範圍級別範圍界定的多個級別。

來源

2017-02-24 20:47:10

奇怪移位/減少不含糊衝突（我認爲）語法

回答

相關問題