【教学课件】第三章词法分析.ppt

《【教学课件】第三章词法分析.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第三章词法分析.ppt（95页珍藏版）》请在三一办公上搜索。

1、第三章 词法分析,词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer)又称扫描器(Scanner)：执行词法分析的程序,3.1 对于词法分析器的要求,一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字：如 begin，repeat，标识符表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，界符：逗号、分号、括号和空白,输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算

2、符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。,例 C程序,while(i=j)i-;输出单词符号：=,-,例 FORTRAN程序,IF(5.EQ.M)GOTO 100输出单词符号：逻辑IF(34，-)左括号(2，-)整常数(20，5的二进制)等号(6，-)标识符(26，M)右括号(16，-)GOTO(30，-)标号(19，100的二进制),二、词法分析器作为一个独立子程序,词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶

3、段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。不作为一遍：将其处理为一个子程序。,词法分析器,词法分析器的结构,预处理子程序,扫描器,输入缓冲区,扫描缓冲区,单词符号,输入,列表,3.2 词法分析器的设计,输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区,起点 搜索指示器 指示器,一、输入、预处理,WhatALongWord,WhatALongWo,rd,rd,WhatALongWo,rd,WhatALongWo,二、单词符号的识别:超前搜索,1 基本字识别:例如:1 DO99K=1，10

4、DO 99 K=1，10 2 IF(5.EQ.M)GOTO55 IF(5.EQ.M)GOTO 553 DO99K=1.104 IF(5)=55需要超前搜索才能确定哪些是基本字,2 标识符识别:字母开头的字母数字串，后跟界符或算符3 常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。5.E084 算符和界符的识别把多个字符符合而成的算符和界符拼合成一个单一单词符号。：=，*，.EQ.，+，-，=,三、状态转换图,1 概念状态转换图是一张有限方向图。,结点代表状态，用圆圈表示。,状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。,一张转换图只包

5、含有限个状态，其中有一个为初态，至少要有一个终态。,识别标识符的状态转换图,1,2,3,字母,其他,字母或数字,*,识别整常数的状态转换图,一个状态转换图可用于识别(或接受)一定的字符串。,2 例子,助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。,几点重要限制不必使用超前搜索所有基本字都是保留字;用户不能用它们作自己的标识符基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。DO99K=1，10 要写成 DO 99 K=1，10,3 状态转换图的实现思想：每个状态结对应

6、一小段程序。做法:1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现,GetChar();if(IsLetter()状态j的对应程序段;else if(IsDigit()状态k的对应程序段;else if(ch=/)状态l的对应程序段;else 错误处理;,3 状态转换图的实现2)对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序.,GetChar();while(IsLetter()or IsDigit()GetChar();状态j的对应程序段,3 状态转换图的实现3)终态结表示识别出某种单词符号，因此，对应语句为 RETURN(C，VAL)其中

7、，C为单词种别，VAL为单词自身值.,全局变量与过程1)ch 字符变量、存放最新读入的源程序字符2)strToken 字符数组，存放构成单词符号的字符串3)GetChar 子程序过程，把下一个字符读入到 ch 中4)GetBC 子程序过程，跳过空白符，直至 ch 中读入一非空白符5)Concat 子程序，把ch中的字符连接到 strToken,6)IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字7)Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送08)Retract 子程序，把搜索指针回调一个字符位

8、置9)InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。,int code,value;strToken:=“”;/*置strToken为空串*/GetChar();GetBC();if(IsLetter()beginwhile(IsLetter()or IsDigit()beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalue:=InsertId(strToken);retu

9、rn($ID,value);endelsereturn(code,-);end,else if(IsDigit()beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);retrnr($INT,value);endelse if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);,else if(ch=*)beginGetChar();if(ch=*)return($POWER,-);Retract();return($STAR

10、,-);endelse if(ch=;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else if(ch=)return($LBRACE,-);else if(ch=)return($RBRACE,-);else ProcError();/*错误处理*/,3.3 正规表达式与有限自动机,几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如:设=a，

11、b，则*=,a,b,aa,ab,ba,bb,aaa,.,*的子集U和V的连接（积）定义为UV|U 记 VVV*，称V+是V的正规闭包。,3.3.1 正规式和正规集,正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。,冯-诺伊曼构造自然数的方案,01,2,3,正规式和正规集的递归定义：对给定的字母表1)和都是上的正规式，它们所表示的正规集为和;2)任何a，a是上的正规式，它所表示的正规集为a;,3)假定e1和e2都是上的正规式，它们所表示的正规集为L(e1)和L(e2)，则i)(e1|e2)为正规式，它所表示的正规集为L(e1)

