首页  思维导图  详情

《编译原理》读书笔记

2021-06-30 21:29:52   0  举报





AI智能生成

学习编程

拆书稿征集

编程

作者其他创作

大纲/内容

CH4

语法分析类别

自顶向下的语法分析

自底向上的语法分析

计算FIRST和FOLLOW(P101)

FIRST

对于文法G的每个非终结符的所有候选式α，其首符号集FIRST，定义如下：

FIRST(α)：从α可能推导出的所有开头终结符号或ε

举例

总结（看例题，我总结的你们可能看不懂，为了方便自己看的）

FIRST意思是求左边某一个字母对应右边的第一个出现的终结符号。最重要的是要考虑空串，如果某个字母可以为空串，就把该字母跳过，把其后面一个元素的FIRST集中去掉空串，加入到该FIRST中；如果不是空串，就把该字母的FIRST加入到左边的FIRST集合中。

对于文法G的非终结符的后跟符号集FOLLOW定义如下：

FOLLOW(A)：是所有句型中紧接A之后的终结符号或#

举例

总结（看例题，我总结的你们可能看不懂，为了方便自己看的）

需要注意该字母的FOLLOW集合，看的是右边的式了，看该元素所有的右边无素的右边那一个。

该式子对应左边的字母的FOLLOW为该元素的FOLLOW的一部分

再观察该式右边的字母是否为空串，如果可以为空串就把右边的字母的FOLLOW集加入到该字母的FOLLOW集合中，如果不为空串，就把右边字母的FIRST集合去掉空串加入到该字母的FOLLOW集合中。如果右边的字母即可以是空串，又可以不是空串，则FIRST和FOLLOW集合都加入到该字母的FOLLOW集合中。

构造LL(1)分析表(P102)（自己多看几遍）

以所有终结符为列坐标，所有非终结符为行坐标先把表格画出来。（注意把空串去掉）

把给出来的文法中的式子都列出来，其中有两个以上的式子都折开。

把FIRST集合里面，左边的字母对应行，右边的元素对应列所对应的式子填入对应表中。直到把所有的都填完。

观察FIRST集合里面有空串式了，观察该元素的FOLLOW集合，看FOLLOW集合对应哪些FIRST集合中没有的元素，把式子填入表中。

CH5

短语、直接短语、句柄、素短语和最左素短语

短语

直接短语（简单短语）

直接短语和素短语的区别

短语就是某句型中的子串，这个子串是由某个非终结符通过至少一步推导得到的子串，而简单短语就是由某个非终结符通过一步推导得到的子串。

从语法树找句型的短语和简单短语

设A是句型αβδ的某一子树的根，其中β是形成此子树的末端结点的符号串，则β是短语。若这个子树只有一层分支（称简单子树），则β简单短语。

句柄

任一句型的最左简单短语称为该句型的句柄。

短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。

分支主题

素短语

素短语是一个短语,它至少包含有一个终结符号,并且除它自身以外不再包含其他素短语。

最左素短语

其中最左边的素短语称为最左素短语。

SLR(1)的DFA，分析表，LR(1)项目集（P137把图看懂，截取一小部分）

对于该部分，如果不会的话我给两个链接，可以看链接里面的视频,直接点字就可以了

SLR(1)

LR(1)

CH6

符号表的作用

登记符号属性值

查找符号的属性、检查其合法性

作为目标代码生成阶段地址分配的依据

编译程序对符号表的操作（标亮处为填空）

对于给定符号，查询此名字是否在符号表中

对于给定符号，在符号表中访问它的属性信息

对于给定符号，在符号表中更新它的属性信息

在符号表中插入一个新的符号及其相关信息

删除一个或一组无用的表项

CH7

过程的活动记录

返回值

形式单元

（可选）控制链

（可选）访问链

机器状态

局部数据

临时数据

参数传递机制

按值调用

引用调用

值-结果调用

换名调用

CH8

语义分析的主要任务

静态语义处理

符合词法、语法规则的程序是否有意义,检查控制结构和数据结构的一致性或完整性。

动态语义处理

生成中间代码或目标代码。

属性文法：类型检查和赋值语句

属性有两种

综合属性

继承属性

CH9

中间代码的形式

后缀式

图形表示

字节代码

三地址码

后缀式

特点

运算对象出现的顺序和原有顺序（从左到右）相同

运算符按实际计算顺序（从左到右）出现

运算符紧跟在运算对象的后面出现，且没有括号

数组地址计算

原理

举例

子主题

while、赋值、if语句翻译为四元式 P272-274

CH10

设计代码生成生成器时的一些通用基本问题（该题是一个简答题，需要对大标题进行解释，自己挑话进行语言组织。P282）

目标程序

代码生成器的输出是目标程序，分为若干种形式。

指令选择

目标机器指令系统的性质决定了指令选择的难易程度，指令系统的一致性和完备性直接影响到源程序和目标代码的对应关系的建立。指令执行速度和机器特点对产生目标代码的质量也十分重要。应该选择效率高、执行速度快的一种。

寄存器分配

寄存器分配和寄存器指派合在一起，统称为寄存器分配。如果一个运算结果要存入某个寄存器，那就应该首先确定它是否被占用。

计算顺序的选择

计算执行的顺序会影响目标代码的质量。改变运算的执行顺序可以减少用来保存中间结果的寄存器的个数，从而提高代码的效率。

目标代码常见的形式

绝对机器代码

可重定位机器代码

汇编程序

CH11

代码优化的原则（标题会，内容理解）

等价原则

经过优化的代码应该保持程序的输入输出，不应改变程序的运行结果。

有效原则

优化后的代码应该在占用空间，运行速度这两个方面，或者其中一个方面得到改善。

经济原则

代码优化需要占用计算机和编译程序的资源，代码优化取得的效果应该超过优化工作所付出的代价。

中间代码优化技术

删除公共子表达式

复写传播

删除无用代码

代码外提

强度削弱和删除归纳变量

课程思政

词法分析和语法分析的工作是检查编写的程序是否符合规则，如标识符是否符合命名规则、语句是否符号语法规则等。我们不难发现其实这个检查过程与一些做人做事的道理是相通的，比如：在学校，要遵守学校的各项规章制度；毕业后，要遵守国家法律法规，做一个遵纪守法的好公民等。请你给出一个本课程中与社会主义核心价值观、优秀传统文化、工程伦理、科学精神等相关的知识点，并简述其对当代大学生学习、生活的启示。

CH1

解释程序和编译程序（了解区别）

编译程序

若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”。

解释程序

（类似于口译，不生成目标代码）对源程序进行解释执行的程序。

共同点

如果源语言是高级编程语言，目标语言是机器代码和汇编语言这样的低级语言，这类翻译程序就叫做编译程序或解释程序。

区别

编译程序会生成目标代码，而解释程序不会。

编译过程（五个阶段，会背，填空题）

词法分析