4_词法分析.ppt

《4_词法分析.ppt》由会员分享，可在线阅读，更多相关《4_词法分析.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 词法分析词法分析14.14.1 词法分析程序的设计词法分析程序的设计(1)(1)任务任务 主要任务主要任务 逐逐个个字字符符地地扫扫描描源源程程序序，识识别别单单词词符符号号（终终结结符符）。在在拼拼单单词词时时作作词词法法检检查查。每每识识别别出出一一个个单单词词，就就翻翻译译成成相相应应的的机机内内表表示（语法分析时的终结符）。示（语法分析时的终结符）。2删去注解、空格、续行符等删去注解、空格、续行符等插入某些信息插入某些信息 有有些些语语言言（如如FORTRANFORTRAN）无无语语句句结结束束符符“；”，就要插入句末符。，就要插入句末符。为为了了语语法法分分析析出出错错

2、处处理理的的错错误误定定位位，要要为为源程序增加行号（在列表文件中可见）。源程序增加行号（在列表文件中可见）。输出源程序清单输出源程序清单3(2)(2)实现方式实现方式 相对独立方式相对独立方式 完全独立方式完全独立方式源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序属性字序列属性字序列.语法分析程序语法分析程序源程序源程序词法分析程序词法分析程序Tokenget token.4(3)(3)单词类别及其输出形式单词类别及其输出形式单词类别及其输出形式单词类别及其输出形式 单词可作各种分类，典型地分为类：单词可作各种分类，典型地分为类：单词可作各种分类，典型地分为类：单词可作各种分类

3、，典型地分为类：保保保保留留留留字字字字：AND,BEGIN,FOR,TYPE,VARAND,BEGIN,FOR,TYPE,VAR等等等等（个个个个数数数数确定，可全体编为一类，称作确定，可全体编为一类，称作确定，可全体编为一类，称作确定，可全体编为一类，称作“一字一类一字一类一字一类一字一类”）标标标标识识识识符符符符：用用用用户户户户定定定定义义义义的的的的常常常常量量量量名名名名、变变变变量量量量名名名名、过过过过程程程程名名名名和和和和类类类类型型型型名名名名（个个个个数数数数不不不不确确确确定定定定，作作作作为为为为一一一一类类类类，称称称称作作作作“一一一一符符符符一一一一类类类类

4、”）常常常常量量量量：12,1997,4.14,12,1997,4.14,A,scnuA,scnu等等等等（个个个个数数数数不不不不确确确确定定定定，按按按按类型分类）类型分类）类型分类）类型分类）运运运运算算算算符符符符,=,=,SG构造方法构造方法（对右线性文法）（对右线性文法）(1)对对每每个个非非终终结结符符画画一一个个结结点点，开开始始符符S为为开开始结点；始结点；(2)增设一个终止结点增设一个终止结点Z;(3)对形如对形如Ua的规则，画一条从的规则，画一条从U到到Z的的a弧弧;(4)对形如对形如UaW的规则，画一条从的规则，画一条从U到到W的的a弧弧;对对左左线线性性文文法法，则则

5、把把上上述述算算法法中中的的“开开始始结结点点”与与“终止结点终止结点”互换，且将各弧反向。互换，且将各弧反向。UWaUaZ+9例例对无符号整数文法对无符号整数文法GN:NdN|d可构造状态图：可构造状态图：NZdd+-10例例2对标识符文法对标识符文法GI:Il|Il|Id可构造状态图：可构造状态图：d+-ZIll114.24.2正则表达式正则表达式(正则式正则式)和和正则集正则集(正则语言正则语言)(1)正规式和正规集正规式和正规集定义定义4.1（正则式和正则集）（正则式和正则集）在在字字母母表表V上上定定义义的的正正则则式式及及其其描描述述的的正正则集递归地定义如下：则集递归地定义如下：