12、L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1)*为正规式，它所表示的正规集为(L(e1)*，仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集。,所有词法结构一般都可以用正规式描述。若两个正规式所表示的正规集相同，则称这两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)*对正规式，下列等价成立：e1|e2=e2|e1 交换律e1|(e2|e3)=(e1|e2)|e3 结合律e1(e2e3)=(e1e2)e3 结合律e1(e2|e3)=e1e2|e1e3 分配律(e2|e3)e1=e

13、2e1|e3 e1分配律e=e=e e1e2 e2 e1,3.3.2 确定有限自动机(DFA),对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,f,S0,F),其中：1.S:有穷状态集，2.：输入字母表(有穷)，3.f:状态转换函数，为SS的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。4.S0S是唯一的一个初态；5 FS：终态集(可空)，。,例如：DFA M=(0，1，2，3，a，b，f，0，3)，其中：f定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(

14、2，b)=3f(3，a)=3 f(3，b)=3,状态转换矩阵,DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用上的不同的输入字符来作标记。,对于*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于，则称为DFA M所识别(接收)DFA M所识别的字的全体记为L(M)。可以证明：上的字集V*是正规集，当且仅当存在上的DFA M，使得VL(M)。,3.3.3 非确定有限自动机(NFA),定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,f,S0,F)，其中：1

15、 S:有穷状态集；2：输入字母表(有穷)；3 f:状态转换函数，为S*2S的部分映射(非单值)；4 S0S是非空的初态集；5 F S：终态集(可空)。,从状态图中看NFA 和DFA的区别：1 弧上的标记可以是*中的一个字，而不一定是单个字符；2 同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。,识别所有含相继两个a或相继两个b的字,ambn|m，n1,定义：对于任何两个有限自动机M和M，如果L(M)=L(M)，则称M与M等价。自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。对于每个NFA M存在一个DFA M，使得 L(M)=L(M)。亦即DFA与NFA描述能力相

16、同。,1.假定NFA M=，我们对M的状态转换图进行以下改造：1)引进新的初态结点X和终态结点Y，X,YS，从X到S0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。2)对M的状态转换图进一步施行替换，其中k是新引入的状态。,证明:,代之为,代之为,代之为,按下面的三条规则对V进行分裂:,逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然L(M)=L(M),识别所有含相继两个a或相继两个b的字,2.把上述NFA确定化采用子集法.,设I是的状态集的一个子集，定义I的-闭包-closure(I)为:i)若sI，则s-closure(I)；ii)若sI，则从s出

17、发经过任意条弧而能到达的任何状态s都属于-closure(I)即-closure(I)=Is|从某个sI出发经过任意条弧能到达s,设a是中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。,-closure(1)=1，2=I J=5，4，3 Ia=-closure(J)=(5，4，3，6，2，7，8),把确定化的过程:不失一般性，设字母表只包含两个a和b，我们构造一张表:,首先，置第1行第1列为-closure(X)求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出

18、每行第2，3列上的集合.重复上述过程，知道所有第2，3列子集全部出现在第一列为止。,I,Ia,Ib,X,5,1,5,3,1,5,4,1,5,3,1,5,2,3,1,6,Y,5,4,1,5,4,1,5,3,1,5,2,4,1,6,Y,5,2,3,1,6,Y,5,2,3,1,6,Y,5,4,6,1,Y,5,4,6,1,Y,5,3,6,1,Y,5,2,4,1,6,Y,5,2,4,1,6,Y,5,3,6,1,Y,5,2,4,1,6,Y,5,3,6,1,Y,5,2,3,1,6,Y,5,4,6,1,Y,现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，

19、它的初态是-closure(X)，它的终态是含有原终态Y的子集。不难看出，这个DFA M与M等价。,3.3.4 正规文法与有限自动机的等价性,对于正规文法G和有限自动机M，如果L(G)L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：,3.3.4 正规文法与有限自动机的等价性,定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)L(G)。2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。,证明：1.对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA

20、）M，使得L(M)L(G)。(1)设右线性正规文法G=。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fVN。令M=，其中状态转换函数由以下规则定义：,(a)若对某个AVN及aVT，P中有产生式Aa，则令(A,a)=f(b)对任意的AVN及aVT，设P中左端为A，右端第一符号为a的所有产生式为：AaA1|aAk（不包括Aa），则令(A,a)=A1,Ak。显然，上述M是一个NFA。,对于右线性正规文法G，在S w的最左推导过程中:利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=的情形）;在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的

21、箭弧到达终结状态f（包括a=的情形）。综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wL(G)当且仅当wL(M)，故L(G)L(M)。,(2)设左线性正规文法G=。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0VN。令M=，其中状态转换函数由以下规则定义：(a)若对某个AVN及aVT，若P中有产生式Aa，则令(q0,a)=A(b)对任意的AVN及aVT，若P中所有右端第一符号为A，第二个符号为a的产生式为：A1Aa,AkAa，则令(A,a)=A1,Ak。与(1)类似，可以证明L(G)L(M

22、)。,GR(A)：A0|0B|1DB0D|1CC0|0B|1DD0D|1D从GR出发构造NFA M=，M的状态转换图如右图所示。显然 L(M)=L(GR)。,例:,证明2：对每一个DFA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。设DFA M=(1)若s0F，我们令GR=，其中P是由以下规则定义的产生式集合：对任何a及A,BS，若有(A,a)=B，则：(a)当BF时，令AaB，(b)当BF时，令Aa|aB。,对任何w*，不妨设w=a1ak，其中ai(i=1,k)。若s0 w，则存在一个最左推导：s0a1A1a1a2A2a1aiAia1ai+1Ai+

23、1a1ak因而，在M中有一条从s0出发依次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,ak。反之亦然。所以，wL(GR)当且仅当wL(M)。,现在考虑s0F的情形：因为(s0,)=s0，所以L(M)。但不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-。所以，我们在上述GR中添加新的非终结符号s0，(s0S)和产生式s0s0|，并用s0代替s0作开始符号。这样修正GR后得到的文法GR仍是右线性正规文法，并且L(GR)=L(M)。(2)类似于(1)，从DFA M出发可构造左线性正规文法GL，使得L(GL)=L(M)。最后，由DFA和NFA之间的等

24、价性，结论2得证。,L(M)=0(10)*GR=，其中P由下列产生式组成：A0|0B|1DB0D|1CC0|0B|1DD0D|1DL(GR)=L(M)=0(10)*,例3.4 设DFA M=。M的状态转换图如下图所示。,从NFA M出发构造左线性正规文法GL=，其中P由下列产生式组成：f0|C0CB1B0|C0D1|C1|D0|D1|B0易证 L(GL)=L(M)。,例3.4 设DFA M=。M的状态转换图如图3.9(a)所示。,3.3.5 正规式与有限自动机的等价性,定理：1.对任何FA M，都存在一个正规式r，使得L(r)=L(M)。2.对任何正规式r，都存在一个FA M，使得L(M)=L

25、(r)。对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号),证明：1 对上任一NFA M，构造一个上的正规式r，使得L(r)=L(M)。首先，在M的转换图上加进两个状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；,代之为,代之为,代之为,1,2,5,4,V1(U1|U2)*W1,V1(U1|U2)*W2,V2(U1|U2)*W2,V2(U1|U2)*W1,最后，X到Y的弧上标记的正规式即为所构造

26、的正规式r显然L(r)=L(M)=L(M),证明2:对于上的正规式r，构造一个NFA M，使L(M)=L(r)，并且M只有一个终态，而且没有从该终态出发的箭弧。下面使用关于r中运算符数目的归纳法证明上述结论。(1)若r具有零个运算符，则r=或r=或r=a，其中a。此时下图所示的三个有限自动机显然符合上述要求。,(2)假设结论对于少于k(k1)个运算符的正规式成立。当r中含有k个运算符时，r有三种情形：情形1：r=r1|r2，r1,r2中运算符个数少于k。从而，由归纳假设，对ri存在Mi=，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。不妨设S1S2=，在S1 S2中加

