爲什麼自頂向下分析器無法處理左遞歸？

Question

我想知道爲什麼自上而下的解析器無法處理左遞歸，並且我們需要消除由於龍書中提到的這個造成的遞歸。

Answer 1

想一想它在做什麼。假設我們有一個左遞歸生產規則A -> Aa | b，現在我們嘗試匹配該規則。所以我們在檢查我們是否可以在這裏匹配A，但爲了做到這一點，我們必須首先檢查我們是否可以在這裏匹配A.這聽起來不可能，而且大部分是。使用遞歸下降解析器，顯然表示無限遞歸。

有可能使用更高級的技術，仍然是自上而下的，例如參見[1]或[2]。

[1]：Richard A. Frost和Rahmatullah Ha fi z。 一種新的自頂向下分析算法，用於適應多項式時間的模糊性和左遞歸。 SIGPLAN Notices，41（5）：46-54,2006。
[2]：R.Frost，R.Hafi和P.Clalaghan，模塊化和高效的自上而下 解析模糊的左遞歸語法。 ACL-IWPT，第109頁 - 120,2007。