如何將語法轉換爲LL（1）語法形式？

Question

E -> E+E|E*E|(E)|a 

鑑於語法， 如何將語法轉換爲LL（1）形式？

E->aX|(E) 
X->+E|*E|epsilon 

這是LL（1）語法嗎？

Answer 1

原始語法是左遞歸的，因此不是LL（1），實際上對於任何k都不是LL（k）。

幸運的是，左遞歸可以被刪除。標準算法通過分別解決即時左遞歸（如我們在這裏）和間接左遞歸這樣做。即時左遞歸是兩者中較簡單的情況。維基百科的文章解釋了它here。

基本上你移動以下遞歸參考到一個新的生產（尾部），其還具有ε替代

X -> ε|+E|*E 

然後刪除從原來生產左遞歸的替代方案，並且允許X部件，遵循所有剩餘的非遞歸的替代品，

E -> (E)X|aX 

請注意，您的提案錯過X以下括號內的表達，這樣就不會RECOG掌握相同的語言。

Answer 2

）查找FIRST（S）和FOLLOW（S），用於此語法： 小號→d S上小號 →C S B小號 →ε