2023SPR《编译原理》笔记

由
内容纲要

第一章 引论

编译程序

翻译程序：把某一种语言程序等价地转换成另一种语言程序的程序。
编译程序：把高级语言程序等价地转换成另一种低级语言程序的程序。
解释程序：把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。

编译过程

编译过程一般经过下列五个步骤：

  • 词法分析，识别出句子中的单词
  • 语法分析，分析句子的语法结构
  • 中间代码产生，根据句子的含义进行初步翻译
  • 优化，对译文进行修饰
  • 目标代码产生，写出最后的译文

词法分析：

  • 任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单次符号
  • 原则：构词规则（保留字、标识符、常数等）
  • 描述工具：有限自动机

语法分析：

  • 任务：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位
  • 原则：语法规则
  • 描述工具：上下文无关文法

中间代码产生：

  • 任务：对各类不同语法范畴按语言的语义进行初步翻译
  • 原则：语义规则
  • 中间代码：三元式、四元式、树形结构等

优化：

  • 任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码
  • 原则：程序的等价变换

目标代码产生：

  • 任务：把中间代码变换成特定机器上的目标代码
  • 依赖于硬件系统结构和机器指令的含义
  • 目标代码有三种形式：
    • 绝对指令代码: 可直接运行
    • 可重新定位指令代码: 需要连接装配
    • 汇编指令代码: 需要进行汇编

编译程序结构

表格与表格管理

编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。
符号表：等级源程序中出现的每个名字以及名字的各种属性。
表格还有：常数表、入口名表、标号表和标号对应的代码形式表。

出错处理

出错处理程序：发现源程序中的错误，把有关错误信息（语法错误、语义错误）报告给用户。

遍pass

所谓"遍"， 就是对源程序或源程序的中间表示从头到尾扫描一次。
阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。

编译前端与后端

编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化。
编译后端：与目标机有关，与目标机有关的优化，目标代码产生。

优点：减少对内存容量的要求，程序逻辑结构清晰; 优化更充分，有利于移植。
不足: 编译程序运行的效率低

编译程序生成

以汇编语言和机器语言为工具
优点: 可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。
缺点: 程序难读、难写、易出错、难维护、生产的效率低。

高级语言书写
利用已有的某种语言的编译程序实现另一语言的编译程序。
优点: 程序易读、易理解、容易维护、生产的效率高。
缺点: 难以充分发挥计算机的系统功能，生成的程序效率低。

自展技术：首先确定一个非常简单的核心语言 L1，用机器语言或汇编语言写出它的编译程序 T1，再把 L1 扩充到 L1+L2，并用 L1编写它的编译程序 T2，……，直到获得要求的编译程序。这种通过一系列自展途径形成编译程序的过程叫自编译过程。

第二章 高级语言及其语法描述

程序语言的定义

语法

语法：一组规则，用它可以形成和产生一 个合式(well-formed)的程序。

词法规则：单词符号的形成规则。描述工具是有限自动机。

语法规则：语法单位的形成规则。描述工具是上下文无关文法。

语法规则和词法规则定义了程序的的形式结构。

语义

语义：一组规则，用它可以定义一个程序的意义。

描述方法：

  • 自然语言描述：可能存在隐藏错误、二义性和不完整性
  • 形式描述

程序语言的基本功能和层次结构

程序语言的基本功能是描述数据和对数据的运算。

程序：

  • 子程序或分程序
    • 语句
      • 表达式
      • 数据引用
      • 算符
      • 函数调用

高级语言的一般特性

高级语言的分类

强制式语言：也称过程式语言，命令驱动，面向语句。

应用式语言：注重程序所表示的功能，而不是一个语句接一个语句地执行。

基于规则的语言：检查一定的条件，当它满足值，则执行适当的动作。

面向对象语言：封装性、继承性和多态性。

程序结构

FORTRAN：

  • 一个FORTRAN程序由一个主程序段和若干个辅程序段组成
  • 辅程序段可以是子程序、函数段或数据块
  • 每个程序段有一系列的说明语句和执行语句组成，各段可以独立编译
  • 模块结构，没有嵌套和递归
  • 各程序段中的名字相互独立，同一个标识符在不同程序段中代表不同的名字

