编译原理什么是自集法

‘壹’ 编译原理全部的名词解释

书上有别那么懒!.
编译过程的六个阶段：词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成
解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序.解释方式是接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句.
编译程序：就是指这样一种程序,通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序).
解释程序和编译程序的根本区别：是否生成目标代码
句子的二义性（这里的二义性是指语法结构上的.）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导),或者存在两棵不同的语法树,则称这个句子是二义性的.
文法的二义性:一个文法如果包含二义性的句子,则这个文法是二义文法,否则是无二义文法.
LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)
第1个L：从左到右扫描输入串 第2个L：生成的是最左推导
1 ：向右看1个输入符号便可决定选择哪个产生式
某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归
文法符号的属性:单词的含义,即与文法符号相关的一些信息.如,类型、值、存储地址等.
一个属性文法(attribute grammar)是一个三元组A=(G, V, F)
G：上下文无关文法.
V：属性的有穷集.每个属性与文法的一个终结符或非终结符相连.属性与变量一样,可以进行计算和传递.
F：关于属性的断言或谓词(一组属性的计算规则)的有穷集.断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.
综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属
继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性.
(1)非终结符既可有综合属性也可有继承属性,但文法开始符号没有继承属性.
(2) 终结符只有综合属性,没有继承属性,它们由词法程序提供.
在计算时： 综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递.
语法制导翻译：是指在语法分析过程中,完成附加在所使用的产生式上的语义规则描述的动作.
语法制导翻译实现：对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算.
中间代码（中间语言）
1、是复杂性介于源程序语言和机器语言的一种表示形式.
2、一般,快速编译程序直接生成目标代码.
3、为了使编译程序结构在逻辑上更为简单明确,常采用中间代码,这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理,并且可以在中间代码一级进行优化工作,使得代码优化比较容易实现.
何谓中间代码：源程序的一种内部表示,不依赖目标机的结构,易于代码的机械生成.
为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言.
(2)便于移植,便于修改,便于进行与机器无关的优化.
中间代码的几种形式：逆波兰记号 ,三元式和树形表示 ,四元式
符号表的一般形式：一张符号表的的组成包括两项,即名字栏和信息栏.
信息栏包含许多子栏和标志位,用来记录相应名字和种种不同属性,名字栏也称主栏.主栏的内容称为关键字（key word）.
符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性.(3)作为目标代码生成阶段地址分配的依据
符号的主要属性及作用：
1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）
4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区）
存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式.
静态存储分配
1、基本策略
在编译时就安排好目标程序运行时的全部数据空间,并能确定每个数据项的单元地址.
2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）
3、静态存储分配的要求：不允许递归调用,不含有可变数组.
FORTRAN程序是段结构,不允许递归,数据名大小、性质固定. 是典型的静态分配
动态存储分配
1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间,那么,就需要采用动态存储管理技术.
2、两种动态存储分配方式：栈式,堆式
栈式动态存储分配
分配策略：将整个程序的数据空间设计为一个栈.
【例】在具有递归结构的语言程序中,每当调用一个过程时,它所需的数据空间就分配在栈顶,每当过程工作结束时就释放这部分空间.
过程所需的数据空间包括两部分
一部分是生存期在本过程这次活动中的数据对象.如局部变量、参数单元、临时变量等；
另一部分则是用以管理过程活动的记录信息(连接数据).
活动记录（AR）
一个过程的一次执行所需要的信息使用一个连续的存储区来管理,这个区 (块)叫做一个活动记录.
构成
1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；
5、控制链；6、实参；7、返回地址
什么是代码优化
所谓优化,就是对代码进行等价变换,使得变换后的代码运行结果与变换前代码运行结果相同,而运行速度加快或占用存储空间减少.
优化原则：等价原则：经过优化后不应改变程序运行的结果.
有效原则：使优化后所产生的目标代码运行时间较短,占用的存储空间较小.
合算原则：以尽可能低的代价取得较好的优化效果.
常见的优化技术
(1) 删除多余运算(删除公共子表达式) (2) 代码外提 +删除归纳变量+ (3)强度削弱; (4)变换循环控制条件 (5)合并已知量与复写传播 (6)删除无用赋值
基本块定义
程序中只有一个入口和一个出口的一段顺序执行的语句序列,称为程序的一个基本块.
给我分数啊.

