编译原理小考点
简答与计算
课本第五页的图(必考)

- 词法分析器:输入源程序,进行词法分析,输出单词符号;
- 语法分析器:根据文法构建分析表,对单词符号进行语法分析,检查程序是否符合语法规则;
- 语义分析与中间代码生成器:按照文法翻译规则对语法分析器归约出的语法单位进行语义分析,并把它们翻译成⼀定形式的中间代码;
- 优化器:对中间代码进行优化处理;
- 目标代码生成器:把中间代码翻译成目标代码。
其它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'?)
1 | S' -> S |
求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 |
4.3 根据预测分析表,写出accd自底向上的推导过程。
