为什么语法可以生成字符串，但不能被相同的递归下降解析器识别？

Question

例如，我们有一个文法S-> aSa | aa，很明显，这个文法可以生成所有偶数长度的a字符串。如果我们为这个文法设计一个递归下降解析器，为什么像"aa"，"aaaa"，"aaaaaa“这样的输入可以被识别，但”aaaaaa“却不能被识别？

这是我的想法：

对于"aa"，尝试S-> aSa，'a‘匹配，但是，'S’不匹配，回溯。尝试S-> aa，matches。

对于"aaaa"，尝试S->aSa，'a‘matches，尝试S-> aSa，我们有aaSaa，S not matches，尝试S->aa，我们有aaaa，matches。

对于"aaaaaa"，尝试S->aSa，'a‘matches，尝试S->aSa，我们有aaSaa，尝试S-> aSa，我们有aaaSaaa，不匹配，尝试S->aa，我们有"aaaaaa“。

我不知道“aaaaaa”是怎么回事。

为什么aaaaaa无法识别？

Answer 1

因为在简单的递归下降解析器中不允许回溯。

递归下降解析器从左到右读取令牌，读取每个令牌一次。

当然，您可以使用回溯递归下降解析器来识别它；但是解析器不再是线性时间。