编译程序第一个工作阶段-词法分析(正规式)

上篇讲述了句型的两种类型--自上而下和自下而上，本篇进入编译程序的第一个工作阶段--词法分析。

我们在第二篇中讲述了关于词法分析的简单介绍，词法分析工作可以独立的一遍，把字符流的源程序变成单词序列，输出在一个中间文件上，这个文件作为下一个工作阶段-词法分析程序的输入而继续编译的过程。

一般情况下降词法程序设计成一个子程序，每当语法分析程序需要一个单词的时候，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词。

那经过第一阶段的加工，我们的词法分析之后，得到什么？

词法分析的输出：读入源程序，输出单词符号，单词符号包括单词的中类和单词自身的值，例如关键字有 end if 、while、var等；运算符有+ ，*，《=等。

又有一个问题了，为什么要有这个阶段，将词法分析这个工作分为一个阶段？为什么将编译过程分为词法分析和语法分析？

笔者认为这就和三层架构一样，系统为什么要分为三层架构？其实这也和我们的生活有关，现代社会不再单靠一个人单打独斗的社会，我们当代的社会人们分工明确，各司其职，社会稳步发展~ 这样提高全社会运转效率。我们的编译程序也是，主要原因有一下三点：

1、使整个编译程序的结构更加简洁、清晰和条理化。

2、编译程序的效率会改进。

3、增强了编译程序的可移植性。

词法分析开始：

词法分析开始，第一步当然是要从源程序中读入单词了，我们在文法中描述单词的工具是什么？正规式（也称正则表达式），是用以描述单词符号的方便工具。

正规式和正规集定义：

字母表集合内，所含有两个相继的a或两个相继的b组成的串 |

正规式服从代数规律：

1）r|s = s|r
2)r|(s|t) = (r|s)|t
3)(rs)t = r(st)
4)r(s|t)r = sr|tr
5)**ε**r = r           r**ε**= r
6)r|r = r

正规文法和正规式的转换：

例如：

将r = a(a|d)* 转换为相应的正规文法。

S->a(a|d)*  ==>  S->aA  A->(a|d)* ==>A->(a|d)B  A->ε ==>B->(a|d)B  B->ε

转换结果为：S->aA A->(a|d)B A->ε B->(a|d)B  B->ε

单词的识别工具--正规式，本篇讲述到这里，下一篇讲述正规式的识别装置--有穷自动机。