PASCAL：

  • PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归

  • 作用域：一个名字能被使用的区域范围称作这个名字的作用域

  • 允许用同一个标识符在不同的过程中代表不同的名字

  • 最近嵌套原则：一个在子程序B1中说明的名字X只在B1中有效（局部于B1）如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明， 那么，B2对X的任何引用都是指重新说明过的这个X

  • PASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存贮空间

ADA：

  • 程序包：把数据和操作代码封装在一起，支持数据抽象
  • 一个程序包分为两部分：
    • 可见的规范说明部分，它定义了程序包外面可以访问的对象
    • 程序包体，它实际定义程序包的实现细节

JAVA：

  • 一种面向对象的高级语言

数据类型与操作

一个数据类型通常包括以下三种要素：

  • 用于区别这种类型数据对象的属性
  • 这种类型的数据对象可以具有的值
  • 可以作用于这种类型的数据对象的操作

标识符与名字

标识符：以字母开头的，由字母数字组成的字符串。

标识符与名字的区别在于：

  • 标识符是语法概念
  • 名字有确切的意义和属性

一个名字的属性包括类型和作用域。

数据结构

数组：

  • 逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离称为下标

内情向量：把数组的有关信息记录在一个“内情向量”中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型。

记录

逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。

域的地址计算：相对于记录结构起点的相对数OFFSET。

字符串、表格、栈

抽象数据类型

一个抽象数据类型包括：

  • 数据对象的一个集合
  • 作用于这些数据对象的抽象运算的集合
  • 这种类型对象的封装，用户只能使用类型定义的运算

语句与控制结构

表达式由运算量和算符组成。

对于多数程序语言来说，表达式的形成规则可概括为：

  • 变量、常数是表达式
  • 若E1、E2为表达式，\theta是一个二元算符，则E1\theta E2是表达式
  • 若E是表达式，\theta是一个一元算符，则\theta E是表达式
  • 若E是表达式，则(E)是表达式

语句

赋值语句：A := B

名字左值：该名字代表的那个单元称为该名字的左值。

右值：一个名字的值称为该名字的右值。

控制语句

说明句：旨在定义名字的性质。定义各种不同数据类型的变量或运算。

简单句和复合句

程序语言的语法描述

上下文无关文法

文法：描述语言的语法结构的形式规则

一个上下文无关文法G是一个四元式
G=(V_T,V_N,S,P)
其中四个符号分别代表：

  • 终结符集合：是一个语言的不可再分的基本符号
  • 非终结符集合：代表一个一定的语法概念
  • 文法的开始符号：特殊的非终结符号
  • 产生式集合：定义语法范畴的一种书写规则，如下述举例：
    • E→i对应a
    • E→E+E对应a+b
    • E→E*E对应a*b
    • E→(E)对应(a)

表示一个文法时，通常只给出开始符号和产生式。

推出：称aAb直接推出a\gamma b，仅当A\rightarrow \gamma是一个产生式，且a,b\in (V_T\cup V_N)^*

假定G是一个文法，S是它的开始符号。如果S经过0步或若干步可以推出a，则称a是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，记为L(G)。

最左推导：任何一步推导都是对a的最左非终结符进行替换。
最右推导：任何一步推导都是对a的最右非终结符进行替换。也称规范推导。

语法树与二义性

用一张图表示一个句型的推导，称为语法树。
若一个文法中存在某个句子，它有两个不同的最左（右）推导，那么这个文法是二义的。
若对于一个语言，不存在无二义性的文法，则这个语言是二义的。

文法的二义性和语言的二义性是两个不同的概念。可能存在两个不同的文法，一个是二义的而另一个不是二义的，但是它们产生的语言是相同的。

描述程序设计语言时，对于上下文无关文法的限制：

  • 不含P→P形式的产生式
  • 每个非终结符P必须有用处

形式语言鸟瞰

Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。

0型文法

短语文法，图灵机
产生式形如：a\rightarrow \beta
其中：a\in (V_T \cup V_n)^*至少含有一个非终结符；\beta \in (V_T \cup V_N)^*。