27、入两个新状态q0，f0。,令M=，其中定义如下：(a)(q0,)=q1,q2(b)(q,a)=1(q,a),当qS1-f1,a1(c)(q,a)=2(q,a),当qS2-f2,a2(d)(f1,)=(f2,)=f0。M的状态转换如右图所示。L(M)=L(M1)L(M2)=L(r1)L(r2)=L(r),q0,f0,情形2：r=r1r2,设Mi同情形1(i=1,2)。令M=，其中定义如下：(a)(q,a)=1(q,a),当qS1-f1,a1(b)(q,a)=2(q,a),当qS2,a2(c)(f1,)=q2 M的状态转换如右图所示。L(M)=L(M1)L(M2)=L(r1)L(r2)=L(r)。

28、,情形3：r=r1*。设M1同情形1。令M=，其中q0,f0S1，定义如下：(a)(q0,)=(f1,)=q1,f0(b)(q,a)=1(q,a),当qS1-f1,a1。M的状态转换如右图所示。L(M)=L(M1)*=L(r1)*=L(r)至此，结论2获证。,q0,f0,1)构造上的NFA M 使得 L(V)=L(M)首先，把V表示成,上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。,代之为,代之为,代之为,然后，按下面的三条规则对V进行分裂,逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然L(M)=L(V),(a|b)*(aa|bb)(a|b)*,3.

29、3.6 确定有限自动机的化简,对DFA M的化简:寻找一个状态数比M少的DFA M，使得L(M)=L(M)假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字而停止于终态，那么同样，从t出发也能读出而停止于终态；反之亦然。两个状态不等价，则称它们是可区别的。,对一个DFA M最少化的基本思想:把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。,具体做法:对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分。假定到某个时候，已含m个子集，记为=I(1)，I(

30、2)，I(m)，检查中的每个子集看是否能进一步划分:对某个I(i)，令I(i)=s1,s2,sk，若存在一个输入字符a使得Ia(i)不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。,例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行中的两个不同子集，说明有一个字，t1读出后到达终态，而t2读出后不能到达终态，或者反之，那么对于字a，s1读出a后到达终态，而s2读出a不能到达终态，或者反之，所以s1和s2不等价。则将分成两半，使得一半含有s1:I(i1)=s|sI(i)且s经a弧到达t,且t与t1属于现行中的同一子集 另一半含有s2:I(i2)=I(i)-

31、I(i1),一般地，对某个a和I(i)，若Ia(i)落入现行中 N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的同一子集。这样构成新的划分。重复上述过程，直到所含子集数不再增长。对于上述最后划分中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的DFA M。若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。,I(1)=0,1,2 I(2)=3,4,5,6,Ia(1)=1,3 I(11)=0,2 I(12)=1,I(2)=3,4,5,6,I(11)=0,2Ia(11)=1 Ib(11)=2,5 I(111)=0 I(

32、112)=2,I(12)=1 I(2)=3,4,5,6,Ia(2)=3,6 Ia(2)=4,5,3.4 词法分析器的自动产生-LEX,词法分析程序自动产生器,词法分析程序L,LEX源程序,词法分析程序L,单词符号,输入串,状态转换矩阵,控制执行程序,AUXILIARY DEFINITIONletterA|B|.|Zdigit 0|1|.|9RECOGNITION RULES1DIM RETURN(1,-)2IF RETURN(2,-)3DO RETURN(3,-)4STOP RETURN(4,-)5END RETURN(5,-)6letter(letter|digit)*RETURN(6,TO

33、KEN)7digit(digit)*RETURN(7,DTB)8=RETURN(8,-)9+RETURN(9,-)10*RETURN(10,-)11*RETURN(11,-)12,RETURN(12,-)13(RETURN(13,-)14)RETURN(14,-),LEX的工作过程：首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi；然后，引进一个新初态X，通过弧，将这些自动机连接成一个新的NFA；最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序,X,P2,M1,Mm,M2,P1,Pm,作业,P64-7，8，12，14,例:对下图NFA M构造其DFA.,解:,用子集法构造转换矩阵,不可识别ba!,1,2 0,ba！,