02-词法分析

正则语言

• 定义：若存在一个 DFA/NFA 能够匹配所有这个语言的字符串，拒绝所有不属于这个语言的字符串，那么这个语言就是正则语言。

• 若 $L_1, L_2$ 是正则语言，则以下也是正则语言

  • $L_1 \cup L_2$

  • $L_1 \cap L_2$

  • $L_1 L_2$

  • $L_1^*$

  • $\overline{L_1}$

  • $L_1^R$

原因：

• 多个终止状态的 NFA 可以合并为一个终止状态（增加 $\epsilon$ 转移）

• $L_1 \cup L_2$：并联两个 NFA

• $L_1 \cap L_2$：使用 De Morgan 定律，转换为 $\overline{\overline{L_1} \cup \overline{L_2}}$

• $L_1 L_2$：串联两个 NFA

• $L_1^*$：将 NFA 首尾相连，增加 $\epsilon$ 转移

• $\overline{L_1}$：将 NFA 的终止状态改为非终止状态

• $L_1^R$：将 NFA 的边反向

正则表达式

• 原始正则表达式

  • 空集：$L(\emptyset)=\emptyset$

  • 空串：$L(\epsilon)=\{\epsilon\}$

  • 字符：$L(a)=\{a\}$

• 正则表达式进行以下运算后还是正则表达式

  • $L(r_1|r_2)=L(r_1)\cup L(r_2)$

  • $L(r_1r_2)=L(r_1)L(r_2)$

  • $L(r_1^*)=L(r_1)^*$

  • $L((r_1))=L(r_1)$

• 若两个正则表达式表示同一种语言，则它们是等价的。

正则表达式的运算定律

• 常见运算符

  • |：或

  • *：0次，1次或多次

  • +：1次或多次

  • ?：0次或1次

• 交换/结合律

  • $r_1|r_2=r_2|r_1$

  • $(r_1|r_2)|r_3=r_1|(r_2|r_3)$

  • $(r_1r_2)r_3=r_1(r_2r_3)$

• 零元/幺元

  • $r|\emptyset=r$

  • $r\emptyset=\emptyset$

  • $r|\epsilon=r$

  • $r\epsilon=r$

• 分配律

  • $r_1(r_2|r_3)=r_1r_2|r_1r_3$

  • $(r_1|r_2)r_3=r_1r_3|r_2r_3$

• 幂等律：$r|r=r$

• 闭包：

  • $(r^*)^*=r^*$

  • $\emptyset^*=\epsilon ^*= \{\epsilon\}$ （ $\emptyset$拼接$0$次是空串，拼接多次是空集）

  • $r^+=r(r^*)=(r^*)r$

  • $r?=\epsilon|r$

正则语言 & 正则表达式

• 任何正则表达式都能表示正则语言：将正则表达式转换为 NFA

  • 原始正则表达式是 NFA 的一个个“部件”

  • 正则表达式的运算是 NFA 的“组装”

• 任何正则语言都能用正则表达式表示：通过正则表达式表示 DFA

  • 将 DFA 的状态转移变为正则表达式的等式

  • 消元，化简，得到正则表达式

词法分析的基础

1. 为词位（lexeme）建立正则表达式，构造 DFA

2. 将源代码作为输入

3. 将 DFA 作为状态机，识别出源代码中的词位

Lexical Analysis 词法分析

• 正则表达式 -> NFA -> DFA -> 最小化 DFA

• 当达到 DFA 的终止状态时，输出 Token

• 当有多个 DFA 同时匹配时

  • 根据优先级选择 或

  • 选择最长的 Token

关系运算符的例子

在知道是<或>之后，需要判断是否是<=或>=，若不是，则需要回退一个字符（DFA 图上标注*）

Pumping Lemma 泵引理

• 如果存在一个常数$n$，使得对于所有长度大于$n$的字符串$w$，$w$可以被分为三个部分$x, y, z$，满足以下条件，那么$L$是正则语言

  • $|xy|\le n$

  • $|y| \le 1$

  • 对于任意$i\ge 0$，$xy^iz\in L$

• 证明思路：设状态数是$n$，长度大于$n$的字符串至少有$n+1$个状态，至少有一个状态被访问两次，产生循环。

• 用于证明一个语言不是正则语言

  • $\forall n$，$\exists w \in L, |w|>n$

  • 选择$x, y, z$，使得

    • $xyz=w$

    • $|xy|\le n$

    • $|y| \le 1$

  • 但是$\exists i, xy^iz\notin L$

• $a^nb^n$是正则语言吗？

  • 设$n=3$，$w=a^3b^3$，$x=a^3, y=b, z=b^2$

  • $xy^2z=a^3b^4\notin L$

  • $a^nb^n$不是正则语言