3 词法分析

  从这一章开始，讨论的词法分析、语法分析方法基本上都是针对于2型或者3型文法。

正规文法的表述方式与相互转换¶

  正规文法（3型文法）除了按照文法的定义由许多产生式描述之外，还有正规式、NFA、DFA 等描述方法。即3型词法有 $3$ 种形式化描述工具——正则文法、正规式、有穷自动机。他们之间的相互转换关系如下。

graph TD
    R["正规式(R)"] <--> G["正规文法(G)"]
    R <--> NFA["非确定有穷状态机(NFA)"]
    NFA --> DFA["确定有穷状态机(DFA)"]
    DFA --> G
    G <--> NFA
    DFA --> mDFA["最小确定有穷状态机(min DFA)"]

正规式↔正规文法¶

  正规式→正规文法，这里主要是靠三个规则进行转换：

1. 形如 $A\to xy$ 的正规式，构造产生式 $\lbrace A\to xB,B\to y\rbrace$。
2. 形如 $A\to x^*y$ 的正规式，构造产生式 $\lbrace A\to xB,A\to y,B\to xB,B\to y\rbrace$。
3. 形如 $A\to x|y$ 的正规式，构造产生式 $\lbrace A\to x,A\to y\rbrace$。

这里的规则2，课堂上曾提过一个问题，为什么不能直接简化为 $A\to xA|y$ 呢？我认为部分时候是可以这样简化的，简化的条件就是当前以 $A$ 为左部只有一个产生式。类似 $A\to a,A\to b$ 和 $A\to a|b$ 都被认为是两个产生式。

  至于正规文法→正规式，这个还是比较容易的，实际上就是把左部相同的产生式归为一组，这样正规式就被分成了好几组。对于每一组，考虑用正规式来构造一个统一的右部。主要是下面三个规则：

1. 形如 $\lbrace A\to xB,B\to y\rbrace$ 的组，可以转换为 $A\to xy$。
2. 形如 $\lbrace A\to xA,A\to y\rbrace$ 的组，可以转换为 $A\to x^*y$。
3. 形如 $\lbrace A\to x,A\to y\rbrace$ 的组，可以砖混为 $A\to x|y$。

可以看到，就是之前的三个规则反过来。

正规式↔NFA¶

  这个真的是太简单了，就看下面这张图，相互转换关系就很明了了。

NFA↔正规文法¶

  这里的正规文法一般指的是右线性文法。右线性文法记为 $G=(V _ N,V _ T,P,S)$，NFA 记作 $M=(V _ N\cup\lbrace Z\rbrace,V _ T,\lbrace S\rbrace,\lbrace Z\rbrace)$。需要记住 NFA 的状态除了正规文法的所有非终结符之外，还会额外多一个 $Z$。这个 $Z$ 有何用呢？也是看下面这个表，就知道相互转换关系了。

左线性正规文法比较啰嗦，但是也能做。此时 NFA 也是比文法多了一个状态，为了区别，我们记作 $A$。

NFA 确定化和 DFA 最小化¶

  NFA 确定化用的是子集构造法。构造的是下面这样的表格：

关于这个子集构造法，如果你发现某个集合是空集，就不要把它加到第一列去了。我们只把非空的集合作为新的状态。
  DFA 最小化就是分割法。一开始所有的终态是一个集合，非终态是另外一个集合。通过不断测试某个集合 $V$ 内的不同状态 $A,B$ 的等价性，试图将这些集合进行分裂。直到最后无法分裂，那么此时同一个集合内部的所有状态等效。