电子科技大学 编译原理期末女娲补天

算是考完了 真难啊。。 学弟学妹们看到了可以参考下 内有真题一套 稍有些混乱的复习笔记一堆 不建议全部相信 因为本人复习得比较拉胯。。
参考下是ok的 语雀链接食用体验更佳 戳这里～

考完来简单总结下
题目与往年差不太多

• 语法树
• FIRSTVT表 LASTVT集
• FIRST集 FOLLOW集 构造预测分析表
• 中间代码分析
• SLR(1)分析法
• 语义子程序的翻译

经验总结：ppt直接看根本看不懂 顺序也比较奇怪 建议先通读一遍ppt 有不懂的先跳过 然后重要知识点多百度一下 可以去bilibili听一些up主讲一下

我晕 图片因为是语雀导出的 所以链接有点问题 懒得改了 咱就是说 建议看语雀上的内容哈 戳这里～

语言部分

1-变量及其属性

变量是对一个(或若干个)存储单元的抽象，赋值语句则是修改存储单元内容的抽象。

属性：

• 作用域：可以访问该变量的程序范围
• 生存期：一个储存区绑定于一个变量的时间区间
• 值：变量对应的存储单元的内容
• 类型：与变量相关联的值的类, 以及对这些值进行的操作的说明。

1-虚拟机的概念


1-程序单元 & 单元实例


• 活动记录：执行单元所需要的信息,以及该单元的局部变量所绑定的数据对象的存储区

2-数据类型的作用

简答题~

• 实现了数据抽象
• 使程序员从机器的具体特征中解脱出来
• 提高了编程效率

2-数据聚合的六种方式

填空题~

2-类型检查及分类

• 对数据对象的类型和使用的操作是否匹配的一致性检查称为类型检查
  • 静态检查
  • 动态检查


2-抽象数据类型的条件

• 在实现该类型的程序单元中,建立与表示有关的基本操作;
• 对使用该类型的程序单元来说,该类型的表示是隐蔽的。


2-何为类型等价


3-语句级控制结构——顺序、选择、重复

• 顺序


• 选择


• 重复


• 语句级控制结构分析


3-单元级控制结构

规定程序单元之间控制流程的机制

3-副作用、别名

• 非局部变量
  一个程序单元可以引用未被本单元说明而被其他单元说明的变量

int a;
int b = 666;
a = 666; —— a为非局部变量 可以这么理解？

• 非局部变量绑定于其他的程序单元（定义该非局部变量的程序单元）的活动记录中的数据对象；
• 或非局部变量绑定全局数据区中的数据对象称为非局部环境

哪俩属于别名？

4-语言的定义

程序设计语言是用来描述计算机所执行的算法的形式表示；

4-语法描述的基本用途


4-文法的定义

用英文大写字母表示非终结符；小写字母表示终结符；希腊小写字母表示串

4-文法的分类

• 0型文法 产生式形如α→b
  • α中至少含一个非终结符
• 1型文法 │α│<=│β│（S→e例外）或产生式形如αAβ→αwβ，w∈V+ (上下文有关文法)
  • α中终结符个数小于β
• 2型文法 产生式形如A→α (上下文无关文法)
  • 产生式右端均为终结符
    • S—>aB|bA
    • A—>aS|bAA|a
    • B—>bS|aBB|b
