有关编写读取CFG并解除左递归的解析器的建议

Question

我需要一些关于编写接受CFG并解除左递归的解析器（使用C和Lex）的建议。由于解析器，需要接受任何字符串和语法，我对如何开始毫无头绪。虽然我熟悉删除左递归的算法（如前面提到的here，但我对如何启动以及涉及到的数据结构会有些无知。什么是存储语法和字符串的最佳方式？我有效地应用算法，请建议。（因为这是家庭作业，请不要我提供的代码，而不是任何其他帮助/伪代码应做到）:)

Answer 1

1. 您需要定义一个语法P是描述语法。这应该很容易。
2. 您需要为P构建解析器。它不需要很复杂，因为P不会很复杂。相信我。您可以使用此方法手动编码递归下降解析器：https://stackoverflow.com/a/2336769/120163
3. 随着P解析，它会建立一个表示语法的数据结构。 这样的数据结构需要记录每条规则的左边，其长度和构成规则体的令牌。
4. 此时，您已经收集了数据结构中的规则，现在您需要通过调整规则来应用左递归算法。
5. 最后你需要打印出规则;他们应该重新出现在您为P选择的语法中。