2 形式语言和自动机
转化为等价的无二义性文法
优先级越高的越在后边
根据描述写非二义性文法
注意左结合是先归约在移进，右结合是先移进再归约
根据描述画DFA
注意这种一般是将第一个0独立出去
根据描述写正规式
3 词法分析
4 语法分析——自上而下分析
消除左递归
改写并判断是否为LL(1)文法
首先要不含左递归不含左公因子
对A的操作是消除公共因子，对B是消除左递归
不要忘记follow含#的情况
只需要对有多个产生式的求FIRST集
不能用普通方法改写为LL(1)文法
尝试作DFA转为正规式
若不能作正规式
说明是否为LL(1)文法
设有下列文法_G_(A)
A→BCc|eDB
B→\(\varepsilon\)|bCD
C→DaB|ca
D→\(\varepsilon\)|dD
(1)计算每个侯选式的FIRST集合，若侯选式的FIRST集合包含\(\varepsilon\)，计算左侧非终结符号的FOLLOW集合。
(2)根据(1)中的计算结果，构造该文法的LL(1)分析表，说明该文法是否为LL(1)文法。
解：
(1)对A：\(FIRST(BCc) = \{a,b,c,d\} \qquad FIRST(eDB) = \{e\} \qquad\)
对B：\(FIRST(\varepsilon ) = \{\varepsilon \} \qquad FIRST(bCD) = \{b\} \qquad FOLLOW(B) = \{\#,a,c,d\}\)
对C：\(FIRST(DaB) = \{a,d\} \qquad FIRST(ca) = \{c\}\)
对D：\(FIRST(\varepsilon ) = \{\varepsilon \} \qquad FIRST(dD) = \{d\} \qquad FOLLOW(D)=\{\#,a,b,c,d\}\)
(2)
LL(1)分析表为：
| a | b | c | d | e | |
|---|---|---|---|---|---|
| A | A→BCc | A→BCc | A→BCc | A→BCc | A→eDB |
| B | B→ε | B→bCD | B→ε | B→ε | |
| C | C→DaB | C→ca | C→DaB | ||
| D | D→ε | D→ε | D→ε | D→ε,D→dB | D→ε |
因为M[D,d] 有多重定义入口，所以该文法不是LL(1)文法。
LL(1)分析分析过程
有文法
_E_→-_E_|(_E_)|_VT_
_T_→-_E_|_ε_
_V_→_iF_
_F_→(_E_)| _ε_
问题：
1． 给出上述文法的LL(1)分析表；
2． 给出句子_i_- - i(i)利用LL(1)分析法的如下图所示的分析过程。
| 步骤 | 分析栈 | 余留输入串 | 所用产生式 |
|---|---|---|---|
5 语法分析——自下而上分析
一个短语必须是和其所有的兄弟节点组成的
如果有两个长的一样的短语但是在不同位置那他们是不同的短语
判定文法具有二义性
SLR(1)解决移进归约冲突
构建SLR(1)分析表
SLR（1）分析+左结合+分析过程
设有下列文法G[S]：
（2）假设加法“+”为左结合，试构造该文法的SLR(1)分析表；
（3）给出句子a+++a++的SLR(1)分析过程。
最后少一步
判断是LR（0）还是SLR（1）
优先级+左结合
LR(1)构建
LALR(1)构建
6 语义分析与中间代码生成
在编译程序中与生成中间代码的目的无关的是D
A.便于目标代码优化
B.便于存储空间的组织
C.便于目标代码的移植
D.便于编译程序的移植
逆波兰表达式、三元式、树以及四元式
- BZ 即如果栈顶元素为零，则进行分支跳转。它通常用于条件判断，当栈顶元素为零时，根据指定的跳转地址进行无条件跳转。
- BR 即无条件分支跳转。它用于无条件地将程序控制流程跳转到指定的地址。
拉链返填(for while if型)
有下列C语言语句
for(i=0; i<n; i++;)
whlile(a>b)do
if(c>d)m=n+1;
s=m;
问题：
1.给出该语句的语义处理(没有优化处理)后的四元式形式的目标代码；
2.设编译器是单遍扫描的编译器，给出中间代码生成后循环处理产生的如下所示的标号表的内容（标号按出现的先后顺序命名为Li，其中i=1，2，…，n；**）。
| 标号名 | 定义否（1/0） | 返填顺序 | 地址 |
|---|---|---|---|
| Li | 1 | ⑤→②→① | |
| … |
注意：
A)无条件转移操作符用“j”表示，条件成立转移的操作符用“jT”表示，条件不成立转移的操作符用“jF”表示；
B)语句标号的定义性出现用Li(i=1，2，…，n)表示，语句标号的地址使用四元式序列的序号表示，序号用①，②，…表示。
拉链返填(for if else if else型)
源程序生成中间代码的目标结构
逆波兰式表示+四元式表示+拉链返填
if-else if-else型
根据文法给出语法分析树
设有文法的语法制导定义如下。
(1) 根据文法给出句子 ((i),((i),(i))) 的语法分析树
(2) 根据语法分析树及语法制导定义，给出句子 ((i),((i),(i))) 的计算过程以及输出结果。
5
8 代码优化
DAG图优化
例题（循环优化）
根据四元式划分基本块
求控制流图和必经结点集
求回边和循环+代码外提
强度削弱+删除归纳变量(循环控制变量)
删除无用转移语句！
例题（基本块优化）
删除无用赋值
常量合并与传播
另一道题
公共子表达式删除
循环展开
（3）
例题
求到达-定值集IN和OUT
生成GEN集和KILL集
![%1D8GYI%3]K`9D{HXD$$B5.jpg
在基本块中如果有两个相同的变量被赋值，GEN集中记录的是最后一个被赋值的变量的定义。
初始化IN和OUT
out都是gen
迭代
注意-和U的优先级相同
求各基本块中变量引用点的ud链
求各基本块的活跃变量集IN和OUT集
生成DEF集和USE集
初始化IN和OUT
迭代
求各基本块中变量定值点的du链