• 3型文法 产生式形如A→α或A→αB (正则文法,右线性文法) α∈VT*
  • 在2型的基础上要求右端最多有一个非终结符，且位于最右端
    • S—>bA
    • A—>(B|a
    • B—>aA


4-文法产生的语言

推导（与归约）


句型 & 句子


文法产生的语言L(G)


• 例一


• 例二


短语、句柄、素短语

• 短语——叶子节点
• 句柄——最左直接短语


语法树（推导树）

字面意思~

4-例题：推导、句型、句子、短语、句柄

• 例一


• 例二


• 例三


编译部分

5-编译等概念

翻译：将一种语言编写的程序转换成完全等效的另一种语言编写的程序的过程。在计算机中，翻译由一 个程序来实现，称为翻译程序

**宿主语言：**编写编译程序的语言。运行翻译程序的机称为宿主机

静态语言需要先进行编译，才能执行代码
动态语言则是可以边解释 边执行代码

5-编译步骤

• 词法分析
  • 输入字符串 根据词法规则识别出单词符号
• 语法分析
  • 根据语法规则 将单词符号构成各类语法单位 并进行语法检查
• 语义分析
  • 根据语义规则，进行初步编译
• 优化
  • 对中间代码进行等价变换 以使代码更有效
• 目标代码生成
  • 生成机器语言程序或汇编语言程序
• 符号表管理
  • 完成符号表的建立、查找、更新
• 出错处理


6-词法分析器的功能

• 扫描源程序的字符串,按照词法规则,识别出单词符号作为输出

• 对识别过程中发现的词法错误输出有关的错误信息。

• 词法分析器是子程序

  • 
  • 

6-单词符号的分类

• 标识符
• 基本字
• 常数
• 运算符
• 界符

单词类别的划分（编码的方式）


6-状态转换图

简称转换图,是一张有限方向图，是设计词法分析器的有效工具；它由如下成分构成：
1.结点(node)：圆圈表示结点，代表状态（state）
2.有向边（弧）:连接结点，边上的标记字符表示该状态下可能接收或识别的字符；

例子


第六章 ppt p21


重点——语法分析

语法分析分为两种
第七章——自上而下(自顶而下)
第八章——自下而上(自底而上)

7-回溯分析法


7-公共左因子

这个例子是啥意思？?

提取公共左因子
先提取左公因子 再消除左递归也ok


7-左递归


消除左递归

• 公式


• 例题


间接左递归的消除


复杂的间接左递归消除


• 这个产生的语言是怎么出来得？


7-ε产生式


提取公共左因子、消除左递归例题

对于文法G=（{a,b,c,d,},{S,A},S,P）;
其中P为:
S → Aa|Ac|bc
A → Ad|Sbc|d
请先提取文法G的工共左因子，再消除左递归

7-递归下降分析法

这个不在老师画的重点中 要考察麽？

7-预测分析法

7-预测分析表的构建方法

预测分析表
对于LL(1)文法来说，在使用最左推导时，非终结符号的每一步推导使用的产生式是确定的，不用进行试探和回溯。
求预测分析表 要先求出来FIRST表
FIRST(α)中的每一个终结符号a，表格项M(A,a)=A→α
如果是非空串产生式A→α，求FIRST(α)，对于FIRST(α)中的每一个终结符号a，M(A,a)=A→α
如果是空串产生式A→α，求FOLLOW(A)，对于FOLLOW(A)中的每一个终结符号b，M(A,b)=A→ε


预测分析方法


例题


7-FIRST集

大白话：

• 非空串产生式

1. 在所要求的字符产生式的右边的第一位寻找终结符，假设该字符产生式集的第一位就是终结符，那么该终结符就是所要求的first集；
2. 假设产生式的右边第一位是非终结符，那么继续寻找该非终结符的first集，直至寻找到一个终结符，即是起初所要求字符的first集；
   
   
   
   
   
   
   

7-FOLLOW集

https://www.jianshu.com/p/210fda081c76

• 如果存在产生式A -> αBβ ，那么 FIRST(β)中所有非ε的符号都在FOLLOW(B)中；
  • 
• 如果存在产生式A -> αB，或者A -> αBβ 且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都加入到FOLLOW(B)中
  • （$=>#）

follow集的意义是寻找所要求字符的下一个字符可能产生的集合，所以寻找follow集应从产生式的右边进行寻找。

大白话求FOLLOW集

1. 在产生式的右边找到相应的字符（从左到右第一个非终结符），假设紧跟其后的是一个终结符，那么该终结符就是所要求的follow集；
2. 假设跟在其后的是一个非终结符，那么需要判断该非终结符是否可以为空：
3. 假如可以为空，那么将该产生式的左边的follow集加入到寻找集合当中，
   1. 因为假如该非终结符为空的话，那么需要寻找产生这个非终结符的产生式左边的非终结符，因为产生式左边的非终结符的follow集就有可能是该非终结符的follow集；
4. 假如不为空，那么寻找该非终结符的first集，并将结果加入到搜索集合当中。
5. 直到不再有非终结符产生，找到所有的终结符，计算结束。

找L的Follow集，先从式子右边找到L——


求follow集的算法

• 默认将右端结束标记 # 放到 FOLLOW(S) 中
• 按照下面两个规则不断迭代，直到所有的FOLLOW集合都不再增长为止
  • 如果存在产生式A -> *B)，那么FOLLOW(B) = { ), # }；——对应上面大白话的1
    • 
  • 如果存在产生式A -> *BC ，那么FOLLOW(B) = FIRST© - ε；——对应上面的2.b
    • 
    • 
  • 如果存在产生式A -> *B，或者A -> xxBC 且FIRST©包含ε，那么FOLLOW(B)=FOLLOW(A)——对应上面的2.a.i

