编译技术-2022fa-回忆版

编译技术 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$

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

题目是错的，下一个。

$LL(1)$

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

1. 写出消除回溯后的文法
2. 写$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)分析表

该文法是LL(1)文法。

LR(1)

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

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

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开始)

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$

不会，放弃。