编译原理为什么存在递归文法

A. 编译原理的消除左递归是怎么回事啊

如果一个CFG像这样
A -> Ab
A -> e

就是有左递归，语法分析里的递归下降法和LL（1）就不能处理啦，因为程序会陷入递归而无法前进。
而CFG
A -> bA'
A' -> bA'|e
和前面一个表达的语言是一样的，但所有语法的第一项都是终结符，就消除了左递归。

有消除左递归的算法，一般编译原理书上会有介绍，不是很复杂。

B. 编译原理问题：求解

E是文法开头。ε代表终结符号(推理中代表终点或结果，程序语言中代表常量等)。E T 这些大写字母一般代表非终结符号（这些代表中间过程，非结果。程序中代表函数等等）。开始是E。因为有个G(E)。E就是文法开始符号。推导就有E开始，它也是一个非终结符(代表函数、或者一个推导过程，类似于程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函数）。

1算术表达式文法：这个文法是一个递归文法。计算机进行逻辑推导时会走很多弯路（类似于遍历一颗树的过程）。为了不让计算机走弯路（提高效率的目的），可以变换为第二种文法。这种文法消除了递归（消除了歧义，类似于后缀表达式），使计算机可以一条直线走到底儿推导出结果。

我也很久没看编译原理了。 呵呵

C. 编译原理语法分析中消除左递归的问题。比如A→Ab|c中为什么说它是左递归呢，明明是A定义为Ab或者

A->Ab|c为什么是左递归，和为什么要消除左递归：

定义，就无需争辩了。至于为什么自顶向下文法不能处理左递归,解释如下：

c∈FIRST(A)，所以当预测分析的栈顶出现非终结符A，而输入字符串最左边为c时，就不知道用产生式A->Ab还是A->c了。无法构造预测分析表。比如输入字符串为cbb，我们人当然容易知道是A->Ab->Abb->cbb了，但是电脑没那么聪明，如果不消除左递归，只有回溯了。

D. 编译原理中,形式语言里怎么区分2型文法与3型文法

通过算法对文法的每一产生式进行分析,如果存在复杂递归,则必是上下文无关文法,否则就是正则文法.
1、像A->Aa|ε这样的文法,虽然存在递归,但却是单一的自递归,可以通过有穷自动机表示和分析处理,所以是正则文法；
2、但是像E->E+T,T->id|(E)这样的文法显然非单一的自递归,而是存在复杂递归,自动机是无法表示和处理的,必然是上下文无关文法.
另外还请注意：
1、正则文法是上下文文法的子集,正则文法也属于上下文无法,但有的上下文文法不一定是正则文法；
2、同时再结合这两个的形式定义认真揣摩必定能悟出一二.

E. 求解编译原理的一道题:设有文法如下

首先要做这题你要知道判别文法类型
包括四个层次：

0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。

1）本题应该是--上下文无关文法

句子是产生式在推导时“仅仅有终结符”的任何一步
2）%mm%nn 是一个句子

由于下面一题的图我等级不够 不能贴图 发你邮箱

F. 编译原理，递归下降子程序语法分析

没学过编译原理，看描述，是让写一个脚本执行软件。
终结符我查了下，就是不可再分的。比如iε。
输入是EGTSFI*/ε组成的字符串。
规则需要预处理。注意转意符在字符串中的效果。因为有/字符。

不会c或c++，只会c#。你可以到贴吧发帖。强人工智能吧 就挺好。算法吧有点乱。

最重要的，不要钱。

G. 【编译原理】第四章：语法分析

从分析树的根节点到叶节点方向构造分析树。
即从开始符号S推导出词串w的过程。

例：

总是选择每个句型的 最左非终结符 进行替换。

总是选择每个句型的 最右非终结符 进行替换。

在自底向上的分析中，总是采用 最左规约 的方式，因此把 最左规约 称为 规范规约 ，对应的 最右推导 称为 规范推导 。

最左推导、最右推导具有唯一性。

自顶向下的语法分析采用最左推导方试，总是选择每个句型的 最左非终结符 进行替换。

由一组 过程 组成，每一个过程对应一个 非终结符 。
从文法开始符号S开始，递归调用文法中的其他非终结符，最终扫描整个输入串，完成分析。

如果其间有不唯一的产生式，就可能需要退回上一步重新尝试的情况，称为 回溯 。

预测分析 是 递归下降分析 技术的一个特例，通过输入中向前看固定个数的符号选择正确的产生式。
如果一个文法可以构造出向前看k个符号的预测分析器，称为LL(k)文法 。

预测分析不需要回溯，具有确定性。

含有 形式产生式的文法称为是 直接左递归 的。
如果一个文法中有一个非终结符A使得对某个串存在推导 ，那么这个文法是 左递归 的。其中，经过两步或以上推导产生的左递归，称为 间接左递归 的。
左递归会使递归下降分析器陷入无限循环。

文法
即
该文法是直接左递归的，会陷入无限循环。

将以上文法转换为：


即可消除左递归。事实上，这个过程把左递归转换成了右递归。

消除直接左递归的一般形式

使用代入法。

对于一个文法，通过改写产生式来 推迟决定 ，等获得足够多的输入信息再做正确的决定。

例：文法：

可以改写为：

从文法的开始符号S开始，每一步推导根据当前句型的最左非终结符A和当前输入符号α，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

S_文法（简单的确定型文法）

可能在某个举行中紧跟在A后面的终结符a的集合，记为 FOLLOW(A) 。
如果A是某个句型的最右符号，则将结束符“ $ ”添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符号串α串首终结符的集合，记作 FIRST(A) 。

H. 编译原理中，形式语言里怎么区分2型文法与3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法 。
B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。
C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端 。
D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：
1）空串
2）只有一个终结符
3）只有一个终结符后接一个非终结符
E、所有的3型文法都是2型文法。

I. 编译原理中 左递归具体解释是什么

定义：
"一个文法是左递归的，若我们可以找出其中存在某非终端符号A，最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型"
即
A -> Aa 或
A -> Ba
B -> A
两种形式的文法.

J. 编译原理中的左递归

1.A->Aa
2.A->Ba
B->Ab (A和B属于非终结符，a和b属于终结符)

通俗点讲：左递归就是情况1所说的“->”两边都含有同一个非终结符；
情况2所说的A->Ba中“->”后面的B 与 B->Ab中“->”前面的B是相同的非终结符
这两种情况就叫作左递归。