如何在GLR解析器中執行關聯性規則？

Question

我正在寫GLR的樂趣（再次，因爲我瞭解了自我的最後一次嘗試以來的一些事情）。解析器正在工作，我正在執行消歧規則。我正在以似乎有效的方式處理優先事項。現在我對結合性有點不知所措。

說我有這樣的語法：

E <- E '+' E (rule 1) 
E <- E '-' E (rule 2) 
E <- '0'  (rule 3) 
E <- '1'  (rule 4) 

如果規則1）和2）具有相同的優先級和左結合。

沒有關聯處理，字符串「1-1 + 0」將產生兩個分析樹：

1    2 
/\   /\ 
/ \   / \ 
2  3   4  1 
| \     | \ 
4 4     4 3 

其中數字是指用於還原規則。正確的解析樹是第一個，因此我只想保留這個。

我想知道如何有效地檢測算法上的結合侵害。

我試過的一種方法是看到在第一棵樹頂部節點處，規則2是規則1的子女列表中的規則3的左邊，而在第二條規則1中是規則4的右邊因此，因爲規則2和1是左聯合的，我只保留第一棵樹。

然而，這並沒有讓我在更復雜的例子中走得更遠。這個解決方案的侷限性是我只能根據與另一棵樹的比較來丟棄樹。

您是否認爲我可以使用此方法的精煉版本找到解決方案？標準的做法是什麼？

Answer 1

在我看來這是最好的融入語法規則，徹底解決歧義表示：

E <- F 
E <- E '+' F 
E <- E '-' F 
F <- '0' 
F <- '1' 

如你對（G）LR設置，它應該有可能同樣表達左和右關聯性。由於單位派生，解析樹的深度增加可以通過適當的後處理來解決。

這將完全避免發明一種新機制，並利用無論如何使用的BNF的表現力。我認爲它需要強有力的論據來取代模糊的記法，再加上一個單獨的如何解決的規範。

XQuery語言規範在其定義過程中，從具有額外消歧規則的模糊EBNF（參見April 30, 2002 draft）演變爲放棄後者，以支持包含優先級和關聯性的明確規則（請參閱August 16, 2002 draft）。作爲一名實施者，我非常感謝 - 這讓我的生活更輕鬆。

Answer 2

爲了在算法上做到這一點，我將創建兩個組：包括規則3和4的SIMPLE和包含規則1和2的COMPLEX。如果（COMPLEX）（子）根的最右邊的子代是COMPLEX，則移除此樹，因爲它（部分）是右聯合的。