以下語法是否適合預測決議，或者它們是修改語法以使其適合預測決議的演算法？
number = digit digit_or_sep* digit | digit
digit_or_sep = '0'..'9' | '_'
digit = '0'..'9'
其中*表示零或更多，并|劃分不同的選擇。
我已經撰寫了一個回溯決議器，它在上述語法上運行良好，但是我讀到現代決議器現在大多是預測決議器，并且很少使用回溯決議器。回溯決議器需要在回溯時回退決議器的狀態，這使得它們的性能不如預測決議器。
將上面的語法轉化為：
number = digit (sep* digit )*
sep = '_'
digit = '0'..'9'
其中 表示一個或多個。
將使預測決議作業，因為它避免digit_or_sep*在 final 之前消耗太多令牌digit。但我不確定是否有一種演算法方法可以自動轉換語法以使其作業。
編輯：我在谷歌上讀過關于左分解的文章，它可能是我需要理解的難題的缺失部分。
經過一點左重構：
number = digit digit_or_sep* digit | digit
digit_or_sep = '0'..'9' | '_'
digit = '0'..'9'
let g = digit_or_sep g | empty
number = digit g digit | digit
let h = g digit | empty
number = digit h
h = g digit | empty
g = digit_or_sep g | empty
g = digit g | sep g | empty
h = (digit g | sep g | empty) digit | empty
h = digit g digit | sep g digit | digit | empty
h = digit h | sep g digit | empty
產生以下語法：
number = digit h
h = digit h | sep g digit | empty
g = digit g | sep g | empty
這應該適用于預測決議器。但是我還沒有想出一個演算法來自動完成它。
編輯：詳細說明我正在嘗試做的事情。上面的語法只是我想轉換的語法的一個小例子。
我實際上是在決議 Kotlin： https ://github.com/clinuxrulz/parse-bolt/blob/main/src/kotlin/parser.rs
它與回溯決議器一起作業正常，但存在性能問題。決議一個簡單的函式型別簽名“(a: String, b: String) -> String” 需要 20 毫秒來決議，這對于這么小的輸入來說太慢了。我可以在我知道的代碼中進行一些優化，但它比我預期的要慢。
另一方面，對于預測決議，我不能簡單地按原樣使用他們的語法。似乎首先需要對語法進行一些手動更改。在生成決議器之前，ANTLR 必須首先對其語法進行一些轉換。
Kotlin 語法檔案的底部與上面的數字示例相同： https ://github.com/Kotlin/kotlin-spec/blob/release/grammar/src/main/antlr/KotlinLexer.g4
我讀過 ANTLR 可以在 1 秒內決議完整的 Java 標準庫。我可能還有很長的路要走。
uj5u.com熱心網友回復：
我同意 rici 的評論，即沒有演算法可以保證任何語法的完全左分解。但是有啟發式搜索方法。
當我需要表現時，我會堅持使用 PEG 并修改我自己的語法。并盡可能優化我的回溯決議組合器，因為它可以處理更多型別的語法并且可能仍然有用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/461351.html