asd*_*sdf 0 grammar parsing programming-languages
我已阅读此内容以了解更多自上而下和自下而上解析之间的区别,任何人都可以解释与自顶向下解析器中的左递归相关的问题吗？
tem*_*def 13
在自上而下的解析器中,解析器以开始符号开头,并尝试猜测要应用哪些产品来到达输入字符串.为此,自上而下的解析器需要使用输入字符串中的上下文线索来指导其猜测.
大多数自上而下的解析器是方向解析器,它在尝试确定要猜测的产品时,在某个方向(通常是从左到右)扫描输入.LL(k)解析器系列就是其中的一个示例 - 这些解析器使用有关输入的下一个k符号的信息来确定要使用的生产.
通常,解析器使用接下来的几个输入标记来猜测产品,通过查看哪些产品最终可以导致以即将到来的标记开始的字符串.例如,如果您有生产
A→bC
除非匹配的下一个字符是b,否则你不会选择使用此产品.否则,你可以保证不匹配.同样,如果下一个输入字符是b,您可能想要选择此产品.
那么左递归在哪里进来？好吧,假设你有这两个作品:
A→Ab | b
该语法生成角色b的一个或多个副本的所有字符串.如果您在输入中看到ab作为下一个字符,您应该选择哪个作品？如果你选择Ab,那么你假设你面前有多个b,即使你不确定是这种情况.如果你选择b,你假设你前面只有一个b,这可能是错误的.换句话说,如果你必须选择两个作品中的一个,你不能总是正确选择.
左递归的问题是,如果你有一个非递归的非终结符并找到一个可能匹配它的字符串,你不一定知道是否使用递归生成一个更长的字符串或避免递归并生成一个更短的字符串.大多数自上而下的解析器要么因为这个原因而无法工作(他们会报告关于如何继续和拒绝解析存在一些不确定性),或者他们可能会使用额外的内存来跟踪每个可能的分支,空间不足.
简而言之,自上而下的解析器通常会尝试从有限的字符串信息中猜测该怎么做.因此,他们会因左递归而感到困惑,因为他们无法始终准确地预测要使用哪些产品.
希望这可以帮助!