6、是正则式，表示空集；是正则式，表示空集；是正则式，表示是正则式，表示；每个每个aV是正则式，表示是正则式，表示a；12若若P和和Q是是正正则则式式，分分别别表表示示正正则则集集L(P)和和L(Q)，则则a)P|Q是正则式，表示是正则式，表示L(P)L(Q)“或或”b)PQ是正则式，表示是正则式，表示L(P)L(Q)“联结联结”c)P*是正则式，表示是正则式，表示L(P)*“闭包闭包”d)(P)是正则式，表示是正则式，表示L(P)仅由有限次使用上述步骤得到的正则式，仅由有限次使用上述步骤得到的正则式，才是才是V上的正则式。运算的优先次序为：上的正则式。运算的优先次序为：*.|(其中其中“|”可写

7、作可写作“+”)。13例：例：设设V=a,b,0,1,则则(a|b)(0|1)(a|b)(a|b|0|1)*(0|1)(0|1)*例：例：PASCAL的无符号实数的正则式：的无符号实数的正则式：d*(.dd*|)(E(+|-|)dd*|)(d为为0-9中的数字中的数字)在前面加上在前面加上(+|-|)后，就是符号实数的定义。后，就是符号实数的定义。表示表示V上的全体标识符上的全体标识符表示表示V上的全体整数上的全体整数 a0,a1,b0,b114定义定义4.2对正则式对正则式P和和Q，若若L(P)L(Q)，则则P与与Q等价，记为等价，记为P=Q。例：例：b(ab)*(ba)*bb(ab)*=(

8、ba)*b=b(ab)n|n0=(ba)nb|n015定理定理4.1对正则式对正则式P,Q,R，以下关系成立：以下关系成立：(1)P|Q=Q|P“或或”交换律交换律(2)P|(Q|R)=(P|Q)|R“或或”结合律结合律(3)P(QR)=(PQ)R“联结联结”结合律结合律(4)P(Q|R)=PQ|PR“联联结结”对对“或或”的左分配律的左分配律(5)(Q|R)P=QP|RP“联联结结”对对“或或”的右分配律的右分配律(6)P=P=P(7)P=P=|P=P|=P16(2)由正则文法构造正则式由正则文法构造正则式(3G-RE)定理定理4.2正则文法规则正则文法规则Ua1W1|a2W2|anWn|b

9、1|b2|bm的等价正则式方程为其中的等价正则式方程为其中U=(b1+b2+bm)+a1W1+a2W2+anWn其中其中Wi是正则变量是正则变量“|”可以写为可以写为“+”17定理定理4.3设设X是正则变量，是正则变量，a和和b是正则是正则式，且式，且X=aX+b则则X=a*b。若若X=Xb+a则则X=ab*。证证：由定理：由定理4.2，正则式方程，正则式方程X=aX+b等等价于以下正则规则：价于以下正则规则：XaX|b其定义的语言和正则式其定义的语言和正则式a*b一样，同为：一样，同为：anb|n=018定义定义4.4n元正则式方程组的标准形式：元正则式方程组的标准形式：X1=a10+a11

10、X1+a12X2+a1nXnX2=a20+a21X1+a22X2+a2nXnXn=an0+an1X1+an2X2+annXn其中，其中，aij是正则式，但不含变量；是正则式，但不含变量；Xi是正则变量（待定正则式）。是正则变量（待定正则式）。19例：例：对文法对文法G:SG:SaA aA A AbSbS|a|a用正则式来描述文法定义的语言：用正则式来描述文法定义的语言：解解:根据定理根据定理4.2S=aA A=a+bS 把把式代入式代入式，式，S=a(a+bS)=aa+abS根据定理根据定理4.3 S=(ab)*aa20例例:对正则文法对正则文法G建立正则式方程：建立正则式方程：G:SaS|b

11、R|RaS解解1:式代入式代入式，得式，得S=+aS+baS=(a+ba)S+=(a|ba)*S=+aS+bRR=aS解解2:=aS+(+baS)=a*(+baS)=a*baS+a*=(a*ba)*a*21例：例：对正则文法对正则文法G建立正则式方程：建立正则式方程：G:S0A|1B|0|1S=(0+1)+0A+1BA0S|1B|1A=1+0S+1BB0A|1S|B=+1S+0A把把B分别代入分别代入和和式，得式，得S=(0+1)+(0+10)A+11SA=1+0S+1(+1S+0A)=1+(0+11)S+10A10A是递归项是递归项=10A+(1+(0+11)S)分为递归项和非递归项分为递归

12、项和非递归项=(10)*(1+0+11)S)(续续)22将将A代入代入式，得式，得S=(0+1)+(0+10)(10)*(1+(0+11)S)+11S=(0+1)+(0+10)(10)*1+(0+10)(10)*(0+11)+11)S=(0+10)(10)*(0+11)+11)*(0+1+(0+10)(10)*1)=(0|10)(10)*(0|11)|11)*(0|1|(0|10)(10)*1)234.34.3有穷自动机有穷自动机(FA)FA)(1)确定有穷自动机（确定有穷自动机（DFA）定定义义4.5一一个个确确定定有有限限自自动动机机(DFA)M是是一一个个五元组：五元组：M=(K,VT,

13、f,S,Z)其中其中K：有穷状态集；有穷状态集；VT：有穷的输入字母表；有穷的输入字母表；f：KVTK是状态转换函数，即是状态转换函数，即f(W,a)=U表示当前状态表示当前状态W下，输入下，输入a时，转到状态时，转到状态U。S：唯一的开始状态唯一的开始状态，SK;Z：终止状态集，是终止状态集，是K的非空子集。的非空子集。24例：例：设有设有M1=(0,1,2,3,a,b,f,0,3),其中：其中：f(0,a)=1f(0,b)=2f(1,a)=3f(1,b)=2f(2,a)=1f(2,b)=3f(3,a)=3f(3,b)=3状态转换表状态转换表的行标表示状态，列标表示输入的行标表示状态，列标表

