词法分析

• 文法：

• 文法的定义：$$G=(V_T,V_N,P,S)$$,P为产生式集合，S为开始符号

• 递归性：文法左递归、文法右递归、文法递归

• 语言：

• 推导：
  • 直接推导（1步）、推导（n步）、广义推导（0到n步）
  • 最左推导（推导时只替换最左的VN）、最右推导（推导时只替换最右的VN）
• 句型与句子：
  • S广义推导出$$x\in(V_T\cup V_N)$$，则它为文法的句型（意为模板，因为它包含VN所以还可以继续生成下去）
  • S广义推导出$$x\in V_T$$，则它为文法的句子

• 语言的定义：文法G[S]产生的所有句子的集合，叫做文法G[S]定义的语言

• 文法与语言的分类($$RG\in CFG\in CSG\in UG$$)

• 无限制文法UG(0型)：生成式左部至少有一个VN，才能进行最基本的生成。
• 上下文有关文法CSG(1型)：$$\alpha_1A\alpha_2\rightarrow\alpha_1\beta\alpha_2$$，限制生成时的上文$$\alpha_1$$和下文$$\alpha_2$$。因此CSG中无$\epsilon$-产生式。
• 上下文无关文法CFG(2型)：$$A\rightarrow\beta$$，不限制上下文。

• 正规/正则文法RG(3型)：左线性文法($$A\rightarrow Bw$$)、右线性文法($$A\rightarrow wB$$)。编程语言基本属于这类。

• 词法分析的输出单词：(单词类别，单词值)

0. 正规式RE<->上下文无关文法CFG

• 对称化：如果RE为${a^n}$

1. 正规式RE<->正规文法RG

• 正规集：正规式产生的所有句子的集合
• 正规式运算：连接$\cdot$(可省略)、或$|$(可写为+)、闭包$*$
• 正规式表示：正规式表达为$$e_1e_2^*$$或者$${e_1e_2^n|n\geq0}$$
• 正规文法->正规式：
• 合成闭包(beta替换x，alpha变闭包)
  1. $$x=\alpha x|\beta\Rightarrow x=\alpha^*\beta$$
  2. $$x=x\alpha|\beta\Rightarrow x=\beta\alpha^*$$
• 合成连接
  1. $A\to aB且B\to b\Rightarrow A=ab$
• 正规式->正规文法：
• 使用$A\to ab\Rightarrow A\to aB和B\to b$，将原正规式全部拆解开。
• 再使用$A\to a^*b\Rightarrow A\to aA|b$转换（b可以为空串）

2. RE->NFA

• 正闭包$a^+=aa^*$

3. NFA->非最简DFA

• 此时DFA的每一个节点中，都存放了一个NFA节点集合
• 需要构造一个==状态-输入转换表==
• 转换方法：
• S不输入时能到达的所有节点，记作DFA的初始节点
• 对初始节点进行不同输入，计算节点的后继
• 如果出现了新的后继：对后继进行不同输入，计算节点的后继。（重复最后一条）
• 一般转换：（别看）

• 带$\epsilon$-边的转换：（别看）
• $\epsilon$-边表示无需输入（输入“空”）就能切换转移状态

4. 非最简DFA->最简DFA

• 消除无效状态：无法到达终结状态的状态。

• 合并等价状态：

• 将图中状态初始分为：终结状态集ST、非终结状态集SN（包含起始状态）

• 给定一个输入a，存在当前状态S1（属于X集中），其转移后的状态S2不在X集内，那么S1就被划分为一个单独集合

语法分析

语法树的基本属性

• 短语：子树的叶子节点
• 直接短语：子树的叶子节点，但是根节点必须直接连接叶子节点
• 句柄（最左直接短语）
• 素短语：短语中，包含终结符且不包含除自身以外的其他素短语。（因此我们先从最小的短语开始看）
• 最左素短语
• 最右推导中，==有二义性==的两种等价判断（最左推导同理）：
• 最右推导的某一次推导中，同时出现了多个可推导方向
• 最右推导最终可以形成多个语法树
• 证明文法==无二义性==（不会出现多个可推导方向）：
• 不出现多个可推导方向 <==> ==同一个左部A==的两种推导F1、F2，对应需要输入字符的可能集合S1、S2，不会有交集
• SELECT(A->$$\alpha$$) $$\cap$$ SELECT(A->$$\beta$$) = $$\empty$$

