第4部分词法分析ppt课件

1、编译原理编译原理第第4 4章章 词法分析词法分析 词法分析程序的设计 单词的描画工具 有限自动机 正规式和有穷自动机的等价性 正规文法和有穷自动机间的转换 词法分析程序的自动构造工具编译原理编译原理 逐个读入源程序字符并按照构词规那么切分成一逐个读入源程序字符并按照构词规那么切分成一系列单词。系列单词。4.1 4.1 词法分析程序的设计词法分析程序的设计 词法分析词法分析lexical analysis 单词是言语中具有独立意义的最小单位，包括保管字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进展。也可以和语法分析结合在一同作为一遍，由语法分析程序调用词法分

2、析程序来获得当前单词供语法分析运用。编译原理编译原理词法分析程序词法分析程序源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token. 主要义务： 读源程序，产生单词符号。滤掉空格，跳过注释、换行符。 追踪换行标志，复制出错源程序。 宏展开， 其他义务：编译原理编译原理单词符号单词符号 单词符号普通可分为以下五种： 根本字关键字：begin, end, if, while, var等。 标识符：各种称号，如常量名、变量名、过程名等。 常数量：25, 3.1415, TRUE, “ABC等 运算符：如 + - * / =等。 界符：逗号，分号，括号等。编译原理编译

3、原理 输出表示单词种别，单词本身的值。输出表示单词种别，单词本身的值。 单词的种别可以用整数编码表示，假设标识符编码为1，常数为2，保管字为3，运算符为4，界符为5。如：程序段 if i=5 then x=y；在经词法分析器扫描后输出的单词符号和它们的表示如下：编译原理编译原理 程序段 if i=5 then x=y - 保管字if(3，if)- 标识符i(1，指向i的符号表入口)- 等号=(4，=)- 常数5(2，5)- 保管字then(3，then)- 标识符x(1，指向x的符号表入口)- 赋值号=(4，=) - 标识符 y(1，指向y的符号表入口)- 分号；(5，；) 编译原理编译原理词

4、法分析任务独立的缘由：词法分析任务独立的缘由： 简化设计 改良编译效率 添加编译系统的可移植性 编译原理编译原理单词的描画工具单词的描画工具 文法文法G=VN，VT，P，S，P中每一产生式的方中每一产生式的方式都为：式都为：AaB或或Aa，其中，其中AVN ，BVN ，aVT。几类单词的描画几类单词的描画4.2 4.2 正那么表达式和正规集正那么表达式和正规集正规文法正规文法编译原理编译原理编译原理编译原理编译原理编译原理正规式正规式(regular expression)(regular expression)v 1。 和都是上的正规式，它们所表示的正规集分别为和；v2。任何a ，a是上的一

5、个正规式，它所表示的正规集为a；v3。假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。编译原理编译原理v 4。仅由有限次运用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。阐明：阐明：其中的其中的“读为读为“或也有运用或也有运用“+“+替代替代 “ 的；的；“ 读为读为“衔接；衔接；“读为读为“闭包即，恣意有限次的自反复衔接。在不闭包即，恣意有限次的自反复衔接。在不致混淆时，

6、括号可省去，但规定算符的优先顺序为致混淆时，括号可省去，但规定算符的优先顺序为“、“ 、“ 。衔接符。衔接符“ 普通可普通可省略不写。省略不写。“、“ 和和“ 都是左结合都是左结合的。的。编译原理编译原理 例4.2 令=a，b， 上的正规式和相应的正规集的例子有： 正规式 正规集 a a aba,b ab ab (ab)(ab)aa,ab,ba,bba ,a,a, 恣意个a的串(ab) ,a,b,aa,ab 一切由a和b组成的串(ab)(aabb)(ab)上一切含有两个相继的a或两个相继的b组成的串编译原理编译原理 例 =l，d，r=l(l d) 定义的正规集: l,ll,ld,ldd,，其中

7、l代表字母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的方式是“字母打头的字母数字串，就是Pascal和多数程序设计言语允许的的标识符的词法规那么。 例4.3 =d，.，e，+，-,那么上的正规式 d(.dd )(e(+- )dd )表示的是无符号数的集合，其中d为09的数字。编译原理编译原理两个正规式等价两个正规式等价 假设两个正规式e1和e2所表示的正规集一样,那么说e1和e2等价,写作e1=e2。例如： e1= (ab)， e2 = ba又如： b(ab) = (ba)b(ab) = (ab)编译原理编译原理正规式的运算律正规式的运算律 设r,s,t为正规式

8、，正规式服从的代数规律有： 1。rs=sr“或服从交换律 2。r(st)=(rs)t“或的可结合律 3。(rs)t=r(st)“衔接的可结合律 4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r是“衔接的恒等元素 6。 rr=r r=rrr “或的抽取律 编译原理编译原理 对于上的正规式r ,存在一个G=(VN,VT,P,S) 使得L(G)=L(r) ，反之亦然。正规文法到正规式正规文法到正规式(1) 对形如 Axy的正规产生式： AxB By BVN编译原理编译原理 (2)对形如Axy的正规产生式：AxB Ay BxB By BVN (3)对形如Axy的正规产生式

