资源描述：
《编译原理 第三章词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章词法分析词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。本章重点：正规式、有限自动机（DFA、NFA）、NFA到DFA的转换、DFA的最小化。第一节词法分析程序的设计一、词法分析程序的输出词法分析程序的功能是读入源程序，输出单词符号，单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分为下列5种：1、基本字，也称关键字，如PASCA
2、L语言中的begin,end,if,while和var等。2、标识符，用来表示各种名字，如常量名、变量名和过程名等。3、常数，各种类型的常数，如25,3.1415,TRUE和“ABC”等。4、运算符，如+,﹡,<=等。5、界符，如逗点，分号，括号等。词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句consti=25,yes=1;中的单词25和1的种别都是常数，常数的值25和1，对于代码生成来说，是必不可少的。有时，对某些单词来说
3、，不仅仅需要它的值，还需要其它一些信息以便编译的进行。比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式（标识符，指向该标识符所在符号表中位置的指针），如上述语句中的单词i和 yes的表示为：（标识符，指向i的表项的指针）（标识符，指向yes的表项的指针）单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段ifi=5thenx：=y；在经词法分析器扫描后输出的单词符号和它们的表示如下：保留字if(3，‘if’)标识符i（1，指向
4、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∈V
5、N，a∈V。正规文法所描述的是V上的正规集。程序设计语言中的几类单词可用下述规则描述：<标识符>→1
6、1<字母数字><字母数字>→1
7、d
8、1<字母数字>
9、d<字母数字><无符号整数>→d
10、d<无符号整数><运算符>→+
11、—
12、﹡
13、/
14、<<等号>
15、><等号>……<等号>→=<界符>→，
16、；
17、（
18、）
19、……其中1表示a~z中的任何一英文字母，d表示0~9中的任一数字。二、正规式正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。11下面是正规式和它所表示的正规集的递归定义。设字母表为Σ，辅助字母表Σ′={Ø，ε,
20、,·,﹡,(,)}。1
21、、ε和Ø都是Σ上的正规式，它们所表示的正规集分别为｛ε｝和Ø；2、任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为｛a｝；3、假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1),和L(e2)，那么，(e1),e1
22、e2,e1·e2和e1﹡也都是正规式，它们所表示的正规集为L(e1),L(e1)UL(e2),L(e1)L(e2)和(L(e1))﹡。4、仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。例1令Σ=｛a,b｝,Σ上的正规式和相应的正规集的例子有：正规式正规集a｛a｝a
23、b｛a,
24、b｝ab｛ab｝(a
25、b)(a
26、b)｛aa,ab,ba,bb｝a﹡｛ε,a,aa,…任意个a的串｝(a
27、b)﹡｛ε,a,b,aa,ab…所有a,b组成的串｝(a
28、b)﹡(aa
29、bb)(a
30、b)﹡Σ﹡上所有含有两个相继的a或两个相继的b组成的串。三、正规文法到正规式一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的正规文法，有些正规语言很容易用文法定义，有些语言更容易用正规式定义，本节介绍两者间的转换，从结构上建立它们的等价性。1、将Σ上的一个正规式转换成文法G
31、=（VN，VT，S，P）。令其中的VT=Σ，确定产生式和VN的元素
