编译原理第三章词法分析

1第三章词法分析词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。本章重点：正规式、有限自动机（DFA、NFA）、NFA到DFA的转换、DFA的最小化。第一节词法分析程序的设计一、词法分析程序的输出词法分析程序的功能是读入源程序，输出单词符号，单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分为下列5种：1、基本字，也称关键字，如PASCAL语言中的begin,end,if,while和var等。2、标识符，用来表示各种名字，如常量名、变量名和过程名等。3、常数，各种类型的常数，如25,3.1415,TRUE和“ABC”等。4、运算符，如+,﹡,=等。5、界符，如逗点，分号，括号等。词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在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，‘；’）第二节单词的描述工具程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立分析技术，进而可以建立词法分析程序的自动构造方法。一、正规文法多数程序设计语言的单词的语法都能用正规文法或3型方法来描述。回顾一下3型方法G=（VN，VT，S，P）的特征，即P中的每一条规则都有下述形式：A→aB或A→a其中A，B∈VN，a∈V*T。正规文法所描述的是V*T上的正规集。程序设计语言中的几类单词可用下述规则描述：标识符→1|1字母数字字母数字→1|d|1字母数字|d字母数字无符号整数→d|d无符号整数运算符→+|—|﹡|/|等号|等号……等号→=界符→，|；|（|）|……其中1表示a~z中的任何一英文字母，d表示0~9中的任一数字。二、正规式正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。2下面是正规式和它所表示的正规集的递归定义。设字母表为Σ，辅助字母表Σ′={Ø，ε,|,·,﹡,(,)}。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、仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。例1令Σ=｛a,b｝,Σ上的正规式和相应的正规集的例子有：正规式正规集a｛a｝a|b｛a,b｝ab｛ab｝(a|b)(a|b)｛aa,ab,ba,bb｝a﹡｛ε,a,aa,…任意个a的串｝(a|b)﹡｛ε,a,b,aa,ab…所有a,b组成的串｝(a|b)﹡(aa|bb)(a|b)﹡Σ﹡上所有含有两个相继的a或两个相继的b组成的串。三、正规文法到正规式一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的正规文法，有些正规语言很容易用文法定义，有些语言更容易用正规式定义，本节介绍两者间的转换，从结构上建立它们的等价性。1、将Σ上的一个正规式转换成文法G=（VN，VT，S，P）。令其中的VT=Σ，确定产生式和VN的元素用如下办法。对任何正规式r，选择一个非终结符S生成产生式S→r，并将S定为G的识别符号。若x和y都是正规式，对形如A→xy的产生式，重写成：A→xB,B→y两产生式，其中B是新选择的非终结符，即B∈VN。对已转换的文法中的形如A→x﹡y的产生式，重写为：A→xBA→yB→xBB→y其中B为一新非终结符，对形如A→x|y的产生式，重写为：A→xA→y不断利用上述规则做变换，直到每个产生式最多含有一个终结符为止。例2将R=a(a|d)﹡转换成相应的正规文法，令S是文法的开始符号，首先形成S→a(a|d)﹡,然后形成S→aA和A→(a|d)﹡，再重写第二条产生式形成S→aA,A→(a|d)B,A→ε,B→(a|d)B和B→ε进而变换为S→aA,B→aB,A→aB,B→dBA→dB,B→εA→ε2、将正规文法转换成正规式。基本上是上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符。其转换规则列于表4.1表4.1正规文法到正规式的转换规则文法产生式正规式规则1规则2规则3A→xB,B→yA→xA|yA→xA→yA→xyA→x﹡yA→x|y例3文法G[S]S→aAS→a3A→aAA→dAA→aA→d先有：S=aA|aA=(aA|dA)|(a|d)再将A的正规式变换为A=(a|d)A|(a|d)，据表中规则2变换为：A=(a|d)*(a|d)，再将A右端代入S的正规式得：S=a(a|d)*(a|d)|a再利用正规式的代数变换可依次得到S=a(a|d)*(a|d)|a即a(a|d)*为所求。第三节有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（DeterministicFiniteAutomata）和不确定的有穷自动机（NondeterministicFiniteAutomata），下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。一、确定的有穷自动机（DFA）一个确定的有穷自动机（DFA）M是一个五元组：M=（K,Σ,f,S,Z）其中1、K是一个有穷集，它的每个元素称为一个状态；2、Σ是一个有穷字母表，它的每个元素称为一个输入字符，所以也称Σ为输入符号字母表；3、f是转换函数，是在k×Σ→K上的映像，即，如f(ki,a)=kj(ki∈k,kj∈k)就意味着，当前状态为Ki，输入字符为a时，将转换到一状态kj，我们把kj称作ki的一个后继状态；4、S∈K是唯一的一个初态；5、ZK，是一个终态集，终态也称可接受状态或结束状态。例3DFAM=（｛S,U,V,Q｝,｛a,b｝,f,S,｛Q｝）其中f定义为：f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,b)=Q一个DFA可以表示成一个状态图（或称状态转换图）。假定DFA有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以“”或标以“—”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj，画标记为a的弧；例3中的DFA的状态图表如图3-3-1。字符状态abSUV0UQV0VUQ0QQQ1图3-3-2矩阵表示a.baaababb图3-3-1状态图表示UQQQQSVa.baaababb图3-3-1状态图表示UQFQQQSV4a，bbaaabbab图3-3-3NFAM01342一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用“”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。例3中的DFA的矩阵表示如图3-3-2对于Σ﹡中的任何字符串t,若存在一条从初态结到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFAM所接受，若M的初态结同时又是终态结，则空字可为M所识别（接受）。DFAM所能接受的字符串的全体（字的全体）记为L（M）。结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。DFA的确定性表现在转换函数f：K×∑→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈∑，f（k，a）唯一地确定了下一个状态。从状态转换图来看，若字母表∑含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。二、不确定的有穷自动机（NFA）一个不确定的有穷自动机（NFA）M是一个五元组，M=（K，∑，f，S，Z）其中1．K是一个有穷集，它的每个元素称为一个状态；2．∑是一个有穷字母表，它的每个元素称为一个输入字符；3．f是一个从K×∑*到K的子集的映像。4．S⊂K，是一个非空初态集；5．Z⊂K，是一个终态集。一个含有m个状态和n个输入字符的NFA可表示成如下的一张状态转换图：这张图含有m个状态结，每个结可射出若干条箭弧与别的结相连接，每条弧用∑*中的一个串作标记，整个图至少含有一个初态结以及若干个终态结。例4一个NFAM=（{0，1，2，3，4}，{a，b}，f，{0}，{2，4}）其中f（0，a）={0，3}f（2，b）={2}f（0，b）={0，1}f（3，a）={4}f（1，b）={2}f（4，a）={4}f（2，a）={2}f（4，a）={4}它的状态图表示如图3-3-3。对于∑*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串（不理采那些标记为ε的弧）等于t，则称t可为NFAM所识别（读出或接受）。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε道路，那么空字可为M所接受。显然DFA是NFA的特例。对于每个NFAM，存在一个DFAM、使得L（M）=L（M`）。对于任何两个有穷自动机M和M`，如果L（M）=L（M`），则称M与M`是等价的。三、NFA→DFA的转换为介绍算法首先定义对状态集合I的几个有关运算：1．状态集合I的ε—闭包，表示为ε—closure（I），定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。如输入字符是空串，则自动机仍停留在原来的状态上，显然，状态集合I的任何状态S都属于5εaεεεεεabbεbεε图3-3-4NFAN012435678910ε—closure（I）。2．状态集合I的a弧转换，表示为move（I，a）定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。假设NFAN＝（K，∑，f，K0，Kt）按如下办法构造一个DFAM＝（S，∑，D，S0，St）使得L（M）＝L（N）：1．M的状态集S由D的一些子集组成。（构造K的子集的算法将在后面给出）我们用[S1，S2，…，Sj]表示S