编译原理课件Chapter4.ppt

《编译原理课件Chapter4.ppt》由会员分享，可在线阅读，更多相关《编译原理课件Chapter4.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 词法分析14.1 词法分析程序的设计(1)任务任务 主要任务主要任务 逐逐个个字字符符地地扫扫描描源源程程序序，识识别别单单词词符符号号（终终结结符符）。在在拼拼单单词词时时作作词词法法检检查查。每每识识别别出出一一个个单单词词，就就翻翻译译成成相相应应的的机机内内表表示（语法分析时的终结符）。示（语法分析时的终结符）。2删去注解、空格、续行符等删去注解、空格、续行符等插入某些信息插入某些信息为为了了语语法法分分析析出出错错处处理理的的错错误误定定位位，要要为为源程序增加行号（在列表文件中可见）。源程序增加行号（在列表文件中可见）。有有些些语语言言（如如FORTRAN）无无语语句句结结

2、束束符符“；”，就要插入句末符。，就要插入句末符。输出源程序清单输出源程序清单3(2)实现方式实现方式 相对独立方式相对独立方式 完全独立方式完全独立方式源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序属性字序列属性字序列.语法分析程序语法分析程序源程序源程序词法分析程序词法分析程序Tokenget token.4(3)单词类别及其输出形式单词类别及其输出形式 单词可作各种分类，典型地分为类：单词可作各种分类，典型地分为类：保保留留字字：AND,BEGIN,FOR,TYPE,VAR等等（个个数数确定，可全体编为一类，称作确定，可全体编为一类，称作“一符一类一符一类”）标标识识符符：

3、用用户户定定义义的的常常量量名名、变变量量名名、过过程程名名和和类型名类型名（个数不确定，作为一类）（个数不确定，作为一类）常常量量：12,1997,4.14,A,scnu等等（个个数数不确定，按类型分类）不确定，按类型分类）运运算算符符,=,RE)定理定理4.2正则文法规则正则文法规则Ua1W1|a2W2|anWn|b1|b2|bm的等价正则式方程为其中的等价正则式方程为其中U=(b1+b2+bm)+a1W1+a2W2+anWn其中其中Wi是正则变量是正则变量15定理定理4.3设设X是正则变量，是正则变量，a和b是正则是正则式，且式，且X=aX+b则则 X=a*b。证证：由定理：由定理4.2

4、4.2，正则式方程，正则式方程X=aX+b等等价于以下正则规则：价于以下正则规则：XaX|b其定义的语言和正则式其定义的语言和正则式a*b一样，同为：一样，同为：anb|n=0 若若X=Xb+a 则则 X=？。（自己证明自己证明）16定义定义4.4 n元正则式方程组的标准形式：元正则式方程组的标准形式：X1=a10+a11X1+a12X2+a1nXn X2=a20+a21X1+a22X2+a2nXn Xn=an0+an1X1+an2X2+annXn其中，其中，aij是正则式，但不含变量；是正则式，但不含变量；Xi是正则变量（待定正则式）是正则变量（待定正则式）。17例：例：对文法对文法G:Sa

5、A AbS|a用正则式来描述文法定义的语言用正则式来描述文法定义的语言解解:根据定理根据定理4.2 S=aA A=a+bS 把把式代入式代入式，式，S=a(a+bS)=aa+abS根据定理根据定理4.3 S=(ab)*aa184.3有穷自动机(FA)(1)确定有穷自动机（DFA）定义4.5一一个个确确定定有有限限自自动动机机(DFA)M是是一一个个五元组：五元组：M=(K,VT,f,S,Z)其中其中K：有穷状态集；有穷状态集；VT：有穷的输入字母表；有穷的输入字母表；f：KVTK是状态转换函数，即是状态转换函数，即f(W,a)=U 表示当前状态表示当前状态W下，输入下，输入a时，转到状态时，转

6、到状态U。S：唯一唯一的开始状态的开始状态，SK;Z：终止状态终止状态集集，是，是K的非空子集。的非空子集。“确定确定”即即f是单值函数是单值函数。19例：例：设有M1=(0,1,2,3,a,b,f,0,3),其中：f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2f(2,a)=1 f(2,b)=3f(3,a)=3 f(3,b)=3fa b-012132213+333一个一个DFA可用一个矩阵表示，该矩阵的可用一个矩阵表示，该矩阵的行行表示表示状态，状态，列列表示输入字母，矩阵元素表示表示输入字母，矩阵元素表示f(W,a)的值，这个矩阵称的值，这个矩阵称状态转移矩阵状态转移

