左遞歸語法識別

Question

通常我們想重構一個上下文無關文法來去除左遞歸。有很多算法來實現這種轉換;例如here或here。

這樣的算法將重構語法而不管是否存在左遞歸。這具有負面的副作用，例如從原始語法產生不同的分析樹，可能具有不同的關聯性。理想情況下，語法只有在絕對必要時纔會被轉化。

是否有一個算法或工具來識別語法中的左遞歸的存在？理想情況下，這也可以對包含左遞歸的生產規則的子集進行分類。

Answer 1

有用於識別爲空的非端，它運行在時間的線性在語法的大小的標準算法（見下文）。完成之後，您可以在所有非終端A，B上構建關係A potentially-starts-with B。 （事實上​​，這是比較正常的，構建在所有的語法符號這種關係，因爲它也用於構建FIRST套，但在這種情況下，我們只需要投射到非終端）。

已經這樣做了，留下-recursive非終端都A這樣A potentially-starts-with+ A，其中potentially-starts-with+是：

potentially-starts-with ∘ potentially-starts-with*

你可以使用任何傳遞閉包的算法來計算這種關係。

---

僅供參考，用於檢測可爲空的非終端。

1. 刪除所有無用的符號。
2. 附加一個指向每個生產的指針，最初位於第一個位置。
3. 將所有作品放入作品中。
4. 雖然可能，發現生產，其執行以下操作之一適用：
   • 如果生產的左手側已被標記爲＆的ε-; - 壬終端，丟棄生產。
   • 如果指針右側的標記是終端，則放棄生產。
   • 如果沒有立即令牌指針（即，指針是在端部）標註生產的左手側作爲與小量的權利; - 壬終端並且丟棄的生產。
   • 如果令牌立即向指針的右側是已經標記爲＆小量非末端; - 壬終端，前進指針一個令牌的權利和生產返回到工作隊列。

一旦它不再能夠從工作隊列，所有的ε-＆選擇生產; - 壬終端已被識別。

只是爲了好玩，上述算法的一個微不足道的修改就可以用來做第1步我會離開它作爲一個練習（這也是在龍書的練習）。作爲練習還剩下的方法是確保上述算法在線性時間內執行。