問題與自頂向下分析中的左遞歸

Question

我已閱讀this以瞭解更多自上而下和自下而上解析之間的區別，任何人都可以解釋與自頂向下分析器中左遞歸相關的問題嗎？

Answer 1

在自上而下的解析器中，解析器以開始符號開始，並嘗試猜測要應用哪些生成以達到輸入字符串。爲此，自頂向下的解析器需要使用輸入字符串中的上下文線索來指導其猜測。

大多數自上而下的解析器都是定向解析器，它在嘗試確定要猜測哪些作品時會在某個方向（通常從左到右）掃描輸入。 LL（k）系列解析器就是這樣一個例子 - 這些解析器使用關於輸入的下k個符號的信息來確定要使用哪些生產。

通常，解析器使用接下來的幾個輸入令牌來猜測哪些產品最終會導致以即將到來的令牌開頭的字符串來猜測產品。例如，如果你有生產

一個→公元前

你會不會選擇使用此產品，除非下一個字符匹配的灣否則，你會保證有一個不匹配的。同樣，如果下一個輸入字符是b，則可能需要選擇此製作。

那麼左遞歸在哪裏進來？那麼，假設你有這兩個產品：

A → Ab | b

該語法生成​​字符b的一個或多個副本的所有字符串。如果你在輸入中看到一個b作爲你的下一個角色，你應該選擇哪個製作？如果您選擇Ab，那麼即使您不確定情況如何，您仍然認爲在您之前有多個b。如果你選擇b，你認爲你前面只有一個b，這可能是錯誤的。換句話說，如果你必須選擇兩個作品中的一個，你不能總是選擇正確。

左遞歸的問題是，如果您有一個左端遞歸的非終結符並且找到可能匹配它的字符串，那麼您不一定知道是使用遞歸生成更長的字符串還是避免遞歸併且生成較短的字符串。大多數自頂向下的解析器或者因爲這個原因而無法工作（他們會報告關於如何進行和拒絕解析的一些不確定性），或者他們可能使用額外的內存來跟蹤每個可能的分支，用盡空間。

總之，自頂向下的解析器通常會嘗試從有限的字符串信息中猜測要做什麼。因此，他們會因左遞歸而感到困惑，因爲他們無法始終準確地預測要使用哪些製作。

希望這會有所幫助！