词法分析和有穷自动机⚓︎

单词符号和输出的形式⚓︎

词法分析程序以字符串的形式作为输入，以单词符号作为输出。单词符号经常以二元式(单词种别，单词自身的值) 表示。

正规式与正规集⚓︎

正规式是正规集的表述形式，每一个正规式对应了一个正规集。对于正规式，其中\(e_1\mid e_2\)表示该字符由\(e_1\)或者\(e_2\)具体表示；\(e_1e_2\)则表示连续的\(e_1e_2\)字符；\((e_1)^*\)则表示其闭包。

直观地说，可以将正规式看作一种类似于正则表达式的表述方式；而其对应的正规集则是这个表达式具体可以表示的字符串集合。

例如，正规式\(aa^*bb^*cc^*\)就表示集合\(\{a^kb^lc^m\mid k,l,m\geqslant 1\}\).

正规式具有以下等价关系：

1. \(A\mid B=B\mid A\),

2. \(A\mid (B\mid C)=(A\mid B)\mid C\),

3. \(A(BC)=(AB)C\),

4. \(A(B\mid C)=AB\mid AC\),

5. \((A\mid B)C=AC\mid BC\),

6. \(A\varepsilon\mid \varepsilon A=A\),

7. \((A^*)^*=A\).

正规式和正规文法的互相转换⚓︎

正规式和正规文法都可以用有限的存储空间表示无穷的字符串集合，所以它们都能用于词法分析，两者也可以相互转化。

正规文法转化为正规式⚓︎

主要过程为消元，也即消去尽可能多的非终结符。过程中重要的两个等价关系为：

若\(A\to \alpha A\mid \beta\)，则\(A\)等价于正规式\(\alpha ^*\beta\)；若\(A\to A\alpha \mid \beta\)，则\(A\)等价于正规式\(\beta \alpha ^*\).

例如，程序标识符的正规文法是：\(S\to l\mid Sl\mid Sd\).则对上式做处理：\(S\to l\mid S(l\mid d)\)，于是其正规式：\(l(l\mid d)^*\).

正规式转化为正规文法⚓︎

反过来，对于给出的一个正规式，也可以转换成正规文法。这种转化方式是首先选取一个开始符号\(S\)使其能够直接推导出正规式，而后对正规式自左向右（或者自右向左）单个部分做拆分，并将剩余部分作为新的非终结符，其中穿插使用两个常用结论，例如：

对于正规式\(l(l\mid d)^*\)，先选取开始符号：\(S\to l(l\mid d)^*\)，而后自左向右作拆分：

其中非终结符\(A\)利用常用规则可以得到：

最后再对非终结符\(A\)的生成式作整理：

就得到了我们想要的文法规则。

评论