编译原理第四章 词法分析.docx

编译原理第四章 词法分析.docx

《编译原理第四章 词法分析.docx》由会员分享，可在线阅读，更多相关《编译原理第四章 词法分析.docx（38页珍藏版）》请在冰点文库上搜索。

编译原理第四章词法分析

第四章词法分析

课前索引

【课前思考】

　◇词法分析程序的功能是什么？

　◇PL/0词法分析程序识别哪几种单词？

　◇画出PL/0词法分析程序的流程图。

　◇C语言，PASCAL语言的标识符和数的表示分别有什么规定？

　◇编写一个程序（C的，或PASCAL的）识别C++语言的标识符。

【学习目标】

　◇明确词法分析在编译过程所处的阶段和作用。

　◇掌握词法分析程序的手工实现方法。

　◇理解通常的单词分类和构词规则。

　◇会使用单词的描述和识别机制。

　◇掌握词法分析程序的自动构造原理。

【学习指南】

　　词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。

词法分析也是语法分析的一部分，把词法分析从语法分析中独立出来是为了使编译程序结构清晰，也是为了便于使用自动构造工具，提高编译效率。

　　本章首先介绍词法分析程序的功能和设计原则，然后引入正规式和其对单词的描述，接着讲述有穷自动机理论，最后给出词法分析程序的自动构造原理。

【难重点】

　◇如何设计和实现词法分析程序

　◇正规式的定义-如何用作单词的描述工具

　◇有穷自动机的定义和分类-如何用作单词的识别系统

　◇正规式到有穷自动机的转换算法-词法分析程序的自动构造原理

【知识结构】

词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。

执行词法分析的程序称为词法分析程序或扫描程序。

本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。

词法分析程序的主要任务：

　　-读源程序，产生单词符号

　　词法分析程序的其他任务：

　　-滤掉空格，跳过注释、换行符

　　-追踪换行标志，复制出错源程序，

　　-宏展开，……

　　本章要点：

　　-告诉你掌握词法分析程序的设计和实现的办法

　　-首先需要描述和刻画程序设计语言中的原子单位--单词，其次需要识别单词和执行某些相关的动作。

　　-描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。

4.1词法分析程序

首先讨论词法分析程序与语法分析程序的接口方式

　　词法分析程序完成的是编译第一阶段的工作。

词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。

然而，更一般的情况，是将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。

词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止。

这种设计方案中，词法分析程序和语法分析程序是放在同一遍里，而省掉了中间文件，象第2章介绍的PL/0编译程序那样.也是大多数编译程序采用的方案。

实现词法分析（lexicalanalysis）的程序

　　逐个读入源程序字符并按照构词规则切分成一系列单词。

单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。

词法分析是编译过程中的一个阶段，在语法分析前进行。

也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。

词法分析程序和语法分析程序的关系

f4-1-1.swf

词法分析程序的主要功能是从字符流的源程序中识别单词，它要从左至右逐个字符地扫描源程序，因此它还可完成其它一些任务。

比如，滤掉源程序中的注释和空白（由空格，制表或回车换行字符引起的空白）；又比如，为了使编译程序能将发现的错误信息与源程序的出错位置联系起来，词法分析程序负责记录新读入的字符行的行号，以便行号与出错信息相联；再有，在支持宏处理功能的源语言中，可以由词法分析程序完成其预处理等等。

接着讨论词法分析程序的输出

　　词法分析程序的功能是读入源程序，输出单词符号。

单词符号是一个程序设计语言的基本语法符号。

程序设计语言的单词符号一般可分成下列5种：

　①保留字，也称关键字，如PASCAL语言中的begin,end,if,while和var等。

　②标识符，用来表示各种名字，如常量名、变量名和过程名等。

　③常数，各种类型的常数，如25，3.1415，TRUE和"ABC"等。

　④运算符，如+，*，<=等。

　⑤界符，如逗点，分号，括号等。

五种单词符号：

　-保留字，关键字

　-标识符

　-常数（量）

　-运算符

　-界符

你能举出一些例子吗?

　　词法分析程序所输出的单词符号常常采用以下二元式表示：

（单词种别，单词自身的值）。

单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。

比如在PASCAL的语句consti=25,yes=1；中的单词25和1的种别都是常数，常数的值25和1对于代码生成来说，是必不可少的。

有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。

比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式（标识符，指向该标识符所在符号表中位置的指针），如上述语句中的单词i和yes的表示为：

　　（标识符，指向i的表项的指针）

　　（标识符，指向yes的表项的指针）

