4_词法分析.ppt

1、1,第四章 词法分析,2,4.1 词法分析程序的设计,(1)任务 主要任务 逐个字符地扫描源程序，识别单词符号（终结符）。在拼单词时作词法检查。每识别出一个单词，就翻译成相应的机内表示（语法分析时的终结符）。,3,删去注解、空格、续行符等 插入某些信息 有些语言（如FORTRAN）无语句结束符“；”，就要插入句末符。 为了语法分析出错处理的错误定位，要为源程序增加行号（在列表文件中可见）。 输出源程序清单,4,(2)实现方式 相对独立方式 完全独立方式,5,(3)单词类别及其输出形式 单词可作各种分类，典型地分为类： 保留字：AND,BEGIN,FOR,TYPE,VAR等（个数确定，可全体编为

2、一类，称作“一字一类”） 标识符：用户定义的常量名、变量名、过程名和类型名（个数不确定，作为一类，称作“一符一类”） 常量：12,1997,4.14,A,scnu等（个数不确定，按类型分类） 运算符, ,=,=,#等（个数确定，“一符一类”） 界限符；,（）等（个数确定，“一符一类”）,6,词法分析程序输出的单词符号通常用二元式 表示：（单词种别，单词自身的值） 单词种别：表示单词种类，常用整数编码，它是语法分析需要的 单词自身的值：是编译中其他阶段所需要的信息,7,(4)词法分析程序的设计过程 3G 3型文法 RE正则表达式 SG状态图 FA确定自动机 NFA 非确定自动机 FA确定自动机

3、NFA 非确定自动机 minFA 最小确定自动机 Scanner扫描器,3G,DFA,NFA,SG,NFA,DFA,minDFA,Scanner,RE,8,定义字母表V上的状态图SG是如下有向图： (1)至少有一个初始结点，用“”标记； (2)至少有一个终止结点，用“”标记； (3)每条边上标记V上的符号串（可以是）。 其中，结点表示状态，边表示所标记的符号串相应的状态转移。从初始结点出发到任一个终止结点的任一条路径上各边标记的符号串的连结，是SG可接受的符号串。SG可接受的符号串的集合记为L(SG)。,9,3G-SG构造方法（对右线性文法） (1)对每个非终结符画一个结点，开始符S为开始结点

4、； (2)增设一个终止结点Z; (3)对形如Ua的规则，画一条从U到Z的a弧; (4)对形如UaW的规则，画一条从U到W的a弧; 对左线性文法，则把上述算法中的“开始结点”与“终止结点”互换，且将各弧反向。,10,例对无符号整数文法 GN: N dN|d 可构造状态图：,11,例2对标识符文法 GI: I l|Il|Id 可构造状态图：,d,+,-,Z,I,l,l,12,4.2正则表达式(正则式)和正则集(正则语言),(1)正规式和正规集 定义4.1（正则式和正则集） 在字母表V上定义的正则式及其描述的正则集递归地定义如下： 是正则式，表示空集； 是正则式，表示； 每个aV是正则式，表示a；,

5、13,若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上的正则式。运算的优先次序为： * . | (其中“|”可写作“+”)。,14,例：设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中的数字) 在前面加上

6、(+|-|)后，就是符号实数的定义。,表示V上的全体标识符,表示V上的全体整数,a0,a1,b0,b1,15,定义4.2 对正则式P和Q，若L(P)L(Q)， 则P与Q等价，记为P=Q。 例： b(ab)* (ba)*b b(ab)* = (ba)*b,=b(ab)n|n0,=(ba)nb|n0,16,定理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 “联结”对“或”的

7、右分配律 (6) P=P=P (7) P=P= |P=P|=P,17,(2) 由正则文法构造正则式(3G-RE) 定理4.2 正则文法规则 Ua1W1|a2W2|anWn|b1|b2|bm 的等价正则式方程为其中 U=(b1+b2+bm)+a1W1+a2W2+anWn 其中Wi是正则变量 “|”可以写为“+”,18,定理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=0,19,定义4.4 n元正则式方程组的标

8、准形式： X1=a10+a11X1+a12X2+ +a1nXn X2=a20+a21X1+a22X2+ +a2nXn Xn=an0+an1X1+an2X2+ +annXn 其中，aij是正则式，但不含变量； Xi是正则变量（待定正则式）。,20,例：对文法G: SaA AbS | a 用正则式来描述文法定义的语言：,解: 根据定理4.2 S=aA A=a+bS 把式代入式， S = a(a+bS) = aa+abS 根据定理4.3 S=(ab)*aa,21,例:对正则文法G建立正则式方程： G: SaS|bR| RaS 解1:式代入式，得 S=+aS+baS =(a+ba)S+ =(a|ba)

