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

罗海丽

(内蒙古科技大学 信息工程学院，内蒙古 包头 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 词法分析器的功能

词法分析器的任务是从左到右逐个字符地读入源程序或文档，对构成源程序或文档的字符流进行扫描和分解，从而识别出一个个单词。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体的含义。……