编译原理 第三章词沸篓分析.docVIP

 PAGE 11 第三章 词法分析 词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 本章重点：正规式、有限自动机（DFA、NFA）、NFA到DFA的转换、DFA的最小化。 第一节 词法分析程序的设计 一、词法分析程序的输出 词法分析程序的功能是读入源程序，输出单词符号，单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分为下列5种： 1、基本字，也称关键字，如PASCAL语言中的begin, end, if, while和var等。 2、标识符，用来表示各种名字，如常量名、变量名和过程名等。 3、常数，各种类型的常数，如25,3.1415,TRUE和“ABC”等。 4、运算符，如+, ﹡, =等。 5、界符，如逗点，分号，括号等。 词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句const i=25, yes=1;中的单词25和1的种别都是常数，常数的值25和1，对于代码生成来说，是必不可少的。有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式（标识符，指向该标识符所在符号表中位置的指针），如上述语句中的单词i和?yes的表示为： （标识符，指向i的表项的指针） （标识符，指向yes的表项的指针） 单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段if i=5 then x ：= y；在经词法分析器扫描后输出的单词符号和它们的表示如下： 保留字if (3，‘if’) 标识符i （1，指向i的符号表入口） 等号 = （4，‘=’） 常数5 （2，‘5’） 保留字then （3，‘then’） 标识符x （1，指向x的符号表入口） 赋值号 ：= （4‘：=’） 标识符y （1，指向y的符号表入口） 分号； （5，‘；’） 第二节 单词的描述工具 程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立分析技术，进而可以建立词法分析程序的自动构造方法。 一、正规文法 多数程序设计语言的单词的语法都能用正规文法或3型方法来描述。 回顾一下3型方法G =（VN，VT，S，P）的特征，即P中的每一条规则都有下述形式：A→aB或A→a其中A，B∈VN，a∈Veq \o(\s\up 5(* ),\s\do 2(T))。正规文法所描述的是Veq \o(\s\up 5(* ),\s\do 2(T))上的正规集。 程序设计语言中的几类单词可用下述规则描述： 标识符→1|1字母数字 字母数字→1| d |1字母数字 |d 字母数字 无符号整数→d | d 无符号整数 运算符→+ | — | ﹡ | / |等号 | 等号…… 等号→= 界符→，| ；|（ | ）| …… 其中1表示a ~ z中的任何一英文字母，d表示0 ~ 9中的任一数字。 二、 正规式 正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。 下面是正规式和它所表示的正规集的递归定义。设字母表为Σ ，辅助字母表Σ′= {?，ε, |,·,﹡, (,) }。 1、ε和?都是Σ上的正规式，它们所表示的正规集分别为｛ε｝和?； 2、任何a ∈ Σ，a是Σ上的一个正规式，它所表示的正规集为｛a｝； 3、假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L (e1),和L (e2)，那么，(e1), e1 |e2, e1·e2和e1﹡也都是正规式，它们所表示的正规集为L (e1), L (e1) UL (e2), L (e1) L (e2)和 (L(e1) )﹡。 4、仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。 例