14、示输入符号，表元素表示符号，表元素表示f(W,a)的值的值。fab-012132213+333KVT25定义定义4.6 字母表字母表V上的上的状态图状态图SG是如下有向图：是如下有向图：(1)至少有一个初始结点，用至少有一个初始结点，用“”标记；标记；(2)至少有一个终止结点，用至少有一个终止结点，用“”标记；标记；(3)每条边上标记每条边上标记V上的符号串（可以是上的符号串（可以是）。）。其中，其中，结点结点表示状态，表示状态，边边表示所标记的符表示所标记的符号串相应的状态转移。号串相应的状态转移。它所对应的转换函数是它所对应的转换函数是f(W,a)=U WUa26假定假定假定假定DFA M

15、DFA MDFA MDFA M含有含有含有含有m m m m个状态和个状态和个状态和个状态和n n n n个输入字符，那么，这个输入字符，那么，这个输入字符，那么，这个输入字符，那么，这个图含有个图含有个图含有个图含有m m m m个状态结点，每个结点最多只能有个状态结点，每个结点最多只能有个状态结点，每个结点最多只能有个状态结点，每个结点最多只能有n n n n条条条条弧从结点射出并与别的结点相连结，每条弧上的标弧从结点射出并与别的结点相连结，每条弧上的标弧从结点射出并与别的结点相连结，每条弧上的标弧从结点射出并与别的结点相连结，每条弧上的标记是输入字母表记是输入字母表记是输入字母表记是输入

16、字母表上的一个字符。整个图只有一个初上的一个字符。整个图只有一个初上的一个字符。整个图只有一个初上的一个字符。整个图只有一个初态态态态结结结结点点点点，用用用用=或或或或标标标标以以以以“”射射射射入入入入的的的的节节节节点点点点表表表表示示示示初初初初态，态，态，态，终态可由若干个，也可以没有，用双圆圈或标以终态可由若干个，也可以没有，用双圆圈或标以终态可由若干个，也可以没有，用双圆圈或标以终态可由若干个，也可以没有，用双圆圈或标以“”表示。表示。表示。表示。12 0 3abaabba,b_+fa b-012132213+33327例：例：设有M1=(0,1,2,3,a,b,f,0,3),f

