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

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

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

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

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

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

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

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

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

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

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

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

11 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]

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

13 例：将语句翻译成四元组 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 S { 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 S { 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 S { 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

14 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

15 举例：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

16 举例：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

17  举例：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

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

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