背景：我正在嘗試解決這個 leetcode 問題：正則運算式匹配。我的方法是實作一個 LL(1) 決議器生成器，對于這個問題可能有點矯枉過正，但這只是一種大腦練習。
我只有決議器理論的入門級知識，所以如果我問的是一個愚蠢的問題，請原諒我。
所以，有一個我失敗的測驗用例。要求是正則運算式模式應該匹配整個字串
Regex: a*a
Input: aaa
我無法思考如何將此模式轉換為 LL(1) 決議器。
在我看來，a*a模式可以轉換為生產規則：
S -> Aa # a*a
A -> aA | ε # a*
決議表：
| 一種 | $ | |
|---|---|---|
| 秒 | S -> Aa | |
| 一種 | A -> aA | A -> ε |
下面是決議步驟：
0: S$ aaa$ # use [S,a]
1: Aa$ aaa$ # use [A,a]
2: aAa$ aaa$ # eat 'a'
3: Aa$ aa$ # use [A,a]
4: aAa$ aa$ # eat 'a'
5: Aa$ a$ # use [A,a]
6: aAa$ a$ # eat 'a'
7: Aa$ $ # use [A,$]
8: a$ $ # Error!
正確的匹配應該是：
a* -> aa
a -> a
但我得到的是：
a* -> aaa
a -> Error!
我不知道我錯過了哪一部分??。
uj5u.com熱心網友回復：
在決議步驟 5 中，決議器應該使用[A,$]而不是[A,a]. 但它只能通過展望未來或回溯來做出這個決定。兩者都超出了 LL(1)。
問題的原因在于您的生產規則。存在 FIRST/FOLLOW 沖突：FIRST( A ) 包含 ε，FIRST( A ) 和 FOLLOW( A ) 都包含a。這里用一個例子來解釋：
https://inst.eecs.berkeley.edu/~cs164/sp18/discussion/04/04-solutions.pdf
更直觀地說，您要求決議器在ain之外向前看S -> Aa，以便能夠決定a應該消耗多少個終端A -> aA | ε。
基本上，LL(1) 決議器無法決議a*a. 它必須首先被重寫aa*。可能有一些演算法可以成功地重寫像a*ato這樣簡單的東西aa*，但是不可能將所有可能的正則運算式重寫為 LL(1) 語法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/314389.html