编译原理 | Hexo

语义分析

大观念是输入一个程序文本，我们把它分解为一个个小的词组(Token)

Token

名字 , $xyz, pi$
常数 , $43, 5.32$
操作符 $+,=$
保留字 $if ,int $

Siever

在做分析之前，我们要进行预处理(pre-processing):

扔掉多余的：空格，注释
收集Pragmas,
用它们更具体的含义代替 Token，比如constants,names

正则表达式

$\Sigma$ 时程序编写的有限字符集

定义：正则表达式的集合 $E _{\Sigma}$ 时最小的集合 $E$ ，满足：

$\epsilon \in E$ ($$ 不是 $\Sigma$ 中的新符号)
$a \in E$ 对于所有 $a \in \Sigma$
$\left(e_{1} | e_{2}\right),\left(e_{1} \cdot e_{2}\right) |, e_{1}^{*} \in E$, 若 $e_{1}, e_{2} \in E$

练习 1.1 根据要求写出正则表达式

我们定义了一个语法：

对于 $e \in E _{\Sigma}$ ,我们递归地定义一个语言 $[e] \subseteq \Sigma^{*}$ 如下： \[ \begin{aligned} &[\epsilon]=\{\epsilon\}\\ &[a] \quad=\quad\{a\}\\ &\left[e^{*}\right] \quad=\quad([e])^{*}\\ &\left[e_{1} | e_{2}\right]=\left[e_{1}\right] \cup\left[e_{2}\right]\\ &\left[e_{1} \cdot e_{2}\right]=\left[e_{1}\right] \cdot\left[ e _{2}\right] \end{aligned} \] > 练习1.2 写出正则表达式的语言

对于一个正则表达式，我们也有一棵树与之对应：

有穷自动机

一个不确定的有穷自动机( nicht-deterministischer endlicher Automat (NFA) ) 是一个元组 $A=(Q, \Sigma, \delta, I, F)$ .

$Q$ 是事件的有限集
$\Sigma$ 是有限的字符集
$I \subseteq Q$ 是初始状态集合
$F \subseteq Q$ 是结束状态集合
$\delta$ 是转移关系

若 $\delta: Q \times \Sigma \rightarrow Q$ 是一个函数，且$\# I=1$(只有一个初始状态)，那么它是确定的有穷自动机

transitiven Abschluss(传递闭包)

传递闭包 $\delta ^{*}$ 是最小的集合 $\delta '$ 满足：

$(p, \epsilon, p) \in \delta^{\prime}$
$(p, xw, p) \in \delta^{\prime}$ 若 $\left(p, x, p_{1}\right) \in \delta \quad$ ，$\quad\left(p_{1}, w, q\right) \in \delta^{\prime}$

传递闭包描述了对于任意两个状态，它们怎么从一个到另一个。

可接受语言

一个自动机的可接受语言是： \[ L (A)=\left\{w \in \Sigma^{*} | \exists i \in I, f \in F: \quad(i, w, f) \in \delta^{*}\right\} \]

从表达式转换到NFA

Thompson's 算法

下面的式子可以这么转换,处理 $n$ 长度的正则表达式需要 $\mathcal{O} (n)$ 事件

练习1.4：把表达式转换成自动机

Berry-Sethi算法

这个算法可以把一个正则表达式的树，转换成自动机。我们在每个节点的左右都画一个点。左边是入口，右边是出口。

我们使用数字来代替节点

Glushkov Automaton

是使用 Berry-Sethi算法转换完后的自动机

结构如下：

状态:每个节点有左右两个点

开始状态是左边的点，结束状态是右边的点。

转换关系：对于叶子就是左节点到右节点

对于其他的可以用下面的表来表示

练习 1.5 写出某个正则操作符的转换关系

如果我们直接把这些关系放到语法树上，那么浪费的节点有很多，我们因此要压缩信息

DFS处理标签

我们用DFS处理出下面的标签

ﬁrst 状态点的集合，前面都是 $\epsilon$
next 这个点的下一个可能的字符
last 这个点最后的字符(到终点是 $\epsilon$ )
empty 语言中包含 $\epsilon$ 的节点