1型文法

上下文有关文法，线性界限自动机
产生式形如：a\rightarrow \beta
其中|a| \leq |\beta|，仅S\rightarrow \epsilon例外。

2型文法

上下文无关文法，非确定下推自动机
产生式形如：A\rightarrow \beta
其中：A\in V_N; \beta \in (V_T \cup V_n)^*。

3型文法

正规文法，有限自动机
产生式形如：A\rightarrow aB | A\rightarrow a
其中：a\in V_T^*; A,B\in V_N。右线性文法。

第三章 词法分析

对词法分析器的要求

词法分析器的功能和输出形式

功能：输入源程序、输出单词符号。
单词符号的种类：

  • 基本字：如begin，repeat
  • 标识符：如变量名、数组名、过程名
  • 常数
  • 运算符
  • 界符：逗号，分号，括号，空格

输出单次符号的表示形式：（单词种别，值）
单词种别通常用整数编码表示。
若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。
若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。
标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。
常数按类型分种；常数的值则表示成标准的二进制形式。

例如：

while (i>=j) i--;

输出单词符号：

<while, ->
<(, ->
<id, 指向i符号表项的指针>
<>=, ->
<id, 指向j的符号表项的指针>
<), ->
<id, 指向i的符号表项的指针>
<--, ->
<;, ->

词法分析器作为一个独立的子程序

作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。
不作为一遍：将其处理为一个子程序。

词法分析器的设计

输入、预处理

输入串放在输入缓冲区中。
预处理子程序：剔除无用的空白、跳格、回车等编辑性字符；区分标号区、捻接续行和给出句末符等。

扫描缓冲区：
一个指示token起点，一个搜索token终点。可将字串先放入一个半区，搜到边缘仍未结束则将后续字串放入另一个半区。
标识符和常数的长度必须受限，小于缓冲区半区长度。

单词符号的识别：超前搜索

对于关键字的识别，如果不存在关键字特殊保护，那么就需要超前搜索后续字符，来区分关键字和用户定义标识符。

对于常数识别，有些也需要超前搜索。

状态转换图

转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭头连接。箭头标记代表在射出节点状态下可能出现的输入字符或字符类。

若：

  • 所有基本字都是保留字;用户不能用它们作自己的标识符；
  • 基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表；
  • 如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔，
    则不必使用超前搜索。

将每个状态节点对应一小段程序，可以实现状态转换图：

  • 对不含回路的分叉结点，可以用一个CASE语句或者一组IF-ELSE实现
  • 对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序
  • 终态结点表示识别出某种单词符号，对应语句为RETURN

正规表达式与有限自动机

正规式和正规集

正规集可以用正规式表示。一个由字构成的集合是正规集，当且仅当它能用正规式表示。

递归定义：
对于给定的字母表\sum

  • \epsilon和\emptyset都是\sum上的正规式，它们所表示的正规集为\{\epsilon\}, \emptyset
  • 任何a \in \sum，a是\sum上的正规式，它所表示的正规集为\{a\}
  • 假定e_1,e_2都是\sum上的正规式，它们所表示的正规集为L(e_1), L(e_2)，则
    • (e_1|e_2)为正规式，它所表示的正规集为L(e_1) \cup L(e_2)
    • (e_1·e_2)为正规式，它所表示的正规集为L(e_1)L(e_2)
    • (e_1)^*为正规式，它所表示的正规集为(L(e_1))^*
      仅由有限次使用上述三步骤定义的表达式才是\sum上的正规式，仅由这些正规式表示的子集才是\sum上的正规集。

确定有限自动机DFA

自动机M是一个五元式M=(S,\sum,f,S_0,F)，其中项依次为：

  • 有穷状态集
  • 输入字母表
  • 状态转换函数
  • S的唯一初态
  • 终态集

非确定有限自动机NFA

一个NFA是一个五元式M=(S,\sum,f,S_0,F)，其中项以此为：

  • 有穷状态集
  • 输入字母表
  • 状态转换函数
  • 非空的初态集
  • 终态集

DFA是NFA的特例。

