消除左递归及提取左公因子

如题所述

举报该问题

第1个回答 2022-06-03

如果一个文法中有一个非终结符号A使得对某个串α存在一个推导A=》Aα，那么这个文法就是左递归的。递归分为立即左递归和非立即左递归。立即左递归单步即可看出来，非立即左递归
举个例子：

消除立即左递归只需要遵循以下规律进行转换就ok。

立即左递归：

非立即左递归：

和数学中的公因子含义相同，就是公共的因子，而左公因子就是最左边的公因子。

例如：

可以看出前n项拥有一个共同的左公因子：a，所以可以把他提取出来。

so easy啦

S → aB1|aB2|aB3|aB4|...|aBn|y
可以看出前n项拥有一个共同的左公因子：a，所以可以把他提取出来。

提取规则
so easy啦

S → aS'|y
S'→ B1|B2|B3|...|Bn

相似回答

【编译原理】自顶向下LL(1)分析中,消除左递归和提取左因子的目的...答：通常LL(1) 是以函数递归调用来实现的如文法: A -> A + a | a 代码实现则为:function A(){ A();match('+');Term(a);} 这样你可以看得出死循环了吧...?将文法消除左递归后 A -> aA'A' -> +aA'则可以避免这一问题提出公因式就像楼上说的一样,避免程序回溯,消除二义性....

编译原理题目 s→ (L)|aS|a L→L,S|S 消除左递归和回溯(过程请详细点...答：消除回溯：提取左公因子a，（注：用e代表一补西农符号，就是反三的那个符号，在电脑上不知道怎么打那个符号）S→aS'|(L)S'→S|e 消除左递归：L→SL'L'→,SL'|e (注意S前面有一个符号“,”)

对下面文法先消除左递归,并提取左公共因子,再判断其是否是LL(1)文法...答：提取公共左因子没有可提文法不含左递归每个非终结符只有一个产生式候选首符集唯一FOLLOW(S')=# 与其首符集相交为空是LL(1)文法本回答由网友推荐举报| 答案纠错 | 评论 3 3 E_C_Ares 采纳率:71% 擅长: 互联网数学其他回答 消除左递归:S -> S' | bS' -> BaS' | εB -> ab是LL 文...

给定文法G=({S,L},{a,(,)},{S→(L)|a L→L,S|S},S)。给出句型“(S,(a...答：L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε} FOLLOW(L’〕＝{ )} 例如：消除回溯：提取左公因子a，（注：用e代表一补西农符号，就是反三的那个符号，在电脑上不知道怎么打那个符号）S→aS'|(L)S'→S|e 消除左递归：L→SL'L'→,SL'|e (注意S前面有一个符号“,”)...

编译原理语法分析中,求first,follow集合时,要消除左递归吗答：如果题目是单纯求first、follow集合,不需要消除左递归.但是,如果求first、follow集合是为了判断文法是否为LL(1)文法的话,可以直接得出否定的结论（因为含有左递归的文法绝对不是LL(1)文法）.可以先对文法进行改写,一般是消除左递归和提取左公共因子,然后再判断.

自顶向下的语法分析方法答：1）文法的等价变换方法，特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL（1）文法的条件。四、确定的自顶向下分析方法掌握递归下降子程序的特点以及用PL/0程序分析PL/0编译程序的语法分析过程。掌握如何构造预测分析表；能用预测分析方法判断给定的输入符号串是否是该文法的句子。

关于LL(1)文法的编译原理题目?答：｜b(M)｜b 第一个产生式中存在左递归:M->MaH 第二个产生式中存在首字符相同:H->b(M) ,H->b 怎么改呢？对第一个产生式，消除左递归就是要变成右递归，把右边剩下的符号提到前面:M->aHM'M'->aHM'对第二个产生式，提出公共因子 H->b( (M)|ε)=> H->bH'H'->(M)|ε ...

对下面文法先消除左递归,并提取左公共因子,再判断其是否是LL(1)文法...答：PS是预测集合等同于课本上的select，我也是自己做的，有错的话希望帮忙回答一下谢谢没用到提取公因数，应该不是很正确

大家正在搜

消除文法的左递归及提取公共左因子消除左递归提取公共左因子消除左递归和提取左因子提取左公共因子公共左因子怎么提取编译原理提取左公共因子消除左公因子消除回溯提左因子如何消除左递归