导图社区 编译原理
- 188
- 5
- 2
- 举报
编译原理
编译原理思维导图，编译原理指的是编译程序的构造原理和技术，源语言程序是高级语言，目标语言是低级语言，这样翻译的程序称为编译程序。本图有助于进行期末复习以及考研复习。
编辑于2023-07-22 23:16:20 江西
- Web开发实践
用于Web学习者和开发者使用，为Web前端开发的新手和有经验的开发者提供了一个清晰、全面的资源，帮助他们了解Web开发的核心技能和实践。感兴趣的小伙伴可以收藏一下~
- 大数据技术基础
随着TT的飞速发展，“大智物移云的时代已经来临。”大智物移云“分别指的是大数据、人工智能、物联网、移动互联、云计算技术。现在是一个计算无处不在、软件定义一切、网络包容万物、连接随处可及、宽带永无止境、智慧点亮未来时代。云技术是指实现云计算的一些技术，包括虚拟化、分布式计算、并行计算等；云计算除了技术之外更多的指一种新的IT服务模式，可以说目前提到较多的云计算30%是指技术，70%是指模式。大数据基础相关知识点，用于帮助同学们复习相关知识点。
- 面向对象程序设计Java
Java面向对象编程思维导图，主要是用于期末复习自学作参考，导图精简且有助于知识点的理解与记忆。
编译原理
社区模板帮助中心，点此进入>>
- Web开发实践
用于Web学习者和开发者使用，为Web前端开发的新手和有经验的开发者提供了一个清晰、全面的资源，帮助他们了解Web开发的核心技能和实践。感兴趣的小伙伴可以收藏一下~
- 大数据技术基础
随着TT的飞速发展，“大智物移云的时代已经来临。”大智物移云“分别指的是大数据、人工智能、物联网、移动互联、云计算技术。现在是一个计算无处不在、软件定义一切、网络包容万物、连接随处可及、宽带永无止境、智慧点亮未来时代。云技术是指实现云计算的一些技术，包括虚拟化、分布式计算、并行计算等；云计算除了技术之外更多的指一种新的IT服务模式，可以说目前提到较多的云计算30%是指技术，70%是指模式。大数据基础相关知识点，用于帮助同学们复习相关知识点。
- 面向对象程序设计Java
Java面向对象编程思维导图，主要是用于期末复习自学作参考，导图精简且有助于知识点的理解与记忆。
- 相似推荐
- 大纲
编译原理
第一讲 绪论
编译原理
编译原理指的是编译程序的构造原理和技术
第一节 编译程序
程序设计语言
计算机语言的分类
计算机语言
低级语言
机器语言
唯一能被计算机执行的语言
高级语言
如PASCAL,C等
执行高级语言或汇编语言步骤
高级语言程序或汇编语言转换成机器语言程序
转换方法
翻译或解释
运行机器语言程序得到的计算结果
翻译程序
翻译程序
源语言程序转换为目标语言程序，后者与前者逻辑上是等价的
编译程序
定义
源语言程序是高级语言，目标语言是低级语言，这样翻译的程序称为编译程序
汇编程序
特定计算机上的汇编语言的翻译程序
分类
交叉编译程序
源程序的编译和目标程序的执行不一定在同一种计算机上完成
诊断编译程序
专门用于帮助程序开发和调试程序的编译程序
优化编译程序
着重于提高目标代码的效率的编译程序
解释程序
定义
边解释边执行源程序本身
与编译程序的主要区别
不产生目标程序
第二节 编译过程的概述
词法分析
语法分析
语义分析
中间代码生成
中间代码优化
目标代码生成
第三节 编译程序的逻辑结构
中间传递物质
源程序
单词符号
词法单位
中间代码
中间代码
中间代码
目标代码
词法分析程序（扫描器）
任务
字符串扫描和分解，识别一个个语法单位（单词符号或词法符号）
删除无用的空白字符、回车符以及其它与输入介质相关的非实质性字符
删除注释
进行词法检查，报告发现的错误
单词符号的表示与分类
表示
二元组
单词类别
单词的值
分类
保留字
标识符
赋值符
数字
界符
词法分析阶段的工作中依循的是语言的词法规则（构词规则），描述词法规则的有效工具是正规式和有限自动机。它是一种线性分析
语法分析程序
任务
在语法分析的基础上，根据语言的语法规则，把单词符号重构成各类语法范畴（语法单位）
分析方法
完成这种分析，一般途径是由语法分析程序试着为其构造一棵完整的语法树
描述手段
遵循的是语言的语法规则。描述语法规则的有效工具是上下文无关法。它是一种层次结构分析
语义分析程序
任务
对语义分析程序所识别的各类语法成分，分析其含义，以保证源程序在语义上的正确性
语义的分类
静态语义
指在编译阶段能检查出的语义，典型静态语义包括声明和类型检查
动态语义
指只有在目标代码的运行阶段才能检查出的语义
分析方法
这一阶段依循的是语言的语义规则。通常使用语法制导翻译描述语法规则
中间代码生成
任务
按语言的语义规则把各类语法范畴翻译成中间代码
中间代码的定义
中间代码是一种独立于具体硬件的记号系统
中间代码形式
四元式
格式
算符，左操作数，右操作数，结果
三元式
间接三元式
逆波兰式
代码优化程序
任务
对前期产生的中间代码进行加工变换，以期在最后阶段能产生更加高效的目标代码
分类
优化分为局部优化和全局优化
优化所遵循的原则
程序等价变换规则的原则
目标代码生成程序
任务
把中间代码变换成变换成特定的机器上的低级语言代码
说明
它依赖于具体的计算机的硬件系统结构和指令系统
要求
一是使所生成的目标代码尽可能短
二是充分利用计算机可用资源的效率
目标代码形式
绝对地址的机器代码
这种代码可以立即执行
汇编语言形式的目标代码
这种代码还需要汇编程序汇编之后才能运行
模块结构的机器指令（可重定位的指令代码）
可以运行的绝对地址的机器指令代码程序
错误检查和处理程序
错误种类
语法错误
语法错误是指源程序中有不符合语法（或词法）规则的错误，它可以在词法分析或语法分析
语义错误
语义错误是指源程序中不符合语义规则的错误
信息表管理程序
最重要的是符号表
信息表结构
名字
信息
第四节 编译程序的组织
遍
定义
是对源程序的中间代码或源程序的中间结果从头到尾扫描一次，并作相关的加工处理，生成新的中间代码或目标程序
一遍和多遍
一遍
多遍
前端和后端
前端
主要与源程序有关但与目标机（运行编译程序的计算机称为宿主机，运行编译程序所产生目标代码的计算机称目标机）无关
后端
包括编译程序中与目标机有关的那部分
优点
取编译程序的前端，改写其后端以生成不同目标机的相同语言的编译程序
第五节 编译程序的生成
编译程序的设计的目标
目标程序小，执行速度快
编译程序小，执行速度快
诊断程序强，可靠性强
可移植性，可扩充性
编译器生成
合理的方法是用另一种语言来编写编译器，而使用该种语言的编译器早已存在
编译程序生成工具
LEX
自动产生词法分析器
词法规则说明--->LEX--->词法分析程序（C/C++程序）
输入
词法（正规表达式）
识别动作（C程序段）
输出
yylex()函数
YACC
自动产生语法分析器
语法规则说明--->YACC--->语法分析程序(C/C++程序）
输入
词法规则（产生式）
语义动作（C/C++程序段）
输出
yyparse()函数
构造一个编译程序必须掌握的内容
源语言
对被编译的语言要深刻理解其结构（语法）和含义（语义）
目标语言
假定目标语言是机器语言，那么，就必须搞清楚硬件的系统结构和操作系统的功能
编译方法
把语言程序翻译成另一种语言程序的方法
第二讲 文法和语言
文法和语言的形式定义
语言
是由句子组成的集合
研究语言
每个句子构成的规律
每个句子的含义
每个句子和使用者的关系
语言研究的三个方面
语法
表示构成语言句子的各个记号的组合规律
语义
语用
文法
上下文无关文法及其语法树
文法的定义
文法G
定义为四元组（VN,VT，P,S），其中
VN
非终结字符集
VT
终结字符集
P
产生式（规则）集合
非空有穷集。S至少在一条规则中作为左部出现。VN∩VT= φ， S∈VN ， V=VN∪VT，称为文法G的字母表（字汇表）
S
开始符号（起始符、识别字符）
S至少在一条规则中作为作为左部出现
习惯上只将产生式写出。并由如下约定
第一条产生式的左部都是开始符号
用尖括号括起的是非终结符，否则为终结符，或者大写字母表示非终结符，小写字母表示终结符
G可写成G[S],其中S是开始符号
推导的定义
直接推导 “=》”
直接推导 “”α→β是文法G的产生式，γ,δ∈V*，若有v,w满足：v=γαδ,w= γβδ,则说：v（应用规则α→β）直接产生w或说：w是v的直接推导，或说：w直接归约到v，记作 v w
推导
+
不包括0步推导
*
包括0步推导
文法的句型、句子的定义
句型
设G[S]是一文法，如果符号串从开始符号推导出来的，即S -*> x，则称x是文法G[S]的句型。
句子
x仅由终结符号组成（即S -* > x，且x∈VT*），则称x是G[S]的句子。
语言的定义
由文法G生成的语言记为L（G），它是文法G的全部句子的集合：L(G) = { x | S x，且x ∈VT*， 其中S为文法的开始符号 }
文法的等价
若L(G1) = L(G2)，则称文法G1和G2是等价的。
语言和文法的对应关系是一对多（1，：n）的关系
符号和符号串
字母表E
元素的非空有穷集合（符号集）
符号
字母表中的元素
符号串
定义
由字母表E的符号组成的任何有穷序列称为该字母表上的符号串
1.空符号串E（没有符号的符号串）是EE上的符号串
2.若x是E上的符号串，a是E元素，则,xa和ax是E上的符号串
3.y是E上的符号串，当且仅当它可以由1和2导出
注意
符号串中的符号排列是有顺序的
可以用字母表示符号串
如果z=xy是一符号串，那么
x是z的头（前缀），y是z的尾（后缀）
如果x非空，那么y是固有尾（真后缀）
如果y非空，那么x是固有头（真前缀）
符号串的运算
符号串的长度
符号串中符号的个数，符号串s的长度记为|s|.E的长度为0
连接
符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy
方幂
符号串x自身连接n次得到的符号串xx.....xx(n个x)表示为x^n
符号串集合
若集合A中一切元素都是某字母表E上的符号串，则称A为字母表E上的符号串集合
两个符号串集合A和B的乘积
定义
AB={xy|xEA且yB}
闭包
使用 * 表示上的所有有穷长的串（包括ε）的 集合。Σ*称为Σ的闭包。
正闭包
从*中除去ε得到的集合记为+ 。 Σ+称为Σ的正闭包。
Σ* = Σ0 ∪ Σ1 ∪ Σ2 … ∪ Σn ∪ … Σ+ = Σ1 ∪ Σ2 … ∪ Σn ∪ … Σ* = Σ0 ∪ Σ+ Σ+ = ΣΣ* = Σ* Σ Σ+ = Σ* -{ε}
文法和语言的形式主义
产生式（重写规则、规则或生成式），是形如α→β或α∷=β的（α，β）有序对，其中α是某字母表V的正闭包V+中的一个符号串，β是V*中的一个符号串。（α∈V+，β∈V*)
α称为产生式的左部（或规则的左部）
β称为产生式的右 部（或规则的右部）
文法的类型
通过对产生式施加不同的限制，Chomsky将文法分为四种类型（称为Chomsky 文法）
0型文法
对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)*
1型文法
对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε 除外
上下文有关文法
α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)
2型文法
对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)*
上下文无关文法
A→β(A在VN中，β在V*中，)
3型文法（也叫正规文法）
任一产生式α→β的形式都为
(1) A→aB 或 A→a，其中A∈VN ，B∈VN ，a∈VT (右线性文法)
非终结符在右边
(2) A→Ba 或 A→a，其中A∈VN ，B∈VN ，a∈VT (左线性文法)
非终结符在左边
文法与语言
0型文法产生的语言称为0型语言
1型文法或上下文有关文法产生的语言称为1型语言或上下文有关语言
2型文法或上下文无关文法产生的语言称为2型语言或上下文无关语言
3型文法或正则（正规）文法产生的语言称为3型语言或正则（正规）语言
上下文无关文法及其语法树
上下文无关文法有足够的能力描述现今程序设计语言的语法结构
算术表达式上下文无关文法表示
上下文无关文法及语法树
用于描述上下文无关文法的句型推导的直观方法
叶子节点
树中没有子孙的结点，从左到右读出推导树的叶子标记，所有的句型为推导树的结果。也把该推导树称为该句型的语法树
推导过程中施用产生式的顺序
最右（最左）推导
在推导的任何一步α->β,其中α、β是句型，都是对α中的最右（最左）非终结符进行替换
最右推导被称为规范推导
由规范推导所得的句型称为规范句型
二义文法
若一个文法存在某个句型对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的
产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的
判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件
二义文法改造成为无二义文法
句型的分析
句型分析
就是识别一个符号串是否为某文法的句型，是某个推导的构造过程
在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法
从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中最左符号，进而依次识别右边的一个符号
分析算法可分为
自上而下分析法（推导）
从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导
自下而上分析法（归约）
从输入符号串开始，逐步进行归约，直至归约到文法的开始符号
两种方法反映了两种不同的语法树的构造过程
一、自上而下的语法分析
二、自下而上的语法分析
三、句型分析有关问题
如何选择使用哪个产生式进行推导
如何识别可归约的串
四、短语、直接短语、句柄的定义
短语
文法 G[S]， αβδ是G的一个句型，如果：S -*-> αAδ且 A -+-> β 则称β是句型αβδ相对于非终结符A的 短语。
直接短语
若有 A β则称β是句型αβδ相对于规则A→β的直接短语（或简单短语）
一个句型的最左直接短语称为该句型的句柄。
句型、短语和句柄
句型
每一句型都有一棵语法树，每个语法树的叶组成一句型
短语
每棵子树的叶组成短语，每棵直接子树的叶组成直接短语，最左直接子树的叶组成句柄
五、有关文法实用中的一些说明
有关文法的实用限制
上下文无关文法中的E规则
六、有关文法的实用限制
文法中不得含有有害规则和多余规则
有害规则
形如U-U的产生式。会引起文法的二义性
多余规则
指文法中任何句子的推导都不会用到的规则
1）文法中某些非终结符不在任何规则的右部出现，该非终结字符称为不可到达
2）文法中某些非终结字符，由它不能推出终结字符串来，称为不可终止
对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件
A必须在某句型中出现
必须能从A推出终结符号串t来
七、化简文法
上下文无关文法中的E规则
具有形式A→ε的规则称为ε规则，其中A∈VN
某些著作和讲义中限制这种规则的出现。因为ε规则会使有关文法的一些讨论和证明变得复杂
两种定义的唯一差别是ε句子在不在语言中
如果语言L有一个有穷的描述，则LU{ε}也同样有一个有穷描述
并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则LU{ε}和L-{ε}分别是上下文有关语言、上下文无关语言和正规语言
定理3.1
文法G，P中的每一个产生式的形式均为A→α，其中A∈VN，α∈(VN ∪VT)*(即α可能为ε)，则L(G)也能由这样一种文法产生：每一个产生式或者为A→β形式，其中A∈VN，β ∈(VN ∪VT)+(即β≠ε)，或者 S→ε且 S不出现在任何产生式右边。
定理3.2
G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。 若G为上下文无关文法或正规文法，类似结论成立。
上下文无关文法的句型分析
有关文法中的一些说明
第三讲 词法分析
词法分析程序设计
词法分析
逐个读入源程序字符并按照构词规则切分成一系列单词
单词
单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量符等
词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用
词法分析程序
源程序
词法分析程序
语法分析程序
主要任务
读源程序，产生单词符号
其他任务
滤掉空格，跳过注释、换行符
追踪换行标志，复制出错程序
宏扩展
单词符号
单词符号可分为下列五种
基本字（关键字）
begin,end,if,while等
标识符
各种名称，如常量名，变量名，过程名等
常数（量）
25，3.1415，TURE，“ABC"
运算符
如+,-,*,/,<,<=等
界符
逗号，分号，括号
输出表示
单词类别
单词自身的值
词法分析工作独立的原因
简化设计
改进编译效率
增加编译系统可移植性
单词描述工具
正规文法
文法G=（VN,VT,P,S），P中每一产生式形式都为
A->aB或A->a(右线性文法）
A->Ba或A->a(左线性文法)
其中A∈VN,B∈VN,a∈VT
几类单词的描述
标识符
<标识符>->I|I<字母数字>
<字母数字>->I|d|I<字母数字>|d<字母数字>
无符号整数
<无符号整数>->d|d<无符号整数>
运算符
<运算符>->+|-|*|/|=|.....
界符
<界符>->,|;|(|)|....
其中I表示字母;d表示数字
无符号实数
<无符号实数>->d<余留无符号数>|.<十进小数>|e<指数部分
<余留无符号数>->d<余留无符号数>|.<十进小数>|e<指数部分>|ε
<十进小数>->d<余留十进小数>
<余留十进小数>->e<指数部分>|d<余留十进小数>|ε
<指数部分>->d<余留整指数>|s<整指数>
<整指数>->d<余留整指数>
<余留整指数>->d<余留整指数>|ε
其中s表示正或负号
正规式
定义（正规式和它所表示的正规集）
正规式等价
若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2
正规式的运算律
设r,s,t为正规式，正规式服从代数运算律有
"或"服从交换律
"或"服从可结合律
"连接"的可结合律
分配律
E是"连接"的恒等元素
“或”的抽取律
正规文法和正规式的等价变换
对E（字母表）上的正规式r，存在一个G=（VN,VT,P,S）使得L（G）=L（r)
VT=E（字母表),S属于VN，生成正规产生式S->r
对形如A->xy的正规产生式:A->xB B->y (B属于VN）
对形如A->x*y的正规产生式:A->xA A->y
对形如A->x|y的正规产生式: A->x A->y
不断应用上述规则做变换，直到每个产生式最多含有一个终结符
将正规文法转换成正规式
有穷自动机
确定的有穷自动机(DFA)
DFA的定义
一个确定的有穷自动机（DFA）M是一个五元组:M=（K,E,f,S,Z)
K
K是一个有穷集，状态集，它的每个元素称为一个状态
E
E是一个有穷字母表，它的每个元素称为一个输入符号，所以也称E为输入符号表
f
f是转换函数，是在KXE->K上的映射
S属于K是唯一的一个初态
ZcK是一个终态集，终态也称为可接受状态或结束状态
DFA的状态图
DFA的矩阵表示
状态
字符
终态用1表示
非终态旁边用0表示
∑* 上的符号串 t 在 M 上运行
∑* 上的符号串 t 被 M 接受
确定的有穷自动机(DFA)接受的语言
DFA M=（K,E,f,S,Z）所能接受的符号串的全体记为L（M）
L(M) = { x | f(S, x) Z , x }
结论
∑上一个字符串集 V属于∑* 是正规的，当且仅当，存在一个 ∑上的确定有穷自动机 M，使得 V=L(M)。
不确定有穷自动机（NFA）
定义
N=（K，E，f,S,Z)
K
K为状态的有穷非空集
E
有穷输入字母表
f为映射函数
f: Kx∑* → 2K
Sc-K是初始状态集，Z c-K为终止状态集。
状态图表示
矩阵表示
注意.表示空
∑*上的符号串t在NFA N上运行。
∑*上的符号串t被NFA N接受（识别）
具有 E 转移的不确定的有穷自动机 NFA f为 KX（EU{E}）到2K的的映射。
对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA Ｍ ，使得L(M)=L(N)。
NFA->DFA的转换
DFA是NFA的特例.对每个DFA M一定存在一个NFA Ｍ' ，使得 L(M)=L(M ')。
对每个NFA M存在着与之等价的DFA M ' 。与某一NFA等价的DFA不唯一。
1
定义对状态集合I的几个有关运算
1 状态集合 I 的 -闭包，表示为 E-closure(I)，定义为一状态集，是状态集 I 中的任何状态 R 经任意条 弧而能到达的状态的集合。状态集合I的任何状态 R 都属于 E-closure(I)。
2 状态集合 I 的 a 弧转换，表示为 move(I,a) 定义为状态集合 J，其中 J 是所有那些可从 I 的某一状态经过一条 a 弧而到达的状态的全体。
3 定义：Ia = -closure(J)，其中：J= move(I,a)
2
NFA到DFA的等价变换算法
DFA的化简
最小状态DFA
没有多余状态（死状态、不可达状态)
没有两个状态是互相等价（不可区别)
两个状态s和t等价：满足
一致性
同时终态或同是非终态
蔓延性
从s出发读入某个a(a属于E)和从t出发读入某个a到达的状态等价
对于一个DFA M =（K,∑,f, k0,kt)，存在一个最小状态DFA M’ =（K’,∑,f’, k0’,,kt’)，使L(M’)=L(M).
算法核心
把M的状态集K分成不相交的子集
结论
接受L的最小状态有穷自动机不计同构是唯一的
正规式和有穷自动机的等价性
对于∑上的NFA M，可以构造一个∑上的正规式R，使得L（R）=L(M)
第一步
在M状态转换图上加进两个结点，一个为x结点，一个为y结点。从x结点用E弧连接到M的所有初态结点，从M的所有终态结点用E弧连接到y结点。形成一个与M等价的M‘，M’只有一个初态x和一个终态y
第二步
逐步消去M‘中所有结点，直至只剩下x和y
最后x和y结点间的弧上的标记为所求的正规式R
对于∑上的一个正规式R，可以构造一个∑上的NFA M,使得L（M）=L（R）
(1) R=空，任一具有空终态集的NFA M
(2)R=E，NFA M=({k0},E,f,k0,{k0}); f(k0,a)对于所有a属于字母表都没定义
(3) R=a,NFA M=({k0,,k1},∑,f,k0.{k1}): f(k0,a) = k1
(4) R =R1 | R2, 分别将步骤（1）（2）（3）应用到R1,R2 产生M1=(K1,∑1,f1,k1,F1), M2=(K2,∑2,f2,k2,F2),其中K1,K2不相交. 则，NFA M= (K1K2{k0},∑,f,k0,F)，k0是新增加的状态符号: ∑ = ∑1 ∑2； f=f1f2{ f(k0,ε)= {k1,k2} }； F=F1 F2
正规文法和有穷自动机间的转换
右线性文法
1.采用下面的规则从正规文法G=（VT,VN,S,P)直接构造一个有穷自动机NFA M=（E,K,f,k0,Z),使得：L(M)=L(G)
采用下面的规则将一个有穷自动机NFA M转换成正规文法G，使得L(G)=L(M)
词法分析程序的自动构造工具
把正规式转换为一个NFA进而转换为相应的DFA，由此构造出词法分析程序。
正规式和有穷自动机等价性
正规文法和有穷自动机之间的转换
词法分析程序的自动构造工具
第四讲 自顶向下语法分析
确定的自顶向下分析思想
状况1
每个产生式的右部都由终结符号开始
如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始
状况2
每个产生式的右部不全是由终结符号开始
如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始
文法中无空产生式
定义
定义：一个上下文无关文法是LL(1)文法的充要条件是： 对每个非终结符A的两个不同产生式A→α和A→β，满足 SELECT(A→α)∩SELECT(A→β)=Φ 其中α,β不能同时 -*->ε
含义
第一个L表示：自顶向下分析是从左向右扫描输入串。
第二个L表示：分析过程中将用最左推导
1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导)
类似也可以有LL（K）文法：须向前查看K个符号才可以确定选用哪个产生式
定义
给定上下文无关文法的产生式 A-a, A属于VN，a属于V*，若α -/*-> ε，则 SELECT(A→α)=FIRST(α) 如果α -*-> ε，则SELECT(A→α)=FIRST(α)∪FOLLOW(A)
LL(1)文法的判别
求出能推出ε的非终结符
计算FIRST集
计算FOLLOW集
1.对于文法的开始符号S，置#于FOLLOW（S）中
2.若A->αBβ是一个产生式，则把FIRST(β)-{ ε}加至FOLLOW(B)中
3.若A->αB是一个产生式，或A->αBβ是一个产生式，而β (即FIRST(β)），则把FOLLOW（A）， 加至FOLLOW（B）中．
计算SELECT集
如果推出非空直接是一个FIRST集
如何过是一个空，直接是FOLLOW集并上空
判别是否是LL（1）文法
某些非LL（1）文法到LL（1）文法的等价变换
提取左公共因子
A→αβ|αγ导致SELECT(A→αβ)∩ SELECT(A→αγ)≠Φ，因此是非LL(1)文法。
消除左递归
直接左递归
消除直接左递归
把直接左递归改写为右递归
间接左递归
消除文法中一切左递归的算法
充分条件
无回路
无空产生式
不确定的自顶向下分析思想
由于相同的左部的产生式的右部FIRST集交集不为空引起回溯
由于相同的非终结符的右部能-*->E且该非终结符FOLLOW集含有其右部FIRST集的元素
由于文法含有左递归而引起回溯
确定的自顶向下分析方法
递归子程序法
实现思想
对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时，能够按LL（1）形式可唯一确定选择某个候选进行推导
限制
对文法要求高，必须满足LL（1）文法；由于递归调用多，速度慢，占用空间多
预测分析表的构造
表达式文法
构造过程
构造预测分析表
运行
判断文法是否为LL（1）文法a、消除左递归
结论
不一定每个文法的左公共因子都能在有限的步骤内替换成无左公因子的文法，文法中不含左公共因子只是LL（1）文法的必要条件
一个文法提取了左公共因子后，只解决了相同左部产生式右部FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL（1）文法，否则还需要LL（1）文法的判别方式进行判断才能确定是否为LL(1)文法
不确定的自顶向下分析思想
确定的自顶向下分析思想
第5讲 自底向上优先分析法
自底向上优先分析概述
自底向上分析方法，也称移进-归约分析法
实现思想
对输入符号串自左向右进行扫描，并将输入符逐个移入一个后金先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产生式的右部），就用该产生式的左部非终结符代替相应的右部文法符号串，这称为归约
重复这一过程直到归约到栈中只剩文法的开始符号时，则为分析成功，也就是确认输入串是文法的句子
算法应考虑的问题
算法是否能够终止
算法是否快速
算法是否能够处理所有情况
在每一步中如何选择字串进行归约
自下而上语法分析策略：移进-归约分析
移进就是将一个终结符推进栈
归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈
移进-归约过程是自顶向下最右推导的逆过程（规范归约，即最左归约）
优先分析法
简单优先分析法
对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范规约
按照文法符号（包括终结符和非终结符）的优先关系确定句柄
优先关系
X=Y 文法G中存在产生式A→...XY... X<Y 文法G中存在产生式A→...XB...， 且B -+-> Y... X>Y 文法G中存在产生式A→...BD...， 且B -+-> - ...X,D -*-> Y...
定义
满足以下条件的文法是简单优先文法
在文法符号集V中，任意两个符号之间只有一种优先关系成立
在文法中任意两个产生式没有相同的右部
不含空产生式
算符优先文法的定义
在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法（OPG）
结论
算符优先文法是无二义的
算符优先关系表的构造
由定义直接构造
由关系图法构造算符优先关系表
简单优先分析概述
算符优先分析
两个概念
FIRSTVT(B)={b|B b…或B Cb...} 对于非终结符B，其往下推导所可能出现的首个算符（终结符）
LASTVT(B)={a|B … a或B ... aC} 对于非终结符B，其往下推导所可能出现的最后一个算符（终结符）
算符优先分析法
只规定算符（终结符）之间的优先关系。找到句柄（最左素短语）就归约，并不考虑归约到哪个非终结符名，不是规范规约
某些文法具有“算符”特性
表达式运算符（优先级、结合性）
人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性
只考虑算符之间的优先关系来确定句柄
如何确定算符优先关系
i的优先级最高
I优先级次于i，右结合
*和/优先级次之，左结合
+和-优先级最低，左结合
括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号
#的优先性低于与其相邻的算符
算符文法的定义
定义
如果不含空产生式的上下文无关文法G中没有形如U->...VM...的产生式，其中V,M属于VN则称G为算符文法（OG)
性质1
在算符文法中任何句型都不包含两个相邻的非终结符（数学归纳法）
性质2
如Vx或xV出现在算符文法的句型a中，其中V属于VN，x属于VT，则a中任何含x的短语必含有V（反证法)
如何计算算符优先关系
'='关系
直接看产生式的右部，若出现了A->...ab..或A->..aBb,则a=b
‘<'关系
求出每个非终结符B的FIRSTVT（B）
若A->..aB..,则任意b属于FIRSTVT（B)，a<b
'>'关系
求出每个非终结符B的LASTVT(B)
若A->...Bb..,则a属于LASTVT(B),a>b
算符优先分析算法
规约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了但非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的
为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念
算符优先分析句型的性质
算符文法的任一句型有如下形式： #N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄，则有 ai-1<ai=ai+1=...= aj-1 = aj> aj+1
对于算符优先文法，如果aNb(或ab)出现在句型 r中 若a<b，则在r中必含有b而不含a的短语存在 若a>b，则在r中必含有a而不含b的短语存在 若a=b，则在r中含有a的短语必含有b，
最左素短语
定义
文法G[S]的句型的素短语是一个短语，他至少包含一个终结符，且除自身外不再包含其他素短语
处于句型最左边的素短语为最左素短语
算符优先分析法的局限性
一般语言的文法很难满足算符优先文法的条件
很难避免把错误的句子得到正确的归约
算符优先分析法仅适用于·表达式的语法分析
第六讲 LR分析法
LR分析概述
LR分析器工作过程示意图
状态栈、符号栈、SP、总控程序，输出 输入串，LR分析表（ACTION表，GOTO表）
可归前缀与活前缀
规范句型的这种前部分符号串称为可归前缀，我们把形成可归前缀之前包括可归前缀的所有规范句型的前缀都称为活前缀
活前缀
定义
S-*->aAw->abw是文法中的一个规范推导，如果符号串y是ab的前缀，则称y是G的一个活前缀
LR分析需要构造识别活前缀的有穷自动机
我们可以把文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态
如何构造识别活前缀有限自动机
已经有了活前缀如何构造有限自动机
活前缀及其可归前缀的一般计算方法
项目
在每个产生式的右部适当位置添加一个圆点构成项目
项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分
由文法的产生式直接构造识别活前缀和可归前缀的有限自动机
有限自动机NFA的每一个状态由一个项目构成
根据圆点所在位置和圆点后是终结符还是非终结符把项目分为有以下几种
移进项目
待约项目
归约项目
接受项目
构造识别一个文法活前缀的DFA项目集（状态）的全体·称为这个文法的LR(0)项目集规范族
NFA确定化DFA的工作量较大，我们考虑直接构造出项目集作为DFA状态，就可直接构造DFA
通过I是文法G‘的一个项目集，定义和构造I的闭包CLOSURE(I)如下
I的项目都在CLOSURE（I）中
若A->a.Bb属于CLOSURE(I)，则每一形如B->.y的项目也属于CLOSURE(I)
重复b)直到CLOSURE（I)不再扩大
通过闭包函数（CLOSURE)来求DFA一个状态的项目集
构造识别活前缀的NFA
把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态
确定初态、句柄识别态、句子识别态
确定状态间的转换关系
若项目i为 X → X1X2...Xi-1 • Xi...Xn 项目j为 X → X1X2...Xi-1 Xi • Xi+1...Xn 则从状态i到状态j连一条标记为Xi的箭弧
总结
构造识别活前缀DFA的三种方法
根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造NFA再确定化为DFA
求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA
使用闭包函数（CLOSURE）和转向函数(GOTO(I,X)构造文法G'的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA
LR(0)分析
LR(0)项目集规范族的项目类型分为如下四种
移进项目
归约项目
待约项目
接受项目
一个·项目集可能包含多种项目
移进和归约项目同时存在。移进-归约冲突
归约和归约项目同时存在 归约-归约冲突
LR(0)文法
若其LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法
LR(0)分析表的构造
LR(0)分析表相当于识别活前缀的有限自动机DFA的状态转换矩阵
LR(0)分析表的构造算法
LR(0)分析器的工作过程
构造文法G[E]的LR(0)分析表
第一步
对文法G进行拓广，得其拓广文法G‘[S']
第二步
对拓广文法G'[S'],构造其LR(0)项目集规范簇I
第三步
根据LR(0)项目集规范簇，构造出LR(0)分析表
ij
大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，及其规范族中会含有冲突的项目集（状态）
若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是SLR(1)文法，所构造的分析表为SLR(1)分析表，使用SLR(1)分析表的分析器为SLR(1)分析器
“改进的”SLR(1)分析
对所有非终结符都求出其FOLLOW集合，这样只有归约项目仅对面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取该产生式归约的动作
LR(1)分析
LR(1)项目集族的构造
针对初始项目[S'->.S,#]求闭包
再用转换函数逐步求出整个文法的LR(1)项目集族
LR(1)分析表的构造
1) 若项目[A→ • a,b]属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj
2) 若项目[A→ • ,a]属于Ik ，则置ACTION[k,a] = rj ，j为产生式在文法G‘中的编号
若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号
4) 若项目[S‘→S • ,#]属于Ik ，则置ACTION[k,#] = acc
5) 其它填上“报错标志”
LR(1)项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长
LALR(1)分析
对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。
合并同心集的几点说明
同心集合并后心仍相同，只是超前搜索符集合各同心集超前搜索符的和集
合并同心集后转换函数自动合并
LR(1)文法合并同心集后也只可能出现归约-归约冲突，而而没有移进-归约冲突
合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的1
二义性文法在LR分析中的应用
对于某些二义性文法，可以人为地给出优先性和结合性的规定，从而可以构造出比相应非二义性文法更优越的LR分析器
LR(0),SLR(1),LR(1),LR(k),LALR(1)
LR(0)
SLR(1)：生成的LR(0)项目集如有冲突，则根据非终结符的FOLLOW集决定
LR(1),LR(k)
项目由心与向前搜索符组成，搜索符长度为1或k
LALR(1):
对LR(1)项目集规范族合并同心集
结论
一个文法使LR(0)文法，一定也是SLR(1)文法，也是LR(1)文法。反之不一定成立
LR(1)分析法强于LALR(1)分析法，LALR(1)分析法强于SLR(1)分析法，SLR(1)分析法强于LR(0)分析法
LALR(1)文法一定是LR(1)文法，反之不一定成立
任何一个二义性文法都不是LR类文法，也不是一个算符优先文法或LL(k)文法
第七讲 语法制导翻译和中间代码
属性文法
属性文法(attribute grammar)是一个三元组:A=(G,V,F)
G
是一个上下文无关文法
V
有穷的属性集，每个属性与文法的一个终结符或非终结符相连
F
关于属性的属性断言或谓语集，每个断言与一个产生式左端或右端的终结符或非终结符相联的属性
综合属性
在分析树中，如果一个结点的某一个属性由其子节点的属性确定，则称这种属性为该结点的综合属性
产生副作用的语义规则
如打印一个值、向符号表中插入信息或更新一个全程变量等
属性文法
语法规则函数都不具有副作用的语法制导定义称为属性文法
在语法制导定义中，一条语义规则完成一个计算属性值的动作。dight是终结符，只使用综合属性，且其属性值由词法分析器提供，通常不要计算属性值
如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S属性定义，通常采用自底向上方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个节点的属性值
继承属性
一个结点的继承属性值是由此结点的父节点和/或兄弟节点的某些属性来决定的
语法制导翻译概论
语法制导翻译概论
在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作)进行翻译的办法称作语法制导翻译
中间代码
中间代码常见形式
逆波兰记号
将运算对象写在前面，把运算符号写在后面
计算方法
自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈
逆波兰式的扩充用途
复杂性
压栈的可能是地址，不是值:栈中不一定产生结果
三元式（树形表示）
格式
间接三元式
三元式表
执行表
四元式
格式
算符
第一运算对象
第二运算对象
结果
特点
类似于三地址指令
利于优化代码生成
一些语句翻译
简单赋值语句的翻译
四元式形式
t:=arg1 op arg2
语义属性
id.name,E.place（值E的位置）
函数
lookuo(id.name)
返回指向id的指针
输出四元式
emit(t:=arg1 op arg2)
过程
生成临时变量
newtemp
布尔表达式到四元式的翻译
布尔表达式的作用
作为控制语句的条件表达式
用于逻辑计值
布尔表达式的文法
E→E∧E │ E∨E │ ～E │ (E) │ i rop i │ i
布尔表达式的计值方法
逐步计算
优化计算
作为逻辑计值的布尔表达式的翻译
作为控制条件的布尔表达式的解释
E的真出口，用E.TC表示
E的假出口，用E.FC表示
为了翻译布尔表达式，我们引入下面三种四元式
（ jnz ，A， ， p）
若A为真，则转到第P号四元式去执行
（ jrop，A，B， p）
若A rop B为真，则转到第p号四元式去执行
（ j ， ， ， p）
无条件转到第p号四元式去执行
由于在分析过程中，一个布尔表达式的真/假出口往往不能在产生四元式的同时就填上。所以我们常采用“拉链-回填”的方式来处理。为此，对布尔表达式E我们赋予两个属性（语义值）
E-TC
存放E的真链链头，该链上的所有四元式均是需要真出口
E-FC
存放E的假链链头，该链上所有四元式均是需要回填假出口的四元式的·地址（编号）
0
表示链尾
回填过程：BackPatch(p,t)
功能
用四元式编号t填入首指针为p的链中的全部四元式中的第四个元
引入以下属性和子程序
E.TC（真链头）；E.FC（假链头）
NXQ：全局变量，其值等于即将产生而又没产生的四元式编号，初始值为100，每调用一次四元式生成子程序，其值自动加1
merge(p1,p2)
将p1和p2两条链合并，返回合并后的链头
backpatch(p,t)
用四元式编号t去填p链所有四元式的第四个元
布尔表达式的语义子程序如下
（1）E->i
{ E.TC = NXQ; E.FC = NXQ + 1; Gen(jnz, Lookup(i.name), , 0); Gen(j, , ,0); }
(2) E → i1 rop i2
{ E.TC = NXQ; E.FC = NXQ + 1; Gen( jrop, Lookup(i1.name), Lookup(i2.name) , 0 ) ; Gen( j, , ,0 ); }
(3) E → (E1)
{ E.TC = E1.TC ; E.FC = E1.FC ; }
(4) E → ～E1
{ E.TC = E1.FC ; E.FC = E1.TC ; }
(5) E∧ → E1 ∧
{ BackPatch( E1.TC, NXQ ) ; E ∧.FC = E1.FC ; }
(6) E → E∧E2
{ E .TC = E2.TC ; E.FC = Merge( E∧.FC, E2.FC ) }
(7) E∨ → E1∨
{ BackPatch( E1.FC, NXQ ) ; E∨.TC = E1.TC ;
(8) E → E∨ E2
{ E .FC = E2.FC ; E.TC = Merge( E∨.TC, E2.TC ) }
翻译
编译程序
编译程序使用说明标识符的过程或函数的静态层次
循环优化
代码外提
强度削弱
删除归纳变量
循环合并
循环展开
LR(0)项目集规范族
LR(0)项目
对应一个NFA状态
LR(0)项目集
对应一个DFA状态
LR(0)项目集规范族
对应所有的DFA状态
LALR（1）
一定不是二义性文法
文法的判定
有个结论是合并同心集不会产生新的移进-归约冲突，但可能会产生新的归约-归约冲突，如果没有产生冲突，那就是LALR文法，反之不是
文法关系
自上而下分析法
LL(1)
自下而上分析法
LR(1)
LALR(1)
SLR(1)
LR(0)
规范句型
最右推导出的句型
规范推导
最右推导
浮动主题
题目新增
试卷一
信息向量|内情向量
数组的类型、维数、各维的上下界，以及数组首地址