7、矩阵。20例：例：设有M1=(0,1,2,3,a,b,f,0,3),其中：f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2f(2,a)=1 f(2,b)=3f(3,a)=3 f(3,b)=3一个一个DFA也可用可用状态图状态图（SG）表示，该图中的表示，该图中的结点结点表示状态，若有表示状态，若有f(W,a)=U，则从状态结点则从状态结点W到到状态结点状态结点U画画标记为标记为a的的弧弧。12 0 3abaabba,b_+21关于DFA的基本概念：定理4.4若若DFA上有一条从初态到终态上有一条从初态到终态的路径产生的路径产生x，则，则x为为DFA所能识别的符所能识别的符

8、号串。号串。注意：注意：若初态和终态是同一状态，若初态和终态是同一状态，则表示则表示为为DFA所识别。所识别。例：例：可识别的符号串可识别的符号串aab,baab,ABDCaaababb_+22显然，不能被识别的字符串有显然，不能被识别的字符串有两种两种情况：情况：(1)读完输入串，状态读完输入串，状态不停在终态，不停在终态，例例aa；(2)在读过程中出现不在读过程中出现不存在的映射，使自动机存在的映射，使自动机无法继续动作，无法继续动作，例例ab。ABDCaaababb_+23定义定义4.7确定有穷自动机确定有穷自动机DFA的的状态转换函状态转换函数数f可扩充为：可扩充为：g:KVT*K特别

9、地，特别地，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,a1a2 an)=g(g(g(g(W,a1),a2),),an)=f(f(f(f(W,a1),a2),),an)24定义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)=DABDCaa

10、ababb_+定义4.9 所有所有DFA所能识别的字符串集合称所能识别的字符串集合称为为DFA所接受的语言，记为所接受的语言，记为L(DFA)25例：例：四个四个DFA能识别的语言能识别的语言 A ZaaAaAZa+ab Aab+26例：例：构造自动机构造自动机A，使得使得 L(A)=,bn,bna|n0 A Zab+27(2)(2)非确定有穷自动机（非确定有穷自动机（NFA）定义定义4.10 一个非确定非确定有限自动机(NFA)M是一个五元组M=(K,VT,f,S,Z)其中:K：有穷状态集；VT：有穷的输入字母表；f：KVT(K)(K的子集)是状态转换 函数；S：为初态集，是K的非空子集;Z

11、：是终态集，是K的非空子集。“非确定非确定”即即f是多值函是多值函数，且输入数，且输入可允许为可允许为。28NFA与与DFA的主要区别是：的主要区别是：(1)S是初态是初态集集，初态不唯一；，初态不唯一；(2)f是是多值多值函数，一个结点的多条引出函数，一个结点的多条引出弧可标同一符号，而且允许输入弧可标同一符号，而且允许输入。类似类似DFA，NFA可用状态转换矩阵和状态可用状态转换矩阵和状态图表示。图表示。NFA所接受的符号串以及所接受所接受的符号串以及所接受语言也是参考语言也是参考DFA给出的定义。给出的定义。29例例 设有设有M3=(P,Q,R,a,b,f,S,Z),其中其中S=P,Q,

12、Z=R,其中其中f(P,a)=Q f(P,b)=P,Rf(Q,a)=f(Q,b)=Rf(R,a)=f(R,b)=Q P Q Rab_+bbbfa b-PQPR-QR+RQ30例例 设有设有NFA如下如下 P Q Rab_+bbb判断bb是否是可识别的符号串?31(3)NFADFA（确定化确定化）定义4.12 设设I是是K的状态子集，的状态子集，I的的闭包闭包（-CLOSURE(I)）为：为：(1)若状态若状态PI，则，则P-CLOSURE(I)；(2)若状态若状态PI，则则P-CLOSURE(I),其中其中P为由为由P出发，经任意条出发，经任意条弧可达弧可达的的K中的状态。中的状态。32例：例