‘贰’ 编译原理文法

编译原理文法的概念为：每一种自然语言或者是编程语言都需要文法来描述，文法相当于语言学的语义分析，即分析每一句话所表示的含义，编译器需要利用文法来完成其语法分析和语义分析。

字母表是元素的非空有穷集合，字母表中的元素称之为符号，因此，字母表也称之为符号集。例如C语言中的字母表由字母、数字、关键字等组成。

符号串，就是由符号集中的元素组成的序列。例如，给定符号集a、b、c，那么abc、abb、ac就是由该符号集组成的符号串。一个文法中，含有一个，或多个产生式，产生式，描述了将终结符集合和非终结符集合组合成串的方法。

‘叁’ 编译原理，子集法将NFA确定为DFA，求问，表格中的部分都是怎么来的

我也在看这个。
先以S开始，经过任意个ε得到的结点就是第一个I，这道题就是{X，1,2}，
然后将{X，1,2}中的每一个字符经过a（中间可以有ε）后得到的结点加起来，X的Ia={1,2}，
1的Ia={1,2}，2的Ia是空集，所以这一行的Ia={1,2}。
后面的Ib也是一样，只不过是经过b后得到的结点的集合。
然后分别将前面的Ia和Ib作为I计算新的Ia和Ib。
再将这些集合依次标号，这道题是{X，1,2}为X，{1,2}为1，{1,2,3}为2，{1,2，Y}为3，根据上面那个表就可以把图画出来了。

‘肆’ 编译原理:怎么用子集法将NFA转换成DFA 用图4.16的NFA举例子

这里你要弄清子集法中，每一行，指的是变迁。比如第一行，代表状态0，画一根线到状态1，因此第1个0是指这个变迁的起点状态0，第3个1是指变迁的终点状态1。
同理，第2行是指从状态1出发，有2个变迁，即第一个是状态1指向状态1（自己），第2个变迁是从状态1到状态1和2。
这样第3行就表示如果从状态{1，2}开始，输入是0和1时的变迁分别是什么，依此类推。
你红的圈出来的就是NFA所有可能的状态和状态组合。

‘伍’ 求编译原理的名词解释题

词法分析（Lexical analysis或Scanning）和词法分析程序（Lexical analyzer或Scanner）
词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。

语法分析（Syntax analysis或Parsing）和语法分析程序（Parser）
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.

语义分析（Syntax analysis）
语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.例如一个C程序片断:
int arr[2],b;
b = arr * 10;
源程序的结构是正确的.
语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.

Lex
一个词法分析程序的自动生成工具。它输入描述构词规则的一系列正规式,然后构建有穷自动机和这个有穷自动机的一个驱动程序,进而生成一个词法分析程序.

Yacc
一个语法分析程序的自动生成工具。它接受语言的文法,构造一个LALR(1)分析程序.因为它采用语法制导翻译的思想,还可以接受用C语言描述的语义动作,从而构造一个编译程序. Yacc 是 Yet another compiler compiler的缩写.[回页首]

源语言（Source language）和源程序（Source program）
被编译程序翻译的程序称为源程序,书写该程序的语言称为源语言.[回页首]

目标语言（Object language or Target language）和目标程序（Object program or Target program）
编译程序翻译源程序而得到的结果程序称为目标程序, 书写该程序的语言称为目标语言.[回页首]

中间语言（中间表示）（Intermediate language(representation)）
在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。

[回页首]

文法（Grammars）
文法是用于描述语言的语法结构的形式规则。文法G定义为四元组(，，，)。其中为非终结符号(或语法实体，或变量)集；为终结符号集；为产生式(也称规则)的集合；产生式(规则)是形如或 a ::=b 的(a , b)有序对,其中(∪)且至少含有一个非终结符，而(∪)。，和是非空有穷集。称作识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。
一个文法的例子: G=(={A，R},={0,1} ，={A?0R，A?01,R?A1},=A) [回页首]
文法分类（A hierarchy of Grammars）
着名语言学家Noam Chomsky定义了四类文法和四种形式语言类，文法的四种类型分别是0型、1型、2型和3型。几类文法的差别在于对产生式施加不同的限制，分别是：
0型文法(短语结构文法)(phrase structure grammars)：
设G=(，，，)，如果它的每个产生式是这样一种结构： (∪) 且至少含有一个非终结符，而(∪)，则G是一个0型文法。
1型文法（上下文有关文法）(context-sensitive grammars)：
设G=(，，，)为一文法，若中的每一个产生式均满足|，仅仅 除外，则文法G是1型或上下文有关的。
2型文法（上下文无关文法）(context-free grammars)：
设G=(，，，)，若P中的每一个产生式满足：是一非终结符，(∪) 则此文法称为2型的或上下文无关的。
3型文法（正规文法）(regular grammars)：
设G=(，，，)，若中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结，a是终结符，则G是3型文法或正规文法。
0型文法产生的语言称为0型语言。
1型文法产生的语言称为1型语言，也称作上下文有关语言。
2型文法产生的语言称为2型语言，也称作上下文无关语言。
3型文法产生的语言称为3型语言，也称作正规语言。

