Compiler Princlple Study Node

编译原理预习

为了暑假好好学习选昱姐的课不会挂的太惨，提前过一遍昱姐的 ppt，和《编译器设计》（第二版）的书籍。内容会交叉进行。

词法分析

FA

为了形式化识别器，引入有限自动机（FA）。有限自动机是一个五元组 $ (S, \Sigma, \delta, s_0, S_A) $：

• $ S $ 是识别器有限状态集，以及一个错误状态 $s_e$。
• $ \Sigma $ 是识别器用的有限字母表。
• $ \delta(s,c) $ 是识别器的转移函数，对每个 $ s \in S , c \in \Sigma $ 对应一个状态。一般也这么表示：$ s_i \xrightarrow{c}{\delta (s_i, c)} $。
• $ s_0 $ 是指定的起始状态。
• $ S_A \in S $ 是接受状态的集合，表示为双层圆圈。

复杂性：

• 注意到 FA 的运行开销只与输入长度成正比（因为就是简单的状态机嘛），而与生成 FA 的 RE 长度或者复杂性没有关系。

正则表达式

RE 描述了一个定义在某个字母表 $ \Sigma $ 上的字符串集合。一个 RE 由三个基本操作构成：

• 选择：$ R | S $
• 连接：$ RS $
• 闭包（Kleene closure）： $ R^* $ ，R 出现零或无穷次
  • 相当于 $ \epsilon | R | RR | RRR | RRRR $ ….（当然，这种写法显然不是 RE）
  • ($ \epsilon $ 表示仅包含空串的集合)
  • 为了方便：
    • 有限闭包 $ R_i $ 为 R 出现一次到 i 次形成的闭包：
      • 例如 $ R^4 $ 也可以表示为 $ R | RR | RRR | RRRR $
    • 正闭包：$ R_+ $ 为 R 出现一次到无穷次形成的闭包
• 优先级：括号>闭包>连接>选择

用上面定义和数理逻辑的东西，可以定义全体 RE 在给定字母表 $ \Sigma $ 上构成的集合。

任何可以利用 RE 定义的语言（即，对于给定语言，可以找出一个 RE 使得语言的所有可能字串都恰好是 RE 可表示的字串）组成的语言集合称为正则语言。

RE 的闭包性质：$ RE op RE $ 的结果仍然是 RE（这里 op 指的是前面那些操作）

• 这样就可以很方便的证明（&寻找算法使得）对于任意 RE 都有 FA 与之对应了

---

JauntyLiu 想出的简单算法：

（这里需要 RE 的分层性质，仿照数理逻辑即可给出）

• 对于任意 $ p \in RE $，它必为下面几种情况之一：
  1. 存在 $ q,r \in RE $，使得 $ p = qr $
  2. 存在 $ q,r \in RE $，使得 $ p = q | r $
  3. 存在 $ q \in RE $，使得 $ p = q* $
     • 正闭包可以写成 $ qq* $，所以不需要单独讨论
     • 有限闭包更显然
  4. p 为一个字母的字母串

4 的构造显然。

下面讨论 1,2,3 的构造。假设 q,r 均有了对应的 FA。

对于 1，FA 构造如下（比较显然）：

• 取 q 的所有 accept state （$ S_A $），分别「接上」r 的 i nitial state （$ S_0 $）就好了
  • 严谨证明的话，可以写成 FA 的语言

对于 2，FA 构造有些难度。我们需要知道「匹配到什么程度才能把 q 和 r 分开」。比如 $ abc $ 和 $ abd $，就要匹配到第三个才知道到底选 q 还是选 r。

• 如果没有闭包，那这个取交集的操作肯定是有限的；那就非常好办。
• 如果有闭包，则不能保证？看书吧

---

书上的做法：RE ==(Thompson)==> NFA ==(子集构造伐)==> DFA ==(Hopcraft)==> 最小 DFA

子集构造法：用 $ \epsilon -closure $ 找状态的等价集合（「配置」），然后遍历。因为总配置数是有限的，所以一定可以停止。

Hopcraft 算法：先分类，然后迭代，找出类中不等价的元素，切分。重复，知道遍历所有类均找不出不等价的元素，这样就构造了一组等价类（状态）。

语法分析