工具准备·
https://wenku.baidu.com/view/b8b4510bba1aa8114431d96c.html
https://max.book118.com/html/2018/1224/7166031033001166.shtm
https://wenku.baidu.com/view/d846931e6bec0975f465e295?bfetype=new
C语言栈方向从高到低延申，字符串拷贝数组操作不对数据长度做审核，实际数据长度超过栈中预留空间，则会栈溢出
龙书 虎书 鲸书
模型驱动 MDA MDE MDT MBSE
建模即编程—低代码，程序自动生成
编译知识结构图·
一、编译基础·
1.1 基本概念·
源程序：用汇编语言或高级语言编写的程序称为源程序。
目标程序：用目标语言所表示的程序。机器语言，或某机器的汇编语言。
翻译程序：将源程序转换为目标程序的程序称为翻译程序。是汇编程序、编译程序以及各种变换程序的总称
编译 ==> Compile ==> 将高级语言经过加工得到目标程序，这样的翻译过程
汇编 ==> Assemble ==> 汇编语言书写，经过翻译程序得到机器语言表示的程序，这时的翻译程序称为汇编程序
分为两种：编译运行和编译-解释执行
1.2 编译过程·
词法分析–>语法分析–>语义分析、生成中间代码–>代码优化–>生成目标程序
词法分析·
分析和识别单词 单词是语言的基本单位 ==> 线性分析
语法分析·
根据语法规则分析并识别各种语法成分，并进行语法正确性检查 ==> 层次分析
语义分析·
生成 中间代码==>一种介于源语言和目标语言之间的中间语言形式
分析语义上的正确性然后翻译成等价的另一种语言
便于做优化，便于编译程序的移植
中间代码常用的有四元式、三元式、逆波兰表示
代码优化·
得到高质量的目标程序
生成目标程序·
建表查表·
符号表管理
出错处理·
遍（pass）·
对源程序（包括源程序中间形式）从头到尾扫描一次， 并做有关的加工处理 ，生成新的源程序中间形式或目标程序
典型编译程序7个逻辑部分·
前端和后端·
与源程序有关的编译部分称为前端 ==> 词法分析，语法分析，语义分析，中间代码生成，代码优化
与目标机有关的部分称为后端 ==>目标程序生成(与目标机有关的优化)
编译程序的前后处理器·
源程序：多文件、宏定义和宏调用，包含文件
目标程序：一般为汇编程序或可重定位的机器代码
作业·
P21： 1,2,3,4,5
二、文法与语言·
2.1 预备知识·
字母表与符号串·
字母表：符号的非空有限集
符号：字母表中的元素
符号串：符号的有穷序列
空符号串：无任何符号的符号串
符号串运算·
符号串相等 每个字符依次相等
符号串的长度（符号串中符号的个数）
符号串联接
符号串乘积运算 $AB={xy|x\in A,y\in B}$
幂运算 $A^n=A*…*A$ $A^0=\epsilon$
闭包，正闭包
$闭包A*:A0\cup A^1\cup …\cup A^n\cup …$
$正闭包A+:A1\cup …\cup A^n\cup …$
某语言分为字符集A和单词集B
单词是定义在字符集上的字符串，句子是定义在单词集上的字符串
2.2 文法的非形式讨论·
2.2.1 文法·
文法和语言<句子>::=<主语><谓语>
::= 由…组成
|表示或
BNF表示法
<句子>::=<主语><谓语>
<主语>::=<代词>|<名语>
文法是形式上描述和推导句子，形式上对句子结构进行定义和描述，但不涉及语义
2.2.2 语法规则·
建立一组规则，来描述句子的语法结构
比如：
1 | <A>::=<B><C> |
2.2.3 由规则推导句子·
有了一组规则，可以按照一定方式推导句子
即从一个要识别的符号开始推导，用相应的规则右部代替左部，每次仅用一条规则，直到所有非终结符均被终结符替代
最左推导 ==> 有若干语法成分同时存在，先从最左的语法成分进行推导
最右推导类似
例子同上，比如上面的文法推出ad
1 | #最左推导 |
2.2.4 语法树——描述语法结构·
识别符号=>开始符号，属于非终结符
非终结符==>语法成分
终结符==>单词符号
2.3 文法和语言的形式定义·
2.3.1 文法的形式定义·
定义1·
文法定义：$G=(V_n,V_t,P,Z)$
$V_n$ 非终结符号集
$V_t$ 终结符号集
$V=V_n\cup V_t$称为文法的字汇表
$P$ 产生式或规则的集合
$Z$ 开始符号（识别符号）$Z\in V_n$
规则定义：$U\rightarrow x 或 U::=x$ $U\in V_n ,x\in V^*$
说明·
- 产生式左边符号构成集合$V_n$
- 有些产生式左部相同，可以合并 类似
A->B|C这样的，也称为文法的BNF表示 - 给定一个文法，需给出产生式（规则）集合，并指定识别符号
2.3.2 推导的形式定义·
定义2·
$文法G:v=xUy,w=xuy.其中x,y,u\in V^*,U\in V_n$
$若U::=u\in P,则v\Rightarrow w$
$若x=y=\epsilon，有U::=u，则U\stackrel G\Rightarrow u$
定义3 $v\stackrel{+}\Rightarrow w$·
$文法G，u_0,u_1,…,u_n\in V^+$
$若 v=u_0\Rightarrow u_1\Rightarrow u_2…\Rightarrow u_n=w$，则$v\stackrel{+}\Rightarrow w$
定义4 $v\stackrel * \Rightarrow w$·
$若v\stackrel + \Rightarrow w或v=w$，则$v\stackrel * \Rightarrow w$
定义5 规范推导·
$有xUy\Rightarrow xuy，若y\in V_t^*$，则此推导为规范的，记为$xUy\nRightarrow xuy$
直观：规范推导=最右推导
2.3.3 语言的形式定义·
定义6 文法G[Z]·
- 句型 $x是句型\Leftrightarrow Z\stackrel * \Rightarrow x，且x\in V^*$
- 句子 $x是句子\Leftrightarrow Z\stackrel + \Rightarrow x，且x\in V_t^*$
- 语言 $L(G[Z])={x|x\in V_t^*,Z\stackrel + \Rightarrow x}$
形式语言理论可证明以下两点：
- $G\rightarrow L(G)$
- $L(G)\rightarrow G1,G2…Gn$
已知文法求语言通过推导即可，但是已知语言求文法无形式化方法，一般是凭借经验
定义7 等价文法·
$G和G’是两个不同文法，若L(G)=L(G’),则G与G’为等价文法$
编译感兴趣的问题： 给定句子以及文法G，求$x\in L(G)?$
2.3.4 递归文法·
规则右部有和左部相同的符号比如 U::=bUc U::=aU U::=Ua 分别代表递归，左递归，右递归
2.3.5 句型的短语、简单短语和句柄·
定义8 短语与简单短语·
$给定文法G[Z]，w=xuy\in V^+，为该文法的句型$
$若Z\stackrel * \Rightarrow xUy，且U\stackrel + \Rightarrow u，则u是句型w相对于U的短语$
$若Z\stackrel * \Rightarrow xUy，且U\Rightarrow u(即单步推出)，则u是句型w相对于U的简单短语$
其中$U\in V_n，u\in V^+，x,y\in V^*$
说明·
短语是前面句型的某个非终结符所能推出的符号串
任何句型本身一定是相对于识别符号Z的短语
定义9 任一句型的最左简单短语称为句柄·
2.4 语法树与二义性文法·
2.4.1 推导与语法（推导）树·
语法树·
句子（句型）结构的图示表示法，有向图，由结点和有向边组成
结点：符号
根结点：识别符号（编译单元）
中间结点：非终结符（各个语法成分）
叶结点：终结符或非终结符（推导过程的每一步的句型或句子都可以以语法树表示，所以中间过程的语法树叶结点可以是非终结符）
有向边：结点间派生关系
比如下列的树：
graph TD Z-->U Z-->V U-->a U-->b V-->c V-->d
子树与短语·
子树：语法树中某个结点（也就是子树的根）连同它向下的派生部分所组成
子树末端结点自左至右顺序为句型的符号串，这个符号串即为相对于该子树根的短语。
短语和简单短语？？·
简单区分：看语法树
短语：对于原语法树中所有节点数大于1的子树，将所有叶子结点从左往右连接起来组成短语。
简单短语：短语中，可以由一个中间句子成分直接推导出来的
句柄：最左边的第一个简单短语
下图中，短语有D F DFE，简单短语有D F 句柄为D
graph TD a[A]-->b[B] a-->c[C] b-->d[D] a-->e[E] c-->f(F)
树与推导·
语法树生长过程 <=> 句型推导过程
从推导构造语法树·
一般采用规范推导即最右推导
由语法树构造推导·
每次修建都剪掉句柄
规范归约和规范推导互为逆过程
规范规约：对句型中最左简单短语（句柄）进行的归约
规范句型：通过规范推导或规范归约所得到的句型
二义性文法·
一个文法
- 某句子存在两种不同的语法树，则此文法为二义性文法，否则是无二义性文法
- 某句子存在两个不同的规范推导，则此文法为二义性文法，否则是无二义性文法
- 某规范句型的句柄不唯一，则此文法为二义性文法，否则是无二义性文法
2.5 句子的分析·
给定一个$G[Z]:S\in V_t^*，判断S\in L(G[Z])是否成立$
词法分析和语法分析的工作
2.6 有关文法的实用限制·
有害规则·
类似U::=U，会引起二义性和无穷递归
一般左递归就是有害规则
多余规则·
- 在推导文法的所有句子中，始终用不到的规则。 即该规则的左部非终结符不出现在任何句型中（不可达符号）
- 在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符（不活动符号）
若某文法中没有有害规则或者多余规则，则称该文法是压缩过的
删除文法中多余结点算法？·
2.7 文法的其他表示法·
扩充的BNF表示·
BNF元符号：< > ::= |
扩充的BNF元符号：< > ::= | { } [ ] ( ) 后面几个分别是0-无穷次 1-无穷次 0-1次
语法图·
2.8 文法和语言分类·
形式语言，文法，语言·
形式语言：用文法和自动机描述的没有语义的语言
乔姆斯基文法定义：
$G=(V_n,V_t,P,Z)$
$V_n$ 非终结符号集 $V_t$ 终结符号集
$P$ 产生式或规则的集合 $Z$ 开始符号（识别符号）$Z\in V_n$
语言定义：$L(G[Z])={x|x\in V_t^*,Z\stackrel + \Rightarrow x}$
文法和语言分类·
分为0、1、2、3型，差别在于对产生式（语法规则）的不同限制
0型 短语结构文法·
1型 上下文有关文法·
2型 上下文无关文法·
3型 正则文法·
- 根据上述讨论，$L0 \supset L1 \supset L2 \supset L3 $
- 0型文法可以产生$L0、L1、L2、L3$，
- 但2型文法只能产生$L2，L3$ 不能产生$L0，L1$
- 3型文法只能产生$L3$
作业·
p29 3,4
习题2-3：p38 1-9
习题2-4： P46-47 1,5,6,8,9
p53 3
三、词法分析·
3.1 词法分析程序的功能及实现方案·
功能：识别单词，返回单词的类别和值·
- 词法分析：根据词法规则识别及组合单词，进行词法检查
- 删去空格字符和注释
- 对数字常数完成从数字字符串到二进制数值的转换
实现方案·
-
词法分析单独一遍
-
作为一个子程序被语法分析程序调用
3.2 单词的种类及词法分析程序的输出形式·
单词种类·
保留字，标识符（用户定义），常数，分界符(+ - * / …)
单词内部形式·
按单词种类分类·
保留字和分界符采用一符一类·
3.3 正则文法和状态图·
左线性文法状态图画法·
识别算法·
3.4 词法分析程序的设计与实现·
graph LR 词法规则-->状态图 状态图-->词法分析程序
作业·
P73 1,2,3(词法见65-67页)
四、语法分析·
4.1 语法分析概述·
功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。
基本任务：识别符号串S是否为某语法成分
graph LR a[两大类分析方法] a-->b[自顶向下分析] a-->c[自底向上分析] b-->b1[主要解决问题] b1-->b11[左递归问题] b1-->b12[回溯问题] b-->b2[主要方法] b2-->b21[递归子程序法] b2-->b22[LL分析法] c-->c1[主要问题] c1-->c11[句柄的识别问题] c-->c2[主要方法] c2-->c21[算法优先分析法] c2-->c22[LR分析法]
4.2 自顶向下分析·
4.2.1 自顶向下分析的一般过程·
预测某一符号串为某一语法成分，根据其文法，为S构造一棵语法树，若成功，则S被识别为某一语法成分，即
$S\in L(G[Z])$，否则，$S\notin L(G[Z])$
分析过程带预测，是试探过程，有时需要回溯
4.2.2 自顶向下分析存在的问题及解决方法·
1.左递归文法·
比如E::=E+T|T
消除直接左递归·
方法1 使用扩充BNF表示改写文法·
规则1：提因子
规则2
方法2 将左递归规则改为右递归规则·
消除一般左递归·
消除所有左递归的算法
2.回溯问题·
$FIRST(\alpha_i)={a|\alpha_i\stackrel *\Rightarrow a…,a\in V_t}$
避免回溯，文法需要满足 $\forall \ i\neq j,FIRST(\alpha_i)\cap FIRST(\alpha_j)=\varnothing$
改写文法·
对具有多个右部的规则反复提取左因子
超前扫描·
向前多看几个符号
文法的两个条件·
为了在不采取超前扫描的前提下实现不带回溯的自顶向下分析，文法需要满足两个条件
-
非左递归（递归下降都需要）
-
不含回溯
4.2.3 递归子程序法（递归下降分析法）·
- 检查并改写文法
- 检查文法的递归性
- 递归调用各个子函数来识别语法成分
作业·
p91: 1-3
五、符号表管理技术·
5.1 概述·
符号表：编译程序记录各种名字的特性信息，名字特性表
源程序中变量要先声明，再引用。引用声明的变量时需要语法语义正确性检查以及生成相应的目标程序
5.2 符号表的组织与内容·
符号表内容·
名字域：标识符字符串
特性域：可包括多个子域
可以有以下内容：
符号表组织方式·
- 统一符号表==>查表方便，结构简单，浪费空间
- 不同种类名字建立各种符号表==>节省空间，填表查表不方便
- 折中办法==>大部分共同信息组成统一格式符号表，特殊信息另外附表，两者指针相连
5.3 非分程序结构语言的符号表组织·
分为全局和局部符号表，分别管理全局变量函数定义，和局部的变量
无序符号表，有序符号表，散列符号表
5.4 分程序结构语言的符号表组织·
分程序结构语言:模块内可嵌入子模块
查表需要从当前层查起，一直往外层查
作业·
作业：P115-116 3,5
非分程序：名字，类型，维数
分程序：序号，名字，属性，外接一个索引的栈
六、运行时的存储组织及管理·
6.1 概述·
运行时的存储组织及管理·
目标程序运行时需要存储空间的组织管理，源程序中变量存储空间的分配
静态存储分配·
在编译阶段由编译程序实现对存储空间的管理和为源程序中的变量分配存储的方法。
必须在编译时能够确定源程序中变量分配存储的方法
动态存储分配·
在目标程序运行阶段由目标程序实现对存储空间的组织与管理，和为源程序中的变量分配存储的方法。
需要生成进行动态分配的目标指令
6.2 静态存储分配·
FORTRAN子程序典型数据区·
6.3 动态存储分配·
栈式动态存储分配
整个数据区为一个堆栈 (1) 当进入一个过程时，在栈顶为其分配一个数据区。 (2) 退出时，撤消过程数据区。
6.3.1 活动记录·
局部数据区：存放模块中定义各个局部变量
参数区：存放隐式参数和显式参数
display区：存放各外层模块活动记录的基地址 =>为了能够利用符号表索引各个块的变量
C语言运行时存储管理·
作业·
p119 1 P133 2,3
七、源程序的中间形式·
7.1 波兰表示·
比如a*b*c+d*(e+f) 波兰表示是：abc**def+*+
即中缀转后缀
操作符栈和操作数栈
波兰表示的代码不易于代码优化
if 语句的波兰表示·
7.2 N元表示·
常用三元式和四元式
三元式·
间接三元式·
执行次序和三元式代码分成两张表进行表示
四元式·
7.3 抽象机代码·
许多 pascel 编译器生成的中间代码是称为 Pcode 的抽象代码。P 即为 Pseudo
Pcode实际上是波兰表示形式的中间代码
Pcode生成后，可以用解释执行程序来解释执行Pcode，也可以再把Pcode变成某一机器的目标代码
作业·
P144 1,2,3,4
八、错误处理·
8.1 概述·
错误的源程序可以通过编译发现并指出错误
正确则生成目标代码
错误处理能力·
侦察错误、报错及时准确、一次编译找出错误、改正能力、遏制重复报错信息
8.2 错误分类·
语法错误：源程序语法上不合乎文法
比如源文法：A::=B{+B} B::=C{*C} C::=a
而出现了 a+*a 这样的句子
语义错误：程序不符合语义规则或者超出了计算机系统的限制
8.3 错误的诊察和报告·
错误侦察·
违反语法和语义规则以及超出编译系统限制 ==> 语义分析需要借助符号表
下标越界 ==> 计算结果溢出以及动态存储数据区溢出
错误报告·
行号计数器 line_no，单词序号计数器 char_no
显示文字信息，给出错误编码
报告错误的两种方式·
- 分析完以后再报告(显示或者打印)
- 边分析边报告
8.4 错误处理技术·
错误改正：编译侦察出错误，根据文法改正错误
错误局部化处理：尽可能把错误影响限制在一个局部范围，避免其扩散影响
一般原则·
发现错误，暂停对后面符号分析，跳过错误所在语法成分
错误局部化处理实现·
递归下降实现
遇到错误，先打印信息，再跳出一段源程序，直到右界符或此语法成分的合法后继符号
目标程序运行时错误检测与处理·
- 下标变量下标值越界
- 计算结果溢出
- 动态存储分配数据区溢出
目标程序运行检测到这类错误，调用异常处理程序，打印错误信息和运行现场（寄存器和存储器中的值），然后停止程序运行
九、语法制导翻译技术·
9.1 翻译文法(TG)和语法制导翻译·
简单文法引入·
@+ @* @i 为动作符号。@为动作符号标记，后面为字符串
这个例子里，语义子程序功能是输出打印动作符号标记后面的字符串
比如$E\rightarrow E+T @+$的语义是分析E,+,T，输出+
比如$i\rightarrow i @i$的语义是分析i，输出i
输入文法·
未插入动作符号的文法，可以推出输入序列
翻译文法·
插入动作符号的文法
由翻译文法可以通过推导产生 活动序列，包含了输入序列和动作序列
例子·
比如用上面的文法推导(i+i)*i
先推导出活动序列
$E\Rightarrow T \Rightarrow TF@\Rightarrow FF@ \Rightarrow (E)F@\Rightarrow (E+T@+)F@$
$\stackrel *\Rightarrow (i@i+i@i@+)i@i@$
活动序列：由翻译文法推导出的由终结符和活动符号组成的符号串
抽去动作符号，可得到输入序列
抽去输入序列，可得动作序列
执行动作序列，完成翻译任务
语法制导翻译·
按翻译文法进行的翻译。给定一输入符号串，根据翻译文法获得翻译该符号串的动作序列，并执行该序列所规定的动作的过程
实现方法·
适当位置插入语义动作符号，当按照文法分析到动作符号就调用相应的语义子程序完成翻译任务
9.2 属性翻译文法(ATG)·
综合属性·
自底向上进行属性计算，所以称为综合属性，用$\uparrow$表示属性计算从下往上
可以改写文法为以下样子
综合属性其实就是一个计算数值属性的过程
继承属性·
类型和名字可以设两个综合属性，即
$Type_{\uparrow t}\ \ t存放类型值$
$id_{\uparrow n} \ \ n存放变量名$
填表动作符号也可以有属性
即$@set_table_{\downarrow t_1,n_1}$ 其中 $t_1,n_1$ 是从前面得到的，因此是继承属性，继承了前面的值
同理有变量表：$<变量表>_{\downarrow t_2}$ 相当于递归的时候能够知道最开始的类型是啥
这样就可以整理成以下的属性翻译文法
这时的语法树和之前有区别了
可见，继承属性求值：自左向右，自顶向下
综合属性求值：自右向左，自底向上
L-属性翻译文法（L-ATG）·
较简单的一种属性翻译文法，要求输入文法为LL(1)文法，可用自顶向下分析构造分析器，分析过程可进行属性求值
L属性翻译文法定义·
属性求值规则·
继承属性·
即，自顶向下，自左向右
综合属性·
即，自底向上，自右向左
简单赋值形式的L_属性翻译文法(SL-ATG)·
改写L-ATG为SL-ATG·
改成如下的样子
无参函数过程作为常数处理
9.3 自顶向下语法制导翻译·
翻译文法的自顶向下语法制导翻译——递归下降翻译器·
即在递归下降语法分析程序中加入处理动作符号，输出动作符号字符串的部分
属性翻译文法的自顶向下语法制导翻译——递归下降属性翻译器·
对每一个非终结符编写一个翻译子程序
继承属性==>声明为赋值形参
综合属性==>声明为变量形参，以指针或者地址的形式传参数到函数内，之后在函数内赋值后自然传回调用位置
属性名约定：产生式左部同名非终结符使用相同的属性名
具有相同值的属性取相同的属性名。这样可以删除属性求值规则
作业·
PPT42页例子
P166 1.(前缀式), 2, 3, 4, 5
十、语义分析和代码生成·
10.1 语义分析的概念·
10.2 栈式抽象机及其汇编指令·
graph LR a[栈式抽象机] a-->a1[指令寄存器] a-->a2[地址寄存器] a1-->一个 a2-->多个 a-->b[存储器] b-->b1[数据存储器-存放AR的运行栈] b-->b2[操作存储器-操作数栈] b-->b3[指令存储器]
10.3 声明的处理·
10.4 表达式的处理·
10.5 赋值语句的处理·
10.6 控制语句的处理·
10.7 过程调用和返回·
作业·
试设计Pascal记录变量（无变体）的属性翻译文法，并构造相应的语义动/作程序。
写出for语句在执行循环体之前先做循环条件测试的属性翻译文法及其处理动作程序
十一、词法自动化·
11.1 正则表达式·
正则表达式相等<=>这两个正则表达式的语言相等
正则表达式与3型文法等价
11.2 自动机·
11.2.1 DFA·
11.2.2 NFA·
在某个状态下，对于某个输入字符存在多个后继状态
11.2.3 NFA的确定化·
不确定的有穷自动机与确定的有穷自动机从功能上来说是等价的
定义1 集合I的$\epsilon$-闭包·
定义2·
11.2.4 DFA的最小化·
消除多余状态和合并等价状态
合并等价状态·
先根据终态和非终态拆分成两个区
再在每个区内分别根据每个符号的状态转移，划分更小的区
11.2.5 正则表达式与DFA的等价性·
四个都对
11.3 词法分析程序的自动生成器 —LEX（LEXICAL）·
词法分析程序包含状态转移矩阵和控制执行程序。
作业·
P254-255 1,2,4,5
十二、语法分析（提高部分）·
功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。
自顶向下分析法·
基本思想·
主要方法·
- 递归子程序法
- LL分析法
一般过程·
对于一个符号串，预测其为某一语法成分，根据其文法设法构造相应语法树
特点·
- 带预测
- 试探过程，可能会有回溯
- 最左推导可用程序实现，带回溯自顶向下分析方法实际上价值不大，效率低
LL分析法·
自左向右扫描，分析和匹配输入串。分析过程有最左推导的性质。
三部分组成：分析表，执行程序，符号栈（分析栈）
分析表：二维矩阵·
$A::=a_i$表示A去匹配输入串且当前输入符号为a时可以用A的第i个选择去匹配
$a_i\neq \epsilon$ 则 $a_i\Rightarrow a… $
$a_i= \epsilon$ 则 $a$ 为 $A$ 的后继符号
error表示不能匹配
符号栈·
开始、工作、出错、结束四种状态
1.执行程序·
-
把#和文法识别符号E推进栈, 读入下一个符号， 重复下述过程直到正常结束或出错。
-
测定栈顶符号X和当前输入符号a,执行如下操作:
2.分析表构造·
需要确定后继符号和能够推导出的符号==>$First$集和$Follow$集
构造FIRST集与FOLLOW集·
根据FIRST和FOLLOW集构造分析表·
3.LL(1)文法·
一个文法G，其分析表M不含多重定义入口(即分析表中无二条以上规则)，则称它是一个LL(1)文法。
可以证明：如果G是左递归的,或者是二义性的文法,则至少有一个多重入口。
自底向上分析法·
基本思想·
主要方法·
- 算符优先分析法
- LR分析法
基本算法思想·
若采用自左向右的描述和分析输入串,那么自底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的句柄(最左简单短语)，并利用有关规则进行归约，若能归约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。
分析过程·
关键是找到句柄
自底向上分析的一般过程（移进-归约分析）·
建立符号栈记录分析历史和现状，根据当前状态，确定下一步移进还是规约。
防止一个终结符可以被两个规则规约成不同句型，引入下列的分析法。
算符优先分析法·
预先规定相邻终结符之间的优先关系，利用这种关系来确定句型的句柄并进行规约
分析过程·
当栈顶(或次栈顶)终结符的优先级大于栈外的终结符的优先级，则进行归约，否则移进。
分析过程不一定是严格的最左规约（即不一定是规范规约），即每次规约不一定是规约当前句型的句柄，而是句柄的变形，即短语。
出错情况:
- 相邻终结符之间无优先关系
- 对双目运行符进行归约时,符号栈中无足够元素
- 非正常结束状态
算符优先分析法的进一步讨论·
(1) 算符优先文法(OPG)·
OPG－Operator Precedence Grammar
算符文法（OG）的定义：若文法中无形如$U∷ = ·¨VW·¨$的规则，这里$V,W∈V_n$ 则称G为OG文法，也就是算符文法。
优先关系的定义
若G是一OG文法，$a,b∈V_t , U,V,W∈V_n$ 分别有以下三种情况:
算符优先文法（OPG）的定义
设有一OG文法，如果在任意两个终结符之间，至多只有上述关系中的一种，则称该文法为算符优先文法(OPG)
几点说明
(2) 构造优先关系矩阵·
具体实现参看P14-第6张PPT
具体实现参看P15-第2张PPT
构造优先关系矩阵的算法·
(3) 算符优先分析算法的设计·
先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的**“句柄”并进行归约。这里的句柄指的是最左素短语**。
素短语：文法G的句型的素短语是一个短语，它至少包含有一个终结符号，并且除它自身以外不再包含其他素短语。
寻找最左素短语·
算符优先分析法的实现·
LR分析法·
概述·
从左到右扫描(L)自底向上进行归约® (是规范归约）, 是自底向上分析方法的高度概括和集中
三部分：状态栈，分析表，控制程序
状态栈：放置分析器状态和文法符号。
分析表：由两个矩阵组成，其功能是指示分析器的动作， 是移进还是归约，根据不同的文法类要采用不同的构造方法。
控制程序：执行分析表所规定的动作，对栈进行操作。
分析表的种类·
- SLR分析表(简单LR分析表) 最易实现，高实用价值
- LR分析表(规范LR分析表) 实用价值不大
- LALR分析表(超前LR分析表) 难度介于上述两者之间
使用SLR分析表进行语法分析的分析器叫SLR分析器。
使用LALR分析表进行语法分析的分析器叫LALR分析器。
例如UNIX的YACC，根据文法规则YACC源文件，得到某语言的LALR分析器
几点说明·
- 三种分析表对应三类文法
- 一个SLR文法必定是LALR文法和LR文法
- 仅讨论SLR分析表的构造方法
LR分析·
逻辑结构·
规范规约：规约当前的句柄
分析表1-状态转移表 (GOTO表)·
一个矩阵： 行—分析器的状态 列—文法符号
分析表2-分析动作表(ACTION表)·
控制程序·
LR分析过程例子·
构造SLR分析表·
- 根据文法构造识别规范句型活前缀的有穷自动机DFA
- 由DFA构造分析表
求LR(0)·
-
列出项目集
-
求出闭包
-
从初始状态
S'-->.S的闭包开始计算得到DFA
得到GOTO表和ACTION表·
GOTO表就是DFA
ACTION根据以下算法求解
作业·
p264:1,2,6，补充题
P279 2(2)，4, 5
P282
P288
P297 1，2，6, 9
P304 1
十四、代码优化·
14.0 概述·
进行优化必须严格遵循“不能改变原有程序语义”原则。
循环：程序中的8-2原则
优化方法分类1·
与机器无关的优化技术·
数据流分析 ，常量传播，公共子表达式删除，死代码删除，循环交换，代码内联等等
与机器相关的优化技术·
面向超标量超流水线架构、VLIW或者EPIC架构的指令调度方法；面向SMP架构的同步负载优化方法；面向SIMD、 MIMD或者SPMD架构的数据级并行优化方法等
特点：仅在特定体系结构下有效
优化方法分类2·
局部优化技术·
指在基本块内进行的优化
例如，局部公共子表达式删除
全局优化技术·
函数/过程内进行的优化
跨越基本块
例如，全局数据流分析
跨函数优化技术·
整个程序
例如，跨函数别名分析 ，逃逸分析等
14.1 基本块与流图·
基本块·
基本块中代码是连续的语句序列
程序的执行只能从基本块第一条语句进入
程序执行只能从基本块最后一条语句离开
算法14.1 划分基本块·
流图·
一般，编译器按照以下结构来组织代码，注意这里的程序在C语言里其实就是函数
graph LR 程序-->流图 流图-->基本块 基本块-->中间代码
14.2 基本块内优化·
常数合并与传播
运算强度削减（乘除优化）
删除冗余代码（死代码，无用代码）
消除公共子表达式·
基本块的DAG图表示·
DAG图的定义·
算法14.2 构建DAG图的算法-消除公共子表达式·
算法14.3 从DAG导出中间代码的启发式算法·
窥孔优化·
关注在目标指令的一个较短的序列上，删除冗余代码，或者用更高效代码替代
14.3 全局优化·
受到控制流影响
消除死代码，变量活性
主要手段：数据流分析
到达定义（reaching definition）分析·
基本块B的到达定义数据流方程·
算法·
活跃变量分析·
算法·
活跃变量分析——死代码删除、寄存器分配
到达定义分析——变量传播
定义-使用链、网和冲突图·
活跃变量到冲突图
变量的定义-使用链，是指变量的某一定义点，以及所有可能使用该定义点所定义变量值的使用点所组成的一个链
14.4 循环优化·
循环不变式的代码外提·
循环中不随循环改变的表达式
循环展开·
代码重复很多次，省去了条件判断和分支语句还有部分的自增语句
归纳变量的优化和条件判断的替换·
归纳变量: 在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值，则称该变量为归纳变量(induction variable)。
可以利用归纳变量对一些表达式做优化
inline展开·
某些函数可以内联形式展开
其他·
多重循环转单层 多个相同结构循环合并
作业·
1到6题
十五、目标代码生成·
15.1 现代微处理器体系结构简介·
1、栈式指令集架构·
2、累加器式指令集架构·
3、寄存器架构·
寄存器-寄存器架构·
1 | load $1 A |
寄存器-内存架构·
即地址可以作为操作数
1 | load $1 A |
12.2 地址空间·
12.4 寄存器的分配和指派作业·
引用计数·
给引用次数排序，前面的分配
图着色寄存器分配·
先利用活跃变量分析，每个基本块入口处活跃变量之间定义相互冲突
建立冲突图之后，使用Chaitin-Briggs算法进行图着色寄存器分配。
新编教材第十五章 1,4,5,6