　　单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段ifi=5thenx∶=y；在经词法分析器扫描后输出的单词符号和它们的表示如下：

　-保留字if（3，'if'）

　-标识符i（1，指向i的符号表入口）

　-等号=（4，'='）

　-常数5（2，'5'）

　-保留字then（3，'then'）

　-标识符x（1，指向x的符号表入口）

　-赋值号∶=（4，'∶='）

　-标识符y（1，指向y的符号表入口）

　-分号；（5，'；'）　

将词法分析工作从语法分析中分离出来的原因

　　实际上，词法也是语法的一部分，词法描述完全可以归并到语法描述中去，只不过词法规则更简单些。

这在后面的章节中可以看到。

为什么将词法分析做为一个独立的阶段？

为什么把编译过程的分析工作划分成词法分析和语法分析两个阶段？

主要的考虑因素为：

　①使整个编译程序的结构更简洁、清晰和条理化。

　②编译程序的效率会改进。

　③增强编译程序的可移植性。

①使整个编译程序的结构更简洁、清晰和条理化。

词法分析比语法分析简单的多，但是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。

例如，空白和注释的处理；再比如对于FORTRAN和cobol那种受书写格式限制的语言，需在识别单词时进行特殊处理等等。

如果统统合在语法分析时一并考虑，显然会使得分析程序的结构复杂得多。

　　②编译程序的效率会改进。

大部分编译时间是花费在扫描字符以把单词符号分离出来。

把词法分析独立出来，采用专门的读字符和分离单词的技术可大大加快编译速度。

另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。

　　③增强编译程序的可移植性。

在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASCII还是EBCDIC字符编码。

另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的"↑"的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。

4.2正规表达式与正规集（正规语言）

程序设计语言中的单词是基本语法符号。

单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。

　　为了理解将使用的形式工具，首先表述一些基本术语和概念。

　　-符号一个抽象实体,我们不再形式地定义它（就象几何中的"点"一样）。

例如字母是符号，数字也是符号。

　　-字母表字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。

　　-符号串由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表Σ={0，1}上的符号串。

不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。

PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。

　　字母表A={a,b,c}上的一些符号串有：

a,b,c,ab,aaca。

在符号串中，符号的顺序是很重要的，例如符号串ab就不同于ba,abca和aabc也不同。

可以使用字母表示符号串，如x=STR表示"x是由符号S、T和R，并按此顺序组成的符号串"。

　　如果某符号串x中有m个符号，则称其长度为m，表示为|x|=m，如001110的长度是6。

　　允许空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即|ε|=0。

下面介绍有关符号串的一些运算。

　　-符号串的头尾，固有头和固有尾

　　-符号串的连接

　　-符号串的方幂

　　-符号串集合

符号串的头尾，固有头和固有尾：

如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。

　　举个例子:

设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是ε,c,bc。

　　当我们对符号z=xy的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：

z=x…；

　　如果只是为了强调x在符号串z中的某处出现，则可表示为：

z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。

　　符号串的连接：

设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串.由于ε的含义，显然有εx=xε=x。

　　例如设x=ST，y=abu，则它们的连接xy=STabu，看出|x|=2，|y|=3，|xy|=5。

　　符号串的方幂：

设x是符号串，把x自身连接n次得到符号串z，即z=xx…xx，称为符号串x的n次方幂，写作z=xn，也即把符号串x相继地重复写n次。

x0=ε,x1=x,x2=xx,x3=xxx分别对应于n=0,1,2和3

　　例子；若x=AB则:

　　x0=ε

　　x1=AB

　　x2=ABAB

　　x3=ABABAB

　　xn=xxn-1=xn-1x（n>0）

符号串集合：

若集合A中的一切元素都是某字母表Σ上的符号串，则称A为字母表Σ上的符号串集合。

两个符号串集合A和B的乘积定义如下：

AB={xy|x∈A且y∈B}，即AB是满足x属于A，y属于B的所有符号串xy所组成的集合。

例如，若A={a,b},B={c,d},则集合AB={ac,ad,bc,bd}。

因为对任意符号串x有εx=xε=x，所以有{ε}A=A{ε}=A。

　　指定字母表Σ之后，使用Σ*表示Σ上的一切符号串（包括ε）组成的集合。

Σ*称为Σ的闭包。

Σ上的除ε外的所有符号串组成的集合记为Σ+。

Σ+称为Σ的正闭包。

　　Σ+=Σ*-{ε}=ΣΣ*=Σ∪Σ2∪Σ3∪……