LL(1)文法与分析方法

• LL(1)文法：
• 最左推导。每次都在源字符串中，向左查看一个字符。
• 特点：无二义性。具体表现为：无左递归、无回溯。
• 证明文法是LL(1)文法 <==> 证明文法无二义性
  • 同一个A的sel集不会有交集，SELECT(A->$$\alpha$$) $$\cap$$ SELECT(A->$$\beta$$) = $$\empty$$
• 消除左递归：(c替换x，beta拆分变右递归)
• x->x$$\beta$$|c (x到x的递归是左递归) ==> x->cA A->$$\beta$$A|$\epsilon$ (A到A的递归不是左递归)
• 消除回溯的两种方法：
• 提取公因式：A->cA|cB|c|d ==> A->cA’|d A’->A|B|$$\epsilon$$
• 使用拓展的BNF（EBNF）改写，方便yacc分析：
  • {a}表示0~n次
  • [a]表示可选择项（可有可无）
  • a(x|y|z)表示a为提取出的公因式
• 分析方法（从上至下的分析）：
• 递归下降分析
• 预测分析（即LL(1)分析）

从上至下的分析

基础属性

• FIRST(A)：A为根的子树，形成的叶子节点中的最左的终结符集合。即，A的短语中的最左终结符集合。
• FOLLOW(A)：A的短语之后出现的第一个终结符。
• A->aB或者A->aB$$\beta$$（$$\beta$$==$$\epsilon$$）：
  • 也就是说，B后紧挨着的终结符就是A紧挨着的终结符，所以FOLLOW(B) = FOLLOW(A)
• A->aB$$\beta$$（$$\beta$$=/=$$\epsilon$$）：
  • 若b为终结符：则FOLLOW(B) = $$\beta$$
  • 若b为非终结符：则FOLLOW(B) = FIRST($$\beta$$)/{$$\epsilon$$}，即去掉$$\epsilon$$的FIRST($$\beta$$)
• SELECT(A->$$\alpha$$)：选择该文法时，需要输入字符的可能集合
• 若该文法有路径可以直接推导至$$\epsilon$$：SELECT(A->$$\alpha$$) = FIRST($$\alpha$$)/{$$\epsilon$$} $$\cup$$ FOLLOW(A)
• 若该文法不会直接推导至$$\epsilon$$：SELECT(A->$$\alpha$$) = FIRST($$\alpha$$)

1. 递归下降分析

• 函数A()就代表非终结符A
• 进入A时：调用A()
• 在A中遇到终结符a：if(ch == a){...}
• 在A中遇到终结符$$\epsilon$$：if(ch不属于FOLLOW(A)) error()

2. LL(1)分析

• 移进-规约

• 移进：字符被逆序移进到栈中

• 规约：有推导A->abc，如果移进c后，栈顶存在abc则可以规约为A
• 根据文法建立一个映射矩阵：规约串（纵轴）->规约结果（横轴），比如abc->A

自下而上的分析方法

1. 算符优先分析

• 只适用于算数表达式，不适合复杂语法
• 优先关系（可以表达语法树中的==左右次序与深度==）
• $a<\cdot\;b$：符号a在符号b左边，且a“浅于”b
• $a\;\cdot> b$：符号a在符号b左边，且a“深于”b
• $a=b$(等号中间有一点)：符号a在符号b左边，且a与b同深度

• OPG文法（即算符优先文法）：

• 任意两个算符间的优先级是确定唯一的

• 最左素短语：P->AabcdB的最左素短语为abcd，因为最左的aB、中间字符优先级相等
• 基础属性
• FIRSTVT(A)：以A为子树根，与它==直接相连的、最左边==的非终结符
• LASTVT(A)：以A为子树根，与它==直接相连的、最右边==的非终结符

• 算符优先表的构建

• 为每一个非终结符计算FIRSTVT、LASTVT

• 对于E*T来说，LASTVT(E) > * < FIRSTVT(T)
• 结束标记的优先级：\$ < FIRSTVT(S),LASTVT(S) > $,\$==\$
• 建立优先关系表（一个对称矩阵）

• 算符优先分析

• 原理：将字符逆序移进栈中，然后不断地试图规约最左素短语

