简答与计算

课本第五页的图（必考）

词法分析器：输入源程序，进行词法分析，输出单词符号；
语法分析器：根据文法构建分析表，对单词符号进行语法分析，检查程序是否符合语法规则；
语义分析与中间代码生成器：按照文法翻译规则对语法分析器归约出的语法单位进行语义分析，并把它们翻译成⼀定形式的中间代码；
优化器：对中间代码进行优化处理；
目标代码生成器：把中间代码翻译成目标代码。

其它5-6题，如二义文法、短语和句柄、FA/正则表达式/线性文法互转、消除左递归、提左公因子、后缀表达式、符号表、运行时空间组织等。

二义文法

给定一个文法判断是不是二义文法（课本32页）

如果一个文法的某个句子对应两棵不同的语法树，就是其最左（最右）推导不唯一，我们则称该文法为==二义文法==。

对于程序设计语言来说，最好不要是二义文法。

消除二义文法

划分优先级和结合性
优先级高一级的运算，增加一层产生式。
递归非终结符在左边，运算具有左结合性；否则具有右结合性

例如例题，通过添加T，F等中间状态，消除了二义性，同时保持了推导结果。

短语和句柄

容易考到（课本85页）

· 两个条件，缺一不可

· 例5.1,5.2

正则表达式

消除左递归

直接的左递归消除和间接的左递归消除（进行==LL（1）==的基础）

例如，既然P->Pa|b，那么Pa就有Pa->Paa|ba。

只要P还在左边，就能一直“递归”

所以设置P->bP'，P'->aP'|ε就可消除左递归。

==（再对消除隐含左递归进行推导一遍）==

提左公因子

课本71页：

看ppt这部分就很好理解，==课本上的解释可以选择性略过==

后缀表达式

课件7.1.1

课本167页

中缀转后缀算法

初始化符号栈，顺序读取中缀表达式，遇到（则将其加入栈中，遇到）则一次弹出栈顶元素到结果串，直到遇到（，将其出栈但是不附加到结果串中。
遇到+和-，弹出栈顶的所有操作符，附加到结果串中，然后自己进栈。
遇到*和/，先让栈顶的*和/出栈，附加到结果串中，然后自己进栈。
遇到数字，直接附加到结果串中。
最后若符号栈非空，将符号栈栈顶元素一次附加到结果串中

符号表

运行时空间

综合题

2.1 词法分析

给定正规式：

构造NFA
确定化（DFA）
最小化

首先构造NFA，下图（2）最后一行的样子

然后进行确定化，构造DFA

最后进行最小化

2.2 LL（1）分析

给出文法：

构造First集合
构造Follow集合
构造LL（1）分析表（可能设计消除二义文法冲突）
识别句子

==首先判断是否符合LL(1)适用条件==：

==首先求First==

注意ε什么时候用什么时候不用

若A->Bc, B->ε, 则First(A)={c} //没有ε

若A->B, B->ε, 则First(A)={ε} //有ε

==接下来求Follow==

==构造分析表==

根据上面的得到的First和Follow构造。

根据不同的式子可以得到不同的First和Follow，一一对应即可。

==识别句子==

格式为

序号	文法符号栈	输入串	所用产生式

2.3 LR分析

给出文法

构造拓广文法（求First集合）
构造拓广文法的LR(0)/LR(1)项目集规范族
构造LR(0)/LR(1)分析表（可能设计消除二义文法冲突）
识别句子

例：

==Q：==构造⽂法G[S]的LR(1)项⽬集规范族：

S -> aCaCb S -> aDb C -> a D -> a

==A：==

构造拓广文法（看起来就是添加一行S'？）

S' -> S
S -> aCaCb
S -> aDb
C -> a
D -> a

求First集合

构造拓广文法的LR(0)/LR(1)项目集规范族

构造分析表并消除二义性

识别句子aaaab和aab

2.4 给出翻译模式和高级语言程序，翻译句子

一般涉及多种类型句子的综合，也可能涉及声明语句填写符号表。

说明语句，课本7.2.1，把信息填到符号表，赋值语句、布尔表达式、控制语句等（ppt第七章）

像ppt例7.16这样的题会考，想让用LR，但是同学都是用构造语法树的方法。

==ppt7.5.3==标红

id	type	offset
x		0
y		8
z		16……

多个语句连接起来(?)

有可能涉及到多个语句

1. 过程中的说明语句

2. 算数表达式的翻译，赋值语句

3. 布尔表达式

2.5 给出基本代码块

构造DAG
写出优化后的中间代码
写出DAG目标优化后的中间代码
根据变量活性和寄存器信息，写出目标代码

DAG直接拿第三步的结果去生成目标代码

ppt 10.2.2等

11.3.1-11.3.3

课本323页，节点的排序方法

==题目：==

DAG有这种情况“重新生成四元式前

课本用的指令是LD和ST（可见课本312页）

考试统一用MOV

例题：

2. 根据正则式a( (b(a|b)*) |$\varepsilon$)ba，写出NFA，确定化，最小化。

3. 语法分析

G[S]文法：S$\rightarrow$CC，C$\rightarrow$cC，C$\rightarrow$d

3.1 G[S]对应的 First和Follow是什么？证明G[S]是LL(1)

3.2 写出G[S]的预测分析表

	c	d
S	S——>CC	S——>CC
C	C——>cC	C——>d

3.3根据预测分析表，写出cdccccd的TOP-DOWN的推导过程。

S$	cdccccd$
CC$	cdccccd$
cCC$	cdccccd$
CC$	dccccd$
dC$	dccccd$
C$	ccccd$
cC$	ccccd$
C$	cccd$
cC$	cccd$
C$	ccd$
cC$	ccd$
C$	cd$
cC$	cd$
C$	d$
d$	d$
$	$

4. 语义分析

根据文法

4.1 证明是LR(0)

4.2 写出预测分析表

STATE			ACTION				GOTO
	a	b	c	d	$	A	B	E
0	S2	S3						1
1					acc
2			S5	S6		4
3			S8	S9			7
4	r2	r2	r2	r2	r2
5			S5	S6		10
6	r5	r5	r5	r5	r5
7	r3	r3	r3	r3	r3
8			S8	S9			11
9	r7	r7	r7	r7	r7
10	r4	r4	r4	r4	r4
11	r6	r6	r6	r6	r6

编译原理小考点