对于empty我们有下面的关系

比如对于下面的树就是

对于first有下面的关系

对应图上就是：

然后我们求next标签，它的关系如下:

我们一般先考虑根节点的出口状态的next是空集，然后一步步倒推来求

最后我们求last，和求first有点类似

例子上是

最后我们就有了高级版的Berry-Sethi算法

我们把上述自动机称为 $A_{e}$ . 比如之前的自动机就长这样：

转换NFA为确定的自动机

比如上面的NFA可以使用Powerset来合并一些节点，由此转换

定理

对于每个 NFA: $A=(Q, \Sigma, \delta, I, F)$，我们都可以求一个确定的自动机 $\mathcal{P} (A)$ \[ \mathcal{L} (A)= \mathcal{L} ( \mathcal{P} (A)) \] 构造：

状态： $Q$ 的Powersets

开始状态：$I$

结束状态: $\left\{Q^{\prime} \subseteq Q | Q^{\prime} \cap F \neq \emptyset\right\}$

转换关系：$\delta_{ \mathcal{P} }\left(Q^{\prime}, a\right)=\left\{q \in Q | \exists p \in Q^{\prime}:(p, a, q) \in \delta\right\}$

但是$Q$ 的Powerset可能有很多很多个，所以我们要根据实际情况来构造Powerset。比如下面这个例子

我们只用到了之前的2个Powerset，所以我们就构造2个就可以了。

定理改进

对每个正则表达式 $e$ 我们可以计算出一个确定自动机 $A = \mathcal{P}(A_{e})$ \[ \mathcal{L} (A)=[ e] \]

设计扫描器Scanner

输入是一组规则，每一个正则表达式对应一个具体动作

输出是一个程序。

它读取最多可以匹配到$\left(e_{1}|\ldots| e_{k}\right)$ 的字符 $w$

然后确定其中一个最小的 $i$ ，使得 $w \in [e_{i}]$

然后执行对应的动作 $action_{i}$

Idea

我们对 $e=\left(e_{1}|\ldots| e_{k}\right)$ 建立一个NFA $P \left(A_{e}\right)=\left(Q, \Sigma, \delta, q_{0}, F\right)$ ,我们定义下面的集合 \[ \begin{aligned} F_{1} &=\left\{q \in F | q \cap \operatorname{last}\left[e_{1}\right] \neq \emptyset\right\} \\ F_{2} &=\left\{q \in\left(F \backslash F_{1}\right) | q \cap \operatorname{last}\left[e_{2}\right] \neq \emptyset\right\} \\ & ... \\ F_{k} &=\left\{q \in\left(F \backslash\left(F_{1} \cup \ldots \cup F_{k-1}\right)\right) | q \cap \operatorname{last}\left[e_{k}\right] \neq \emptyset\right\} \end{aligned} \] 它们对应了每一个$e_{i}$ 的状态。

对于输入 $w$ ，它匹配到某一个动作，当且仅当 $\delta^{*}\left(q_{0}, w\right) \in F_{i}$

Scanner状态

Scanner可以有不同的状态，我们根据不同的状态来应对不同类型的文本，比如在处理注释的时候。

左边<state> 是Scanner状态，后面是该状态对应的正则表达式和操作$yybegin(state_{i})$ 是转换到第i个状态。

比如在YYINITIAL中，看到了/* 就要转换到COMMENT状态.在 COMMENT状态下，看到了*/就要转换回YYINITIAL。

语法分析

在语法分析 Syntatic analysis的任务是把Tokens变成更大的程序单元，如表达式，条件分支，循环。

Parser并不是用手写，而是生成出来的

上下文无关文法

一个程序可能有任意多个token，但是只有固定的类别 Token-classes.

定义

一个上下文无关文法(context-free gramar) (CFG)是一个4元组 $G = (N,T,P,S)$

$N$ : nonterminals 的集合就是可以拓展的表达式
$T$: terminals 的集合，无法拓展的表达式
$P$ : 规则的集合
$S \in N$ : 开始符号

约定 Conventions