17、(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 FASG：12 0 3abaabba,b_+从初始结点出发到任一个终止结点的任一条路径上各边标记的符号串的连结，是SG可接受的符号串。28定理定理4.4若DFA上有且仅有一条从初态到终态的路径产生x，则x为DFA所能识别的字符串。例：例：输入字符串aabABDCaaabbbb_+29显然，显然，不能被接受不能被接受的字符串有两种情况：的字符串有两种情况：(1)读完输入串，状态不停在终态；读完输入串，状态不停在终态；(2)在读过程中出现不存在的映射，使自动

18、机无在读过程中出现不存在的映射，使自动机无法继续动作。法继续动作。ABDCaaabbbb_+当前状态 输入字符串 后继状态A aabBB abCC bD30定义定义4.7确定有穷自动机确定有穷自动机DFA的状态转换函的状态转换函数数f可扩充为：可扩充为：g:KVT*K特别地，特别地，g(W,)=W对空串，状态不变对空串，状态不变g(W,a)=g(f(W,a),)=f(W,a)即，即，f有定义，则有定义，则f与与g一致。一致。g(W,a1a2)=g(g(W,a1),a2)=f(f(W,a1),a2)g(W,a1a2an)=g(g(g(g(W,a1),a2),),an)=f(f(f(f(W,a1)

19、,a2),),an)31定义定义4.8若若xVT*且且g(S,x)Z，则称则称x为为DFA所识别的字符串。所识别的字符串。例：例：输入字符串输入字符串aabg(A,aab)=g(g(A,a),ab)=g(B,ab)=g(g(B,a),b)=g(C,b)=DABDCaaabbbb_+所有所有DFA所能识别的字符串集合记为所能识别的字符串集合记为L(DFA)32例：例：四个四个DFA能识别的语言能识别的语言 A ZaaAaAZa+ab Aab+aa*|A(a|b)*|33例：设有M2=(A,B,C,D,a,b,f,A,D),从前几例可见，从前几例可见，f是单值的，即是单值的，即“确定的确定的”。f

20、a b-ABABCCBD+DBAABDCaaabbbb_+34(2)(2)非确定有穷自动机（非确定有穷自动机（NFA）定义定义4.9一个非确定有限自动机一个非确定有限自动机(NFA)M是一是一个五元组个五元组M=(K,VT,f,S,Z)其中其中:K：有穷状态集；有穷状态集；VT：有穷的输入字母表；有穷的输入字母表；f：KVT(K)(K的子集的子集)是状态转换函数；是状态转换函数；S：为初态集，是为初态集，是K的非空子集的非空子集;Z：是终态集，是是终态集，是K的非空子集。的非空子集。35NFANFA与与与与DFADFA的主要区别是：的主要区别是：的主要区别是：的主要区别是：(1)(1)S S是

21、初态集，初态不唯一；是初态集，初态不唯一；是初态集，初态不唯一；是初态集，初态不唯一；(2)(2)f f是多值函数，一个结点的多条引出弧可是多值函数，一个结点的多条引出弧可是多值函数，一个结点的多条引出弧可是多值函数，一个结点的多条引出弧可标同一符号。标同一符号。标同一符号。标同一符号。定义定义定义定义4.104.10非确定有穷自动机非确定有穷自动机非确定有穷自动机非确定有穷自动机NFANFA的状态转换的状态转换的状态转换的状态转换函数函数函数函数f f可如可如可如可如D DFAFA扩充为：扩充为：扩充为：扩充为：g:Kg:K V VT T*(K)(K)特别地，特别地，特别地，特别地，g(W,

22、g(W,)=W)=W g(W,g(W,txtx)=)=g(Pg(Pi i,x),x)其中其中其中其中P Pi i g(W,t),tg(W,t),tV VT T,x,xV VT T*i36例例设有设有M3=(P,Q,R,a,b,f,S,Z),其中其中S=P,Q,Z=R P Q Rab_+bbbL(M3)=b*(ab(bb)*|b(bb)*)|b(bb)*37定理定理4.7对任意的正则式对任意的正则式e，存在接受正则存在接受正则集集L(e)的非确定有穷自动机的非确定有穷自动机NFA，反之亦然反之亦然。4.4由正则式构造自动机由正则式构造自动机NFA（自动机）自动机）38RERE NFANFA构造方

23、法：见书构造方法：见书构造方法：见书构造方法：见书P62P62 正则式正则式正则式正则式转换系统转换系统转换系统转换系统 a aPQPQP|QP|QPP*SZSZ SZaSiZPQSZPQSZPQSZP|QSiZ SZP*j P39例：例：构造出正则式构造出正则式(a|b)*abb的的自动机自动机(1)(2)(3)(4)(5)SZ(a|b)*abbSZ(a|b)*abbSZ(a|b)*abbZSabb a|b ZS abbab40定义4.11 设设I是是K的状态子集，的状态子集，I的的闭包闭包（-CLOSURE(I)）为：为：(1)若状态若状态PI，则则P-CLOSURE(I)；(2)若状态若

24、状态PI，则则P-CLOSURE(I),其中其中P为由为由P出发，经任意条出发，经任意条弧可达弧可达的的K中的状态。中的状态。4.5NFADFA（确定化）确定化）41例：例：设有NFA的状态转换图如下:5S3124Z6abaabbabI-CLOSURE(I)SS,2 S,3,1S,3,1,2,4,Z_+42定义定义4.12设设I是是K的状态子集，状态集的状态子集，状态集合合I的的a弧转换弧转换（move(I,a)）,表示表示I中状中状态经过一条态经过一条a边可到达的状态的集合。而边可到达的状态的集合。而Ia=-CLOSURE(move(I,a)。43例：例：设有NFA的状态转换图如下:5S31

25、24Z6abaabbabIMove(I,a)IaS,1,3+_3,53,1,544例：例：设有NFA的状态转换图如下NFADFA：5S3124Z6abaabbab+_45IMove(I,a)IaMove(I,b)IbS31353153631631535231524Z363163163531536231624Z31524Z352431524Z3643164Z31624Z3543154Z362431624Z3164Z3543154Z362431624Z3154Z352431524Z3643164Z根据上边状态转换矩阵，可以得到根据上边状态转换矩阵，可以得到DFA N的状态集合（表的的状态集合（表的

26、最左列状态），即最左列状态），即K=S31,315,316,31524Z,31624Z,3164Z,3154Z,开始状态：开始状态：S31,终止状态：终止状态：31524Z,31624Z,3164Z,3154Z46(4)确定有穷自动机的化简（求最小确定有穷自动机的化简（求最小DFA）最小最小DFA的含义：的含义：（1）没有多余状态（）没有多余状态（死状态）死状态）（2）没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状态两个状态两个状态s s和和和和t t等价的条件：等价的条件：等价的条件：等价的条件：一致性一致性一致性一致性s s和和和和t t同是终态或同是非

27、终态同是终态或同是非终态同是终态或同是非终态同是终态或同是非终态蔓延性蔓延性蔓延性蔓延性从从从从s s出发读入某个出发读入某个出发读入某个出发读入某个a a a a和从和从和从和从t t出发出发出发出发读入读入读入读入 某个某个某个某个a a到达的状态等价。到达的状态等价。到达的状态等价。到达的状态等价。对于对于对于对于 a a,f(r,a)=r,f(r,a)=r,f(s,a)=s,f(s,a)=s,rr和和和和s s必须等价。必须等价。必须等价。必须等价。47定义定义4.13不同状态不同状态A和和B是等价的，是等价的，当且仅当当且仅当f(A,t)Zf(B,t)ZtVT*,Z是终态集。是终态集

28、。若若A和和B不等价，则称为是可区分的。不等价，则称为是可区分的。48化简方法（分割法）化简方法（分割法）：(1)将将S划划分分为为终终态态集集和和非非终终态态集集，得得S=Z,S-Z。(2)递递归归地地分分割割S中中的的子子集集，使使得得任任何何两两个个不不同同子子集集的的状状态态都都是是可可区区分分的的，而同一个子集中的状态都是等价的。而同一个子集中的状态都是等价的。(3)S中的每个子集合并为一个状态。中的每个子集合并为一个状态。(4)含含原原初初态态的的状状态态为为初初态态；含含原原终终态态的状态为终态。的状态为终态。49例：设有例：设有例：设有例：设有DFAMDFAM如右图所示：如右图

29、所示：如右图所示：如右图所示：划分状态集为划分状态集为划分状态集为划分状态集为44和和和和 0,1,2,30,1,2,3对于对于对于对于0,1,2,30,1,2,3和输入字符和输入字符和输入字符和输入字符a a和和和和b:b:f(0,a)=1f(1,a)=1f(0,a)=1f(1,a)=1f(2,a)=1f(3,a)=1f(2,a)=1f(3,a)=1f(0,b)=2f(1,b)=3f(0,b)=2f(1,b)=3f(2,b)=2f(3,b)=4f(2,b)=2f(3,b)=4只有状态只有状态只有状态只有状态3 3在输入为在输入为在输入为在输入为b b时映像的后继状态不在时映像的后继状态不在时

30、映像的后继状态不在时映像的后继状态不在 0,1,2,30,1,2,3中，因此该状态集划分为中，因此该状态集划分为中，因此该状态集划分为中，因此该状态集划分为33和和和和0,1,20,1,2对于对于对于对于0,1,20,1,2：状态：状态：状态：状态1 1在输入为在输入为在输入为在输入为b b时的后继状态不在时的后继状态不在时的后继状态不在时的后继状态不在0,1,20,1,2中，因此划分为中，因此划分为中，因此划分为中，因此划分为11和和和和0,20,2对于对于对于对于0,2:0,2:对于相同输入字符，该子集中每一状态对于相同输入字符，该子集中每一状态对于相同输入字符，该子集中每一状态对于相同输

31、入字符，该子集中每一状态映像得到的后继状态都相同，因此不再可划分映像得到的后继状态都相同，因此不再可划分映像得到的后继状态都相同，因此不再可划分映像得到的后继状态都相同，因此不再可划分最后划分为：最后划分为：最后划分为：最后划分为：4310,24310,2b02314bbbbaaaaa50对于划分结果对于划分结果4,3,1,0,2，把，把0,2合并为一个状态，分别标记为新状态合并为一个状态，分别标记为新状态3,2,1,0，其状态转换图如图：，其状态转换图如图：3aaaabbb02102314bbbbbaaaaab351例：例：(先构造先构造DFA，再构造再构造MinDFA)设有设有NFAQ PZ11011,0_+_52