‘陆’ 编译原理-LL1文法详细讲解

我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一个表达式的文法:

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

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

最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

方法解析:

这种方式称为递归下降分析( Recursive-Descent Parsing )：

当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

这种方式叫做预测分析( Predictive Parsing )：

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

例子:

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

什么是空产生式(ε产生式)？

例子

这里 A 有了空产生式，那么 S 的产生式组 S -> aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。

因此对于 A -> ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。

由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)

因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

在 S_文法基础上，我们允许有空产生式，但是要做限制:

将上面例子中的文法改造:

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:

定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。

定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。

因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:

但是这里有一个关键点，如何求非终结符的串首终结符集？

因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。
其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

上面章节我们知道了，对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。

仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。

因此求非终结符 A 的 后继符号集 算法：

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。

我们可以求出 LL(1) 文法中每个产生式可选集:

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

有了预测分析表，我们就可以进行预测分析了，具体流程:

可以这么理解：

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:

那么如何进行改造呢？
其实很简单，进行如下转换:

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

这种改造方法称为 提取公因子算法 。

当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:

因此对于:

文法中不能包含这两种形式，不然最左推导就没办法进行。

例如:

它能够推导出如下:

你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:

因此消除 直接左递归 算法的一般形式：

例如:

消除间接左递归的方法就是直接带入消除，即

消除间接左递归算法：

这个算法看起来描述很多，其实理解起来很简单：

思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

‘柒’ 编译原理四——代码优化

1、基本块的划分方法：

3、DAG图实现基本块的优化

1、程序流图与循环
控制流程图就是有唯一首节点的有向图，用三元组G=（N，E，n ₀ ）表示（节点集，边集，首节点）节点集就是基本块集，有向边表示如下：基本块i出口语句不是转向语句或停语句，i与紧随其后的基本块j有有向边。或者i出口转向j入口语句。
2、循环：程序流图里的一个节点序列强连通，任意两个节点都有至少一条通路，它们中有且只有一个入口节点。（从序列外某节点有一条有向边引导它，或他是程序流图的首节点。
3、找循环：
必经节点集：从流图首节点出发，到n的任意通路都要经过m，m是n的必经节点，记为mDOMn；流图中结点n的所有必经节点的集合称为节点n的必经结点集，极为D(n)。
DOM的性质：自反性：流图中任意节点a，都有aDOMa。传递性：aDOMb，bDOMc则aDOMc。反对称性：aDOMb,bDOMa,a=b。DOM是一个偏序关系，任何节点n的必经节点集是一个有序集。
必经节点的求法：一定包括自己好吧。。。。。。必经节点集就是前驱节点必经节点集的交集加自己没准。
找回边：假设a b是流图中的一条有向边，如果bDOMa，则a b是流图中的一条回边。已知有向边n d是一条回边，则由它组成的循环就是由结点d、结点n以及有通路到达n但该通路不经过d的所有结点组成的。
4、可规约流图：当且仅当一个流图除去回边后，其余边构成一个无环路流图。性质：1. 图中任何直观环路都是循环。2. 找到所有回边可以对应找出所有循环。3. 循环或嵌套或不相交（可能有公共入口节点），goto语句不可跳入循环。

5、循环优化

‘捌’ 编译原理

编译原理)：利用编译程序从源语言编写的源程序产生目标程序的过程； 用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。

编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成

(8)编译原理什么是自集法扩展阅读：

编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。

编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。

而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。