　　Σ*={ε}∪Σ∪Σ2∪……

　　例：

Σ={a,b}

　　Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}

　　Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

我们用以描述单词符号的工具是正规式。

　　正规表达式（regularexpression）是说明单词的模式（pattern）的一种重要的表示法（记号），是定义正规集的工具。

　　正规式也称正则表达式，也是表示正规集的数学工具。

下面是正规式和它所表示的正规集的递归定义。

　　定义（正规式和它所表示的正规集）：

　　设字母表为Σ，辅助字母表Σ`={Φ，ε，|，·，*，（，}。

　　①ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{}；

　　②任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；

　　③假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L（e1）和L（e2），那么，（e1）,e1|e2,e1·e2,e1*也都是正规式,它们所表示的正规集分别为L（e1）,L（e1）∪L（e2）,L（e1）L（e2）和（L（e1））*。

　　④仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。

正规式定义中的“|”读为“或”（也有使用“+”代替“|”的）；“·”读为“连接”；“*”读为“闭包”（即，任意有限次的自重复连接）。

在不致混淆时，括号可省去，但规定算符的优先顺序为“（”、“）”、“*”、“·”、“|”。

连接符“·”一般可省略不写。

“*”、“·”和“|”都是左结合的。

　　令∑={a，b}，∑上的正规式和相应的正规集的例子有：

　　正规式　　　　　　　正规集

　　a　　　　　　　　　　{a}

　　a|b　　　　　　　　　{a,b}

　　ab　　　　　　　　　　{ab}

　　（a|b）（a|b）　　　　　　{aa,ab,ba,bb}

　　a*　　　　　　　　　　{ε,a,a,……任意个a的串}

　　（a|b）*　　　　　　　　{ε,a,b,aa,ab……所有由a和b组成的串}

　　（a|b）*（aa|bb）（a|b）*　{∑*上所有含有两个相继的a或两个相继的b组成的串}

　　若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2。

　　例如：

e1=（a|b），e2=b|a

　　又如：

e1=b（ab）*，e2=（ba）*b

　　再如：

e1=（a|b）*，e2=（a*|b*）*

　　设r,s,t为正规式，正规式服从的代数规律有：

　　①r|s=s|r　　　　　　"或"服从交换律

　　②r|（s|t）=（r|s）|t　"或"的可结合律

　　③（rs）t=r（st）　　　　"连接"的可结合律

　　④r（s|t）=rs|rt

　　　（s|t）r=sr|tr　　　　分配律

　　⑤εr=r,rε=r　　　ε是"连接"的恒等元素零一律

　　⑥r|r=r

　　　r*=ε|r|rr|…　　　　"或"的抽取律

程序设计语言的单词都能用正规式来定义。

请看下面两个例子：

例4.1

　　令Σ={l，d}，则Σ上的正规式r=l（l|d）*定义的正规集为：

{l,ll,ld,ldd,……}，其中l代表字母，d代表数字，正规式，即是字母（字母|数字）*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。

例4.2

　　Σ={d，·，ε，+，-},则Σ上的正规式d*（·dd*|ε）（ε（+|-ε|）dd*|ε）表示的是无符号数的集合。

其中d为0~9的数字。

外文教材中常常遇到的术语

　-Token单词,词标，符号

　-lexeme词素，词位

　-pattern模式，式样

　　这段话帮你理解外文教材中常常遇到的术语Ingeneral，thereisasetofstringsintheinputforwhichthesametokenisproducedasoutput.Thissetofstringsisdescribedbyarulecalledapatternassociatedwiththetoken.Thepatternissaidtomatcheachstringintheset.Alexemeisasequenceofcharactersinthesourceprogramthatismatchedbythepatternforatoken.例如：

　　源程序语句Constpi=3.14159，x1=10；中的pi和x1是token“identifier”的lexeme，其pattern为字母开头，后面跟有字母和/或数字的字符序列。

4.3有穷自动机

有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。

有穷自动机分为两类：

确定的有穷自动机（DeterministicFiniteAutomata）和不确定的有穷自动机（NondeterministicFiniteAutomata），下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。

　　关于有穷自动机我们将讨论如下题目

　　-确定的有穷自动机DFA

　　-不确定的有穷自动机NFA

　　-NFA的确定化

　　-DFA的最小化

4.3.1确定的有穷自动机DFA

　　DFA定义：

-一个确定的有穷自动机（DFA）M是一个五元组：

M=（K，Σ，f，S，Z）其中

　　①K是一个有穷集，它的每个元素称为一个状态；

　　②Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；

　　③f是转换函数，是K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；

　　④S∈K是唯一的一个初态；

　　⑤Z

K是一个终态集，终态也称可接受状态或结束状态。

举一个DFA的例子：

　　DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：

　　f（S，a）=Uf（V，a）=U

　　f（S，b）=Vf（v，b）=Q

　　f（U，a）=Qf（Q，a）=Q

　　f（U，b）=Vf（Q，b）=Q

　　一个DFA可以表示成一个状态图（或称状态转换图）。

假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头"=>"或标以"-"，终态结点用双圈表示或标以"+"，若f（ki,a）=kj，则从状态结点ki到状态结点kj画标记为a的弧；

DFA的状态图表示

一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f（k,a）的值。

用双箭头"=>"标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。

DFA的矩阵表示

状态\字符

a

b

S

U

V

U

Q

V

V

U

Q

Q

Q

Q

0

0

0

1

DFA的确定性表现在转换函数f:

K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f（k,a）唯一地确定了下一个状态。

从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。

为了说明DFA如何作为一种识别机制,我们还要理解下面的定义。

∑*上的符号串t在M上运行

　　-一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFAM上运行的定义为：

　　-f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K

　　-扩充转换函数f，是K×Σ*→K上的映射，且：

f（ki，ε）=ki

∑*上的符号串t被M接受

　　-若t∈∑*，f（S，t）=P，其中S为M的开始状态，P∈Z，Z为终态集。

　　-则称t为DFAM所接受（识别）

　　DFAM所能接受的符号串的全体记为L（M）

结论：

　　∑上一个符号串集V

∑*是正规的，当且仅当存在一个∑上的确定有穷自动机M，使得V=L（M）

例：

证明t=baab被下图的DFA所接受。

　　f（S，baab）=f（f（S，b），aab）

　　=f（V，aab）=f（f（V，a），ab）

　　=f（U，ab）=f（f（U，a），b）

　　=f（Q，b）=Q

　　Q属于终态。

　　得证。

4.3.2不确定的有穷自动机NFA

　接下来我们讨论不确定的有穷自动机NFA

　定义

　不确定的有穷自动机NFA　N=（K，∑，f，S，Z）

　其中：

　K为状态的有穷非空集

　∑为有穷输入字母表

　f为K*∑*到K的子集（2K）的映射

　S

K是初始状态集

　Z

K为终止状态集。

例子：

　　NFAN=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）

　　其中

　　f（S，0）={P}

　　f（Z，0）={P}

　　f（P，1）={Z}

　　f（Z，1）={P}

　　f（S，1）={S，Z}

状态图表示

同样NFA也有矩阵表示

f4-2-1.swf

类似DFA,对NFAN=（K，∑，f，S，Z）也有如下定义

　　∑*上的符号串t在NFAN上运行

　　一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFAN上运行的定义为：

　　f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K.

　　∑*上的符号串t被NFAN接受

　　若t∈∑*，f（S，t）=P，其中S为N的开始状态，P∈Z，Z为终态集。

　　则称t为NFAN所接受（识别）

　　∑*上的符号串t被NFAN接受也可以这样理解：

对于Σ*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串（不理采那些标记为ε的弧）等于t，则称t可为NFAM所识别（读出或接受）。

若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε道路，那么空字可为M所接受。

　　NFAN所能接受的符号串的全体记为L（N）

结论：

　　∑上一个符号串集V

∑*是正规的，当且仅当存在一个∑上的不确定的有穷自动机N，使得V=L（N）

下图的NFA称作具有ε转移的不确定的有穷自动机

对任何一个具有ε转移的不确定的有穷自动机NFAN，一定存在一个不具有ε转移的不确定的有穷自动机NFAM，使得L（M）=L（N）。

这里给出与上图等价的一个NFA。

4.3.3不确定的有穷自动机N的确定化

　　根据定义，显然DFA是NFA的特例。

对于每个NFAM，存在一个DFAM′，使得L（M）=L（M′）。

　　对于任何两个有穷自动机M和M′，如果L（M）=L（M′），则称M与M′是等价的。

　　我们将介绍一种算法，对于给定的NFAM，构造其等价的DFAM′。

请你注意这个结论：

DFA是NFA的特例

　　对每个NFAN一定存在一个DFAM，使得L（M）=L（N）。

对每个NFAN存在着与之等价的DFAM。

与某一NFA等价的DFA不唯一。

　　在有穷自动机的理论里，有这样的定理：

设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。

我们不对定理进行证明，只介绍一种算法（这种