526互联

编译原理部分题型总结

发布时间 2023-06-24 12:04:17作者: LateSpring

2 形式语言和自动机

转化为等价的无二义性文法

image.png
image.png
优先级越高的越在后边

根据描述写非二义性文法

image.png
image.pngimage.png
注意左结合是先归约在移进，右结合是先移进再归约

根据描述画DFA

image.png
注意这种一般是将第一个0独立出去

根据描述写正规式

image.png
image.png

3 词法分析

image.png
image.png

4 语法分析——自上而下分析

消除左递归

image.png
image.png

改写并判断是否为LL(1)文法

HSH%NM5GMEDW0JE3BAD`2QJ.png
首先要不含左递归不含左公因子
对A的操作是消除公共因子，对B是消除左递归
image.png
不要忘记follow含#的情况
只需要对有多个产生式的求FIRST集

image.png
image.png
image.png

不能用普通方法改写为LL(1)文法

尝试作DFA转为正规式
image.png
image.png
若不能作正规式
image.png
image.png

说明是否为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)分析表；
image.png
2． 给出句子_i_- - i(i)利用LL(1)分析法的如下图所示的分析过程。

步骤 分析栈 余留输入串 所用产生式

IMG_20230617_190859-01.jpeg
image.png
image.png

5 语法分析——自下而上分析

image.png
一个短语必须是和其所有的兄弟节点组成的
image.png
如果有两个长的一样的短语但是在不同位置那他们是不同的短语

判定文法具有二义性

image.png
image.png

SLR(1)解决移进归约冲突

image.png
image.png
image.png

构建SLR(1)分析表

image.png
image.png

SLR（1）分析+左结合+分析过程

设有下列文法G[S]：
image.png
（2）假设加法“+”为左结合，试构造该文法的SLR(1)分析表；
（3）给出句子a+++a++的SLR(1)分析过程。
IMG_20230618_201043_edit_1434101939294191-01.jpeg
最后少一步
image.png

判断是LR（0）还是SLR（1）

image.png
image.png
image.png

优先级+左结合

image.png

LR(1)构建

image.png
image.png
image.png

LALR(1)构建

image.png
image.png
image.png

6 语义分析与中间代码生成

在编译程序中与生成中间代码的目的无关的是D
A.便于目标代码优化
B.便于存储空间的组织
C.便于目标代码的移植
D.便于编译程序的移植

逆波兰表达式、三元式、树以及四元式

image.png

  • BZ 即如果栈顶元素为零，则进行分支跳转。它通常用于条件判断，当栈顶元素为零时，根据指定的跳转地址进行无条件跳转。
  • BR 即无条件分支跳转。它用于无条件地将程序控制流程跳转到指定的地址。

image.png
image.png

拉链返填(for while if型)

有下列C语言语句

for(i=0; i<n; i++;) 
    whlile(a>b)do
        if(c>d)m=n+1;
s=m;

问题：
1.给出该语句的语义处理(没有优化处理)后的四元式形式的目标代码；
image.png
2.设编译器是单遍扫描的编译器，给出中间代码生成后循环处理产生的如下所示的标号表的内容（标号按出现的先后顺序命名为Li，其中i=1，2，…，n；**）。

标号名 定义否（1/0） 返填顺序 地址
Li 1 ⑤→②→①
…

IMG_20230618_231535-01.jpeg
注意：
A)无条件转移操作符用“j”表示，条件成立转移的操作符用“jT”表示，条件不成立转移的操作符用“jF”表示；
B)语句标号的定义性出现用Li(i=1，2，…，n)表示，语句标号的地址使用四元式序列的序号表示，序号用①，②，…表示。

拉链返填(for if else if else型)

image.png
image.png
image.png
image.png
源程序生成中间代码的目标结构
IMG_20230611_185335-01.jpeg
IMG_20230611_184845-01.jpeg
image.png

逆波兰式表示+四元式表示+拉链返填

image.png
image.png
image.png

if-else if-else型

image.png
image.png

根据文法给出语法分析树

设有文法的语法制导定义如下。
image.png
(1) 根据文法给出句子 ((i),((i),(i))) 的语法分析树
(2) 根据语法分析树及语法制导定义，给出句子 ((i),((i),(i))) 的计算过程以及输出结果。
IMG_20230616_181315-01.jpeg
5

8 代码优化

DAG图优化

image.png
image.png
image.png
image.png
image.png
image.png

例题（循环优化）

image.png
image.png

根据四元式划分基本块

image.png
image.png

求控制流图和必经结点集

image.png

求回边和循环+代码外提

image.png

强度削弱+删除归纳变量(循环控制变量)

image.png
删除无用转移语句！
image.png
image.png

例题（基本块优化）

image.png
image.png

删除无用赋值

image.png
image.png
image.png

常量合并与传播

image.png

另一道题

image.png
image.png

公共子表达式删除

image.png
image.png
image.png

image.png
image.png

循环展开

image.png
（3）
image.png
image.png
image.png

例题

image.png

求到达-定值集IN和OUT

image.png

生成GEN集和KILL集

![%1D8GYI%3]K`9D{HXD$$B5.jpg
在基本块中如果有两个相同的变量被赋值，GEN集中记录的是最后一个被赋值的变量的定义。
image.png

初始化IN和OUT

out都是gen
image.png

迭代

注意-和U的优先级相同
image.png
image.png

求各基本块中变量引用点的ud链

image.png
image.png
image.png

求各基本块的活跃变量集IN和OUT集

image.png

生成DEF集和USE集

image.png
image.png

初始化IN和OUT

迭代

image.png
image.png

求各基本块中变量定值点的du链

image.png
image.png