HIT-编译系统笔记

御敌之策，成竹在胸

1 概述

Import *Note

2 文法

Import Automata.Note

符号约定

• 终结符：前几位小写字母
• 非终结符：前几位大写字母
• 文法符号：后几位大写字母
• 终结符号串：后几位小写字母（包括空串）
• 文法符号串：小写希腊字母

3 词法分析

• 词法分析器读入表示源程序的字符流，按照程序功能要求，转换为对应的单词序列，并剔除注释和空字符
• 词素/单词/token：程序设计语言中具有独立意义的最小语法单位
  • 编译的第一步即是利用词法分析器将源程序切分为单词
  • 单词在编译过程中不会被继续切分
• token序列二元组：(种别，属性值)

词法分析例题

例3.1 分词

• 写出token序列
• 哪些token具有关联的属性值？
• 应该具有什么值？

例3.2 符号表的名称字段为什么要设计成字符串表这种数据结构？

不同标识符的NAME字段长度往往不同，如果以变长存储，就会使得符号表的查询效率降低，增大符号表管理的难度； 而若是以定长存储，很显然必须为该字段按照最大长度分配空间，而造成空间的严重浪费.

4 语法分析

语法分析-概念

• 根据文法，识别成分然后构造语法树
• 以token作为终结符
• 寻求无二义性
  • 对任意CFG，不存在算法判定其二义性
  • 但是能给出一组充分条件，满足充分条件的文法是无二义性的
• 推导：自顶向下；规约：自底向上

最左推导&最右推导

最左推导总是选择每个句型的最左非终结符进行替换；如果$S\rArr _{lm}^* \alpha,$则$\alpha$是当前文法的最左句型。

相同地，有最右推导和最右句型。最右句型又叫规范句型，从而最左规约=规范规约，最右推导=规范推导。

最左推导&最右推导都是唯一的。

预测分析

• 预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数符号来选择正确的产生式。
• 对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类
• 预测分析不需要回溯，是确定的自顶向下的分析方法

Follow集合

非终结符$A$后继符号集合记作$Follow(A)=\{a|S\rArr^* \alpha A a\beta,a\in V_{Terminate},\alpha,\beta\in V_{All}\}$，表示在某个句型中紧跟在$A$后边的终结符$a$的集合； 如果$A$可能是某个句型的的最右符号，则将结束符\$$添加到Follow(A)$中；

Select集合

产生式$A\rarr \beta$的可选集$Select(A\rarr \beta)$是指可以选用该产生式进行推导时对应的输入符号的集合

• 如果$\varepsilon\notin First(\alpha),Select(A\rarr \alpha)=First(\alpha)$
• 否则$Select(A\rarr \alpha)=(First(\alpha)-\{\varepsilon\})\cup Follow(A)$

挺好理解的，当读到特定符号可以选定(Select)特定产生式的集合，正是如此

First集合

文法符号串$\alpha$的串首终结符集$First(\alpha)$是指可以它推导出的所有串首终结符构成的集合。如果$\alpha\rArr^*\varepsilon$，则$\varepsilon\in First(\alpha)$

计算算法：

• 不断应用以下规则，直到没有新的终结符或$\varepsilon$可以被加入到任何First集合中为止
  • 如果X是一个终结符，则$First(X)=\{X\}$
  • 否则，$X\rarr T_1\cdots Y_k\in P(k\ge 1)$，则
    • 如果$\exist i,a\in First(Y_i)\wedge (\forall j=1,\cdots i-1,\varepsilon \in First(j))$，则$a\in First(X)$
    • 如果$\forall j=1,2,\cdots k,\varepsilon \in First(Y_j)$,$\varepsilon\in First(X)$
  • 如果$X\rarr \varepsilon$,$\varepsilon\in First(X)$

一些文法

• S文法：简单确定性文法，要求每个产生式的右部都以终结符开始，同一非终结符的各个候选式的首终结符都不同，不含空产生式
• q文法：每个产生式右部或为空，或以终结符开始；具有相同左部的产生式有不相交的可选集(Select)

LL(1)

文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式$A\rarr \alpha|\beta$满足下面的条件：

1. 不存在终结符a，是的$\alpha ,\beta$均能推导出a开头的串
2. $\alpha ,\beta$至多一个能推导出空
3. 如果$\beta \rArr^*\varepsilon,$则$First(\alpha)\cap Follow(A)=\emptyset$；反之亦然。

第一个L表示从左向右扫描，第二个L表示最左推导；1表示每一步中只需要向前看一个输入符号来决定语法分析动作

递归与非递归方法

	递归方法	非递归方法
程序规模	大	主控程序规模小
分析表需求	不需要	需要
直观性	好	差
效率	低下	正比于长度
自动生成	难	容易

实现步骤

1. 构造文法
2. 改造文法：消除二义性、左递归、回溯
3. 求First和Follow集合，从而求Select集合
4. 检查是否为LL(1)文法，如果是，构造预测分析表
5. 对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法

错误预测

两种情况下可以检测到错误

1. 栈顶的终结符和当前输入符号不匹配
2. 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

恐慌模式是指，忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元集合中的某个词法单元；synch是指，如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符，则可根据相应非终结符的Follow集得到的同步词法单元

移入-归约分析

自底向上的分析，利用最左归约，反向构建最右推导