• 在栈中找最左素短语
  • 先找尾（最左素短语中的最右字符）
  • 再找头（最左素短语中的最左字符）
  • 找不到头尾就继续移进字符，找到就开始规约
• 规约最左素短语
  • 无需指明规约到什么符号中，因为该算法不关心非终结符，只关心终结符的位置
  • 因此==随便起一个名字N作为规约名就行==

2. LR(0)分析

• LR(0)分析：ACTION表与GOTO表的使用

• s代表shift(移入)，sn表示先移入符号
  • 查ACTION(该状态，输入字符) == sn：将输入字符移入栈中，并切换到==状态n==

• r代表return(规约)，rn表示移入符号

  • 查ACTION(该状态，输入字符) == rn：首先使用==第n号产生式==进行规约，将规约符号移入栈中，并==撤回到上一个状态==
  • 查GOTO(上一个状态，规约符号) == m：切换到新状态m

• 基本属性

• LR(0)项目：移进项目、待约项目、规约项目

• 增广文法：目的是统一开始符号数量为1个

  • 仅更改原先的初始生成式S->...，就可以把原来的文法变为增广文法。

  • 将{S->...,S1->...}更改为{S’->S|S1,S->...,S1->...}即可。

• 等价项目：

  

  • 其中$S'\rightarrow\cdot S$中提及了$\cdot S$，而$\cdot S=S\rightarrow\cdot BB$，因此它们相互等价
  • 其中$S\rightarrow\cdot BB$中提及了$\cdot B$，而$\cdot B=B\rightarrow\cdot aB和\cdot b$，因此它们相互等价
  • 等价的生成式均被包含在同一个项目集闭包（对应自动机的一个state）

• 自动机状态图构造

• 边上是一个非终结符，表明这是一个GOTO动作

• 边上是一个终结符

  • 当前状态有出边：表明这是一个ACTION移入动作，写sn
  • 当前状态无出边：表明这是一个ACTION规约动作，这一排都写rn

• LR0冲突问题：一个项目集闭包内，同时出现了冲突项目

• 类型：移进/规约冲突、规约/规约冲突

• 如果LR0分析表中无冲突，就叫LR0文法。

3. SLR(1)分析

• 额外考虑FOLLOW集约束，只能解决部分LR0冲突。

• 消解部分LR0冲突

• 若项目集存在$$A\rightarrow\alpha\cdot a\beta$$和$$B\rightarrow\gamma\cdot$$（一般不止一个冲突生成式），下一个输入字符是a

• 前提：若干FOLLOW(B)集合、{若干a}之间互不相交。其实就是各自的FOLLOW(点)集合不相交

• 解决方法：若a属于若干FOLLOW(B)集合，则使用B规约；若a属于{若干a}，则将a移入栈。此外就报错。

4. LR(1)分析

• 额外考虑后继符集合（FOLLOW的子集）约束，可解决所有LR0冲突。

• 基本属性

• LR(1)项目：形如$$[A\rightarrow\alpha\cdot\beta,a]$$，前者为产生式，后者表示==产生式后必须紧跟该终结符==（称为展望符）

  • 也就是说：发生冲突时，必须往后再看一位输入符号，如果满足展望符要求，才能做相应操作

• 等价项目：

  

  • b的取指有两种情况：
  • 若beta不为空，则b就属于beta的FIRST集（自生的后继符）
  • 若beta为空，那么b直接等于A的展望符（继承的后继符）
  • 合起来就是$$(b\in FIRST(\beta)或者b=a)\Rightarrow(b\in FIRST(\beta a))$$

语法制导翻译SDT

• 语法制导定义SDD：一个产生式附加一个对应的语义规则
• 语法制导翻译方案SDT：在产生式右部嵌入一个程序片段（即嵌入语义动作），嵌入位置表明其作用时机

1. 语义分析

• 继承属性与综合属性：前者用于”自上而下传递信息“，后者用于”自下而上传递信息“
• 属性文法：无副作用的SDD

2. 中间代码生成

• 常见中间语言：逆波兰式、三元式和树形表示、四元式和三地址代码。
• 波兰转逆波兰：(a+b)*c => ab+c*
• 先画表达式树，注意单目运算的符号是@
• 波兰式即中缀树，逆波兰式即后缀树

• 三元式、间接三元式与树形表示

• 三元式形式：(i) (op,src1,src2)

