2012软考系统分析师经典教程：重点与难点(2)

2.5.2 词法分析

　　词法分析的任务是把构成源程序的字符串转换成单词符号串的中间程序。词法规则可用3型文法（正规文法）或正规表达式描述。转换方法有人工的状态转换图方法和有限自动机的自动方法。

　　这部分主要涉及以下两个方面的内容。

　　● 正规表达式和正规集

　　正规表达式是一种极为有用的工具。

　　例如，对于正规文法

　　〈标识符〉→〈标识符〉字母

　　〈标识符〉→〈标识符〉数字

　　〈标识符〉→字母(31)

　　所定义的语法范畴〈标识符〉，我们可用如下的式子加以表述：

　　字母·(字母|数字)*(32)

　　这就是一个正规式。其中“·”，“|”及“*”分别为“连接”、“或”及“闭包”运算符。上述正规式指明，语法范围〈标识符〉被定义为以字母开头，且其后跟以由零个或多个字母和数字的任意序列。由这些序列所组成的集合，我们称之为相应于正规式(32)的正规集。可见正规式(32)也就刻画了某种程序设计语言的标识符的结构。

　　如所周知，每一程序设计语言都有它自己的字符集Σ。语言中的每一单词，或者是Σ上的单个字符 (如运算符，分隔符等)，或者是Σ上的字符按一定方式组成的字符串 (如常数、关键字、标识符以及关系运算符等)。这里所说的“按一定方式组成”，也就是对字符或字符串进行一定的“·”，“|”或者“*”运算。因此，如果我们把每类单词均视为一种语言，那么，每一类单词都可用一个正规式来描述，而每一类单词中的全体单词也就组成了相应的正规集。

　　设Σ为一字母表，则Σ上的正规式及其所表征的正规集可递归地定义如下。

　　1是一个正规式，相应的正规集为空集。

　　2ε是一个正规式，相应的正规集为{ε}。

　　3对于每一a∈Σ，a是一个正规式，相应的正规集为{a}。

　　4若r,s是正规式，且相应的正规集分别记为Lr及Ls，则

　　(1) (r)·(s)是正规式，相应的正规集为LrLs；

　　(2) (r)|(s)是正规式，相应的正规集为Lr∪Ls；

　　(3) (r)*是正规式，相应的正规集为L*r。