13、：设有NFA的状态转换图如下:5S3124Z6abaabbabI-CLOSURE(I)SS,2 S,3,1S,3,1,2,4,Z_+33定义定义4.13设设I是是K的状态子集，状态集的状态子集，状态集合合I的的a弧转换弧转换（move(I,a)）,表示表示I中状中状态经过一态经过一条条a边可到达的状态的集合。而边可到达的状态的集合。而Ia=-CLOSURE(move(I,a)。34例：例：设有NFA的状态转换图如下:5S3124Z6abaabbabIMove(I,a)IaS,3,1+_5,35,3,1Ia即从I中任一状态出发，经a弧（可跳过a弧之后的任意条弧）可达的状态集。35 NFA的确定化

14、的确定化 例子4f35621iaaaabbbb364f35621iaaaabbbb37 等价等价的的DFAaCDBAEFSbaaaaabbbbbabF38(4)确定有穷自动机的化简（确定有穷自动机的化简（最小化最小化）最小最小DFA的含义：的含义：(1)没有多余状态没有多余状态：从该自动机的开始从该自动机的开始状状态出发，任何输入串也不能到达那个状态，态出发，任何输入串也不能到达那个状态，或者从这个状态出发没有通路可以到达终态。或者从这个状态出发没有通路可以到达终态。(2)没有两个状态是互相等价没有两个状态是互相等价（可区别）（可区别）39例：例：给定给定DFA如下，其中如下，其中0132ab

15、abb_+4b在在DFA中，状态中，状态2是是不能到达不能到达的状态，的状态，而状态而状态4是是不能终止不能终止的状态，因此都是的状态，因此都是多余状态。多余状态。40两个状态两个状态s和和t等价的条件：等价的条件：一致性一致性s和和t同是终态或同是非终态同是终态或同是非终态蔓延性蔓延性从从s出发读入某个出发读入某个aa和和从从t出发出发读入某个读入某个a到达的状态等价。到达的状态等价。对对于于a,f(r,a)=r,f(s,a)=s,r和和s必必须等价。须等价。41化简方法（分割法）：(1)将S划分为终态集和非终态集，得S=Z,S-Z。(2)递归地分割S中的子集，使得任何两个不同子集的状态都是

16、可区分的，而同一个子集中的状态都是等价的。(3)S中的每个子集合并为一个状态。(4)含原初态的状态为初态；含原终态的状态为终态。42例：设有例：设有DFA M如右图所示：如右图所示：划分状态集为4和 0,1,2,3对于0,1,2,3和输入字符a和b:f(0,a)=1 f(0,b)=2f(1,a)=1 f(1,b)=3 f(2,a)=1 f(2,b)=2f(3,a)=1 f(3,b)=4只有状态3在输入为b时映像的后继状态不在0,1,2,3中，因此该状态集划分为3和0,1,2对于0,1,2：状态1在输入为b时的后继状态不在0,1,2中，因此划分为1和0,2对于0,2:对于相同输入字符，该子集中每

17、一状态映像得到的后继状态都相同，因此不再可划分最后划分为：4 3 1 0,2 b02314bbbbaaaaa43对于划分结果4,3,1,0,2，把0,2合并为一个状态，分别标记为新状态4,3,1,0，其状态转换图如图：3aaaabbb03102314bbbbbaaaaab444例：(先构造DFA，再构造MinDFA)设有NFAQ PZ11011,0_+_45定理4.7（RENFA）对于任意的正则式e，存在一个与之相应的NFA M，使得L(M)=L(e)。定理4.8对于任意的NFA M，存在一个与之相应的正则式e，使得L(e)=L(M)。4.4 正规式和有穷自动机的等价性46RENFA构造方法（

18、见书P63）正则式 NFA a PQ P|Q P*SZSZ SZaSiZPQSZPQSZPQSZP|QSiZ SZP*P47例：构造出正则式(a|b)*abb的NFA (1)(2)(3)(4)(5)SZ(a|b)*abbSZ(a|b)*abbSZ(a|b)*abbZSabb a|bZS abbab484.5正规文法和有穷自动机的等价性3GNFA：（右线性文法）(1)对每个非终结符画一个结点，开始符S为开始状态；(2)增设一个终止状态Z;(3)对形如Ua的规则，画一条从U到Z的a弧;(4)对形如UaW的规则，画一条从U到W的a弧;例：例：G:S0A|1B A1S|1 B0S|0493GNFA：（左线性文法）(1)对每个非终结符画一个结点，开始符S为终止状态；(2)增设一个开始状态Z;(3)对形如Ua的规则，画一条从Z到U的a弧;(4)对形如UWa的规则，画一条从W到U的a弧;例：例：G:SA0|B1 AS1|1 BS0|0对左线性文法，则把上述规则中的对左线性文法，则把上述规则中的“开始状态开始状态”与与“终止状态终止状态”互换，且将各弧反向。互换，且将各弧反向。50