有不少不考的内容就没有整理。很功利了就是说。
符号表
符号表的作用
符号表自创建后便开始被用于收集符号（标识符）的属性信息，不同阶段会有不同的信息。
语义分析中，进行上下文合法性检查。
目标代码生成阶段，是对符号名进地址分配的依据。
还需要体现符号的作用域与可见性信息。
符号表的常见属性
符号的名字：作为查询的关键字
符号的类别：常量，变量，函数符号，类名等
符号的类型：数据类型，函数类型等。（决定了存储格式与可进行的运算操作）
符号的存储类别和存储分配信息：存储在数据区or代码区，静态or动态，堆or栈。分配信息包括：数据单元的大小，相对存储地址的偏移位置等。
符号的作用域与可见性
符号表的实现
创建符号表：在进入一个作用域的时候会创建符号表。
插入表项：新的符号声明。
查询表项：引用符号。
修改表项：符号获得新的语义值信息时进行。
删除表项：符号不再可见/不再需要信息。
释放符号表空间：退出作用域。
可以用多种数据结构实现。
常见在语法分析同时创建，也可以在语法分析之后语义检查之前创建。
符号表体现作用域与可见性
拥有共同有效范围的符号所在的程序单元构成作用域，作用域之间要么嵌套要么不相交，该点所在作用域称为当前作用域，包含它的作用域称为开作用域。
- 只有开作用域能访问符号。
- 若一个符号被多个开作用域声明，则取最近的一个
- 新的声明只能出现在当前作用域
作用域与单符号表组织 ※
单符号表有以下特性：
- 嵌套的作用域共用一个全局符号表
- 每个作用域对应一个作用域号
- 仅记录开作用域中的符号（也就是说变成闭作用域之后会删掉该作用域中声明的符号）
哈希表的单符号表组织
- 括号内数字表示嵌套层数
- 顺序插入，所以离表头最近的就是最近的声明
线性单符号表组织
- LEV表示最外层的层号，之后往上叠加
- ADDR表示相对于基址的偏移（假定每个变量占一个单元的存储）从DX开始排
- SIZE表示过程在被调用时申请的空间大小，应取CX+局部变量的数目
作用域与多符号表组织 ※
多符号表有以下特性：
- 每个作用域有自己的符号表
- 需要维护一个作用域栈
自顶向下语法分析
基本思想
从开始符号进行推导，每次获得文法的一个句型，直到产生想要的句子（或者失败）
带回溯的自顶向下分析
两类非确定性：对哪一个非终结符进行推导，选择哪一个产生式。
采用最左推导可以消除第一类非确定性。
自顶向下预测分析
通过向前查看确定数目的单词符号，然后确定应该选择哪个产生式进行最左推导，这种方法称为自顶向下预测分析。
LL(1) 分析
First 集合和 Follow 集合
First集合：设上下文无关文法，对：
也就是说，First集合描述了一个符号可以推出的第一个终结符的集合。或者说，下一个可能出现的终结符是啥。
实际应用的时候，我们关注下面这个集合的First集合：
这个其实就是全部的终结符非终结符的集合，以及推导式右边的全部后缀（为什么要带上后缀，是因为推导过程中，会用后缀去推整个式子的First集合）
上课讲的时候并没有要求带后缀，和讲义里稍有差异。
计算方法
- 初始化，置所有终结符的First集合为它本身。其余置为空。
- 重复以下步骤直到收敛
- 对于所有后缀类型的符号，取First集合为顺序组成它的符号的First集合的并集，直到遇到一个First集合不包含的符号为止。
- 对于所有表达式左侧的非终结符，将其First集合并上它右边表达式的First集合。
总结：先把能确定的填好，之后两边来回捯饬。
Follow集合：对每个：
其中#代表结束符。直观理解就是，Follow集合定义了一个非终结符其后可能出现的第一个终结符。
计算方法
- 初始化，置，其余为空。
- 重复以下步骤直到收敛
- 顺次取一个产生式
- 令
- 若，则还要并上
注意：Follow集合根据定义是不会出现的。
总结：对于产生式右侧的每一个非终结符进行的操作，它的后一个可能是后面式子的First，也可能是整个产生式的Follow。
LL（1）文法
预测集合：对每个产生式，定义：
- 如果，那么
- 如果，那么
预测就是说，当我最左推导要从某个非终结符推导下去的时候，第一个推导出的终结符可能是啥。如果说First不为空那肯定就是First了，但是如果可能为空，那还得要考虑Follow。
LL(1)文法：任意两个产生式的PS集合交集为空。（这样就可以通过看句子里的下一个终结符来确定当前用哪条产生式了！）
LL（1）分析的实现
- 递归下降 LL（1）分析程序
就是根据lookahead来不断Parse和MatchToken的过程。
- 表驱动 LL（1）分析程序
就是根据PS的结果把选用的表达式填到表里。
分析过程如上，首先下推栈中只有#和S，然后不断根据余留符号串来选用合适的产生式。
文法变换：消除左递归、提取左公因子
消除左递归
左递归：。
为直接左递归，否则为间接。
对于直接左递归，可以先完成，再另设一个非终结符Q消A。
对于无回路（NO ），无产生式的文法，可以用下面的方法消除一般左递归：
- 按序排列
- 顺序遍历这些非终结符，如果有的情况，也就是排在后面的非终结符生成了排在前面的，就用来取代。最后消除的直接左递归。
- 化简
提取左公因子
提取后变成
自底向上语法分析
基本思想
从要分析的终结符串开始归约，每次寻找当前串中与某个产生式右部相匹配的子串，利用产生式进行替换。
可归约串：一个子串根据某产生式进行归约之后，得到文法的另一个句型（也就是说可以继续归约到底），那么称之为可归约串。
如果能总是选到可归约串进行归约，就可以大大减少回溯。
短语和直接短语
短语：且，则称是句型的一个短语。也就是说，一个句型中的可以归约到某个单个非终结符的子串。
寻找短语的方法是，利用分析树，每个非叶节点都对应这该句型的一个短语。从这个内部节点往下找，全部的叶节点就是它对应的短语。
直接短语：短语定义中的改成，也就是说，可以一步归约到某个单个非终结符的子串。
寻找直接短语的方法是，利用分析树，只包含直接子孙的非叶节点与直接短语一一对应。
（这里想到为啥要找直接短语，因为在一次归约中只能使用一个产生式，所以只能对直接短语进行归约。）
句柄
承接上文，对哪个直接短语进行归约呢。通常选择最左边的直接短语进行归约。最左归约对应着最右推导。
句柄：若且，则是右句型的一个相对于非终结符A的句柄。（其中）
句柄一定是相对于特定的非终结符而言的。
相比于直接短语，句柄的定义中多了最右推导，所以句柄是最左边的直接短语。（这个可以反证，如果左边还有一个，那么不可能跨过左边这个首先归约右边那个...说的好抽象）
但如果是二义文法，就需要画出全部分析树，也就可能导致多个句柄。
移进-归约分析
借助下推栈，分析引擎根据当前状态、下推栈中的内容、余留的输入符号串来唯一确定以下动作之一，然后进入新的状态：
- Reduce：归约（对于栈顶的短语）
- Shift：移进一个字符
- Error：语法错误
- Accept：分析成功
两类冲突：移进-归约与归约-归约，前者是不知道进行啥操作，后者不知道选哪个产生式进行归约。
无论采用什么技术，不可能找到通用的解决方法适用于任何文法来解决移进-归约冲突。
例如：
LR 分析方法
LR 分析基础
后续动作取决于，当前所期待的哪些句柄的哪些部分已经出现在了栈顶！
首先状态”0”包含，即栈顶为空但期待E，要期待E则必然先出现E+T或T，于是E+T和T也是期待的句柄，以此类推。
当某符号入栈之后，状态发生转移。根据入栈的符号来确定转移的方向（也就是选择的期待）。例如下面的描述：
就是说，当你期待一个非终结符的时候，你会期待所有能够归约到它的子串，这些都有可能出现在后面来使得你完成这个期待。而这些由一个期待引发的期待在栈中没有任何已有元素，只是期待而已。
这里没有考虑期待的句柄是针对哪个产生式，因为碰巧文法G[E]中产生式右边的符号串均不同，不会影响。之后应当考虑。
由此可以构造LR分析表，如下：
具体使用是需要构造两个栈：状态栈与符号栈，可以将状态栈与符号栈合并为分析栈。
使用方法为，根据当前栈顶的状态和余留串的首元素进行不同操作：
- ：移进该元素，并且切换到状态i
- ：使用第i条产生式进行归约
- GOTO：在归约时，从符号栈移除若干个元素，从状态栈移除相同多个状态，查看当前栈顶状态与栈顶元素，根据GOTO进行状态转移。
LR（0） 分析
针对LR(0)文法。向前查看0个元素就可以做出决定。
- 增广文法：引入
- 活前缀：是右句型的一个相对于非终结符A的句柄，则的任何前缀都是文法G的活前缀。
或者，它可以理解为针对w的分析过程中某时刻分析栈上的符号串。若活前缀中包含句柄全部符号，说明右部已出现在栈顶；若包括一部分或者不包括任何，则期待从输入串中看到该句柄未出现部分所推导出的符号串。
- LR（0）有限状态机
- 移进项目：
- 待约项目：
- 归约项目：
- 接受项目：
- 不断迭代直至收敛：
- CLOSURE(I)=J
LR(0)项目：产生式右端某一位置有圆点的产生式。圆点标志着已经分析过的串与该产生式匹配的位置。
可以根据圆点位置对项目进行划分：
LR(0)有限状态机的任一状态是某个项目集I的闭包CLOSURE(I)，计算过程如下：
特别的，初态为：
这个过程可以理解为：对于所有圆点后面的非终结符，期待能够归约得到它。需要收集能够归约得到它的表达式。
定义LR(0)有限状态机的转移函数为：
其中。就是说，在I状态下，如果接受到符号X，下面会期待的集合就是CLOSURE(J)。
把GO集合不断加入到状态集合C中，最后会收敛到一个DFA。
- 这个DFA的语言是增广文法所有活前缀的集合，只要不进到死状态，那么这些符号串就是某个右句型的活前缀。如果在最右推导中用到了，我们就说该项目针对活前缀是有效的。
这些项目集合构成的集合称为文法G的LR(0)项目集规范族。
之后由这个DFA来构建LR(0)分析表。
- LR（0） 分析表
- 对于，进行移进操作，即为sj
- 对于，进行归约操作，所有的ACTION都要记为rj
- 对于，ACTION[k,#]进行接收，记为acc
- 对于，即非终结符的情况，置
在没有多重定义的情况下，称G为一个LR(0)文法。
SLR（1） 分析
满足LR(0)的不多，条件太苛刻了。于是想到可以往前查看一位，在归约时只把Follow(A)的ACTION记为rj。（毕竟别的在这一步是不可能进行归约的）这样可以解决一部分的归约-归约冲突和移进-归约冲突。
语法制导的语义计算基础
基于属性文法的语义计算
属性文法
- 引子
在文法的基础上，为文法符号关联有特定意义的属性，并为产生式关联相应的语义动作或条件微词，称为属性文法。
语义动作一般形式：
复写规则：
- 综合属性和继承属性
对于产生式的语义动作，若是的某个属性，则称是的一个综合属性。（就是说，父节点的信息来自于子节点）
而如果b是产生式右部某个符号X的属性，则称为继承属性。
遍历分析树进行语义计算
步骤如下：
- 构造输入串的语法分析树
- 构造依赖图（就是说把所有的属性列成带标号的结点，之后根据依赖关系构建有向边。）
- 若依赖图无圈，则可按某种拓扑排序进行遍历。有圈则失效。
遍历分析树是有通用性的方法，但是是在语法分析之后进行的，希望能同时完成。但也不是所有属性文法都适合单遍处理，需要有所限制，如下两类：
S-属性文法和L-属性文法
S-属性文法：只包含综合属性，是特殊的L-属性文法
L-属性文法：对于产生式，每个语义动作涉及的属性或者是综合属性，或者是的继承属性，只能依赖于的继承属性，或者的属性。（就是它之前的符号）
基于S-属性文法的语义计算
在LR分析的基础上，加上一个语义栈，以元组的形式存放当前的语义。由于值包含综合属性，所以当分析到的时候，语义一定足以计算。
初始分析栈为（0#-），分别为初始状态、符号、语义值。
基于L-属性文法的语义计算
计算方法为：自顶向下深度优先遍历，同时从左到右计算每一个孩子的继承属性值，最后计算父节点的综合属性值。
基于翻译模式的语义计算
翻译模式
在形式上类似属性文法，但是允许{}的语义动作出现在产生式右端任何位置，来表达计算顺序。
S-翻译模式：还是只涉及综合属性，所以语义动作全部位于末尾。
L-翻译模式：语义动作不访问位于它右边的符号的属性。
基于S-翻译模式的语义计算
使用表示栈顶第i个元素（从0开始）。
基于L-翻译模式的自顶向下语义计算
假定基础文法是LL(1)文法。以递归下降分析程序为基础。改进后的称为递归下降（预测）语义计算程序（or翻译程序）
parseA的继承属性为形参，A的综合属性为返回值。（若有多个综合属性，可返回记录类型的值）
- 消除左递归后的翻译模式
基于L-翻译模式的自底向上语义计算
目的是消除所有的继承属性，只有综合就可以自底向上（变成S）。
一种方法是引入非终结符N和产生式。把嵌入的语义动作用产生式替换。
然而在集中关联有继承属性的时候情况更加复杂。一个原则是，继承属性求值需要以某个综合属性值存放在语义栈中，同时对继承属性的访问需要落实到对于综合属性的访问。
- 如果属性通过复写规则赋值，那么可以在栈中找到该值
- 如果属性是通过普通函数f(A.s)来求值，那需要让f(A.s)也在栈上，所以可以引入非终结符M。
- 有可能会出现不一致访问的情况。如下：
这个时候有可能在v[top-1]或者v[top-2]。不确定，所以需要引入新的非终结符M：
- 通常情况下会按序执行，先解决普通函数求值问题，再解决访问一致性。
静态语义分析与中间代码生成
静态语义分析
静态语义分析简介
静态语义检查：
- 控制流检查。例如跳转语句会跳到由标号指明的后续语句。例如break需要在循环语句内。
- 唯一性检查。
- 名字的上下文相关性检查。
- 类型检查。运算数与运算是否兼容。
类型检查
可维护程序中变量、表达式和其他程序单元的类型信息。
- 类型系统简介（不考）
- 借助翻译模式描述类型检查的实现算法
就是说在翻译模式的语句中插入类型检查的语句，一般是addtype(id.entry,)，loopup_type(id.name)之类。
中间代码生成
常见的中间表示形式
- AST：抽象语法树，改进形式为DAG（有向无圈图）
- TAC：三地址码or四元式
或者
- P-code
- Bytecode（Java虚拟机的输入）
- SSA（静态单赋值形式）
- 对于定值点重新命名，同样一个变量在多次赋值的时候进行重命名。
- 插入函数。在多个定值点合流时，需要判断使用哪个定值点。
单赋值的意思是程序中的名字只有一次赋值。也就是“定值点”。
所以获取SSA形式需要两个步骤：
DAG对AST的改进在于，对于执行同样动作的子树进行了合并。
生成抽象语法树
生成三地址码
- 声明语句的翻译
重点在于使得变量标识符的偏移地址信息可以保存至符号表。
全局变量：最重要的就是求出全局的offset，为了得到这玩意还需要一个综合属性width。
局部变量：注意在块内部，width为0，体现局部作用域。
- 数组声明和数组元素引用的翻译
- 包括第i维的上下界
- 数组元素类型
- 数组首地址
- 数组维数
- 存储空间
- 计算元素偏移地址时不变的部分
- （可以有一个相对于上下文基地址的偏移offset）
对于静态数组，内情向量放在符号表内；对于动态数组，需要在运行时建立内情向量。
使用以下方案进行数组存储分配：在堆区申请空间，在栈区使用两个单元，一个用于记录数组首地址元素，另一个记录数组存储空间大小。所以在声明的时候width需要改成2。生成TAC的时候使用alloc。
- 表达式的翻译
这里有一个叫做的东西，指的是存放E的值的存储位置（我觉得是里面的值），可以被赋值为某个确切的值。
- 布尔表达式的翻译
一种是可以直接对布尔表达式进行求值，1为true，0为false。
另一种是通过控制流体现布尔表达式的语义，即转移到程序中某个位置。（这样还可以得到短路代码而避免不必要的求值）
- 语句的翻译
- 利用S.next表示退出S是转向的语句标号，往往赋值给分支跳转的true和false。也可以是newlabel然后把它gen出来（这尤其用在多语句情况下）
- memo ‘XXX’ 这条语句是用来记录函数参数距离基址的偏移量
- 利用S.break确定循环体内break之后的去向，在不被while包围的语句中取任意标号，同时需要把break传递下去（需要在许多if之类包裹的语句跳出外层循环）。在while内则取S.next。
运行时存储组织
运行时存储组织的作用与任务
程序运行时存储空间的布局
主要分为代码区和数据区。但是一般需要划分为更多的逻辑区域，至少包含保留地址区，代码区，静态数据区，动态数据区。
存储分配策略
静态存储分配
编译时确定大小，简单但会带来存储空间浪费。
栈式存储分配
活动记录：参与栈式存储分配的存储单元。
编译过程中应能确定块活动记录大小的最大值，否则需要使用堆式存储管理。
堆式存储分配
存储分配算法：
- 最佳适应算法，即空间浪费最少
- 最先适应算法：最先找到的足够大的存储块
- 循环最先适应算法：起始点不同的最先适应。
活动记录
过程活动记录
过程活动记录指运行栈上的栈帧。（本讲义中的栈增长方向默认自下而上...好奇怪）
对于动态数组，需要一个保存一个内情向量，和起始位置的指针。
嵌套过程定义中非局部量的访问
- Display表（不考）
- 静态链与动态链
- 静态链（访问链）
- 动态链（控制链）
所有活动记录增加一个域，指向直接外过程运行时最新的活动记录
指向调用过程的活动记录。
嵌套程序块的非局部量访问（不考）
动态作用域规则 vs. 静态（词法）作用域规则
过程调用与参数传递
活动记录中与过程/函数调用相关的信息
参数传递方式
目标代码生成和代码优化基础
基本块、流图和循环
基本块
流图
循环
数据流分析基础
数据流方程的概念
到达-定值数据流分析
活跃变量数据流分析
几种重要的变量使用数据流信息
- UD链
- DU链
- 基本块内变量的待用信息
- 基本块内变量的活跃信息
Loading Comments...