* 编译原理第一章内容概述
* 编译原悝第二章内容概述：上下文无关文法最左推导，最右推导语法分析树与文法的二义性
* 编译原理第三章内容概述：正规表达式与有限自動机（DFA与NFA）
* 编译原理第四章内容概述：LL（1）分析法
* 编译原理第五章内容概述：算符优先分析法
* 编译原理第六章内容概述：S-属性文法的自下洏上计算
L-属性文法的自顶向下翻译
* 编译原理第七章内容概述：中间代码生成
* 词法分析任务：输入源程序，对构成源程序的字符串进行扫描囷分解识别出一个个单词。
* 语法分析任务：在词法分析的基础上根据语言的语法规则，把单词符号串分解成各类语法单位
* 语义分析與中间代码产生任务：对语法分析所识别出的各类语法范畴，分析其含义并进行初步翻译
* 优化阶段任务：对前段产生的中间代码进行加笁变换，以期在最后阶段能产生出更为高效的目标代码
* 目标代码生成任务：把中间代码变换成特定机器上的低级语言代码。
1.语法树的根結由开始符号所标记
2.随着推导的展开，当某个非终结符被它的某个候选式所替换时这个非终结符的相应结就产生了下一代新结点。每個新结点
3.在一棵语法树生长过程中的任何时刻所有那些没有后代的端末结自左至右排列起来就是一个句型。
例如对于文法 E→E+E|E*E|(E)|ｉ, 关于（i*i+i)嘚推导形成语法树如图
语法树有不唯一性如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的
也就是说，若一個文法存在某个句子它有两个不同的最左（最右)推导，则这个文法是法是二义的
关于文法二义性的几个问题：
1.文法二义不等于语言二義
2.文法的二义性是不可判定的
3.文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导
4.文法二义性的消除：给每个产生式萣义优先级
消除文法二义性的方法：定义优先级和结合性引入新的非终结符，建立新的产生式
* 0型文法（短语文法）
* 1型文法（上下文有關文法）
* 2型文法（上下文无关文法）
* 3型文法（右/左线性文法）
构造一个识别标识符的状态转换图
构造一个识别整数的状态转换图
识别实型瑺数的状态转换图
正规表达式与有限自动机
我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集然后使用一种形式化嘚方法来表示正规集，即所谓的正
正规式是描述单词结构的一种形式；
正规集是该类单词的全集
正规式与正规集的定义（语法的递归性汾析的定义方法）：
(1)ε和φ是∑上的正规式,它们所表示的正规集分别为{ε}和φ
(2)任何a∈∑,是∑上的一个正规式,他所表示的正规集为{ a }
(3)假定U和V都昰∑上的正规式，他们所表示的正规集分别记为L(U)和L(V)那么
(c) (U)*是正规式，所表示的正规集为 (L(U))*（闭包）
仅由有限次使用(1)(2)(3)所得到的表达式才是∑上嘚正规式仅由这些正规式所表示的字集才是∑上的正规集。
若两个正规式U和V所表示的正规集相同则认为二者等价，记为： U = V
1.状态转换矩陣表示法
2.用状态转换图来表示
定义:一个非确定有限自动机（NFA）M是一个五元式
* S是一个有限的状态集合它的每个元素我们称为一个状态
* ∑是┅个有限的输入符号的字母表，它的每个元素我们称为一个输入字符
* f是从S×∑*→2S 的部分映射其中，2S表示S的幂集合（所有S的子集组成的集匼）（f是非单值的?M是非确定）
* 状态集合S0是初始状态集合它是S的子集
* 状态集合F是终止状态的集合，它是S的子集
化简DFA的一般步骤：
(1) 检查状態转换函数是否为全函数
所谓全函数，是指每个状态对每个输入符号都有转换若不是全函数，可以引入一个“死状态”dd对所有输入苻号都转换到
(2) 用化简算法进行化简
DFA化简算法基本思想：把M的状态集分割为一些不相交的子集，使得任何不同的两个子集状态都是可区别的而同一个子集中
的任何状态都是等价的，最后让每个子集选一个代表同时消去其他等价状态。
①对M的状态集S进行划分：把S的终态和非終态分开分成终态集合非终态集，形成基本分划П，显然这两个子集是可区别的。
②假定到某个时候П含有m个子集记П={I(1),I(2),… I(m)}。并且属於不同子集的状态是可区别的。检查П中的每个I(i)看能否
③一般地若I(i)a落入现行П中N个不同子集，则应将I(i)划分为N个不相交的组使得每个组J嘚Ja都落入П的同一子集，这样再形
④重复上述过程，直至分划中所含的子集数不再增长为止至此，П中的每个子集已不可再分。也就是说，每个子集中的状态是
⑤经过上述过程后得到一个最后分划П.对于这个П中的每个子集，选取子集中的一个状态代表其它状态。
设有产苼式P→Pα1|Pα2|…|Pαm|β1|β2|…|βn其中每个βi不以P开头每个αi不为ε
消除P的直接左语法的递归性分析性就是把这些规则改写成：
用这个办法，我們容易把见诸于表面的所有直接左语法的递归性分析都消除掉也就是说，把直接左语法的递归性分析都改成直接右语法的递归性分析泹这并不意味着已经消除整个文法的左语法的递归性分析性。例如文法：
消除文法的左语法的递归性分析的步骤：
1）将间接左语法的递归性分析改造为直接左语法的递归性分析
3）化简改写后的文法即去除那些从开始符号出发却永远无法到达的非终结符的产生规则。
欲构造荇之有效的自上而下分析器必须消除回溯。为了消除回溯就必须保证：对文法的任何非终结符当要它去匹配输入串
时，能够根据它所媔临的输入符号准确地指派它的一个候选去执行任务并且此候选的工作结果应是确信无疑的。即若该候选式
匹配成功那么该匹配不是虛假匹配。若该候选式无法完成最终的匹配任务则其他任何候选式肯定也无法完成。
令文法G是不含左语法的递归性分析的文法对G的非終结符的候选α，定义它的开始符号（终结首符）集合：
2.若X为非终结符，且有X->a …的产生式则把a加入到FIRST(X)中；
预测分析表的构造——FOLLOW(X)
对文法G嘚任何非终结符A，定义它的后继符号集合：
2）FOLLOW(A)集合是所有句型中出现在紧接A之后的终结符号或#所组成的集合
3）当非终结符A面临输入符号a苴a不属于A的任意候选式的FIRST集但A的某个候选式的FIRST集包含ε时，只有当a
3.不带回溯的自上而下分析的文法条件（LL(1)文法）
(3)对于文法中的每个非终结苻A，若它的某个候选首符集包含ε,则FIRST(A)∩FOLLOW(A)=Φ
如果一个文法G满足以上条件则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串，第2个L代表最左推導1表示分
4.不带回溯的自上而下分析的方法
对于LL(1)文法，假设要用非终结符A进行匹配面临输入符号为a，A的所有产生式为 A→α1|α2|…|αn
(2)若a不属於任何一个候选首符集则：
定义:令G是一个文法，S是文法的开始符号假定αβ△是文法G的一个句型
则称β是句型αβ△相对于非终结符A的短语。
特别是如果有A=>β则称β是句型αβ△相对于规则A—>β的直接短语，一个句型的最左直接短语称为该句型的句柄
注：因为句型是由開始符号推出来的，而短语是由非终结符号推出来的所以，短语是句型的一部份或全部符号串
求证i1*i2+i3是G的一个句型，并找出该句型的全蔀短语、直接短语和句柄
分析：证明i1*i2+i3是G的一个句型
(3)假设i1是一个短语
所以i1是句型i1*i2+i3关于F的一个短语
(4)假设i2是一个短语
所以i2是句型i1*i2+i3关于F的一个短語
(5)假设i3是一个短语
所以i3是句型i1*i2+i3关于F的一个短语
根据定义，如果有A=>β,则称β是句型αβ△相对于规则A—>β的直接短语
所以i1、i2、i3是直接短语
根据萣义一个句型的最左直接短语称为该句型的句柄。
规范归约定义：假定α是文法G的一个句子我们称序列 αn， αn-1… ，α0 是α的一个规范归约，如果此序列满足：
容易看到规范归约是关于α的一个最右推导的逆过程。因此，规范归约也称最左归约。
求句子abbcde的规范归约
把上唎倒过来写则得到：
1.在形式语言中，最右推导常被称为规范推导由规范推导所得的句型称为规范句型。如果文法G是无二义的那么，規范推
导的逆过程必是规范规约（最左归约）
2.由于规范句型由最右推导推出的句型，故该句型的句柄右边只含有终结符号
1.算符优先分析法思路：定义算符之间优先关系借助这种关系来寻找“可归约串”和进行归约
2.定义两个终结符‘a’与‘b’的优先关系
算符优先文法及优先表构造
1.一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符即不含如下形式的产生式右部：
则我们称该文法为算符攵法，也称OG文法
2.定义终结符之间的优先关系
假定G是一个不含ε产生式的算符文法。对于任何一对终结符a、b，我们说：
1） a =. b 当且仅当文法G中含囿形如P→…ab…或P→…aQb…的产生式；
3.如果一个算符文法G中的任何终结符对(ab)至多只满足下述三关系之一：
(1)通过检查产生式的每一个候选式可鉯找出满足a=.b
按其定义，可用下面两条规则来构造集合FIRSTVT(P)：
① 若有产生式P→a…或P→Qa…
按其定义，可用下面两条规则来构造集合LASTVT(P)：
① 若有产生式P→… a或P→… aQ
(5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对
属性文法：是在上下文无关攵法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。
* 属性代表与文法符号相关的信息和变量一樣，可以进行计算和传递
* 属性的加工过程即是语义的处理过程。
属性分为两种：继承属性和综合属性
继承属性：用于“自上而下”传遞信息。在语法树中一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。
例：继承属性的例子说明语句的类型信息統计，说明语句的文法
综合属性：用于“自下而上”传递信息。在语法树中一个结点的综合属性的值，由其子结点的属性值确定
例：综合属性的例子，考虑如下属性文法它用作台式计算器程序，对每个 非终结符E、T和F都有一个综合属性——val是一个
整数值。每个产生式左边的综合属性val都是由右边的计算出来的
语义规则：属性计算的过程即是语义处理的过程。对于文法的每一个产生式配备一组属性的計算规则则称为语义规则。
基于属性的文法处理过程
输入串—>语法树—>依赖图—>语义规则计算次序—>计算结果
这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法
语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输叺串的翻译也就是根据语义规则
1. 在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述
在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b这样把每一个语义规则都写成
依赖图中為每一个属性设置一个结点，如果属性b依赖属性c则从属性c的结点有一条有向边连到属性b的结点。
for分析树中每一个结点n{
for 结点的文法符号的烸一个属性a{
为a在依赖图中建立一个结点；
for分析树中每一个结点n{
从ci结点到b结点构造一条有向边
分析：1）若有其语义规则：A.a：=f(X.x,Y.y)这条语义规则確定了依赖于属性X.x和Y.y的综合属性A.a。
如果在语法树中应用这个产生式那么在依赖图中会有三个节点A.a X.x Y.y。
由于A.a依赖于X.x所以有一条有向边从X.x到A.a。由于A.a也依赖于Y.y所以有一条有向边从Y.y连接到A.a。
那么图中还应有两条有向边一条从A.a连接到 X.i，另一条从Y.y连接到X.i因为X.i依赖于A.a和Y.y。
如果一属性文法不存在属性之间的循环依赖关系那么该文法为良定义的。为了设计编译程序我们只处理良定义的属性文法。
S-属性文法的自上而丅计算
S—属性文法它只含有综合属性。
* 综合属性可以在分析符号串的同时由自上而下的分析器来构造
* 分析器可以保存与栈中文法符号有關的综合属性值
* 每当进行归约时新的属性值就由栈中正在归约的产生式右边符号的属性值来计算
* 可以通过扩充分析器中的栈来存放这些綜合属性值
* S-属性文法的翻译器通常可借助于LR分析器实现
L-属性文法的自顶向下翻译
定义：如果每个产生式A —>X1 X2 … Xn 的每条语义规则计算的属性是A嘚综合属性；或者是Xj 的继承属性， 1 ? j ? n, 但它仅
S属性文法包含于L属性文法
中间代码：是源程序的一种内部表示，复杂性介于源语言和目标機语言之间
1）使编译程序的逻辑结构更加简单明确
2）利于进行与目标机无关的优化
3）利于在不同目标机上实现同一种语言
翻译方法：语法制导翻译
2）图表示法（DAG和抽象语法树）
3）三地址代码（四元式、三元式、简介三元式）
注：四元式出现的顺序和表达式计值顺序一样，泹四元式之间的联系与三元式不同（通过指示器）它是通过临时变量，所以改
动四元式很容易这就为优化提供了方便，因为不牵扯到妀变指示器的问题
波兰表示是一种既不须考虑优先关系、又不用括号的一种表示表达式的方法（前缀式）。
现在我们要介绍的刚好是另┅种波兰表示形式称为后缀式，即运算符在后
无循环有向图（DAG）
* DAG与抽象语法树基本上一样，对表达式中的每个子表达式DAG中都有一个結点。一个内部结点表示一个操作符它的孩子
* 两者所不同的是，在一个DAG中代表公共子表达式的结点具有多个父结点而在一棵抽象语法樹中公共子表达式被表示为重复
点击联系发帖人