Context-free Grammar的格式是这样的： \[ A \rightarrow \alpha \quad \text { with } \quad A \in N, \quad \alpha \in(N \cup T)^{*} \] 比如

序号

对于每个nonterminal，我们从左到右来记录扩展规则

以上这两者描述的是相同的语言

派生 Derivation

一个序列 $\alpha_{0} \rightarrow \ldots \rightarrow \alpha_{m}$ 是派生 derivation, 比如

派生树

比如上面的可以这样画

语法的唯一性

一个语法 $ G$ 是唯一的，若对于每个 $w \in T^{*}$ 只有一个派生树

下推自动机

一个上下文无关文法推出的语言会被下推自动机(Pushdown Automata)所接受

定义

一个下推自动机(PDA) 是一个元组$M=(Q,T,\delta,q_{0},F)$

$Q$ 是状态的有限集
$T$ 是输入字符集
$q_{0} \in Q$ 是开始状态
$F \subseteq Q$ 是中止状态的集合
$\delta \subseteq Q^{+} \times(T \cup\{\epsilon\}) \times Q^{*}$ 是传递关系的有限集

比如

从开始状态开始，左边是0，右边第一个字符是a，于是把0替换成右边的11；然后左边第一个字符是1，右边第一个字符是a，所用第二条关系。以此类推...

所以计算关系是 $(\alpha \gamma, x w) \vdash\left(\alpha \gamma^{\prime}, w\right) \quad$ for $\quad\left(\gamma, x, \gamma^{\prime}\right) \in \delta$

确定的下推自动机

一个下推自动机 $M$ 是确定的，若每个设置里有最多一个后继

定理

对于每个上下文无关文法 $G = (N,T,P,S)$ ,我们可以造一个下推自动机 $M$ , $\mathcal{L}(G) = \mathcal{L}(M)$

自顶向下Parsing

Item 下推自动机

它是一个前序遍历构造派生树的下推自动机，比如

它的转换关系是：

根据上面下推自动机的推导步骤可以推出来这个例子。

我们可以发现他有三种转换关系

Expansions(扩大): $([A \rightarrow \alpha \bullet B \beta], \epsilon,[A \rightarrow \alpha \bullet B \beta][B \rightarrow \bullet \gamma])$ ,对于$A \rightarrow \alpha B \beta, B \rightarrow \gamma \in P$
Shifts(移动点): $([A \rightarrow \alpha \bullet a \beta], a,[A \rightarrow \alpha a \bullet \beta])$ 对于$A \rightarrow \alpha a \beta \in P$
Reduces(减少): $([A \rightarrow \alpha \bullet B \beta][B \rightarrow \gamma \bullet], \epsilon,[A \rightarrow \alpha B \bullet \beta])$ 对于 $A \rightarrow \alpha B \beta, B \rightarrow \gamma \in P$

问题

有可能会发生歧义，解决办法有2个想法

GLL Parsing

对每个冲突，制造一个虚拟拷贝然后平行计算

回溯

用DFS来回溯

看前面

可以看下一步输入来判断如何解决

LL(1)-Parser 的结构

这个Parser访问长度为1的输入。

他对应一个下推自动机

表格 $M[q, w]$ 包含选择的规则

定义 $LL(1)$

一个reduced grammer 是 $LL(1)$ 若每2个冲突的规则 $A \rightarrow \alpha, A \rightarrow \alpha^{\prime} \in P$ 且每次推导 $S \rightarrow_{L}^{*} u A \beta$ , $u \in T^{*}$ 下面的是合法的： \[ \text { First }_{1}(\alpha \beta) \cap \text { First }_{1}\left(\alpha^{\prime} \beta\right)=\emptyset \]

向前看集合 Lookahead Sets

定义 $First_{1}$- Sets

对于一个集合 $L \subseteq T^{*}$ 定义： \[ \text { First }_{1}(L)=\{\epsilon \mid \epsilon \in L\} \cup\left\{u \in T \mid \exists v \in T^{*}: \quad u v \in L\right\} \] 就是 $L$ 后面可以生成的集合，比如

算数

