正规文法在词法分析器建模中的应用研究

罗海丽

(内蒙古科技大学 信息工程学院，内蒙古 包头 014010)

1.引言

软件所对应的问题域可看作信息的集合，信息就是符号串，问题域就是符号串的集合。问题域中的符号串都应遵从该问题域中的特定规则，即问题域可看作符合某种规则的符号串的集合。语言可定义为符合某种规则的符号串的集合，所以问题域可看作某种语言。文法是语言的一种建模工具，因此文法也是问题域的建模工具。建模是词法分析器构造的基础，对词法分析器建模的核心是选择一种恰当的工具描述词法，正规文法是描述词法的最佳工具。利用正规文法可对词法分析器进行建模，进而构造词法分析器，用这种方法构造的词法分析器形式化程度更高、更高效，这种构造词法分析器的方法比其它方法更为简洁。

2.利用正规文法对词法分析器建模

2.1 正规文法的概念

文法 G 可定义为四元组（VN，VT，P，S），其中 VN为非终结符的集合，VT为终结符的集合，P为产生式的集合，S为开始符号。若P中的每个产生式的形式都是A→аB或A→а，其中A、B都是非终结符，а∈VT*,则G是正规文法。[1]

文法可用来描述某种语言中的句子所遵从的规则，用正规文法所描述的规则更适于被计算机进行高效的处理。

2.2 词法分析器的功能

词法分析器的任务是从左到右逐个字符地读入源程序或文档，对构成源程序或文档的字符流进行扫描和分解，从而识别出一个个单词。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体的含义。比如程序设计语言中的标识符是以字母开头，后跟字母、数字字符的字符序列组成的一种单词。关键字是一种单词，此外还有运算符、界符等。[2]

词法分析器可应用于语言编译器、文档编辑器等软件中进行词法检查。

2.3 用正规文法建立PL/0语言的词法模型

以PL/0语言为例，用正规文法建立其词法模型。用正规文法建立PL/0语言的词法模型如下：

<标识符>→l∣l<字母数字>

<字母数字>→l∣d∣l<字母数字>∣d<字母数字>

<无符号整数>→d∣d<无符号整数>

<运算符>→+∣-∣*∣/∣=∣#∣<∣>∣<<等号>∣><等号>∣：<等号>

<等号>→=

< 界符 >→,∣;∣.∣（∣）

其中l表示a——z中的任何一个字母，d表示0——9中的任何一个数字。

关键字也是一种单词，关键字集合是标识符集合的子集，关键字与标识符的构词原则相同。

整数前面的正负号在词法分析中可看作运算符，因此只定义无符号整数的词法。

3.词法分析器的构造

以PL/0语言为例，构造PL/0语言的词法分析器。

3.1 将词法模型转化为DFA

将2.3中给出的用正规文法建立的PL/0语言的词法模型转化为一个确定的有穷自动机（DFA）。

(1)将各类单词的正规文法转化为DFA

2.3中给出用正规文法建立的PL/0语言的词法模型，将各类单词的正规文法转化为一个DFA。

例如，标识符的正规文法为：<标识符>→l∣l<字母数字>，<字母数字>→l∣d∣l<字母数字>∣d<字母数字>。首先，将该标识符的正规文法转化为一个NFA=({X,Q0,Q1,Y},{l,d},f1,{X},{Y})，其中，映射为 f1，f1(x,l)={Q0},f1(Q0,ε)=Q1,f1(Q1,l)=Q1,f1(Q1,d)=Q1,f1(Q1,ε)=Y。

然后，用子集法将该NFA转化为DFA=({0,1,2},{l,d},f2,0,{1,2}),其中 f2(0,l)=1,f2(1,l)=2,f2(1,d)=2,f2(2,l)=2,f2(2,d)=2。

最后，将该DFA化简为一个最小的DFA=（{0,1},{l,d},f3,0,{1}）,其中f3(0,l)=1,f3(1,l)=1,f3(1,d)=1。初态0表示准备识别单词的状态，0状态下接收到字母转向状态1，状态1为正在识别标识符的状态。[3]