求预测分析表过程中的应用

• 空串产生式
  • 
  • 

LL(1)文法的判定

每一个推导式经过推导其对应的SELECT集的交集为空，其为LL（1）文法。

7-求first follow 预测分析表例题

p55之后

8-自下而上的语法分析——规约


算符优先文法的判定

上下文无关文法G,没有形如P→ε或P→. . .QR. . .的产生式,则称G为算符文法。
若算符文法G的任何终结符a,b之间的优先关系至多有=、>、<中的一个, 则G为算符优先文法

最左素短语分析法——基于算符优先表的下堆栈分析过程


-P21才到优先分析表 中间是一些规约的方法


8-FIRSTVT集


8-LASTVT集


8-*算符优先（分析）表的构造


规范句型的活前缀

最右推导就是规范推导，因此最右推导过程中产生的句型都是规范句型
活前缀：规范句型的不含句柄之后任何符号的一个前缀。
如：aAcde => aAbcde，句柄为A→Ab， 活前缀为：ε，a， aA， aAb

构造识别所有活前缀的转换图——识别全部活前缀的DFA

• 构造分算符优先表的准备工作~
• 推导的过程中注意——是否有重复的项目
  • 推导到后期一般就是看是否有重复项目了 I10前后


8-LR(0)分析法

关键：构建LR(0)分析表

• 拓广文法
• 识别全部活前缀的DFA


LR(0)项目集规范族的构造

*LR分析表的构造

https://www.cnblogs.com/xpwi/p/11070888.html


基于LR分析表的分析过程

规约时退出的状态个数，规约后用goto判断下一状态

8-SLR(1)分析法

通过考察有关非终结符的FOLLOW集来解决移进-归约和归约-归约冲突——DFA中存在冲突项目（一个状态li中同时有移进、规约项目/有两个规约项目），以此构造出来的LR分析表，叫 做SLR(1)分析表
I={X→a•bb, A→a•, B→a•}
当状态I面临任何输入符号xi时，可采用如下策略：

• 若xi=b，则移进
• 若xi∈FOLLOW(A),则用产生式A→a归约
• 若xi∈FOLLOW(B),则用产生式B→a归约
• 此外，报错。


9-语法制导翻译

每使用一次产生式则调用相应的语义子程序，则推导完成时，语义值E.VAL也计算出来。

9-*语义子程序的翻译

9-*语句的四元式翻译

10-局部优化方法


10-全局优化方法

循环优化

10-翻译过程的寄存器分配

每次操作只能是寄存器-寄存器或寄存器-变量；不能是变量-变量

10-参数传递

引用调用（传地址）、值调用、名调用三种方式的输出结果

11-活动记录的内容

• 临时变量、局部变量
• 参数单元、参数个数
• 现场保护
• 静态链接、动态链接
• 返回指针

11-三种存储分配模式——静态、栈式、堆

11-只含半静态变量的栈式分配

11-静态作用域

11-动态作用域

11-数据参数的传递方式