‘玖’ 【编译原理】第四章：语法分析

从分析树的根节点到叶节点方向构造分析树。
即从开始符号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) 。

‘拾’ 编译原理

C语言编译过程详解
C语言的编译链接过程是要把我们编写的一个C程序(源代码)转换成可以在硬件上运行的程序(可执行代码)，需要进行编译和链接。编译就是把文本形式源代码翻译为机器语言形式的目标文件的过程。链接是把目标文件、操作系统的启动代码和用到的库文件进行组织形成最终生成可执行代码的过程。过程图解如下：

从图上可以看到，整个代码的编译过程分为编译和链接两个过程，编译对应图中的大括号括起的部分，其余则为链接过程。
一、编译过程
编译过程又可以分成两个阶段：编译和汇编。
1、编译
编译是读取源程序(字符流)，对之进行词法和语法的分析，将高级语言指令转换为功能等效的汇编代码，源文件的编译过程包含两个主要阶段：
第一个阶段是预处理阶段，在正式的编译阶段之前进行。预处理阶段将根据已放置在文件中的预处理指令来修改源文件的内容。如#include指令就是一个预处理指令，它把头文件的内容添加到.cpp文件中。这个在编译之前修改源文件的方式提供了很大的灵活性，以适应不同的计算机和操作系统环境的限制。一个环境需要的代码跟另一个环境所需的代码可能有所不同，因为可用的硬件或操作系统是不同的。在许多情况下，可以把用于不同环境的代码放在同一个文件中，再在预处理阶段修改代码，使之适应当前的环境。
主要是以下几方面的处理：
(1)宏定义指令，如 #define a b。
对于这种伪指令，预编译所要做的是将程序中的所有a用b替换，但作为字符串常量的 a则不被替换。还有 #undef，则将取消对某个宏的定义，使以后该串的出现不再被替换。
(2)条件编译指令，如#ifdef，#ifndef，#else，#elif，#endif等。
这些伪指令的引入使得程序员可以通过定义不同的宏来决定编译程序对哪些代码进行处理。预编译程序将根据有关的文件，将那些不必要的代码过滤掉
(3) 头文件包含指令，如#include "FileName"或者#include <FileName>等。
在头文件中一般用伪指令#define定义了大量的宏(最常见的是字符常量)，同时包含有各种外部符号的声明。采用头文件的目的主要是为了使某些定义可以供多个不同的C源程序使用。因为在需要用到这些定义的C源程序中，只需加上一条#include语句即可，而不必再在此文件中将这些定义重复一遍。预编译程序将把头文件中的定义统统都加入到它所产生的输出文件中，以供编译程序对之进行处理。包含到C源程序中的头文件可以是系统提供的，这些头文件一般被放在/usr/include目录下。在程序中#include它们要使用尖括号(<>)。另外开发人员也可以定义自己的头文件，这些文件一般与C源程序放在同一目录下，此时在#include中要用双引号("")。
(4)特殊符号，预编译程序可以识别一些特殊的符号。
例如在源程序中出现的LINE标识将被解释为当前行号(十进制数)，FILE则被解释为当前被编译的C源程序的名称。预编译程序对于在源程序中出现的这些串将用合适的值进行替换。
预编译程序所完成的基本上是对源程序的“替代”工作。经过此种替代，生成一个没有宏定义、没有条件编译指令、没有特殊符号的输出文件。这个文件的含义同没有经过预处理的源文件是相同的，但内容有所不同。下一步，此输出文件将作为编译程序的输出而被翻译成为机器指令。
第二个阶段编译、优化阶段。经过预编译得到的输出文件中，只有常量；如数字、字符串、变量的定义，以及C语言的关键字，如main,if,else,for,while,{,}, +,-,*,\等等。
编译程序所要作得工作就是通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码。
优化处理是编译系统中一项比较艰深的技术。它涉及到的问题不仅同编译技术本身有关，而且同机器的硬件环境也有很大的关系。优化一部分是对中间代码的优化。这种优化不依赖于具体的计算机。另一种优化则主要针对目标代码的生成而进行的。
对于前一种优化，主要的工作是删除公共表达式、循环优化(代码外提、强度削弱、变换循环控制条件、已知量的合并等)、复写传播，以及无用赋值的删除，等等。
后一种类型的优化同机器的硬件结构密切相关，最主要的是考虑是如何充分利用机器的各个硬件寄存器存放的有关变量的值，以减少对于内存的访问次数。另外，如何根据机器硬件执行指令的特点(如流水线、RISC、CISC、VLIW等)而对指令进行一些调整使目标代码比较短，执行的效率比较高，也是一个重要的研究课题。
2、汇编
汇编实际上指把汇编语言代码翻译成目标机器指令的过程。对于被翻译系统处理的每一个C语言源程序，都将最终经过这一处理而得到相应的目标文件。目标文件中所存放的也就是与源程序等效的目标的机器语言代码。目标文件由段组成。通常一个目标文件中至少有两个段：
代码段：该段中所包含的主要是程序的指令。该段一般是可读和可执行的，但一般却不可写。
数据段：主要存放程序中要用到的各种全局变量或静态的数据。一般数据段都是可读，可写，可执行的。
UNIX环境下主要有三种类型的目标文件：
(1)可重定位文件
其中包含有适合于其它目标文件链接来创建一个可执行的或者共享的目标文件的代码和数据。
(2)共享的目标文件
这种文件存放了适合于在两种上下文里链接的代码和数据。
第一种是链接程序可把它与其它可重定位文件及共享的目标文件一起处理来创建另一个 目标文件；
第二种是动态链接程序将它与另一个可执行文件及其它的共享目标文件结合到一起，创建一个进程映象。
(3)可执行文件
它包含了一个可以被操作系统创建一个进程来执行之的文件。汇编程序生成的实际上是第一种类型的目标文件。对于后两种还需要其他的一些处理方能得到，这个就是链接程序的工作了。
二、链接过程
由汇编程序生成的目标文件并不能立即就被执行，其中可能还有许多没有解决的问题。
例如，某个源文件中的函数可能引用了另一个源文件中定义的某个符号(如变量或者函数调用等)；在程序中可能调用了某个库文件中的函数，等等。所有的这些问题，都需要经链接程序的处理方能得以解决。
链接程序的主要工作就是将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。
根据开发人员指定的同库函数的链接方式的不同，链接处理可分为两种：
(1)静态链接
在这种链接方式下，函数的代码将从其所在地静态链接库中被拷贝到最终的可执行程序中。这样该程序在被执行时这些代码将被装入到该进程的虚拟地址空间中。静态链接库实际上是一个目标文件的集合，其中的每个文件含有库中的一个或者一组相关函数的代码。
(2) 动态链接
在此种方式下，函数的代码被放到称作是动态链接库或共享对象的某个目标文件中。链接程序此时所作的只是在最终的可执行程序中记录下共享对象的名字以及其它少量的登记信息。在此可执行文件被执行时，动态链接库的全部内容将被映射到运行时相应进程的虚地址空间。动态链接程序将根据可执行程序中记录的信息找到相应的函数代码。
对于可执行文件中的函数调用，可分别采用动态链接或静态链接的方法。使用动态链接能够使最终的可执行文件比较短小，并且当共享对象被多个进程使用时能节约一些内存，因为在内存中只需要保存一份此共享对象的代码。但并不是使用动态链接就一定比使用静态链接要优越。在某些情况下动态链接可能带来一些性能上损害。
我们在linux使用的gcc编译器便是把以上的几个过程进行捆绑，使用户只使用一次命令就把编译工作完成，这的确方便了编译工作，但对于初学者了解编译过程就很不利了，下图便是gcc代理的编译过程：

从上图可以看到：
预编译
将.c 文件转化成 .i文件
使用的gcc命令是：gcc –E
对应于预处理命令cpp
编译
将.c/.h文件转换成.s文件
使用的gcc命令是：gcc –S
对应于编译命令 cc –S
汇编
将.s 文件转化成 .o文件
使用的gcc 命令是：gcc –c
对应于汇编命令是 as
链接
将.o文件转化成可执行程序
使用的gcc 命令是： gcc
对应于链接命令是 ld
总结起来编译过程就上面的四个过程：预编译、编译、汇编、链接。了解这四个过程中所做的工作，对我们理解头文件、库等的工作过程是有帮助的，而且清楚的了解编译链接过程还对我们在编程时定位错误，以及编程时尽量调动编译器的检测错误会有很大的帮助的。
是否可以解决您的问题？