\[ \begin{aligned} \text { First }_{1}(\emptyset) &=\emptyset \\ \text { First }_{1}\left(L_{1} \cup L_{2}\right) &=\text { First }_{1}\left(L_{1}\right) \cup \text { First }_{1}\left(L_{2}\right) \\ \text { First }_{1}\left(L_{1} \cdot L_{2}\right) &=\text { First }_{1}\left(\text { First }_{1}\left(L_{1}\right) \cdot \text { First }_{1}\left(L_{2}\right)\right) \\ &:=\text { First }_{1}\left(L_{1}\right) \odot_{1} \text { First }_{1}\left(L_{2}\right) \end{aligned} \]

定义 1-连接

若 $L_{1}, L_{2} \subseteq T \cup\{\epsilon\}$ 且 $L_{1} \neq \emptyset \neq L_{2}$ , 那么 \[ L_{1} \odot_{1} L_{2}=\left\{\begin{aligned} L_{1} & \text { if } \epsilon \notin L_{1} \\ \left(L_{1} \backslash\{\epsilon\}\right) \cup L_{2} & \text { otherwise } \end{aligned}\right. \]

快速计算Lookahead Set

Let empty $(X)=$ true iff $X \rightarrow^{*} \epsilon$

我们对没有 $\epsilon$ 的 $First_{1}$ 集合写成一个系统 \[ \begin{array}{l} F_{\epsilon}(a)=\{a\} \quad \text { if } \quad a \in T \\ F_{\epsilon}(A) \supseteq F_{\epsilon}\left(X_{j}\right) \quad \text { if } \quad A \rightarrow X_{1} \ldots X_{m} \in P, \quad \text { empty }\left(X_{1}\right) \wedge \ldots \wedge \text { empty }\left(X_{j-1}\right) \end{array} \] 比如

然后我们可以把这些关系写成自动机的形式

这个是变量依赖图(Variable Dependency Graph) 。然后我们把强连通分量合并。

然后我们从没有入度的边开始，把它们的元素加入里面

然后就可以把这个点“删掉”.

比如

定义 $Follow_{1}$- Sets

\[ \begin{array}{lllll} \text { Follow }_{1}(S) & \supseteq & \{\$\} & & \\ \text { Follow }_{1}(B) & \supseteq & F_{\epsilon}\left(X_{j}\right) & \text { if } & A \rightarrow \alpha B X_{1} \ldots X_{m} \in P, \operatorname{empty}\left(X_{1}\right) \wedge \ldots \wedge \text { empty }\left(X_{j-1}\right) \\ \text { Follow }_{1}(B) & \supseteq & \text { Follow }_{1}(A) & \text { if } & A \rightarrow \alpha B X_{1} \ldots X_{m} \in P, \text { empty }\left(X_{1}\right) \wedge \ldots \wedge \text { empty }\left(X_{m}\right) \end{array} \]

也就是 $S$ 的后面是什么

LL(1)-Lookahead Table

我们设表格 $M[B, w]=i$ ，$B \rightarrow \gamma^{i}$ if $w \in$ First $_{1}(\gamma) \odot_{1}$ Follow $_{1}(B)$

比如

我们就可以根据这个表格来解决冲突

RR-CFG

定义 RR-CFG

一个 right-regular context-free grammar (RR-CFG) 是一个4元组 $G=(N, T, P, S)$ ，其中

$N$ : nonterminals 的集合就是可以拓展的表达式
$T$: terminals 的集合，无法拓展的表达式
$P$ : 正则表达式规则的集合
$S \in N$ : 开始符号

例如数学表达式：

我们可以把这个规则通过添加标签转化一下，拆解开来

转化的规则是

所以上面的可以写成

我们可以得到一个$LL(1)$ 的语法

定义 RLL(1)

一个 RR-CFG $G$ 是 RLL(1), 若它的 CFG $\langle G\rangle$ 是一个 $LL(1)$ 语法

Recursive Descent RLL Parsers

Recursive desent RLL(1)-parser 是一个表格驱动的parser

对于 S() 函数是一个生产器

它具体是

对于正则表达式的逻辑可以这样实现