這可以由LALR（1）解析器解析嗎？

-2

我寫在野牛解析器對於具有以下構造，以及其他語言：這可以由LALR（1）解析器解析嗎？

自調度：identifierarguments]
調度：expression。 identifierarguments]
字符串切片：expression [expression，expression] - 與Python類似。

arguments是逗號分隔的表達式列表，它也可以是空的。以上所有內容都是表達自己的。我的問題是，我不知道如何解析[method [other_method]]和[someString[idx1, idx2].toInt]，或者是否可以使用LALR（1）解析器完成此操作。

更準確地說，讓我們看看下面的例子：[a[b]]（調用方法a，方法b的結果）。當它達到狀態[a。 [b]]（向前是第二個[），它不知道是否將a（已經減少到identifier）減少到expression，因爲可能跟隨a[b,c]之類的東西（其本身可以減少爲expression並繼續第二個構造從上面）或保留identifier（並將其移位），因爲會出現一個arguments列表（例如[b]）。

由於我表達這種語法的方式，或者不可能用LALR（1）解析器解析所有這些結構，這種轉換/減少衝突嗎？

而且，更常見的問題是，如何證明某種語言不能被特定類型的解析器解析？

來源

2016-11-05 Călin Cruceru

「如何證明某個特定類型的解析器無法解析某個東西？」請明確「某事」。 [語言和語法有所不同]（/ a/476009/824425）（該答案應該回答你關於LL（1）的最後一個問題，但概括幾乎任何解析器類型）。您在這裏指定的是該語言的一些功能，但沒有語法，真的沒什麼可談的。 – 2016-11-05 10:41:30

@Rhymoid我編輯它更清晰。我問的是語言，而不是語法。我不認爲有必要添加我作爲問題的一部分寫的語法，僅僅是因爲我問LALR（1）是否可以解析* language *（它的一些構造，更準確）不是語法。 –

@EJP我有。我寫了一個語法，它具有上述的轉換/減少衝突。我想了很多如何避免它，我失敗了。而現在我在想，也許由於這些構造，語言本身不能用LALR（1）解析器進行分析，而不考慮你編寫語法的方式。 –

假設你的語法是明確的（你描述的部分似乎是），那麼你最好的選擇是指定一個%glr-parser。由於在大多數情況下，只有幾個令牌後纔會強制執行正確的解析，所以開銷不應該很明顯，而且優點是不需要使AST的語法或構造複雜化。

其中一個缺點是，野牛無法驗證語法是否明確 - 一般來說，這是不可能的 - 並且不容易證明。如果事實證明某些輸入不明確，那麼GLR解析器將產生一個錯誤，所以一個好的測試套件很重要。

證明語言不是LR（1）將是棘手的，我懷疑這是不可能的，因爲語言可能是可識別與LALR（1）分析器。（雖然沒有看到整個語法，但是不可能分辨出來。）但是解析（在CS理論之外）需要創建一個正確的解析樹以便有用，而產生LR語法所需的修改也會修改AST ，需要一個解析後修正。在從

a[b[c],d]

和

[a[b[c],d]]

之間按優先級的差異在第一（子集）的情況下產生一個正確的AST彈簧的困難，b結合其參數列表[c]和逗號具有較低優先級;最後，b[c]和d是切片的兄弟姐妹。在第二種情況下（方法調用），逗號是參數列表的一部分，並且與方法應用程序綁定更緊密; b,[c]和d是方法應用中的同胞。但是，直到任意長的輸入（因爲d可能是任何表達式），您無法決定分析樹的形狀。

由於「優先順序」不是正式可定義的，並且存在可能使調整樹成爲可能的黑客手段，所有這些都是手動的。由於LR屬性不是真正可組合的，因此可以提供更嚴格的分析。但無論如何，GLR解析器可能是最簡單和最健壯的解決方案。

未來參考的一個小點：CFG不僅僅是一種編程工具;他們也服務於清晰地傳達有關語法的目的。最後，如果你想描述你的語言，你最好使用明確的CFG，而不是非正式地描述。當然，有意義的非終端名稱將有所幫助，並且一些例子從未受到傷害，但是語法的本質在於正式的描述和省略，這使得其他人更難以「有所幫助」。

來源

2016-11-07 18:11:22 rici

這可以由LALR（1）解析器解析嗎？

回答

相關問題