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的符号表入
4、口)-分号；(5，；)编译原理编译原理编译原理编译原理编译原理编译原理词法分析工作独立的原因词法分析工作独立的原因：简化设计 改进编译效率 增加编译系统的可移植性 编译原理编译原理编译原理编译原理编译原理编译原理单词的描述工具单词的描述工具 文法G=（VN，VT，P，S），P中每一产生式的形式都为：或，其中AVN，BVN，aVT。几类单词的描述几类单词的描述：标识符l|l字母数字字母数字l|d|l字母数字|d 字母数字4.2 4.2 正则表达式和正规集正则表达式和正规集正规文法正规文法编译原理编译原理编译原理编译原理编译原理编译原理：无符号整数d|d无符号整数：运算符+|-|*|/|=|等号等
5、号=：界符,|;|(|)|编译原理编译原理编译原理编译原理编译原理编译原理：无符号实数 d 余留无符号数|.十进小数|e指数部分余留无符号数 d 余留无符号数|.十进小数|e指数部分|十进小数 d 余留十进小数余留十进小数 e指数部分|d 余留十进小数|指数部分 d 余留整指数|s整指数整指数 d 余留整指数余留整指数 d 余留整指数|其中s表示正或负号。如 25.55e+5 和 2.1编译原理编译原理编译原理编译原理编译原理编译原理正规式正规式(regular expression)regular expression)和它所表示的和它所表示的正规集正规集设字母标为，辅助字母表=，。v 1。
6、和都是上的正规式，它们所表示的正规集分别为和；v2。任何a，a是上的一个正规式，它所表示的正规集为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。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。说明：说明：其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的
7、自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。编译原理编译原理编译原理编译原理编译原理编译原理 例4.2 令=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代表字
8、母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。例4.3 =d，.，e，+，-,则上的正规式 表示的是无符号数的集合，其中d为09的数字。编译原理编译原理编译原理编译原理编译原理编译原理两个正规式两个正规式等价等价 若两个正规式e1和e2所表示的,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b(ab)=(ab)编译原理编译原理编译原理编译原理编译原理编译原理正规式的运算律正规式的运算律 设r,s,t为正规式，正规式服从的代数
9、规律有：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)，反之亦然。反之亦然。VT=,S VN，生成正规产生式 Sr正规文法到正规式正规文法到正规式(1)对形如 Axy的正规产生式：AxB By BVN编译原理编译原理编译原理编译原理编
10、译原理编译原理(2)对形如Axy的正规产生式：AxB Ay BxB By BVN (3)对形如Axy的正规产生式: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
11、=(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编译原理编译原理编译原理编译原理编译原理编译原理4.34.3有穷自动机有穷自动机 确定的有穷自动机（DFA）不确定的有穷自动机（NFA）NFA DFA 的转换 DFA的化简编译原理编译原理编译原理编译原理编译原理编译原理：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，S，Z）其中其中1 1。是一个有穷集，它的是一个有穷集，它的称称一个一个；2 2。一个有穷字母
12、表，它的每个元素称为一个输入一个有穷字母表，它的每个元素称为一个输入符号，所以也称符号，所以也称为为；3 3。，是在，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状就意味着，当前状态为态为ki，输入符为输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把我们把kj称作称作kiki的一个后继状态；的一个后继状态；4。K K的一个的一个；5 5。K一个一个，终态也称，终态也称可接受状态可接受状态或或结束状结束状态态。编译原理编译原理编译原理编译原理编译原理编译原理DFA 例：DFA M=（S,U,V,Q,a,b,f,S,Q）其中
13、 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）=Qab
14、SUVUQVVUQQQQ字符状态0100编译原理编译原理编译原理编译原理编译原理编译原理DFA的确定性表现在：的确定性表现在：转换函数转换函数f:KK是一个单值函数是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有任何一个状态结点最多有n条条弧射出弧射出，而且每条弧以一个不同的输入字符标记。编译原理编译原理编译原理编译原理编译原理编译原理一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在DFA M上的定义为：其中QK 扩充转换函数f，是K*K上的映射，
15、且：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)。编译原理编译原理编译原理编译原理编译原理编译原理不
17、确定的有穷自动机不确定的有穷自动机NFANFA 定义定义 N=K，f，S，Z，其中的有穷非空，有穷输入，K*到K的子集的，K，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）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111状态图表示状态图表示编译原理
18、编译原理编译原理编译原理编译原理编译原理矩阵表示矩阵表示01SPS,Z0PZ0ZPP1简化为01SPS,Z0P.Z0ZPP1NFA 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)。编译原理编译原理编译
19、原理编译原理编译原理编译原理DFA M=（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的几个有关运算：
20、的几个有关运算：1 状态集合I的-闭包，表示为，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2 状态集合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编译原理编译原理编译原理编译原理
21、编译原理编译原理NFADFANFADFA 假设NFA N=(K,f,K0,Kt)按如下办法构造一个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=4.为M的开始状态；5.St=
22、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中 t
23、hen 将U作为未标记的子集加在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,7
24、1,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,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,
25、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,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2初态终态b02134abaaaabbbDFA M编译原理编译原理编译原理编译原理编译原理编译原理DFADFA的最小化（化简）的最小化（化简）最小状态DFA没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价：满足一致性同是终态或同是
26、非终态蔓延性从s出发读入某个aa和从 t出发读入某个a到达的状态等价。编译原理编译原理编译原理编译原理编译原理编译原理消除多余状态消除多余状态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7编译原理编译原理编译原理编译原理编译原理编译原理 如图，
27、状态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).算法的核心：算法的核心：。使得任何不同两子集中的状态都是可区别的，而同一子集中的任何两状态是等价的。结论 接受L的最小状态有穷自动机不计同构是 唯一唯一的。编译原理编译原理编译原理编译原理编译原理编译原理将下图中的将下图中的DFA MDFA M最小化最小化 1,2,3,4,5,6,7Ia:6,7,1,
28、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，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。编译原理编译原理编译原理编译原理编译原理编译原理1.对于对于上的上的NFA M，可以构造一个，可以
29、构造一个上上的正规式的正规式R,R,使得使得L(R)=L(M)。第一步：在M的状态转换图上，一个为x结点，一个为y结点。从x结点用弧连接到M的，从M的用弧连接到y结点。形成一个与M等价的M,M只有和。第二步：逐步消去M中的所有结点，直至只剩下x和y。（消去规则见下页）最后x和y结点间的弧上的标记则为所求的正规式R。编译原理编译原理编译原理编译原理编译原理编译原理123R1R213R1 R213R1R213R1|R2123R1R3R213R1 R2*R3消为消为消为消为消为消为编译原理编译原理编译原理编译原理编译原理编译原理例：例：03124a,baaa,ba,bbb求正规式求正规式R编译原理编
30、译原理编译原理编译原理编译原理编译原理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，可以构造一，可以构
31、造一个个上的上的NFA M，使得，使得L(M)=L(R)。由正规表达式构造等价的NFA M的方法如下：(1)将正规表达式R表示成如图所示的拓广转换图。(2)对正规表达式采用下图所示的三条转换规则来构造NFA M。X2 YR编译原理编译原理编译原理编译原理编译原理编译原理sisjr1|r2sisjr1r2sisjr1*123sisjr1r2sisjskr1r2sisjskr1编译原理编译原理编译原理编译原理编译原理编译原理对于给定的正规表达式R，首先将其表示成拓广转换图，其中X为初始状态，Y为终止状态；然后逐步将这个拓广转换图运用三条转换规则运用三条转换规则不断加入新结点进行分解，直至每条有向边
32、上不断加入新结点进行分解，直至每条有向边上仅标识有仅标识有的一个字母或的一个字母或为止为止，则NFA M构造完成。注：注：采用本办法比教材讲授的办法简单，并采用本办法比教材讲授的办法简单，并且得到的且得到的NFA的状态要少。的状态要少。编译原理编译原理编译原理编译原理编译原理编译原理例：例：为为构造构造NFA N，使得使得L(N)=L(R)。解一：解一：采用教材讲授的方法。采用教材讲授的方法。2354ab2354ab16编译原理编译原理编译原理编译原理编译原理编译原理2354ab162354ab1607继续加上abb即可得到结果。编译原理编译原理编译原理编译原理编译原理编译原理2354ab16
33、078910abb一共一共1111个状态个状态编译原理编译原理编译原理编译原理编译原理编译原理xiy(a|b)*abbxjyabbia|bX2 Y第一步：构造拓广转换图第二步：不断应用三个规则增加结点和弧，直至每条有向边直至每条有向边 上仅标识有上仅标识有的一个字母或的一个字母或为止。为止。编译原理编译原理编译原理编译原理编译原理编译原理xjyabbiabybxjiabklab一共一共6个状态个状态编译原理编译原理编译原理编译原理编译原理编译原理正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换采用下面的规则从正规文法采用下面的规则从正规文法G直接构造一个有直接构造一个有穷自动机穷自动机
34、NFA M，使得使得L(M)=L(G)：字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，（不妨取称相同的名字）G的开始符号是开始状态S；增加一个新状态Z，作为NFA的状态；对G中的形如的产生式（其中t为终结符或，A和B为非终结符），构造M的一个转换函数；对G中形如的产生式，构造M的一个转换函数。编译原理编译原理编译原理编译原理编译原理编译原理 例：与文法GS等价的NFA MGS：SaASbBSAaBAbABaSBbABSABZaabbab编译原理编译原理编译原理编译原理编译原理编译原理4.4 4.4 词法分析程序的自动构造工具词法分析程序的自动构造工具把正规式转换为一个NFA进而转换为相应的DFA，由此构造出词法分析程序。LEX编译系统
