考前总结 背景 必要性 作用 新旧版交替面临一些问题 从教学目标和要求说起 知识梳理 可能有助于提高考试成绩 或者让知识掌握得更好

知识梳理方法 过程性 抽象性 建立联系 补漏

过程性 源程序 Token流 DFA 3型文法 语法单位 LL(1)分析 LR分析 2型文法 语法树 中间代码 属性文法 运行时系统 4 优化代码 优化类别 CFG SSA 5 目标程序 寄存器分配

抽象性 推导 LL(1)文法 规范归约CFG文法 规范归约 算法优先文法 预测分析 LR分析表 移进归约框架 优先关系表 移进归约框架 递归下降分析

抽象性 单元的SIZE，对齐 单元的访问，偏移量 SP-TOP Calling Sequence p257 FP-SP Return Sequence 建立和退除 SP-TOP FP-SP SP-TOP-D DFA NFA r G 实现Scanner是否方便

建立联系 LL分析 推导 归约 LR分析 扩展语法树 归约语法树 语法树 语法单位及其之间的联系 二义性文法 带注释语法树 抽象语法树 语义分析 短语，直接短语，句柄

建立联系 布尔表达式 名字作用域 过程符号表 复合语句 拉链返填 分支循环 声明语句 属性文法 属性 属性方程 标号 控制结构 带注释语法树 过程调用 分步归约 四元组 栈帧 引入产生式 运行时栈

补漏 交叉编译器、前端/后端，遍 Token格式 文法修剪（消除左递归、消除回溯、拓广文法、引入产生式、分步归约） 有穷自动机与语言之间关系 自下而上的分析（LR(0), SLR(1), 算符优先文法） 中间表示（逆波兰、三地址码、AST、DAG） 符号表信息 运行时存储空间划分 基本块、CFG、局部优化概念

补漏：主要教学内容对照 引论 第一章 1.1-1.5 形式语言简介 第二章 2.1-2.3 第三章 3.1-3.3 词法分析 第四章 4.1-4.5 第五章 5.1, 5.2/5.3.1-3 第七章 7.1-7.6 第八章 8.1-8.4 第九章 9.1-9.5 第十章 10.2 引论 形式语言简介 词法分析 自顶向下语法分析 自底向上语法分析 中间代码生成 符号表 运行时存储空间组织 局部优化

举例：运行时栈 低 代码区 代码区 低 全局/ 静态区 全局/ 静态区 堆区 栈区 栈区 堆区 高 高 SP-TOP FP-SP

fp 访问链 控制链 返回地址 x:. 空闲区 chain sp p q r r←4[fp] r←4[r] x值：-6[r] program chain; procedure p; var x:integer; procedure q; procedure r; begin x:=2; ... if ... then p; end; r; q; p; end fp 访问链 控制链 返回地址 x:. 空闲区 chain sp p q r r←4[fp] r←4[r] x值：-6[r]

过程作为参数 实参是过程闭包 由IP和EP两个指针组成（对应书上的B1和B2） 形参超长处理 最外层过程（主程序）的活动记录中有啥？ 该层定义的变量？ 静态链、动态链的链尾 其他略去

例：将语句翻译成四元组 if x<y then x:=1 else while x>=y do x:=x-d E → i1 rop i2 { Gen(jrop,i1,i2,0); E.tc=nxq; Gen(j,-,-,0); E.fc=nxq; } C → if E then { bp (E.tc, nxq); C.chain := E.fc; } S → C S1 { S.chain := merg(C.chain, S1.chain); } Tp → C S1 else { q:=nxq; Gen(j, _, _, 0); bp(C.chain,nxq); Tp.chain:=merge(S1.chain,q);} S → Tp S1 { S.chain := merge(Tp. chain, S1.chain; } W → while { W.quad := nxq; } Wd → W E do { bp (E.tc,nxq); Wd.chain := E.fc; Wd.quad := W.quad ;} S → Wd S1 { bp(S1.chain,Wd.quad); Gen(j, _, _, Wd.quad); S.chain := Wd.chain;} S → A { S.chain := 0;} if x<y then x:=1 else while x>=y do x:=x-d

100 (j<, x, y, 0) 101 (j,-,-,0) 102 (:=,1,_,x) 103 (j,_,_,0) 104 (j>=,x,y,0) 105 (j,_,_,0) 106 (-,x,d,t1) 107 (:=, t1,_,x) 108 (j,_,_,104) 100 (j<, x, y, 102) 101 (j,-,-,103) 102 (:=,1,_,x) 103 (j,_,_,0) 104 (j>=,x,y,106) 105 (j,_,_,103) 106 (-,x,d,t1) 107 (:=, t1,_,x) 108 (j,_,_,104) S chain=105 S chain=105 Tp chain=103 Wd chain=105 quad=104 C chain=101 tc=104 fc=105 E W tc=100 fc=101 S E S chain=0 quad=104 chain=0 if x<y then x:=1 else while x>=y do x:=x-d

举例：NFA转DFA a a  a a  b b d d  c  c 5 5 1 1 2 3 4 3 7 7 2 6 6 4 8 9

举例：NFA转DFA a a  a a  b b d d  c  c 5 5 1 1 2 3 4 3 7 7 2 6 6 4 8 9

 举例：NFA转DFA a a  a a  b b d  c  c c b 5 5 1 1 2 3 4 3 7 7 2 8 9 2 6 6 4 8 9 c b

例：移进归约框架 Action 1 # (())# shift 13 #( ())# 133 #(( ))# 1334 #(() )# reduce X →() 135 #(X 1356 #(X) reduce X →(X) 12 #X reduce S →X accept

预祝新年快乐！考试取得好成绩！