统统必考。

第五章 语法制导定义

前言：

• 语法制导定义说的就是一个表格。在这个表格中，给每一个文法产生式赋予一个具体的含义（叫语义）。

• 请注意，光有语法，我们不知道语义。你可能说你看到一个文法就能猜到它是什么含义（比如S->L.R, L->LB, R->BR, B->0|1，这一看就是个二进制数），但这是你猜的。我完全可以赋予它另外一个含义（输出另外的结果）。

• 所以为什么第四章语法分析之后紧接着是语法制导定义。因为在这里我们给语法赋予语义。

考法：

• 判断继承属性、综合属性

  • 继承属性：要让写原因文字叙述：该节点属性值由其父亲兄弟节点属性值决定。
  • 综合属性：该节点属性值由其子节点属性值决定。

• 判断S属性定义、L属性定义

  • S属性定义：只用到综合属性（理解：自下而上一遍得出结果）
  • L属性定义：计算规则只依赖：出现在它左侧的符号的综/继

• 画注释分析树

  • 如果让用题里给的语法制导定义or翻译方案进行翻译，就画树即可。（验证自己设计的翻译方案同理。）

• 画依赖图

  • 树边是虚线
  • 依赖关系用实线箭头表示。
  • 来个例题：
    

• 画语法树

• 画dag（在语法树的基础上把相同的节点捏一块）

第五章 设计翻译方案√

语法制导定义与翻译方案的区别
如果题目让写出语法制导定义，那么列如下形式的表

产生式	语义规则
S→？？	S.??=??

如果让写翻译方案，那么在表格的基础上写出翻译方案。继承属性放前边，综合属性放最后。

做题方法是先找个例子（给定文法能接收的字符串），然后根据例子画分析树，猜出每个节点需要记录哪些信息。最后画出表格，根据表格写方案。

对于同一个文法，给出不同的翻译方案（语义规则），最终就可以得到不同的结果。下面来看几个文法的常见文法。

文法一：(a,a)式文法
文法形式化描述：

问题：

1. 输出配对括号个数

2. 输出a的最大嵌套深度
   

3. 输出每个a的嵌套深度
   

4. 输出每个a在串中的位置
   

5. 输出位置，最后输出a的个数
   

6. 对于每个a，输出位置和嵌套深度。最后输出字符串长度，a的个数
   

文法二：二进制数文法
形式化描述：

问题：

1. 输出十进制数值
   

2. 输出每个1的权值（如4，2，1，0.5……）
   

补充：如果善良点，文法可改为S→L.R，这样就把小数点前后区别开了。

第六章 语义分析-类型表达式（仅记录，没说考）

第七章 参数传递 √

当属最不费力的题型了，只需画表。

此处只展示例题：

第七章 运行栈、display表 √

前言：

1. 为什么这些在C语言中都没遇到过？因为C语言不允许函数嵌套。所以函数外的非局部名字一定是全局变量，所以访问链 只能指向 全局区。这还考什么画法？
2. 为什么访问链要画在栈上？答：过程能访问到的名字与该过程怎么激活的有关。（特指递归调用，总能访问 最新的 活动记录的内部名字）

解题方法：

先画一个栈。

• 栈帧的顺序：画一个活动树，有助画栈帧。
• 每个栈帧中有（从上到下）：函数名，形参，控制链，访问链，局部变量

再连访问链、控制链。

• 控制链的作用是恢复调用者运行环境。 所以是谁调的，就连到谁身上。
• 访问链的作用是找非局部名字。 7.3节专门介绍访问链的连接方式。
  • 如果 调用者深度 == 被调者深度，二者指向同一个外围
  • 如果 调用者深度 + 1 == 被调者深度 ，被调者指向调用者
  • 如果 调用者深度 == 被调者深度 + r，沿着调用者的访问链向前走r个节点，得到的指针复制给被调者。
  • 以上三条是理论，通通不用看，瞪眼法指向直接外围过程就好了。

但为什么还要把理论贴这里呢。因为还有个升级版：D表画法

• D表将深度相同的函数对应的栈帧连成了一个链表
• 最外围过程（一般是main）的深度认为是1（不是0，记住）

例题1：来源：课件

画出第一次进入exchange(1,3)时的运行栈。

例题2：来源：教材7.4

考虑如下pascal程序：

请为f的活动记录建立访问链
答案：

例题3：来源：教材7.5

考虑如下pascal程序：


答案：
（1）输出结果是2.（重点：那么多个m，f中能访问到的是哪个？——是过程c中的局部变量m）

display表有个问题，待解决。

第八章 写三地址代码

前言：不难。

翻译方案是看不懂的，瞪眼法做一下吧。可能出现的源代码有以下几个语法：

普通赋值语句转三地址

例题：
x:=a+b*y，x和y的类型是real，a和b的类型是int

分析：
计算顺序是by，a+by，x:=a+by
运算符两边类型不等就要转换，如inttoreal，并且运算符分为int+，real+，int，real*

结果：

t1:=inttoreal b
t2:= t1 real* y
t3:= inttoreal a
t4:=t3 real+ t2
x:=t4

数组转三地址

例题：
A[x]
B[y, z]

定义：A:array[2…5] of integer
B:array[1…10, 1…20] of integer

分析：
算常数：A的常数是24=8，B的常数是（120）* 4=84
算格子数：A是x，B是y * 20+z
写三地址代码时，先算格子数，再算base，然后格子数乘域宽

结果：

t1=x
t2=A-8
t3=t1*4
t4=t2[t3]