• 栈内符号串+剩余输入=规范句型
• 移入：将下一个输入符号移到栈的顶端
• 规约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
• 每次归约的符号串称为"句柄"
• 接收：宣布语法分析过程成功完成
• 报错：发现一个语法错误，并调用错误恢复子例程
• LR文法是最大的、可以构造出相应移入-归约语法分析器的文法类，L表示从左到右扫描，R表示反向构造最右推导
  • LR(k)文法表示需要向前查看k个输入符号的LR分析
  • k=0和k=1两种有实践意义，默认k=1
• LR分析器基于一些状态来构造自动机进行句柄的识别
• 有动作表和转移表

LR(0)分析

• 右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目），描述句柄识别的状态
  • 空产生式$A\rarr\varepsilon$只生成一个项目$A\rarr\cdot$
  • 同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目（如$A\rarr\alpha\cdot X\beta$的后继项目为$A\rarr\alpha X\cdot\beta$）
• 如果G是一个以S为开始符号的文法，则G的增广文法G'就是在G中加上新开始符号S'和产生式$S'\rarr S$而得到的文法
  • 增广文法使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态
• 规范句型的活前缀：不含句柄右侧任意符号的规范句型的前缀
  • LR自动机中从初始状态开始的每一条路径对应一个规范句型活前缀
• 如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法
• 不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法

LR(0)的Closure

可以把等价的项目组成一个项目集(I)，Closure(I)称为项目集闭包，每个项目集闭包对应着自动机的一个状态

$$Closure(I)=I\cup\{B\rarr\cdot\gamma|A\rarr\alpha\cdot B\beta\in Closure(I),B\rarr\gamma\in P\}$$

算法：

• $J=I$
• do
  • for ($A\rarr \alpha\cdot B\beta\in J$)
    • for ($B\rarr\gamma\in G.P$)
      • if ($B\rarr\cdot\gamma\notin J$)
        • $J+=B\rarr\cdot\gamma$
• until $J==I$ // 没有新项目加入
• return $J$

LR(0)的Goto

项目集$I$对应于文法符号$X$的后继项目集闭包记作$Goto(I,X)=Closure(\{A\rarr\alpha X\cdot\beta|A\rarr\alpha\cdot X\beta\in I\})$

⭐ LR(0)规范项集族

$$C=\{I_0\}\cup\{I|\exist J\in C,X\in V_N\cup V_T,I=Goto(J,X)\}$$

LR(0)分析表的构造

