编译原理期末复习

引论

计算机程序设计语言及编译

编译：将 高级语言 翻译成 汇编语言或机器语言 的过程

编译器的结构

语言及其文法

字母表上的运算

字母表 $\sum {}_{1}$ 和 $\sum {}_{2}$ 的乘积

${0, 1\}\{a, b\} = \{0a, 0b,1a,1b \}$
字母表 $\sum$ 的n次幂
$\sum {}^{0} = \{ \varepsilon \}$

${0, 1\}^3=\{000, 001, 010, 011, 100, 101, 110, 111\}$

字母表 $\sum$ 的正闭包
$^+ = ∑ ∪ ∑^2 ∪ ∑^3 ∪ …$

${a, b, c, d \}^+ = \{a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …\}$

字母表的正闭包:长度正数的符号串构成的集合

字母表 $\sum$ 的克林闭包
$^* = ∑^0 ∪ ∑^+ = ∑^0 ∪ ∑ ∪ ∑^2 ∪ ∑^3 ∪ …$

$\{a, b, c, d \}^* = \{\varepsilon,a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …\}$

字母表的克林闭包：任意符号串（长度可以为零）构成的集合

串

设 ∑ 是一个字母表， $\forall x \in ∑^*$ ，x称为是∑上的一个串

串上的运算—连接
$\ \ \ \ \ xy=doghouse$
串上的幂运算
$s^0 = \varepsilon$

$s^n = s^{n-1}s$

文法的定义

文法的形式化定义

$G = (V_T,V_N,P,S)$

$V_T$ : 终结符集合，是文法定义的语言的基本符号，有时也称为 token

$V_N$ : 非终结符结合，是用来表示语法成分的符号，有时也称为“语法变量”

$P$ : 产生式，描述了将终结符和非终结符组合成串的方法

产生式的一般形式： $\alpha \rightarrow \beta$
$\alpha \in (V_N \bigcup V_T )^+$ ，且 $\alpha$ 中至少包含 $V_N$ 中的一个元素
$\beta \in (V_N \bigcup V_T )^*$

$S$ : 开始符号，是该文法中的最大的语法成分

产生式的简写

$a \rightarrow b_1, a \rightarrow b_2,…, a \rightarrow b_n $ 简写为： $\rightarrow b_1|b_2|...|b_n$

$b_1,b_2,...b_n$ 是 $a$ 的候选式

语言的定义

推导：

如果有产生式 $α \to β \in P$ ，那么可以将符号串 $γ α δ$ 中的 $α$ 替换为 $β$ 即将 $γ α δ$ 重写为 $γ β δ$ ，这个替换记做

$γαδ\Rightarrow γβδ$ ,叫做文法中的符号串 $γ α δ$ 直接推导出 $γ β δ$

推导和归约

在这里插入图片描述

句型和句子

$如果S\Rightarrow{}^*\alpha,\alpha \in(V_T,V_N)^*,则称\alpha是G的一个句型$
- 一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串
$如果S\Rightarrow{}^*w,w \in V_T^*,则称w是G的一个句型$
- 句子是不包含非终结符的句型

由文法 G 的开始符号 S 推导出的所有句子构成的集合称为文法 G 生成的语言，记为 L(G)

语言上的运算

例: 令 $L=\{A，B，…，Z, a,b,…\}$ ， $D=\{0，1,…，9\}$ 。则 $L(L\bigcup D)^*$ 表示的语言是标识符

文法的分类

0型文法无限制文法： $\forall \alpha \rightarrow \beta \in P$ , $\alpha$ 中至少包含一个非终结符
1型文法(CSG) 上下文有关文法： $|\alpha| \leq |\beta|$
2型文法(CFG) 上下文无关文法： $\alpha \in V_N$
3型文法(RG) 正则文法： $\rightarrow wB$ 或 $\rightarrow w$

CFG的分析树

在这里插入图片描述

短语

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语

如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。

词法分析

正则表达式

正则表达式的定义

$\xi$ 是一个RE， $L(\xi)=\{ \xi \}$

如果 $\in \sum$ ，则a是一个RE， $L(a) = \{a\}$

假设r和s都是RE，表示的语言分别是 $L (r)$ 和 $L (s)$ ，则

r|s是一个RE, $L (R ∣ S) = L (R) \cup L (s)$
rs是一个RE, $L (r s) = L (r) L (s)$
$r^*$ 是一个RE, $L(R^*)=(L(r))^*$
®是一个RE, $L ((r)) = L (r)$

十进制整数的RE

$1|...|9)(0|...|9)^*|0$

正则定义

c语言中标识符的正则定义

digit → 0|1|2|…|9
letter_ |B|…|Z|a|b|…|z|_

有穷自动机

有穷自动机

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

转换图

结点

初始状态（开始状态）：只有一个，由start箭头指向
终止状态（接受状态）：可以有多个，用双圈表示

带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

FA定义(接受)的语言

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收
由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收)的语言，记为 $L (M)$

在这里插入图片描述

最长子串匹配原则

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进匹配。

有穷自动机的分类

确定的有穷自动机（DFA）

$(S,\sum,\delta,s_0,F )$

S:有穷状态集
$\sum$ :输入字母表，即输入符号集合
$\delta$ :将 $S×\sum$ 映射到 S 的转换函数。 $\forall s \in S,a\in \sum,\delta(s,a)$ 表示从状态s触发，沿着标记为a的边所能到达的状态。
$s_0$ :开始状态（初始状态）
$F$ :接受状态（终止状态）集合

在这里插入图片描述

非确定的有穷自动机（NFA）

$(S,\sum,\delta,s_0,F )$

S:有穷状态集
$\sum$ :输入字母表，即输入符号集合
$\delta$ :将 $S×\sum$ 映射到 $2^S$ 的转换函数。 $\forall s \in S,a\in \sum,\delta(s,a)$ 表示从状态s触发，沿着标记为a的边所能到达的状态集合。
$s_0$ :开始状态（初始状态）
$F$ :接受状态（终止状态）集合

在这里插入图片描述

NFA和NFA的等价性

对任何非确定的有穷自动机N，存在定义同一语言的确定的有穷自动机D
对任何确定的有穷自动机D，存在定义同一语言的非确定的有穷自动机N
DFA和NFA可以识别相同的语言

在这里插入图片描述

带有 $\xi$ 边的NFA

$(S,\sum,\delta,s_0,F )$

S:有穷状态集
$\sum$ :输入字母表，即输入符号集合
$\delta$ :将 $S×(\sum∪ \{ \xi \})$ 映射到 $2^S$ 的转换函数。 $\forall s \in S,a\in \sum ∪ \{ \xi \},\delta(s,a)$ 表示从状态s触发，沿着标记为a的边所能到达的状态集合。
$s_0$ :开始状态（初始状态）
$F$ :接受状态（终止状态）集合