同理，常数的正规文法<无符号整数>→d∣d<无符号整数>经过一系列转化可得一个最小的DFA=({0,2},{d},f4,0,{2}),其中f4(0,d)=2,f4(2,d)=2,初态0表示准备识别单词的状态，0状态下接收到数字转向状态2，状态2表示正在识别常数的状态。

其它各类单词的正规文法均可按相同方法构造DFA，所有这些DFA都有相同的初态0，初态0均为准备识别单词的状态。

(2)将各类单词正规文法对应的DFA按相同的初态0连接成一个完整的DFA M

其中，映射f定义如下：

该DFA M表示在准备识别单词的状态下,根据所接收到的符号转向不同的后继状态，若后继状态为终态则终态之前接收到的符号串构成一个单词，此时识别出一个PL/0语言的合法单词。该DFA M能识别的符号串的全体即为所有PL/0语言的合法单词。

3.2 构造控制程序

词法分析器中的控制程序如图1所示。

图1中的限制条件是指控制程序已读入的符号串的长度是否大于正在识别的单词的最大长度。

当控制程序识别出一个以字母开头的字母数字串时，须区分该单词是标识符还是关键字，此时控制程序中识别出一个单词的后续处理部分须完成区分工作。例如，可建立一张关键字表，其中存放PL/0语言中的所有关键字，当识别出一个字母数字串时，则查关键字表，若此单词在关键字表中，则为关键字，否则为标识符。[4]

图1 控制程序

3.3 词法分析器进行词法分析的过程

DFA M和图1的控制程序配合即为PL/0语言的词法分析程序，它可以对PL/0源程序进行词法分析。下面以一例说明词法分析过程。

例如一段PL/0语言源程序…X：=a09+90；…

假设，PL/0语言中标识符最大长度为3，则当识别标识符时，控制程序中的限制条件为已接收字符串长度是否大于3；常数最大长度为2，则当识别常数时，控制程序中的限制条件为已接收字符串长度是否大于2；>=，<=,：=长度为2，识别这三个单词时，控制程序中的限制条件为已接收字符串长度是否大于2；剩余其它运算符分界符长度均为1，识别这些单词时，控制程序中的限制条件为已接收字符串长度是否大于1。

词法分析时，首先启动控制程序，DFA初态0作为当前状态，从源文件中读入一个字符X，接收到的第一个符号是字母，说明开始识别一个标识符，查DFA，0状态下接收符号X转向后继状态1，由于当前已接收符号个数为1不大于3，所以不满足限制条件，后继状态1变为当前状态，继续读下一个符号：，查DFA，1状态下接收符号：，无后继状态，当前状态1为终态，此时终态1之前接收的符号串X即为一个单词。至此控制程序执行完一次，识别出一个单词X。继续调用一次控制程序，与上一次过程类似，又可识别出下一个单词：=,调用一次控制程序，便可识别出一个单词，这样不断调用控制程序，便可不断从源文件中识别单词，达到词法分析的目的。

4.结论

利用正规文法对词法分析器建模，就是用正规文法描述词法。描述词法的正规文法可转化为一个确定的有穷自动机，该有穷自动机表达了识别单词的动态过程。有穷自动机配合控制程序便可构成词法分析器，这种构造词法分析器的方法更为简洁、高效。

[1]何炎祥，伍春香，王汉飞.编译原理[M].北京：机械工业出版社，2010.

[2]张素琴，吕映芝，蒋维杜.编译原理（第2版）[M].北京：清华大学出版社，2005.

[3]葛寒松.正规文法与有限自动机的等价性研究[J].商丘师范学院学报，2010，26（12）：75-77.

[4]罗海丽.基于LEX语言的词法分析程序自动构造过程[J].内蒙古科技大学学报，2005，24（4）：314-317.