对于任何两个有限自动机M和M'，如果L(M) = L(M')则二者等价。

NFA确定化

对于每个NFA存在一个DFA，二者等价。

对于一个NFA，进行如下改造：

  • 引进新初态终态X和Y，其不属于S。将X到S_0中任意状态连一条\epsilon弧，从F中任意状态连一条\epsilon弧到Y
  • 按照下面三条规则分裂所有弧

采用子集法确定化上述NFA。

  • 将初态X及其经过任意条\epsilon弧能到达的状态放入初始集合中
  • 对于在字符表中的所有字符，写出其从初始集合的任意状态经过1条此字符的弧后，经过任意条\epsilon弧能到达的所有状态的集合
  • 如果上述集合不在表的第一列，则将其加入第一列
  • 重复上述步骤，直到没有新的集合
  • 将所有集合标号，相同集合标相同的号，将其视为状态转换矩阵画出DFA

正规文法与有限自动机等价性

对右线性文法，创建一个新状态f，所有文法中的非终结符经过其能推导到的非终结符左侧所有终结符组成的弧到达此非终结符。如果推导中不含非终结符，则将其连入f。

对有限自动机M，如果其终态可以射出一条弧到达出错处理状态，则任何连入此终态的弧，其对应的文法需要加入一个不含非终结符的推导。

左线性文法考虑每个状态射入的弧。

正规式与有限自动机等价性

按上述规则分裂。

DFA最小化

寻找一个状态数比M少的DFA，使两个DFA等价。

把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其它状态。

第四章 语法分析——自上而下分析

上下文无关文法的定义

一个上下文无关文法G是一个四元式G=(V_T,V_N,S,P)。

语法分析的方法

自下而上分析法：从输入串开始，逐步进行归约，直到文法的开始符号。根据文法的产生式规则，把产生式的右部替换成左部符号。

自上而下分析法：从文法开始符号出发，利用各种产生式规则，寻找匹配的推导。

自上而下分析面临的问题

分析过程中，可能走入暂时成功的匹配，后续会出错，需要回溯。
对于左递归的文法，会使得分析进入无限循环。

LL(1)分析法

左递归的消除

一般而言，假定P关于的全部产生式是
P\rightarrow Pa_1|Pa_2|...|Pa_m|b_1|b_2|...|b_n
那么，消除P的直接左递归就是把这个规则改写成
P\rightarrow b_1P'|b_2P'|...|b_nP'
P'\rightarrow a_1P'|a_2P'|...|a_mP'|\epsilon

间接左递归也算左递归。

将间接左递归的推导代入，直到得到直接左递归的推导。然后改写成右递归形式，去除多余的规则即可。

消除回溯，提左因子

假定关于A的规则是
A\rightarrow \delta b_1|\delta b_2|...|\delta b_n|\gamma_1|\gamma_2|...|\gamma_m
那么可以把这些规则改写成
A\rightarrow \delta A'|\gamma_1|\gamma_2|...|\gamma_m
A'\rightarrow b_1|b_2|...|b_n

经过反复提取左因子，能把每个非终结符的所有候选首符集变成为两两不相交。

FIRST、FOLLOW集合

令G是一个不含左递归的文法，对G的所有非终结符的每个候选a定义它的终结首符集FIRST(a)为下述字符组成的集合：

  • 所有能直接推出的最左终结符（包括\epsilon）
  • 在文法中出现在此非终结符紧左的终结符
  • 若某个推导中，最左侧为非终结符，此非终结符的FIRST集合的所有元素
  • 如果上述最左的非终结符可以推出\epsilon，则考虑其紧右的符号，如是终结符，将其加入集合，如是非终结符，考虑第三条规则

求出文法G的所有非终结符的FOLLOW集合为下述字符组成的集合：

  • G中直接位于此非终结符紧右的终结符（对于开始符号，终止符属于FOLLOW集合）
  • G中直接位于此非终结符紧右的非终结符的FIRST集合的所有元素
  • 若此非终结符位于一个推导的最右侧，此推导的源终结符的FOLLOW集合的所有元素

