编译技术-2022fa-回忆版

发表于 2025-12-25 更新于 2025-12-29 分类于期末复习本文字数： 2.1k 阅读时长 ≈ 2 分钟

编译技术 2022 秋季学期的回忆版真题，来源于计算机速通之家 | QQ 群号：468081841。

本文连载于编译技术-2022fa-回忆版| HeZzz

🙇‍♂️🙇‍♂️🙇‍♂️时间仓促，有不足之处烦请及时告知。邮箱hez2z@foxmail.com 或者在速通之家群里 @9¾。

正则表达式转换

写出 ${a^n b^n c^m \mid n \geq 1, m \geq 0}$ 文法

设有文法

$S \rightarrow A C$

$A \rightarrow a A b \mid a b$

$C \rightarrow c C \mid \varepsilon$

证明二义性

$S \rightarrow S \text{ or } S \mid S \text{ and } S \mid (S) \mid p \mid q \mid \text{not } S$ 证明二义性

反例句子：$p \text{ and } q \text{ and } p$

过程不写了，来不及了。

语法分析树

$F \rightarrow ET+ \mid T$
$T \rightarrow TF* \mid F$
$F \rightarrow Fp \uparrow P$
$P \rightarrow E \mid i$

推导 $ip \uparrow *+$ 句型语法分析树
短语、直接短语、句柄

题目是错的，下一个。

$LL(1)$

$S \rightarrow AcB \mid Bd$
$A \rightarrow AaB \mid c$
$B \rightarrow aA \mid a$

写出消除回溯后的文法
写$LL(1)$分析表，是否为$LL(1)$文法

1. 判断文法是否是LL(1)

左递归检查： A存在左递归（A → AaB）
左公因子检查： B存在左公因子（B → aA | a）

需要改造文法：

消除A的左递归：A → CA', A' → aBA' | ε
消除B的左公因子：B → aB', B' → A | ε

最终文法：

$S \to AcB \mid Bd$

$A \to c A’$

$A’ \to a B A’ \mid \varepsilon$

$B \to a B’$

$B’ \to A \mid \varepsilon$

2. First集合与Follow集合

First集合：

First(S) = {a, c}
First(A) = {c}
First(A’) = {a, ε}
First(B) = {a}
First(B’) = {c, ε}

Follow集合：

Follow(S) = {$}
Follow(A) = {a, c, d, $}
Follow(A’) = {a, c, d, $}
Follow(B) = {a, c, d, $}
Follow(B’) = {a, c, d, $}

3. LL(1)分析表

非终结符	a	c	d	$
S	S → Bd	S → AcB
A		A → CA’
A’	A’ → aBA’	A’ → ε	A’ → ε	A’ → ε
B	B → aB’
B’	B’ → ε	B’ → A	B’ → ε	B’ → ε

该文法是LL(1)文法。

LR(1)

$S \rightarrow BB$
$B \rightarrow aB$
$B \rightarrow b$

$LR(1)$ DFA
$LR(1)$分析表
给出句子(不记得了)的分析过程
格式(步骤状态栈符号栈输入串动作)

DFA

构造增广文法

$S’ \rightarrow S$

$S \rightarrow BB$

$B \rightarrow aB$

$B \rightarrow b$

然后状态转移表什么的，太多了，压榨 AI 也没法写了，直接看视频吧。

【编译原理速成之LR(0)和SLR(1)】

四元式

while (a + b < c) do
    if (a > b && b < c) {
        c = c + 1
    } else {
        b = b + 1
    }

写出四元式，(假设序号从100开始)

序号	四元式	说明
100	(ADD, a, b, T1)	T1 = a + b
101	(LT, T1, c, T2)	T2 = T1 < c (while条件)
102	(JFALSE, T2, 111)	若T2为假(即!(a+b<c))，跳转到111(结束)
103	(GT, a, b, T3)	T3 = a > b
104	(LT, b, c, T4)	T4 = b < c
105	(AND, T3, T4, T5)	T5 = T3 && T4 (if条件)
106	(JFALSE, T5, 109)	若T5为假，跳转到109(else分支)
107	(ADD, c, 1, c)	c = c + 1 (then分支)
108	(JMP, 110)	跳转到110(if-else结束)
109	(ADD, b, 1, b)	b = b + 1 (else分支)
110	(JMP, 100)	跳转回100(while条件判断)
111		循环结束

NFA 构造

十进制整型常量

八进制整型常量前缀为 $0$

十六进制整型常量前缀为$0_x$,

后缀为 $L$ 或 $l$ 的整型常量代表类型为long int.

写出整型常量的 $NFA$

看这个编译技术 -2025fa-lb 复习课/利用正规式描述高级语言中的某个单词结构

翻译

$S \rightarrow \text{List}$

$\text{List} \rightarrow (\text{op})$

$\text{op } \rightarrow \text{op List}$

$\text{op } \rightarrow \text{List}$

$\text{list} \rightarrow \text{num}$

写一个翻译模式可以输出括号内有n个数
例如 $((123)(123456))$ 输出为 $3,6,2$

不会，放弃。