9、: A x A y 不断运用上述规那么做变换，直到每个产生式不断运用上述规那么做变换，直到每个产生式右端只含一个右端只含一个VN。编译原理编译原理 例 r = a(ad) VT=a,d Sa(ad)Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB BSaAA(ad) A(ad)BAB(ad)BB规那么一规那么二编译原理编译原理 S=aAa例Gs:SaA AaA AdA Sa Aa Ad A =aAdA a d =(ad)A(ad) =(ad)(ad) S=a(ad)(ad)a =a(ad)(ad) =a(ad) R=a(ad)1AxB, ByA=xy 2AxA

10、y A=x y3Ax yA=x y编译原理编译原理4.34.3有穷自动机有穷自动机 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA DFA 的转换 DFA的化简编译原理编译原理编译原理编译原理DFA 例：DFA M=S,U,V,Q, a,b, f, S, Q其中 f 定义为：fS，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=Q编译原理编译原理DFA DFA 的形状图表示的形状图表示fS，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=QbSUVQaaaba，bb编译原理编译原理DFA DFA 的矩阵表

11、示的矩阵表示fS，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=QabSUVUQVVUQQQQ字符形状0100编译原理编译原理DFA确实定性表如今：确实定性表如今：转换函数转换函数f:KK是一个单值函数，也就是一个单值函数，也就是说，对任何形状是说，对任何形状kK，和输入符号，和输入符号a，f(k,a)独一地确定了下一个形状。独一地确定了下一个形状。从形状转换图来看，假设字母表从形状转换图来看，假设字母表含有含有n个输个输入字符，那末任何一个形状结点最多有入字符，那末任何一个形状结点最多有n条条弧射出，而且每条弧以一个不同的输入字弧射出，而且每条弧以一

12、个不同的输入字符标志。符标志。编译原理编译原理编译原理编译原理* *上的符号串上的符号串 t t 被被 M M 接受接受对于*中的任何字符串t，假设存在一条从初态结到某一终态结的道路，且这条路上一切弧的的标志符衔接成的字符串等于t，那么称t可为DFA M所接受，假设M的初态结同时又是终态结，那么空字可为M所接受识别。假设t *，f(S，t)=P，其中S为DFA M的开场形状，P Z，Z为终态集。那么称t为DFA M所接受识别。编译原理编译原理例：证明例：证明t=baab被如下的被如下的DFA所接受。所接受。DFA M=S,U,V,Q, a,b, f, S, Q其中其中 f 定义为：定义为：fS

13、，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=QbSUVQaaaba，bb证明：证明： fS，baab=ffS，b，aab=fV，aab=ffV，a，ab=fU，ab=ffU，a，b=fQ，b=QQ属于终态。得证。属于终态。得证。编译原理编译原理 DFA M所能接受的符号串的全体记为L(M) 结论： 上一个字符串集V是正规的，当且仅当存在一个上确实定有穷自动机M，使得V=L(M)。编译原理编译原理不确定的有穷自动机不确定的有穷自动机NFANFA 定义定义 N=K，f，S，Z，其中，其中K为形状为形状的有穷非空集，的有穷非空集， 为有穷输入字母表，为有

14、穷输入字母表，f为为K * 到到K的子集的映像，的子集的映像，SK是是初始形状集，初始形状集，Z K为终止形状集。为终止形状集。由此定义可看出：由此定义可看出：DFA是是NFA的特例的特例DFA与与NFA的区别：的区别：DFA的初态独一，的初态独一，NFA的初态不独一。的初态不独一。DFA的转换函数是单值，的转换函数是单值， NFA的转换函数是多值。的转换函数是多值。编译原理编译原理例子例子NFA N=S，P，Z，0，1，f，S，P，Z其中 fS，0=PfS，1=S，ZfP，1=ZfZ，0=PfZ，1=PSPZ00,1111形状图表示形状图表示编译原理编译原理矩阵表示矩阵表示01SPS,Z0P

15、Z0ZPP1简化为01SPS,Z0P.Z0ZPP1NFA N=S，P，Z，0，1，f，S，P，Z其中其中 fS，0=PfS，1=S，ZfP，1=ZfZ，0=PfZ，1=P编译原理编译原理 *上的符号串t在NFA N上运转 *上的符号串t被NFA N接受读出、识别 具有转移的不确定的有穷自动机NFAf为 K 到K的子集的映像 对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。编译原理编译原理DFA M=K，f，S，Z的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=g

16、etchar; ;if K is in Z then return (yes) else return (no)编译原理编译原理NFANFA确实定化确实定化 DFA是NFA的特例.对每个NFA M一定存在一个DFA ，使得 L(M)=L(M )。 对每个NFA M存在着与之等价的DFA M 。与某一NFA等价的DFA不独一。编译原理编译原理定义对形状集合定义对形状集合I I的几个有关运算：的几个有关运算： 1 形状集合I的-闭包，表示为-closure(I)，定义为一形状集，是形状集I中的任何形状S经恣意条弧而能到达的形状的集合。形状集合I的任何形状S都属于-closure(I)。 2 形状集