如果一个文法不含左递归，每一个非终结符的各个推导的FIRST集合两两不相交，且对于每个非终结符A，若它存在某个候选首符集包含\epsilon，其FIRST集合和FOLLOW集合不相交，则称此文法为LL(1)文法。

递归下降分析程序构造

LL(1)文法可以构造递归下降分析程序。

递归下降分析程序的出错处理可以在主程序中统一执行，也可以在每个终结符对应的函数内部执行。

预测分析程序

又叫LL(1)分析法，包括：

  • 总控程序
  • 分析表M[A,a]矩阵
  • 分析栈，存放文法符号

总控程序根据现行栈顶符号X和大当前输入符号a执行下列三种动作之一：

  • 若X=a='#'，则宣布分析成功，停止分析
  • 若X=a不等于终止符，则把X从栈顶逐出，让a指向下一个输入符号
  • 若X是一个非终结符，则查看分析表M
    • 若M中存放一个关于X的产生式，把X逐出战斗顶，把产生式的右部符号串按照反序一一推进栈
    • 若对应出错，则调用ERROR

构造分析表

首先构造每个非终结符A及其任意候选a的FIRST(a)和FOLLOW(A)集合。

利用上述集合构造分析表：

  • 对每个产生式执行2和3步
  • 对每个终结符a\in FIRST(a)，把A\rightarrow a加入M[A,a]中
  • 若\epsilon \in FIRST(a)，把任何b\in FOLLOW(B)把A\rightarrow a加入M[A,b]中
  • 把所有无定义的M[A,a]加上出错标志

如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。一个文法G的预测分析表不含多定义入口，当且仅当该文法为LL(1)。

第五章 语法分析——自下而上分析

归约

用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。
自下而上的分析要解决的核心问题：识别可归约串。

规范规约

在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。
最左直接短语就是句柄。

假定a是文法G的一个句子，我们称a_n, a_{n-1},...,a_0是一个规范归约，如果：

  • a_n = a
  • a_0为文法的开始符号S
  • 对任何i，0 \leq i \leq n，a_{i-1}是从a_i经把句柄替换成相应产生式左部符号得到的

规范归约是最右推导的逆过程。由规范推导推出的句型称为规范句型。

LR分析法

LR分析器

LR分析器核心是分析表：

  • ACTION[s,a]：当状态s面临符号a时，应采取什么动作
  • GOTO[s,X]：当状态s面临符号X时，下一个跳转的状态

每一项ACTION的规定的四种动作：

  • 移进：把(s,a)的下一状态s'和输入符号a推进栈，下一输入符号变成现行输入符号
  • 归约：利用某产生式A\rightarrow b归约，设b长度为r，归约动作是，去除栈顶r个项，使s_{m-r}变成栈顶状态，然后把下一状态s'=GOTO[s_{m-r}, A]和文法符号A推进栈
  • 接收：宣布分析成功
  • 报错

对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。
一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。

LR(0)项目集族和分析表构造

活前缀：指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
LR分析就是保证栈中总是活前缀。

文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目。

加入新初态称为唯一的接受态，形成拓广文法G'。

