时间戳

首页 > 解决方案 > 完全左因子以下语法，使其适合在自顶向下编译器中使用

recursion - 完全左因子以下语法，使其适合在自顶向下编译器中使用

问题描述

这里 S 是非终结符开始符号；A、B、C 是非终结符；x, y, 是终端符号

S → A B A C | A C A B
A → A x | A y
B → B x x | B y y
C → x y | y x

看过视频后，我了解了消除生产规则中左递归的简单示例，例如

S → a S a
S → b S b
S → ε

但我不明白如何在上面显示的规则中消除左递归。谁能解释或指出我的解释方向？

标签： recursioncompiler-constructioncontext-free-grammarambiguous-grammar

解决方案

在您的第二个示例中没有左递归，因此删除左递归是微不足道的。

在您的第一个语法中，您需要先进行左因子，然后才能解决递归消除问题。（事实上​​，你的问题的标题是“左因素”，所以你在家庭作业/测验中已经有了这个线索。）

上面提供的链接是谷歌通过搜索词“左因子语法”找到的数百个链接之一，但我建议你至少考虑一下你的课程材料是比谷歌搜索（或随机 Youtube）更好的信息来源的可能性视频）。

推荐阅读