t1:=y*20
t1:=t1+z
t2:=B-84
t3:=4*t1
t4:=t2[t3]

布尔表达式转三地址（回填法）

例题：
a>b and c>d or e<f

分析：
画一个叠叠图，找各表达式出口。goto哪可以看出来。但要是让画注释分析树就得 真会回填法了。

结果：

if (a>b) goto ___
goto ___
if (c>d) goto ___
goto ___
if (e<f) goto ___
goto ___

我发现注释分析树也能通过答案反推 （毕竟我们是拥有智慧的活人）

首先树的形状得会。这些注释，就看**翻译到这一句时，哪些行的goto还是空着的。**比如二层左边那个E，是第104句及之前。104句前，101、102、103的goto空着，那么就是这三个出现在注释中。

if-else转三地址

例题：
if (a>b) A1 else A2

结果：
if (a<b) goto ___
goto ___
【A1’s code……】
goto L:
【A2’s code……】
L: ……

while转三地址

例题：
while (a<b) {
A3
}
A4

结果：
L: if (a<b) goto ___
goto ___
【A3’s code……】
goto L

for转三地址

例题：
for (i=1; i<=m; i++)
A1;
halt
结果：
i=1
L: if (i>m) goto halt
【A1’s code……】
goto L
halt

大例题：

模块化。分为五坨东西：

1. 布尔表达式（a>b and c>d aor e<f）
2. 真出口（A1）
   A1做完无条件goto “布尔表达式(a<b)”
3. 假出口（A2）
4. 布尔表达式(a<b)
5. 真出口（A3）
   A3做完无条件goto “布尔表达式(a<b)”
6. 假出口（后续代码）

答案：

第十章 代码优化

基本块优化+循环优化

理论很简单，把题目完全做对是难的：

注意：

1. 代码外提时，如果形如a[i,j]，那么可以外提一半，也就是t=i*n2可外提，但t=t+j不能外提。需要将t重命名为t’再外提。（当然下一步削弱计算强度时还能让t和t’重新合并）
2. 删除归纳变量时，要么删干净，那么这个变量就不会出现，其他变量初始化时不能用它；要么留着初始化，那么同族变量的初始化就能用这个变量，但是条件中被代替。

(模拟试卷1)
七、（10 分）有如下三地址代码
(1) i:=1
(2) if i>10 goto (29)
(3) j:=1
(4) if j>20 goto (27)
(5) k:=1
(6) if k>5 goto (25)
(7) t1:=i*20
(8) t1:=t1+j
(9) t2:=a-84
(10) t3:=4*t1
(11) t4:=i*5
(12) t4:=t4+k
(13) t5:=b-24
(14) t6:=4*t4
(15) t7:=t5[t6]
(16) t8:=k*20
(17) t8:=t8+j
(18) t9:=c-84
(19) t10:=4*t8
(20) t11:=t9[t10]
(21) t12:=t7+t11
(22) t2[t3]:=t12
(23) k:=k+1
(24) goto (6)
(25) j:=j+1
(26) goto (4)
(27) i:=i+1
(28) goto (2)
(29) halt

确定其入口语句有哪些，划分基本块，并画出流图。
在该段代码上进行内循环优化，给出优化过程中采用的优化技术及相应的优化结果

模拟试卷2
六、（15 分）有如下三地址代码:
(1) i:=1
(2) if i<=10 goto (4)
(3) goto (17)
(4) t1:=a-4
(5) t2:=4*i
(6) t3:=a-4
(7) t4:=4*i
(8) t5:=t3[t4]
(9) t6:=b-4
(10) t7:=4*i 
(11) t8:=t6[t7]
(12) t9:=t5+t8
(13) t1[t2]:=t9
(14) t10:=i+1
(15) i:=t10
(16) goto (2)
(17) halt
（1）将它划分基本块，并画出控制流图；
（2）在该段代码上进行基本块优化和循环优化，给出优化后的三地址代码。

---

* * * 期 中 之 前 的 内 容 * * *

---

第四章 LL1文法

first集和follow集会求。例题，这很重要

判断LL1：

1. 左前缀、左递归，若有则必不是
2. 只看多产生式，first集相交为空（说白了就是不能有左前缀）
3. 如果多产生式其中有一个产生的是epsilon，那么左侧符号的follow集与右侧产生式的first相交为空。（意思是，follow代替了该项的first集去和其他产生式比）

来看一道题。

第四章 LR文法

如果问你是不是LRx文法，画出DFA才可判断。

四个文法强度排序

四个兄弟之间的关系：（从高到低）

要求最高的是LR(0)文法，从不向前看。DFA中不能有移进归约在一起的情况。
次之为SLR(0)文法，用follow集当作向前看符号集。DFA中要保证移进符号(即·后的终结符)∩规约项follow集=Φ
要求比LR1高的是LALR1文法。需保证将LR1文法中的同心集合并后，仍没有冲突。
最低的是LR1文法，有自己的向前看符号集。DFA中要保证移进符号(即·后的终结符)∩规约项向前看符号集=Φ

没有要求的是LRK文法。

切记切记，LR(0)要求最高！！！
是谁期中因为这个扣了三分 (⌒_⌒;)

所以是LR1文法，一定是SLR1对吗？不对！！！反过来就对了，是SLR1，则一定是LR1

例题

做题总结：

2022-2023（A）
第二次做，错了求first集，如果S->A……A可推出空，那么S要往后看一个，而不是直接得出结论S也能推出空。

first(S)={a, +}