令每个项目集I_k的下标k作为分析器的状态，包含拓广文法的唯一接收态集合的下标k作为分析器初态。
根据DFA构造分析表，对每个箭弧：

  • 若箭弧标注非终结符a，对于箭弧起点状态S，终点状态S'，标注ACTION[S,a]=sS'
  • 若箭弧标注终结符A，对于箭弧起点状态S，终点状态S'，标注GOTO[S,A]=S'
  • 若状态存在归约项目（记归约用产生式顺序为N）
    • 状态为唯一接收态，标注ACTION[S,#]=acc
    • 状态不为唯一接收态，对每个终结符a（包括#），标注ACTION[S,a]=rN
  • 其余区域填上报错标志

SLR分析表构造

假定一个LR(0)规范族中含有如下的一个项目集状态I=\{X\rightarrow a·b\beta, A\rightarrow a·, B\rightarrow a·\}。A和B的FOLLOW集合交集为空，且不包含b，那么当状态I面临任何输入符号a时，可以：

  • 若a=b则移进
  • 若a属于A或B的FOLLOW集合，则用产生式A→a或B→a进行归约
  • 此外，报错

上述冲突性动作解决方案叫做SLR(1)解决办法。

SLR(1)分析表构造方法：

  • 若箭弧标注非终结符a，对于箭弧起点状态S，终点状态S'，标注ACTION[S,a]=sS'
  • 若箭弧标注终结符A，对于箭弧起点状态S，终点状态S'，标注GOTO[S,A]=S'
  • 若状态存在归约项目（记归约用产生式顺序为N）
    • 状态为唯一接收态，标注ACTION[S,#]=acc
    • 状态不为唯一接收态，对每个终结符a（包括#）如果属于FOLLOW(A)（与LR(0)不同），标注ACTION[S,a]=rN
  • 其余区域填上报错标志

SLR(1)利用FOLLOW获得的超前符号集合可能大于实际能出现的超前符号集合（很多文法并非SLR(1)）。也就是说，FOLLOW集合提供的信息太泛。

LR(1)分析表构造

项目集I的闭包CLOSURE(I)构造方法：

  • I的任何项目都属于CLOSURE(I)
  • 若项目A\rightarrow \alpha·B\beta, a属于CLOSURE(I)，B\rightarrow \sigma是一个产生式，那么对于FIRST(\beta a)中的每个终结符b，如果B\rightarrow ·\sigma,b原来不在CLOSURE(I)中，则加入
  • 反复执行2，直到不能继续

LALR(1)构造

合并LR(1)同心集后的项目集其核心部分不变，仅搜索符合并。

第六章 属性文法和语法制导翻译

属性文法

在上下文无关文法得到基础上，为每个文法符号配备若干相关的值。
语义规则：对于文法的每个产生式都配备了一组属性的计算规则。

对于产生式的一套语义规则b:=f(c1,c2,…,ck)：

  • b是A的综合属性，并且c是产生式右边文法符号的属性，或者A的其他属性
  • b是产生式右边某个文法符号的一个继承属性，并且c是A或产生式右边任何文法符号的属性

终结符只有综合属性，由词法分析器提供。
非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。
对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。

综合属性

在语法树中，一个结点的综合属性的值由其子节点的属性值确定。使用自底向上的方法在每一个节点处使用语义规则计算综合属性的值。
仅使用综合属性的属性文法称为S-属性文法。

继承属性

在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。

基于属性文法的处理方法

由源程序的语法结构所驱动的处理办法就是语法制导翻译法。

依赖图

for 语法树中的每一结点n do
    for 结点n的文法符号的每一个属性a do
        为a在依赖图中建立一个结点;

for 语法树中的每一个结点n do
    for 结点n所用产生式对应的每一个语义规则 b:=f do
        for i:=1 to k do
            从ci结点到b结点构造一条有向边;

如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。

一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。

树遍历

假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性。
以某种次序反复遍历语法树，计算出能计算的所有属性，直至计算出所有属性。

一遍扫描

语法分析的同时计算属性值。
L-属性文法适合于一遍扫描的自上而下分析。
S-属性文法适合于一遍扫描的自下而上分析。

所谓语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。
语义规则被计算的时机：

  • 自上而下：产生式匹配输入串成功时
  • 自下而上：产生式被用于进行归约时

抽象语法树

在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树。

S-属性文法的自下而上计算

S-属性文法：只含有综合属性。
分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。

L-属性文法和自顶向下翻译

通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值。
一个属性文法称为L-属性文法，如果对于每个产生式A\rightarrow X_1X_2...X_n，其每个语义规则中的每个属性或者是综合属性，或者是继承属性，这个继承属性仅依赖于：

  • 其左侧符号的属性
  • A的继承属性

由于S-属性文法仅含综合属性，所以它一定是L-属性文法。

翻译模式

给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来。

设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。L-属性文法确保了这一点。

当只需要综合属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
如果既需要综合属性又需要继承属性，则要保证：

  • 产生式右边符号的继承属性必须在这个符号以前的动作计算出来
  • 一个动作不能引用这个动作右边符号的综合属性
  • 左边非终结符得到综合属性必须在引用的所有属性计算出来后才能计算，动作放在右端末尾可以解决大部分情况的问题

自顶向下翻译

消除左递归，构造新的翻译模式。

递归下降翻译器的设计

对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数。
函数的返回值为A的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性。
A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。

非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。

每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：

  • 对带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。
  • 对于每个非终结符B，产生一个右边带有函数调用的赋值语句
  • 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用

第七章 语义分析和中间代码产生

中间语言

后缀式

又称逆波兰表示法。可以如下定义：

  • 对表达式E，如果E是一个常量或变量，则E的后缀式就是E本身
  • 如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1' E2' op，其中E1' E2'为E1和E2的后缀式
  • 如果E是(E)形式的表达式，那么E后缀式是本身

后缀式的计算用栈实现，自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。

图表示法

无循环有向图(DAG)：

  • 对表达式中的每个子表达式，DAG中都有一个结点
  • 一个内部节点代表一个操作符，它的子结点代表操作数
  • 在一个DAG中代表公共子表达式的结点具有多个父节点

三地址代码

形如x:=y op z，可以看成是抽象语法树或DAG的一种线性表示。

三地址语句的种类：

  • x:=y op z
  • x:=op y
  • x:=y
  • goto L
  • if x relop y goto L / if a goto L
  • param x / call p, n / return y
  • x:=y[i] / x[i]:=y
  • x:=&y / x:=*y / *x:=y

生成三地址代码时，临时变量的名字对应抽象语法树的内部结点。

四元式

四个域的记录结构，域分别为：

  • 操作符
  • 操作数1
  • 操作数2
  • 结果
三元式

通过计算临时变量值的语句的位置来引用这个临时变量。
三个域：

  • 操作符
  • 操作数1
  • 操作数2
间接三元式

用三元式表和间接码表来表示中间代码。

赋值语句的翻译

简单算术表达式及赋值语句

非终结符号E有如下两个属性：

  • E.place表示存放E值的名字
  • E.code表示对E求值的三地址语句序列
    函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,…。

非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。

数组元素的引用

元素A[i1,i2,...,ik]的相对地址公式：
((...(i_1n_2+i_2)n_3+i_3)...)n_k+i_k)×w+base-((...((low_1n_2+low_2)n_3+low_3)...)n_k+low_k)×w
c = base-((...((low_1n_2+low_2)n_3+low_3)...)n_k+low_k)×w

引入下列语义变量或语义过程：

  • Elist.ndim：下标个数计数器
  • Elist.place：表示临时变量，临时存放已形成的Elist中的下表表达式计算出来的值
  • limit(array, j)：给出数组array第j维的长度

布尔表达式的翻译

布尔表达式有两种计算方法：

  • 按照算术表达式的计算方法，一步步算
  • 用if-else语句解释

过程emit将三地址代码送到输出文件中，nextstat给出输出序列中下一条三地址语句的地址索引，每产生一条三地址语句，过程emit把nextstat加1。

两遍扫描：为给定的输入串构造一棵语法树，深度优先遍历，按照语义规则翻译。

一遍扫描：采用四元式形式，四元式存入一个数组中，下标代表标号。

约定：

  • (jnz, a, - ,p)：if a goto p
  • (jrop, x, y, p)： if x rop y goto p
  • (j, -, -, p)： goto p

有时转移地址无法立即知道，需要回填。

第九章 运行时存储空间组织

目标程序运行时的活动

过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间。

参数传递

传地址 Call by reference

过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。

得结果 Call by result

形参有两个单元，第一个单元存地址，第二个单元存值。在过程体中，引用第二个单元，在结束后将计算后的值回填到第一个单元的地址中。

传值 Call by value

只传值，不传地址。过程体对形参的操作不会影响实际参数。

传名 Call by name

把过程的代码抄到被调用的位置，形参全部被替换成实参。

运行时存储器的划分

一个目标程序运行所需的存储空间包括：

  • 存放目标代码的空间
  • 存放数据的空间
  • 存放程序运行的控制或连接数据所需单元（控制栈）

活动记录

假定语言的特点为:允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如C语言。

活动记录：运行时，每当进入一个过程就有一个相应的活动记录置于栈顶。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。

存储分配策略

静态分配策略(FORTRAN)：如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。
动态分配策略(PASCAL)：如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程和动态申请释放内存。

静态存储管理

由于每个FORTRAN程序段可以独立编译，运行前由装入程序把各段连成可运行的整体。通常按数据区组织存储:

  • 每个程序段定义一个局部数据区，用来存放程序段中未出现在COMMON里的局部名的值
  • 每个公用块定义一个公用数据区，用来存放公用块里各个名字的值

一个简单栈式存储分配

C的活动记录

C的过程调用、过程进入、数组空间分配和过程返回

过程调用的四元式序列：

par T1
par T2
...
par Tn
call P, n

par表示传参，call表示调用。

每个par Ti可以直接翻译成如下指令：

  • (i+3)[TOP]:=Ti 将Ti的值存储到TOP+i+3的地址上
  • (i+3)[TOP]:=addr(Ti) 将Ti的地址存储到TOP+i+3的地址上

call P, n被翻译成：

  • 1[TOP]:=SP 保护现SP
  • 3[TOP]:=n 传递参数个数为n
  • JSP P 跳转子指令

转进过程P后，首先应执行下述指令:

  • SP:=TOP+1
  • 1[SP]:=返回地址
  • TOP:=TOP+L L是过程P活动记录需要的单元数

过程返回时，应执行下列指令:

  • TOP:=SP-1 恢复调用前TOP
  • SP:=0[SP] 恢复调用前SP
  • X:=2[TOP] 把返回地址取到X
  • UJ 0[X] 按X返回

嵌套过程语言的栈式实现

假定语言不仅允许过程的递归调用(和可变数组)，而且允许过程定义的嵌套，如PASCAL，PL语言。

非局部名字的访问的实现

主程序的层次为0；在i层中定义的过程，其层次为i+1;
过程运行时，必须知道其所有外层过程的当前活动记录的起始地址。

静态链和活动记录

静态链：指向本过程的直接外层过程的活动记录的起始地址，也称存取链。
动态链：指向本过程的调用过程的活动记录的起始地址，也称控制链。

活动记录从下至上依次为：

  • 动态链
  • 返回地址
  • 静态链
  • 参数个数
  • 形式单元
  • 变量等过程内部信息
嵌套层次显示表display

当进入一个过程后，在建立其活动记录区的同时建立一张嵌套层次显示表display，把display表作为活动记录的一部分。

假设过程R的外层为Q，Q外层为主程序P，则过程R的运行时DISPLAY表内容为：

  • 2 R现行活动记录地址 SP现值
  • 1 Q的最新活动记录地址
  • 0 P的活动记录地址
PL全局display表

记录结构：

  • RA
  • DL
  • SL
  • 形式单元

通过全局display表找到活动记录。
display表的1层放主程序记录RA，第二层放最新调用的所有于主程序层次差为1的过程记录RA，第三层层次差为2，以此类推。

第十章 优化

对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。

优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循一定的原则：

  • 等价原则：经过优化后不应改变程序运行的结果；
  • 有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小；
  • 合算原则：应尽可能以较低的代价取得较好的优化效果。

三个不同级别：

  • 局部优化
  • 循环优化
  • 全局优化

种类：

  • 删除多与运算
  • 代码外提
  • 强度削弱
  • 变换循环控制条件
  • 合并已知量
  • 复写传播
  • 删除无用赋值

局部优化

基本块：指程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。

如果一条三地址语句为x:=y+z，则称对x定值并引用y和z。

局限于基本块范围内的优化称为基本块内的优化，或称局部优化。

划分基本块

求出四元式程序中各个基本块的入口语句:
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句。

对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。

凡未被纳入某一基本块中的语句，可以从程序中删除。

流图

每个流图以基本块为结点。如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点。如果在某个执行顺序中，基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边。

描述计算过程的DAG是一种带有下述标记或附加信息的DAG：
图的叶结点以一标识符或常数作为标记，表示该结点代表该变量或常数的值;
图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果;

留下评论