17、合I的a弧转换，表示为move(I,a)定义为形状集合J，其中J是一切那些可从I的某一形状经过一条a弧而到达的形状的全体。 定义Ia = -closure(J)编译原理编译原理例I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa编译原理编译原理NFADFANFADFA 假设NFA N=(K, ,f,K0,Kt)按如下方法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1. M的形状集S由K的一些子集组成。用S1 S2

18、. Sj表示S的元素，其中S1, S2,. Sj是K的形状。并且商定，形状S1, S2,. Sj是按某种规那么陈列的，即对于子集S1, S2= S2, S1,来说，S的形状就是S1 S2；编译原理编译原理2. M和N的输入字母表是一样的，即是；3. 转换函数是这样定义的： D(S1 ,S2 ,. , Sj,a)= R1 , R2 ,. , Rt，其中 R1 , R2 ,. , Rt = -closure(move(S1 ,S2 ,. , Sj,a) 4. S0=-closure(K0)为M的开场形状；5. St=Si ,Sk ,.,Se，其中Si ,Sk ,. ,SeS且Si , Sk,. S

19、eKt编译原理编译原理构造构造NFA NNFA N的形状的形状K K的子集的算法：的子集的算法： 假定所构造的子集族为C，即C= (T1, T2,. TI),其中T1, T2,. TI为形状K的子集。 1. 开场，令-closure(K0)为C中独一成员，并且它是未被标志的。编译原理编译原理 2.while C中存在尚未被标志的子集Tdo 标志T； for 每个输入字母a do U:= -closure(move(T,a)； if U不在C中 then 将U作为未标志的子集加在C中编译原理编译原理例例4.8 将以下图的将以下图的NFA N转换成转换成DFA M023456789101bbbaa

20、NFA N编译原理编译原理023456789101bbbaa-closure(move(Ti,a)-closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,7,10 加入为T4T4= 1,2,4,

21、5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2编译原理编译原理-closure(move(Ti,a)-closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5

22、,7,10 加入为T4T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2初态终态b02134abaaaabbbDFA M编译原理编译原理DFADFA的最小化化简的最小化化简 最小形状DFA 没有多余形状(死形状) 没有两个形状是相互等价不可区别 两个形状s和t等价：满足 一致性同是终态或同是非终态 蔓延性从s出发读入某个aa和从 t出发读入某个a到达的形状等价。编译原理编译原理消除多余形状消除多余形状s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s

23、6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7编译原理编译原理 如图，形状0和4是可区别的。 形状2和3是可区别的，由于读入b后分别到达2和4，而2和4不是等价的。b02134abaaaabbbDFA M编译原理编译原理 对于一个DFA M =K,f, k0,kt)，存在一个最小形状DFA M =K,f,k0,kt)，使L(M)=L(M). 算法的中心： 把M的形状集K分成不相交的

24、子集。使得任何不同两子集中的形状都是可区别的，而同一子集中的任何两形状是等价的。 结论 接受L的最小形状有穷自动机不计同构是 独一的。编译原理编译原理将以下图中的将以下图中的DFA MDFA M最小化最小化 1,2,3,4,5,6,7Ia: 6,7,1,4,7,4,4Ib: 3,3,5,6,3,1,21,2,3,4 5,6,71,2 3,4 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbba13546aaaabbbbb去处多余形状，合并去处多余形状，合并等价形状等价形状 编译原理编译原理正规式和有穷自动机的等价性正规式和有穷自动机的等价性 1. 对于上的NFA M

25、，可以构造一个上的正规式R,使得L(R)=L(M)。 2.对于上的一个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。编译原理编译原理 1. 对于上的NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。 第一步：在M的形状转换图上加进两个结，一个为x结点，一个为y结点。从x结点用弧衔接到M的一切初态结点，从M的一切终态结点用弧衔接到y结点。构成一个与M等价的M,M只需一个初态x和一个终态y。 第二步：逐渐消去M中的一切结点，直至只剩下x和y。消去规那么见下页 最后x和y结点间的弧上的标志那么为所求的正规式R。编译原理编译原理123R1R213R1 R213R1R213R

26、1| R2123R1R3R213R1 R2* R3消为消为消为消为消为消为编译原理编译原理例：例：03124a,baaa,ba,bbb求正规式求正规式R编译原理编译原理a,b03124a,baaa,bbbxya|b024a|baaa|bbbxy编译原理编译原理a|b024a|baaa|bbbxy0a|baa(a|b)*bb(a|b)*xy编译原理编译原理0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)* |bb(a|b)*xy(a|b)* (aa |bb)(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)*编译原理编译原理 2.对于上的一个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。 由正规表达式构造等价的NFA M的方法如下： (1) 将正规表达式R表示成如下图的拓广转换图。 (2) 对正规表达式采用以下图所示的三条转换规那么来构造NFA M。X2 YR编译原理编译原理sisjr1 | r2sisjr1r2sisjr1*123sisjr1r2sisjskr1r2sisjskr1编译原理编译原理 对于给定的正规表达式R，首先将其表示成拓广转换图，其中X为初始形状，Y为终止形状；然后逐渐将这个拓广转换图运用三条转换规那么不