• 求规范项目项集族$C$ // C为自动机状态集合
• foreach $I_i\in C$
  • if($A\rarr\alpha\cdot a \beta\in I_i$)
    • 如有$I_j=Goto(I_i,a),Action[i,a]=s_j$ // $s_j$表示将符号$a$状态$j$入栈
  • if($A\rarr\alpha\cdot B \beta\in I_i$)
    • 如有$I_j=Goto(I_i,B),Goto[i,B]=j$
  • if($A\rarr\alpha\cdot\in I_i$)
    • if($A=S'$)
      • Action[i,\]=acc$//$acc$表示接受
    • if($A\not ={S'}$)
      • foreach a\in V_T\cup\{\}$
        • $Action[i,a]=r_j$ // $r_j$表示用第j个产生式进行归约,$j$是产生式编号

SLR分析

• LR(0)考虑了A的上文（规范句型的前缀），但未考虑A的下文，因此消解冲突能力有限
• 如果给定文法的SLR分析表中不存在有冲突的动作，那么该文法称为SLR文法
• SLR只是简单地考察下一个输入符号$b$是否属于与归约项目$A\rarr\alpha$相关联的Follow，但$b\in Follow(A)$只是归约$\alpha$的一个必要条件，而非充分条件

SLR基本思想

如果已知项目集合，$a_i$是移进项目的句柄中，点后第一个元素，$B_i$是规约项目中的产生式左部；如果$\{a_1,a_2,\cdots,a_m\}$和$Follow(B_1),Follow(B_2),\cdots,Follow(B_n)$两两不相交，则项目$I$中的冲突可以按照以下原则解决：

设a是下一个输入符号

• if$a\in \{a_1,a_2,\cdots ,a_m\}$，则移入a
• if$a\in Follow(B_i)$，则用产生式$B_i\rarr \gamma_i$归约
• else error

SLR分析表的构造

• 求规范项目项集族$C$ // C为自动机状态集合
• foreach $I_i\in C$
  • if($A\rarr\alpha\cdot a \beta\in I_i$)
    • 如有$I_j=Goto(I_i,a),Action[i,a]=s_j$ // $s_j$表示将符号$a$状态$j$入栈
  • if($A\rarr\alpha\cdot B \beta\in I_i$)
    • 如有$I_j=Goto(I_i,B),Goto[i,B]=j$
  • if($A\rarr\alpha\cdot\in I_i$)
    • if($A=S'$)
      • Action[i,\]=acc$//$acc$表示接受
    • if($A\not ={S'}$) // 注意此处和LR(0)的区别
      • foreach $a\in Follow(A)$
        • $Action[i,a]=r_j$ // $r_j$表示用第j个产生式进行归约,$j$是产生式编号

LR(1)分析

• 在特定位置，$A$的后继符集合是$Follow(A)$的子集
• 如果LR(1)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(1)文法
• LR(1)分析实际上是根据后继符集合的不同，将原始的LR(0)状态分裂成不同的LR(1)状态

规范LR(1)项目

将一般形式为$[A\rarr\alpha\cdot\beta,a]$的项目称为LR(1)项目，其中$A\rarr\alpha\beta$是一个产生式，$a$是终结符或者$$$，它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符。

• LR(1) 中的1指的是项的第二个分量的长度
• 对于$\beta\not ={\varepsilon}$，的情况$a$没有任何作用
• 对于$[A\rarr\alpha\cdot,a]$的项目只有在下一个输入符号为$a$时才可以按照$A\rarr\alpha$进行规约
  • 这样的$a$构成的集合总是$Follow(A)$的子集，且通常为真子集
• 如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的

LR(1)项目的后继符

设$[A\rarr\alpha\cdot B\beta,a]$，若有$B\rarr \gamma\in P$，则其有等价LR(1)项目$[B\rarr\cdot\gamma,b\,b\in First(\beta a)$。

• 当$\beta\rArr^+\varepsilon$时，$b=a$叫继承的后继符
• 否则叫自生的后继符

LR(1)的Closure

$$Closure(I)=I\cup\{[B\rarr\cdot\gamma,b]|[A\rarr\alpha\cdot B\beta,a]\in Closure(I),B\rarr\gamma\in P,b\in First(\beta a)\}$$

算法：

• $J=I$
• do
  • for ($[A\rarr\alpha\cdot B\beta,a]\in J$)
    • for ($B\rarr\gamma\in G.P$)
      • for ($b\in First(\beta a)$)
        • $J+=[B\rarr\cdot\gamma,b]$
• until $J==I$ // 没有新项目加入
• return $J$

LR(1)的Goto

项目集$I$对应于文法符号$X$的后继项目集闭包记作$Goto(I,X)=Closure(\{[A\rarr\alpha X\cdot\beta,a]|[A\rarr\alpha\cdot X\beta,a]\in I\})$

LR(1)规范项目项集族

$$C=\{I_0\}\cup\{I|\exist J\in C,X\in V_N\cup V_T,I=Goto(J,X)\}$$

其中I_0=Closure(\{[I_0,\]})$

LR(1)分析表的构造

• 求规范项目项集族$C$ // C为自动机状态集合
• foreach $I_i\in C$
  • if($[A\rarr\alpha\cdot a \beta,b]\in I_i$)
    • 如有$I_j=Goto(I_i,a),Action[i,a]=s_j$ // $s_j$表示将符号$a$状态$j$入栈
  • if($[A\rarr\alpha\cdot B \beta,b]\in I_i$)
    • 如有$I_j=Goto(I_i,B),Goto[i,B]=j$
  • if($[A\rarr\alpha\cdot,b]\in I_i$)
    • if($A=S',b=$$)
      • Action[i,\]=acc$//$acc$表示接受
    • if($A\not ={S'},b=a$) // 注意此处和LR(0)的区别
      • $Action[i,a]=r_j$ // $r_j$表示用第j个产生式进行归约,$j$是产生式编号

LALR分析

• 寻找具有相同核心的LR(1)项集，并将这些项集合并为一个项集(项目集的核心就是项目的核心的集合)
• 根据合并后得到的项集族构造语法分析表，如果分析表中没有语法分析动作冲突，给定的文法就称为LALR(1)文法，就可以根据该分析表进行语法分析
• 合并同心项集不会产生移进-归约冲突
• LALR分析法可能会作多余的归约动作，但绝不会作错误的移进操作
• 形式上与LR(1)相同，而大小上与LR(0)/SLR相同
• 分析能力介于SLR和LR(1)之间
  • 合并后的战亡父集合仍为Follow集合的子集

二义性文法的LR分析

• 每个二义性文法都不是LR的，但是某些类型的二义性文法在语言的描述和实现中很有用
• 这些二义性可以用优先级和结合性解决冲突
• 应该保守地使用二义性文法，并且必须在严格控制之下使用，因为稍有不慎就会导致语法分析器所识别的语言出现偏差

LR分析中的错误处理

LR分析中的恐慌模式

• 从栈顶向下扫描，直到发现某个状态$s_i$，它有一个对应于某个非终结符$A$的$Goto$目标，可以认为从这个$A$推导出的串中包含错误
• 然后丢弃0个或多个输入符号，直到发现一个可能合法地紧跟在$A$之后的符号$a$为止
• 之后将$s_{i+1}=Goto(s_i,A)$压入栈中，继续进行正常的语法分析
• 实践中可能会选择多个这样的非终结符A

LR分析中的短语层次

检查LR分析表中的每一个报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误,然后构造出适当的恢复过程

核心问题

二义性的消除

• 修改文法，引入新语法变量，细化表示范畴
• 引入原则/规则

例：

<stmt> -> if <expr> then <stmt>
        | if <expr> then <stmt> else <stmt>
        | other

if B_1 then S_1
if B_2 then S_2
else S_3

else该与哪个if配对？

1. 引入原则：就近匹配
2. 修改文法，引入新变量

<stmt> -> <matched_stmt> | <unmatched_stmt>
<matched_stmt> -> if <expr> then <matched_stmt> else <matched_stmt>
                | other
<unmatched_stmt> -> if <expr> then <stmt>
                  | if <expr> then <matched_stmt> else <unmatched_stmt>

回溯问题

• 提取左公因子：通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择;如此操作，可以使得每个非终结符的任意两个产生式体都没有公共前缀

见例4.1

左递归引起无穷推导

直接左递归修改为右递归

如

$$E\rarr E+T|T\\ T\rarr T\star F|F\\ F\rarr(E)|id$$

可通过消解为

$$E\rarr TE'\\ E'\rarr +TE'|\varepsilon\\ T\rarr FT'\\ T'\rarr \star FT'|\varepsilon\\ F\rarr(E)|id$$

一般形式：

$$A\rarr A\alpha_1|A\alpha_2|\cdots|A\alpha_n|\beta_1|\beta_2|\cdots|\beta_m \space (\alpha_i\not=\emptyset)$$

可化为

$$A\rarr \beta_1A'|\beta_2A'|\cdots|\beta_mA'\\ A'\rarr\alpha_1A'|\alpha_2A'|\cdots|\alpha_nA'|\varepsilon$$

间接左递归通过算法消除

不含循环推导$A\rArr^+ A$和$\varepsilon-$产生式的文法可通过算法消解间接左递归

算法的思想是通过代入法，将间接左递归化为直接左递归从而消去。

Input：不含循环推导$A\rArr^+ A$和$\varepsilon-$产生式的文法$G$ Output：与G等价的无左递归文法

步骤：

• 将$G$的所有语法变量排序为$A_1,A_2,\cdots,A_n$;
• for i = 1 to n
  • for j = 1 to i-1
    • 用产生式$A_i\rarr \alpha_1\beta|\alpha_2\beta |\cdots |\alpha_k \beta$ 替换每一个形如$A_i\rarr A_j\beta$的产生式
    • 其中，$A_j\rarr \alpha_1|\alpha_2|\cdots |\alpha_k$是所有的当前$A_j$产生式
  • 消除$A_i$产生式中所有的直接左递归

如：

$$S\rarr Ac|c\\ A\rarr Bn|b\\ B\rarr Sa|a$$

语法分析例题

从文法到LL(1)分析器的构造

1. 文法改造，消除二义性、回溯和左递归
2. 求各个产生式两端的First和Follow集合
3. 求各个产生式的Select集合
   • 三列，n行表，n为产生式数目。第一列为产生式左部，第二列为产生式，第三列为其Select集合
4. 判定是否为LL(1)文法，如果是，给出预测分析表
   • 第一列为产生式左部，其余列为输入符号，单元格为产生式

指出最右句型的句柄/短语

• 句柄就是每次归约时，被归约的符号串。
• 句柄也是最左直接短语
• 短语是语法树的一棵子树(包括本身)
• 直接短语是不含子树的语法树

求SLR项目集，Goto函数，构造分析表，判断冲突

1. 求项目集：从$I_0$开始，逐步构造
2. 计算Goto函数
3. 计算Action(注意$$$也可能在Follow中和acc)和Goto矩阵，生成分析表
4. 检查分析表中是否有冲突(即一个单元格是否有不止一个动作)

说明是LL的，但不是SLR的

分别构造分析表/状态集

求LALR项集族

从$I_0$开始，逐步构造；注意每一步都要求闭包

5 语法制导翻译

• 语义分析：静态检查
• 中间代码生成
• 语义翻译=语义分析+中间代码生成
• 语法制导翻译=语义翻译+语法分析
  • 使用CFG引导翻译，是面向文法的技术

语法制导翻译的基本概念

• 为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息
• 文法符号的语义属性值，是用与文法符号所在产生式相关联的语义规则来计算的；
  • 对于给定的输入串$x$，构建$x$的语法分析树，并利用与产生式相关联的语义规则来计算分析树中各结点对应的语义属性值
• 将语义规则同语法规则（产生式）联系起来要涉及两个概念：语法制导定义SDD和语法制导翻译方案SDT
• SDD:如果$X$是一个文法符号，$a$是$X$的一个属性，则用$X.a$表示属性$a$在某个标号为$X$的分析树结点上的值
• SDT:在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内
• 没有副作用的SDD又称属性文法，其仅通过其他属性值和常量定义属性值

文法符号的属性

综合属性

• 在分析树结点$N$上的非终结符$A$的综合属性只能通过$N$的子结点或$N$本身的属性值来定义
• 终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值

继承属性

• 在分析树结点$N$上的非终结符$A$的继承属性只能通过$N$的父结点、兄弟结点或其本身的属性值来定义
• 终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值

属性求值顺序-依赖图

• 描述了分析树中结点属性间依赖关系的有向图
• 结点为分析树结点的属性
• 边由被依赖结点指向依赖结点
• 如果图中没有环，那么至少存在一个拓扑排序

S-SDD和L-SDD

• 仅仅使用综合属性的SDD称为S-SDD；如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值，其可以在自底向上的语法分析过程中实现
• 在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左的属性定义称为L-SDD
  • 一个SDD是L-SDD，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：
    • 假设存在一个产生式$A\rarr X_1X_2\cdots X_n$，其右部符号$X_i(1\le i\le n)$的继承属性仅依赖于下列属性
      • $A$的继承属性
      • 产生式中其左边符号$X_1,\cdots X_{i-1}$的属性
      • $X_i$本身的属性，但其全部属性不能在依赖图中成环
• S-SDD都是L-SDD

S-SDD的SDT

• 将一个S-SDD转换为SDT的方法，是将每个语义动作都放在产生式的最后。
• 如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现

L-SDD的SDT

• 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
• 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端
• 如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现

L-SDD与非递归的LL

• 增加属性值（value）字段
  • 终结符的综合属性存放在其记录的属性值字段
  • 对于非终结符A，将继承属性和综合属性存放在不同的记录中
  • 增加动作记录用来存放语义动作代码的指针
  • 不光是动作记录，其实分析栈中的每一个记录都对应着一段执行代码

L-SDD与递归的LL

• 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值
• 对出现在A产生式右部中的每个文法符号的每个属性都设置一个局部变量
• 非终结符A的代码根据当前的输入决定使用哪个产生式

L-SDD与LR

• 给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

  • 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性， 并在产生式后端放置语义动作计算综合属性
  • 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记$M$都有一个产生式$M\rarr\varepsilon$
  • 如果标记非终结符$M$在某个产生式$A\rarr\alpha\{a\}\beta$中替换了语义动作$a$，对$a$进行修改得到$a'$ ，并且将$a'$关联到$M\rarr\varepsilon$上。动作$a'$
    • 将动作$a$需要的$A$或$\alpha$中符号的任何属性作为$M$的继承属性进行复制
    • 按照$a$中的方法计算各个属性，但是将计算得到的这些属性作为$M$的综合属性

• 修改后的SDT，所有语义动作都位于产生式末尾

语法制导翻译习题

给出下列表达式对应的注释语法分析树

已知依赖图，求拓扑排序

Auto()

判断是否满足S/L-SDD的要求，判断求值顺序

Auto()

设计S/L-SDD

Auto()

设计SDT

LikeLab()

// TODO 检查题型是否在考试中出现

6 中间代码生成

中间代码生成的基本概念

声明语句的翻译

任务：

• 收集标识符的类型等属性信息
• 并为每一个名字分配一个相对地址
• 名字的类型和相对地址信息保存在相应的符号表记录中

类型表达式：

• 基本类型
• 可以为类型表达式命名，类型名也是类型表达式
• 将类型构造符作用于类型表达式可以构成新的类型表达式
  • 数组
  • 指针
  • 笛卡尔积(元组)
  • 函数
  • 记录(结构体)

赋值语句的翻译

任务：

• 生成对表达式求值的三地址码
• 对于引用，还需要确定数组元素的存放地址，也就是数组元素的寻址

控制语句的翻译

翻译成跳转指令

⭐回填

生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时，才去填充这些指令的目标标号。

非终结符的综合属性

• $B.truelist$:指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
• $B.falselist$:指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号
• $S.nextlist$:指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

函数

• $makelist(i)$:创建一个只包含i的列表，i是跳转指令的标号，函数返回指向新创建的列表的指针
• $merge(p_1,p_2)$:合并两个列表，返回指向合并后的列表的指针
• $backpatch(p,i)$:将 i 作为目标标号插入到 p所指列表中的各指令中

编写要点：

• 文法改造
  • 在list箭头指向的位置设置标记非终结符M
• 在产生式末尾的语义动作中
  • 计算综合属性
  • 调用backpatch()函数回填各个list

中间代码生成例题

手动翻译为四元式序列

Auto()

注：四元式一般形式为$(op,arg_0,arg_1,res)$，$op$可选集合{=,+,-,*,/,j,jnz,nez,jROP}

控制流的翻译(回填)

Auto()

注意：

空产生式紧跟在某个语句块的后面，一般是要用于生成goto的，因此它会生成如下两句话：

N.nextlist=makelist(nextquad);
gen('goto _');

画符号表

画代码结构图

7 运行储存分配

运行储存分配的基本概念

• 使用过程(或函数、方法)作为用户自定义动作的单元的语言，其编译器通常以过程为单位分配存储空间
• 过程体的每次执行称为该过程的一个活动
• 过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录
• 在静态存储分配中，编译器为每个过程确定其活动记录在目标程序中的位置；过程每次执行时，它的名字都绑定到同样的存储单元
  • 数组上下界必须是常数
  • 不允许递归
  • 不允许用户动态建立数据实体
• 几乎所有针对这些语言的编译器都把它们的(至少一部分的)运行时刻存储以栈的形式进行管理，称为栈式存储分配
  • 当一个过程被调用时，该过程的活动记录被压入栈；当过程结束时，该活动记录被弹出栈
  • 这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间，而且允许以如下方式为一个过程编译代码：它的非局部变量的相对地址总是固定的，和过程调用序列无关
• 用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树
  • 树中的每个结点对应于一个活动。根结点是启动程序执行的main过程的活动
  • 在表示过程p的某个活动的结点上，其子结点对应于被p的这次活动调用的各个过程的活动。按照这些活动被调用的顺序，自左向右地显示它们。一个子结点必须在其右兄弟结点的活动开始之前结束
  • 当一个过程是递归的时候，常常会有该过程的多个活动记录同时出现在栈中
• 非局部数据的访问
  • 访问链
  • display表
• 参数传递
• 符号表

访问链

• 静态作用域规则：只要过程b的声明嵌套在过程a的声明中，过程b就可以访问过程a中声明的对象
• 可以在相互嵌套的过程的活动记录之间建立一种称为访问链(Access link)的指针，使得内嵌的过程可以访问外层过程中声明的对象

display表

• 嵌套层次显示表
• 是一个指针数组d，在任何时刻，d[i]均指向运行栈中最新建立的嵌套深度为i的过程的活动记录（在运行栈中可能存在多个嵌套深度为i的过程的活动记录）
• 如果要访问某个嵌套深度为i的非局部名字x，只要沿着指针d[i]找到x所属过程的活动记录，再根据已知的偏移量就可以在活动记录中找到x

维护：

• 每当开始一个新活动时都要修改display表。
• 而当控制从新活动中返回时，又必须恢复display表的状态
• 如果嵌套深度为np的过程p被调用，并且它的活动记录不是d[np]直接指向的的活动记录，则p的活动记录要保存d[$n_p$]原来的值，同时置d[$n_p$]指向p的这个活动记录
• 当p返回且它的活动记录被从运行栈中清除时，再将d[$n_p$]恢复为调用p之前的旧值
• 如果运行栈中存在多个嵌套深度为i的过程的活动记录，则通过这些保存的d[i]就将它们链接在了一起，但是d[i]始终指向当前活跃的那个活动记录

储存分配例题

画活动树

画访问链

画display表

8 代码优化

代码优化的基本概念

流图

• 基本块(Basic Block)是满足下列条件的最大的连续三地址指令序列，因此每个基本块由一组总是一起执行的指令组成
  • 控制流只能从基本块的第一条指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
  • 除了基本块的最后一条指令，控制流在离开基本块之前不会跳转或者停机
• 流图是一个有向图，它的每个结点是一个基本块
  • 从基本块B到基本块C之间有一条边当且仅当基本块C的第一条指令可能紧跟在B的最后一条指令之后执行

常用优化

• 删除公共子表达式
• 删除无用代码
  • 复制传播：在复制语句$y=x$之后尽可能地用$y$代替$x$
  • 无用代码：其计算结果永远不会被使用的语句
  • 常量合并：如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式
• 代码移动：对循环不变计算，在进入循环之前就对它们求值
• 强度削弱：用较快的操作代替较慢的操作，如用加代替乘
• 删除归纳变量：对于一个变量x ，如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c，那么x就称为归纳变量
  • 归纳变量可以通过在每次循环迭代中进行一次简单的增量运算(加法或减法)来计算
  • 如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个

基本块的优化

• 局部优化技术首先把一个基本块转换成为一个无环有向图
• 对每个具有若干定值变量的节点，构造一个三地址语句来计算其中某个变量的值
  • 倾向于把计算得到的结果赋给一个在基本块出口处活跃的变量(如果没有全局活跃变量的信息作为依据，就要假设所有变量都在基本块出口处活跃，但是不包含编译器为处理表达式而生成的临时变量)
  • 如果结点有多个附加的活跃变量，就必须引入复制语句，以便给每一个变量都赋予正确的值
• 对于形如a[j] = y的三地址指令，创建一个运算符为"[]="的结点，这个结点有3个子结点，分别表示a、j和y
  • 该结点没有定值变量表
  • 该结点的创建将杀死所有已经建立的、其值依赖于a的结点
  • 一个被杀死的结点不能再获得任何定值变量，也就是说，它不可能成为一个公共子表达式

数据流分析

• 一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术
• 在每一种数据流分析应用中，都会把每个程序点和一个数据流值关联起来
  • 程序点：流图基本块中的位置
• 语句的数据流模式
  • IN[s]:语句s之前的数据流值
  • OUT[s]:语句s之后的数据流值
  • $f_s$:s的传递函数，指一个赋值语句s之前和之后的数据流值的关系
• 基本快的数据流模式
  • IN[B]=IN[$s_1$]
  • OUT[B]=OUT[$s_n$]
  • $f_B$

到达定值分析

• 变量x的定值是(可能)将一个值赋给x的语句
• 如果存在一条从紧跟在x的定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被"杀死" (如果在此路径上有对变量x的其它定值d′，则称定值d被定值d′"杀死"了) ，则称定值d到达程序点p
  • 如果某个变量x的一个定值d到达点p，在点p处使用的x的值可能就是由d最后赋予的
• 语句的到达定值传递函数
  • $gen_d$:由语句d生成的定值的集合
  • $kill_d$:由语句d杀死的定值的集合
  • $f_d(x)=gen_d\cup(x-kill_d)$
• 基本块的到达定值传递函数
  • $gen_B$:由基本块B生成的定值的集合，基本块中没有被块中各语句"杀死"的定值的集合
  • $kill_B$:由基本块B杀死的定值的集合
  • $f_B(x)=gen_B\cup(x-kill_B)$
• 到达定值的数据流方程
  • IN[B]：到达流图中基本块B入口处的定值的集合
  • OUT[B]：到达流图中基本块B出口处的定值的集合
  • 方程
    • $OUT[Entry]=\emptyset$
    • $OUT[B]=f_B(IN[B]),B\not ={Entry}$
    • $f_B(x)=gen_B\cup(x-kill_B)$
    • $IN[B]=\cup_{P\prec B} OUT[P]$
  • $gen_B$和$kill_B$的值可以直接从流图计算出来，因此在方程中作为已知量

计算到达定值的迭代算法

• $OUT[Entry]=\emptyset$
• foreach $B,B\not ={Entry}$
  • $OUT[B]=\emptyset$
• while 某个OUT值发生了改变
  • foreach $B,B\not ={Entry}$
    • $IN[B]=\cup_{P\prec B} OUT[P]$
    • $OUT[B]=f_B(IN[B])$

活跃变量分析

• 活跃变量：对于变量x和程序点p，如果在流图中沿着从p开始的某条路径会引用变量x在p点的值，则称变量x在点p是活跃(live)的，否则称变量x在点p不活跃(dead)
• 活跃变量的传递函数
  • IN[B]=$f_B$(OUT[B])
  • $f_B(x)=use_B\cup(x-def_B)$
  • $use_B$:在基本块B中引用，但是引用前在B中没有被定值的变量集合
  • $def_B$:在基本块B中定值，但是定值前在B中没有被引用的变量的集合
• 活跃变量的数据流方程
  • IN[B]：到达流图中基本块B入口处的活跃变量的集合
  • OUT[B]：到达流图中基本块B出口处的活跃变量的集合
  • 方程
    • $IN[Exit]=\emptyset$
    • $IN[B]=f_B(OUT[B]),B\not ={Exit}$
    • $f_B(x)=use_B\cup(x-def_B)$
    • $OUT[B]=\cup_{S\succ B} IN[S]$
  • $use_B$和$def_B$的值可以直接从流图计算出来，因此在方程中作为已知量
• ud链：引用-定值链

计算活跃变量的迭代算法

• $IN[Exit]=\emptyset$
• foreach $B,B\not ={Exit}$
  • $IN[B]=\emptyset$
• while 某个IN值发生了改变
  • foreach $B,B\not ={Exit}$
    • $OUT[B]=\cup_{S\succ B} IN[S]$
    • $IN[B]=f_B(OUT[B])$
• du链：引用-定值链

可用表达式分析

• 如果从流图的首节点到达程序点p的每条路径都对表达式x op y进行计算，并且从最后一个这样的计算到点p之间没有再次对x或y定值，那么表达式x op y在点p是可用的
  • 在点 p上，x op y已经在之前被计算过，不需要重新计算
• 可用表达式的传递函数
  • $e\_gen_B$如果基本块B对x op y进行计算，并且之后没有重新定值x或y，则称B生成表达式x op y
  • $e\_kill_B$基本块B所杀死的U中的可用表达式的集合;如果基本块B对x或者y进行了(或可能进行)定值，且以后没有重新计算x op y，则称B杀死表达式x op y
    • U:所有出现在程序中一个或多个语句的右部的表达式的全集
  • $f_B(x)=e\_gen_B\cup(x-e\_kill_B)$
• 可用表达式的数据流方程
  • IN[B]：到达流图中基本块B入口处的可用表达式的集合
  • OUT[B]：到达流图中基本块B出口处的可用表达式的集合
  • 方程
    • $OUT[Entry]=\emptyset$
    • $OUT[B]=f_B(IN[B]),B\not ={Entry}$
    • $f_B(x)=e\_gen_B\cup(x-e\_kill_B)$
    • $IN[B]=\cap_{P\prec B} OUT[P]$
  • $e\_gen_B$和$e\_kill_B$的值可以直接从流图计算出来，因此在方程中作为已知量

生成集合的计算

• $e\_gen_B=\emptyset$
• foreach $z=x\space op\space y \in B$
  • $e\_gen_B+=x\space op\space y$
  • $e\_gen_B-=z^*$ // $z^*$表示和$z$相关的表达式

杀死集合的计算

• $e\_kill_B=\emptyset$
• foreach $z=x\space op\space y \in B$
  • $e\_kill_B-=x\space op\space y$
  • $e\_kill_B+=z^*$ // $z^*$表示和$z$相关的表达式

计算可用表达式的迭代算法

• $OUT[Entry]=\emptyset$
• foreach $B,B\not ={Entry}$
  • $OUT[B]=U$
• while 某个OUT值发生了改变
  • foreach $B,B\not ={Entry}$
    • $IN[B]=\cap_{P\prec B} OUT[P]$
    • $OUT[B]=f_B(IN[B])$

流图中的循环

• 支配结点：如果从流图的入口结点到结点n的每条路径都经过结点d，则称结点d支配(dominate)结点n，记为d dom n
  • 每个结点只支配它和它的后代结点
• 支配的数据流方程
  • IN[B]：到达流图中基本块B入口处的支配节点的集合
  • OUT[B]：到达流图中基本块B出口处的支配节点的集合
  • 方程
    • $OUT[Entry]=\{Entry\}$
    • $OUT[B]=IN[B]\cup\{B\},B\not ={Entry}$
    • $IN[B]=\cap_{P\prec B} OUT[P],B\not ={Entry}$
• 如果存在有向边$n\rarr d$，而d dom n，则该边称为回边
• 自然循环是一种适合于优化的循环，它满足以下性质
  • 有唯一的入口结点，称为首结点，它支配循环中的所有结点
  • 循环中至少有一条返回首结点的路径，否则，控制就不可能从"循环"中直接回到循环头，也就无法构成循环
• 给定一个回边$n\rarr d$，该回边的自然循环为{d，以及所有可以不经过d而到达n的结点}
  • d为该循环的首结点
• 如果两个自然循环的首结点不相同，则这两个循环要么互不相交，要么一个完全包含(嵌入)在另外一个里面
  • 最内循环 (Innermost Loops): 不包含其它循环的循环
• 如果两个循环具有相同的首结点，那么很难说哪个是最内循环。此时把两个循环合并

计算支配节点的迭代算法

• $OUT[Entry]=\{Entry\}$
• foreach $B,B\not ={Entry}$
  • $OUT[B]=N$ // N为全部节点
• while 某个OUT值发生了改变
  • foreach $B,B\not ={Entry}$
    • $IN[B]=\cap_{P\prec B} OUT[P]$
    • $OUT[B]=IN[B]\cup\{B\}$

计算回边的自然循环

• $stack=new(),loop=\{n,d\},push(n)$
• while $stack.any()$
  • $m=pop()$
  • foreach $p\prec m$
    • if $p\notin loop$
      • $loop+=p$
      • $push(p)$

全局优化

删除公共子表达式

• 可用表达式的数据流问题可以帮助确定位于流图中p点的表达式是否为全局公共子表达式

算法：

• foreach $s:z=x\space op\space y$
  • if $x\space op\space y$在$s$之前可用
    • 从s开始逆向搜索，但不穿过任何计算了$x\space op\space y$的块，找到所有离s最近的计算了$x\space op\space y$的语句
    • 建立新的临时变量$u$
    • 替换找到的语句$w=x\space op\space y$为$u=x\space op\space y;w=u$
    • 用$z=u$替代$s$

删除复制语句

• 对于复制语句s:x=y，如果在x的所有引用点都可以用对y的引用代替对x的引用(复制传播)，那么可以删除复制语句x=y

算法：

• 对每个赋值语句
  • 根据du链找出该定值所能够到达的那些对x的引用
  • 确定是否对于每个这样的引用，x=y都在IN[B]中(B是包含这个引用的基本块) ，并且B中该引用的前面没有x或者y的定值
  • 如果确定，删除之 ，且把找到的对x的引用用y代替

代码移动

循环不变计算的检测算法

1. 将下面这样的语句标记为"不变"：
   • 语句的各运算分量或者是常数
   • 或者其所有定值点都在循环L外部
2. 重复执行步骤3，直到某次没有新的语句可标记为"不变"为止
3. 将下面这样的语句标记为"不变"：
   • 先前没有被标记过，且各运算分量或者是常数
   • 或者其所有定值点都在循环L外部
   • 或者只有一个到达定值，该定值是循环中已经被标记为"不变"的语句

循环不变计算语句移动的条件

设$s:x=y+z$

• $s$所在的基本块是循环所有出口结点(有后继结点在循环外的结点)的支配结点
• 循环中没有其它语句对$x$赋值
• 循环中对$x$的引用仅由$s$到达

归纳变量的强度削弱

• 如果循环L中的变量$i$只有形如$i =i+c$的定值($c$是常量)，则称$i$为循环L的基本归纳变量
• 如果$j = c\times i+d$，其中$i$是基本归纳变量，$c$和$d$是常量，则$j$也是一个归纳变量，称$j$属于$i$族
• 每个归纳变量都关联一个三元组。如果$j=c\times i+d$，其中$i$是基本归纳变量，$c$和$d$是常量，则$j$相关联的三元组是$(i,c,d)$

归纳变量检测算法

• 扫描L的语句，找出所有基本归纳变量。在此要用到循环不变计算信息。与每个基本归纳变量$i$相关联的三元组是$(i,1,0)$
• 寻找L中只有一次定值的变量$k$，它具有这样的形式：$k=c'\times j+d'$,$c'$和$d'$是常量
  • 如果$j$是基本归纳变量，则$k$的三元组可被确定
  • 否则，可以利用$j$的三元组计算$k$的三元组

作用于归纳变量的强度削弱算法

对于每个基本归纳变量$i$，对其族中的每个归纳变量$j:(i,c,d)$执行下列步骤：\

1. 建立新的临时变量$t$。如果变量$j_1$和$j_2$具有相同的三元组，则只为它们建立一个新变量
2. 在前置节点的末尾，添加语句$t=c*i$和$t=t+d$ ，使得在循环开始的时候$t=c*i+d=j$
3. 在L中紧跟定值$i=i+n$之后，添加$t=t+c*n$。将$t$放入$i$族，其三元组为$(i, c, d)$ 4.用$j=t$代替对$j$的赋值

删除归纳变量

• 对于在强度削弱算法中引入的复制语句$j=t$，如果在归纳变量j的所有引用点都可以用对$t$的引用代替对$j$的引用，并且$j$在循环的出口处不活跃，则可以删除复制语句$j=t$
• 如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个

代码优化例题

画DAG

Auto()

画流图

手动优化

// TODO 手动优化

• 找出所有的全局公公子表达式
• 寻找每个循环中的归纳变量
• 寻找每个循环的全部循环不变计算

计算各种集合

Auto()

计算支配关系、画支配节点树、寻找自然循环

// TODO

目标代码生成:IIgnorable