• 间接三元式的目的是优化时减少改动三元表顺序，需要使用间接码表来记录记值顺序。

• 四元式与三地址代码

• 四元式形式：(i) (op,src1,src2,res)

• 等价的三地址代码形式：(i) res = src1 op src2

符号表

• 符号表的组织
• 名字栏(标识符名，或称关键字)
  • 三类组织方式：直接方式、间接方式、按标识符种属
• 信息栏(名字有关、标志位)
  • 两类组织方式：固定信息内容、仅记载信息地址
• 符号表的建立与查找
• 线性表
• 二叉树与二分查找
  • 符号表需要有序存储，比如名字栏按名字大小顺序排列
• hash法与hash查找
  • 需要设置一个hash函数，比如设M为某素数，Hash(K)=K%M

代码优化

• 优化目标代码（机器相关）：窥孔优化
• 优化中间代码（机器不相关）：局部优化、循环优化、全局优化

1. 基础优化策略

• 删除公共子表达式：删除相同表达式，仅引用第一次计算的结果
• 代码外提：循环内不变运算提到循环体外
• 强度削弱：不改变运算结果，但减少运算时间
• 减少循环变量：如果一个非循环变量A，与循环变量i存在线性关系，则直接用A起到循环变量的作用，删掉i
• 合并已知量：在编译时就直接计算，此时可以确定的量
• 复写传播
• 删除无用赋值

2. 局部优化

• 基本块划分————局部优化的基本单元
• 入口：入口为程序第一个语句，或由转移语句转移到的语句（条件为真语句/无条件跳转目标），或紧跟条件转移语句的语句（条件为假语句）
• 出口：从入口后继续扫描，出口为下一个入口语句的上一条语句，或转移语句本身，或停语句本身。
• 无效语句：未被纳入基本块中的语句，永远执行不了，可以直接删除

• 流图

• 首节点：程序第一条语句

• 后继：紧接着执行（并且==块最后不是无条件跳转==）、条件转移、无条件转移时的基本块
• AST（语法树）的DAG：略

• 基本块的DAG

• 节点附加标记T：表示T=节点的值，或者表示T=节点表示的跳转地址（赋值附加）

• A:=B[C]的DAG
• D[C]:=B的DAG
• if A rop B goto C的DAG

• 基本块优化：

• 将每一条四元式/三元式，化成一个DAG

• 对每一个DAG：
  • 合并已知量：叶子都是已知量。比如已知T0:=3.14的节点，现在有一条T1:=2*T0语句，放弃添加“*“新节点，直接创建6.28节点
  • 删公共子表达式：若待添加的节点的叶子，和已经添加过的节点一致，则可以直接用”赋值附加标记“代替
  • 删除无用赋值：如果先后赋了两次值，则前一次多余，”赋值附加标记“需要被后一次覆盖
• 根据DAG重写四元式（有”赋值附加标记“的才能重写）
  • 如果一个节点上有几个标记，只需要重写一个标记就行，其他的直接赋值过去。
  • 如果基本块结束后，有标记A是活跃的，那么与A无关的中间变量可以去除，有关的已知中间变量可以直接替换。

运行时存储组织与管理

• 存储环境：完全静态环境、基于栈的存储环境、基于堆的存储环境

• 存储空间：目标区、静态数据区、栈区、堆区

• 静态存储分配

• 所有数据都是静态的，在编译时就能确定全部数据大小，从而提前安排好数据存放位置

• 栈式存储分配（动态）

• 存储空间是一个栈，调用函数时，就压入一个栈帧；结束时就弹出栈帧
• 堆式存储分配（动态）
• 如果程序语言允许自由分配和释放空间，则一定不是“FIFO”结构，因此需要堆式存储分配

目标代码生成

• 形式：机器语言代码、待装配的机器语言模块、汇编语言程序
• 待用信息与活跃信息：四元式i对变量A定值，中途没有A的其他定值点，而后面四元式j引用了A的值，则称“A是活跃信息”、“j是i中的变量A的待用信息”
• 寄存器分配的三个状态：
• 变量A确定，且已经在寄存器R1中，则直接读取
• 变量A确定，但在其他存储单元中，可以调入空闲寄存器R1，再读取R1
• 变量A确定，但在其他存储单元中，而且没有空闲寄存器（把R1的值X保存起来，把A调入R1，使用后将值X恢复到R1中）