上下文無關語法是否可以左右遞歸？

Question

ex。

S-> S + T | T

T> U - T | U

U - > ID | N

顯然不保留相關性。但我看不出它在任何情況下都是模棱兩可的。那麼這是一個非模糊的cfg嗎？

Answer 1

語法可以同時具有左右遞歸，就像您展示的那樣，但這並不意味着太多。任何語法可以重寫，因此所有的遞歸的左邊或右邊的（但不是一致的同一個，除非語法規則）：

A -> B A C 

變爲：

A -> B X 
X -> A C 

您現在有一個相互遞歸它在一條規則的左邊，另一條的右邊。你問題中的語法似乎是明確的，但這與左遞歸和右遞歸沒有任何關係。