9、*,S=+aS+bR R=aS ,解2: =aS+(+baS) =a*(+baS) =a*baS+a* =(a*ba)*a*,22,例：对正则文法G建立正则式方程： G: S0A|1B|0|1 S=(0+1)+0A+1B A0S|1B|1 A=1 +0S+1B B0A|1S| B= +1S+0A 把B分别代入和式，得 S=(0+1)+(0+10)A+11S A =1+0S+1(+1S+0A) =1+(0+11)S+10A 10A是递归项 =10A+(1+(0+11)S) 分为递归项和非递归项 =(10)*(1+0+11)S) (续),23,将A代入式，得 S=(0+1)+(0+10)(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),24,4.3有穷自动机(FA),(1) 确定有穷自动机（DFA） 定义4.5 一个确定有限自动机(DFA)M是一个五元组：M=( K , VT , f , S , Z ) 其中 K： 有穷状态集； VT：有穷的输入字母表； f：KVTK是状态转换函数，即f(W,a)=U 表示当前状态W下，输入a时，转到状态U。

11、S：唯一的开始状态，SK; Z：终止状态集，是K的非空子集。,25,例：设有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)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 状态转换表的行标表示状态，列标表示输入 符号，表元素表示f(W,a)的值。,K,VT,26,定义4.6 字母表V上的状态图SG是如下有向图： (1)至少有一个初始结点，用“”标记； (2)至少有一个终止结点，用“”标记； (3)每条边上标记V上的符号串（可以是）。 其中，结点表示状态，边表示所标记的符 号串相应的状态转移。

12、 它所对应的转换函数是f(W,a)=U,27,假定DFA M含有m个状态和n个输入字符，那么，这 个图含有m个状态结点，每个结点最多只能有n条 弧从结点射出并与别的结点相连结，每条弧上的标 记是输入字母表上的一个字符。整个图只有一个初 态结点，用=或标以“”射入的节点表示初态， 终态可由若干个，也可以没有，用双圆圈或标以 “”表示。,1,2,0,3,a,b,a,a,b,b,a,b,_,+,28,例：设有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)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 F

13、ASG：,从初始结点出发到任一个终止结点的任一条路径上各边标记的符号串的连结，是SG可接受的符号串。,29,定理4.4若DFA上有且仅有一条从初 态到终态的路径产生x，则x为DFA所 能识别的字符串。 例：输入字符串aab,30,显然，不能被接受的字符串有两种情况： (1) 读完输入串，状态不停在终态； (2) 在读过程中出现不存在的映射，使自动机无法继续动作。,31,定义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(

14、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),32,定义4.8 若xVT* 且 g(S,x)Z，则称x为 DFA所识别的字符串。 例：输入字符串aab g(A,aab)=g(g(A,a),ab) =g(B,ab)=g(g(B,a),b) =g(C,b)=D,所有DFA所能识别的字符串集合记为L(DFA),33,例：四个DFA能识别的语言,a,a,+,+,+,aa*|,A(a|b)*|,34,例：设有M2=(A,B,C,D,a,b,f,A,D), 从前几例可见，f是单

15、值的，即“确定的”。,35,(2)非确定有穷自动机（NFA） 定义4.9 一个非确定有限自动机(NFA)M是一 个五元组M=(K,VT,f,S,Z) 其中: K：有穷状态集； VT：有穷的输入字母表； f：KVT(K)(K的子集)是状态转换函数； S：为初态集，是K的非空子集; Z：是终态集，是K的非空子集。,36,NFA与DFA的主要区别是： (1) S是初态集，初态不唯一； (2) f是多值函数，一个结点的多条引出弧可 标同一符号。 定义4.10非确定有穷自动机NFA的状态转换 函数f可如DFA扩充为：g:KVT*(K) 特别地， g(W,)=W g(W,tx)= g(Pi,x) 其中Pi

16、 g(W,t), tVT, xVT*,i,37,例 设有M3=(P,Q,R,a,b,f,S,Z),其中 S= P,Q,Z=R,L(M3)=b*(ab(bb)*|b(bb)*)|b(bb)*,38,定理4.7对任意的正则式e，存在接受正则 集L(e)的非确定有穷自动机NFA，反之亦然。,4.4由正则式构造自动机NFA（自动机）,39,RE NFA构造方法：见书P62 正则式 转换系统 a PQ P|Q P*,S,Z,S,Z,40,例： 构造出正则式(a|b)* abb的自动机 (1) (2) (3) (4) (5),S,Z,(a|b)* abb,S,Z,(a|b)*,abb,a,b,b,41,定

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

18、有NFA的状态转换图如下:,5,S,3,1,2,4,Z,6,a,b,a,a,b,b,a,b,+,_,3,5,3,1,5,45,例：设有NFA的状态转换图如下 NFADFA：,46,根据上边状态转换矩阵，可以得到DFA N的状态集合（表的最左列状态），即K=S31,315,316,31524Z,31624Z ,3164Z,3154Z,开始状态：S31,终止状态：31524Z, 31624Z,3164Z,3154Z,47,(4)确定有穷自动机的化简（求最小DFA） 最小DFA的含义： （1）没有多余状态（死状态） （2）没有两个状态是互相等价（不可区别） 两个状态s和t等价的条件： 一致性s和t同是终态或同是非终态 蔓延性从s出发读入某个aa和从t出发读入 某个a到达的状态等价。对于a , f(r,a)=r, f(s,a)=s, r和s必须等价。,48,定义4.13不同状态A和B是等价的， 当且仅当 f(A,t)Zf(B,t)Z tVT*, Z是终态集。 若A和B不等价，则称为是可区分的。,49,