《第4章词法分析教案.ppt》由会员分享，可在线阅读，更多相关《第4章词法分析教案.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理编译原理第4章词法分析 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望编译原理编译原理逐个读入逐个读入源程序字符并按照构词规则切分成一系列单词。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中每一产生式的形式都为：AaBAaB或AaAa，其中AVN，BVN，aVT。几类单词的描述几类单词的描述标识符标识符：标识符l|l字母数字字母数字l|d|l字母数字|d 字母数字4.2 4.2 正则表达式和正规集正则表达式和正规集正规文法正规文法编译原理编译原理无符号整数无符号整数：无符号整数d|d无符号整数运算符运算符：运算符+|-|*|/|=|等号等号=界符界符：界符,|;|(|)|编译原理编译原理无符号实数无符号实数：无符号实数 d 余留无符号数|.十进小数|e指数
5、部分余留无符号数 d 余留无符号数|.十进小数|e指数部分|十进小数 d 余留十进小数余留十进小数 e指数部分|d 余留十进小数|指数部分 d 余留整指数|s整指数整指数 d 余留整指数余留整指数 d 余留整指数|其中s表示正或负号。如 25.55e+5 和 2.1编译原理编译原理正规式正规式(regular expression)regular expression)正规式正规式正规式正规式和它所表示的和它所表示的正规集正规集设字母标为，辅助字母表=，。v 1。和都是上的正规式，它们所表示的正规集分别为和；v2。任何a，a是上的一个正规式，它所表示的正规集为a；v3。假定e1和e2都是上的正
6、规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。编译原理编译原理v 4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。说明：说明：其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。编译原理编译原理例4.2 令
7、=a，b，上的正规式和相应的正规集的例子有：正规式 正规集a aaba,bab 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,，其中l代表字母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。例4.3 =d，.，e，+，-,则上的正规式 d d (.dd
8、(.dd )(e(+)(e(+-)dd)dd )表示的是无符号数的集合，其中d为09的数字。编译原理编译原理两个正规式两个正规式等价等价若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b(ab)=(ab)编译原理编译原理正规式的运算律正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：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
9、=r r=rrr “或”的抽取律 编译原理编译原理 对于对于 上的正规式上的正规式r,存在一个存在一个G=(VN,VT,P,S)使得使得L(G)=L(r)，反之亦然。反之亦然。1.1.将正规式转换成正规文法将正规式转换成正规文法 VT=,S VN，生成正规产生式 Sr正规文法到正规式正规文法到正规式(1)对形如 Axy的正规产生式：AxB By BVN编译原理编译原理(2)对形如Axy的正规产生式：AxB Ay BxB By BVN (3)对形如Axy的正规产生式:A x A y 不断应用上述规则做变换，直到每个产生式右不断应用上述规则做变换，直到每个产生式右端只含一个端只含一个VN。编译原理
10、编译原理例 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规则一规则二编译原理编译原理2.2.将正规文法转换成正规式将正规文法转换成正规式将正规文法转换成正规式将正规文法转换成正规式 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)（1）AxB,ByA=xy（2）AxA y A=x y（3）Ax yA=x y文法产生式文法产生式文法产
11、生式文法产生式正规式正规式正规式正规式编译原理编译原理4.34.3有穷自动机有穷自动机确定的有穷自动机（DFA）不确定的有穷自动机（NFA）NFA DFA 的转换DFA的化简编译原理编译原理 DFA DFA定义定义定义定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，S，Z）其中其中1 1。K K K K是一个有穷集，它的是一个有穷集，它的每个元素每个元素每个元素每个元素称称为为为为一个一个状态状态状态状态；2 2。是是是是一个有穷字母表，它的每个元素称为一个输入一个有穷字母表，它的每个元素称为一个输入符号，所以也称符号，所以也称为为输入符号
12、字母表输入符号字母表输入符号字母表输入符号字母表；3 3。f f f f是转换函数是转换函数是转换函数是转换函数，是在，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态就意味着，当前状态为为ki，输入符为输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把我们把kj称作称作kiki的一个后继状态；的一个后继状态；4。S S S SK K是唯一是唯一是唯一是唯一的一个的一个初态初态初态初态；5 5。Z Z Z Z K是是是是一个一个终态集终态集终态集终态集，终态也称，终态也称可接受状态可接受状态或或结束状结束状态态。编译原理编
13、译原理DFA 例：DFA M=（S,U,V,Q,a,b,f,S,Q）其中 f 定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q编译原理编译原理DFA DFA 的状态图表示的状态图表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb编译原理编译原理DFA DFA 的矩阵表示的矩阵表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）
14、=Q字符状态0100编译原理编译原理DFA的确定性表现在：的确定性表现在：转换函数转换函数f:KK是一个单值函数是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有任何一个状态结点最多有n条条弧射出弧射出，而且每条弧以一个不同的输入字符标记。编译原理编译原理*上的符上的符号号串串t在在M上运行上运行一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在DFA M上运行运行的定义为：f f（Q Q，Tt1 Tt1）=f=f（f f（Q Q，T T），），t1t
15、1）其中QK 扩充转换函数f，是K*K上的映射，且：f（Q，）=Q编译原理编译原理*上的符号串上的符号串 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
16、 定义为：定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb证明：证明：f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ属于终态。得证。属于终态。得证。编译原理编译原理DFA M所能接受的符号串的全体记为L(M)结论：结论：上一个字符串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。编译原理编译原理不确定的有穷自动机不确定的有穷自动机NFANFA定义
17、定义N=K，f，S，Z，其中KK为状态为状态为状态为状态的有穷非空集集集集，为为为为有穷输入字母表字母表字母表字母表，f f为为为为K*到K的子集的映像映像映像映像，S SK是是初始状态集初始状态集初始状态集初始状态集，Z Z K为终止状态集为终止状态集为终止状态集为终止状态集。由此定义可看出：由此定义可看出：DFA是是NFA的特例的特例DFA与与NFA的区别的区别：1)DFA的初态唯一初态唯一，NFA的初态不唯一初态不唯一。2)DFA的转换函数转换函数是单值单值，NFA的转换函数转换函数是多值多值。编译原理编译原理例子例子NFA N=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=
18、Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111状态图表示状态图表示编译原理编译原理矩阵表示矩阵表示简化为NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P编译原理编译原理*上的符号串t在NFA N上运行*上的符号串t被NFA N接受（读出、识别）具有转移的不确定的有穷自动机NFAf为 K（）到K的子集的映像对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。编译原理编译原理DFA M=（
19、K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c);c:=getchar;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)closure(I)，定义为一状态集
20、，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2 状态集合I的a弧转换，表示为move(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)按如下办法构
21、造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：1.M的状态集S由K的一些子集组成。用S1 S2.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(moveclosure(move(S S1 1,S,S2 2,.,.,S Sj j,a)a)4.S S0 0=-closure(Kclo
22、sure(K0 0)为M的开始状态；5.St=Si,Sk,.,Se，其中Si,Sk,.,SeS且Si,Sk,.SeKt编译原理编译原理构造构造NFA NNFA N的状态的状态K K的子集的算法：的子集的算法：假定所构造的子集族为假定所构造的子集族为C，即即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集。的子集。1.开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。编译原理编译原理2.while（C中存在尚未被标记的子集T）do 标记T；for 每个输入字母a do U:=-closure(move(T,a)；if U不在C中 then 将U作为未标
23、记的子集加在C中编译原理编译原理例例4.8 将下图的将下图的NFA N转换成转换成DFA M023456789101bbbaaNFA 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
24、,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,7,10 加入为T4T4=1,2,4,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,
25、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,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 s
26、7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 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
27、 M=（K,f,k0,kt)，使L(M)=L(M).算法的核心：算法的核心：把把M的状态集的状态集K分成不相交的子集分成不相交的子集。使得任何不同两子集中的状态都是可区别的，而同一子集中的任何两状态是等价的。结论 接受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去处多余状态，合并去处多余
28、状态，合并等价状态等价状态 编译原理编译原理正规式正规式和和有穷自动机有穷自动机的等价性的等价性1.对于上的NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。编译原理编译原理1.对于对于上的上的NFA M，可以构造一个，可以构造一个上上的正规式的正规式R,R,使得使得L(R)=L(M)。第一步：在M的状态转换图上加进两个结加进两个结，一个为x结点，一个为y结点。从x结点用弧连接到M的所有初态结点所有初态结点，从M的所有终态结点所有终态结点用弧连接到y结点。形成一个与M等价的M,M只有一个初态一个初态x x
29、和一个终态一个终态y y。第二步：逐步消去M中的所有结点，直至只剩下x和y。（消去规则见下页）最后x和y结点间的弧上的标记则为所求的正规式R。编译原理编译原理123R1R213R1 R213R1R213R1|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)*xy
30、0a|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。编译原理编译原理编译原理编译原理对于给定的正规表达式R，首先将其表示成拓广转换图，其中X为初始状态，Y为终止状态；然后逐步将这个拓广转换图运运用用三三条条
31、转转换换规规则则不不断断加加入入新新结结点点进进行行分分解解，直直至至每每条条有有向向边边上上仅仅标标识识有有的的一一个个字字母母或或为为止止，则NFA M构造完成。注：注：采采用用本本办办法法比比教教材材讲讲授授的的办办法法简简单单，并并且得到的且得到的NFA的状态要少。的状态要少。编译原理编译原理例：例：为为R=(a|b)*abbR=(a|b)*abb构造构造NFA N，使得使得L(N)=L(R)。解一：解一：采用教材讲授的方法。采用教材讲授的方法。2354abR=(R=(a a|b)*abb|b)*abbR=(a|R=(a|b b)*abb)*abb2354ab16R=(R=(a|ba|
32、b)*abb)*abb编译原理编译原理2354ab16R=(R=(a|ba|b)*abb)*abb2354ab16R=R=(a|b)*(a|b)*abbabb07继续加上abb即可得到结果。编译原理编译原理2354ab16078910abb一共一共1111个状态个状态编译原理编译原理解二：解二：解二：解二：xiy(a|b)*abbxjyabbia|bX2 Y(a|b)*abb(a|b)*abb第一步：构造拓广转换图第二步：不断应用三个规则增加结点和弧，直至每条有向边直至每条有向边 上仅标识有上仅标识有的一个字母或的一个字母或为止。为止。编译原理编译原理xjyabbiabybxjiabklab一
33、共一共6个状态个状态编译原理编译原理正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换采用下面的规则从正规文法采用下面的规则从正规文法G直接构造一个有直接构造一个有穷自动机穷自动机NFA M，使得使得L(M)=L(G)：字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，（不妨取称相同的名字）G的开始符号是开始状态S；增加一个新状态Z，作为NFA的状态；对G中的形如AtBAtB的产生式（其中t为终结符或，A和B为非终结符），构造M的一个转换函数f(A,t)=Bf(A,t)=B；对G中形如AtAt的产生式，构造M的一个转换函数f(A,t)=Zf(A,t)=Z。编译原理编译原理例：与文法GS等价的NFA MGS：SaASbBSAaBAbABaSBbABSABZaabbab编译原理编译原理4.4 4.4 词法分析程序的自动构造工具词法分析程序的自动构造工具把正规式转换为一个NFA进而转换为相应的DFA，由此构造出词法分析程序。LEX编译系统