recursion - 语法 - 左递归

Question

我在理解左递归方面遇到了问题。我知道这是左递归：A->Aa 你能告诉我这是否是左递归吗？A->aA

你能解释一下为什么这是一个间接的左递归吗？

• D ---> dcD' | 标清'
• D' --> DbaD' | 直流' | e

谢谢你的帮助！

Answer 1

如果从非终结E符开始并应用规则您找到一个以E自身开头的字符串，则语法是递归的。如果它是直接规则，那么它是直接左递归的A- > Aa。如果您必须应用更多规则，那么它是间接的。

我假设你的语法是

- `D ---> dcD' | D'`
- `D' --> DbaD' | DcD' | e`

然后你有推导

 D -> D' -> DbaD'

所以这是间接左递归。

现在，如果您确定存在S，那么这取决于您可以从中得出什么S。但是，如果D从 派生的任何单词的开头都没有S，则它是非左递归的。

顺便说一句，最好在 https://cs.stackexchange.com/上问这类问题