《编译原理第3讲》由会员分享，可在线阅读，更多相关《编译原理第3讲（83页珍藏版）》请在金锄头文库上搜索。
1、1盛威网：专业的计算机学习网站2盛威网：专业的计算机学习网站第四章词法分析v4.1 词法分析程序的设计词法分析程序的设计v4.2 单词的描述工具单词的描述工具v4.3 有穷自动机有穷自动机v4.4 正规式和有穷自动机的等价性正规式和有穷自动机的等价性v4.5 正规文法和有穷自动机的等价性正规文法和有穷自动机的等价性v4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具v4.7典型例题及解答典型例题及解答3盛威网：专业的计算机学习网站知知识识结结构构4盛威网：专业的计算机学习网站词法分析词法分析自动构造工具自动构造工具正规集正规集正规式正规式有穷自动机（有穷自动机（NFA DFA)正规文
2、法正规文法知识结构5盛威网：专业的计算机学习网站第四章词法分析4.1词法分析程序的设计源程序词法分析程序语法分析程序Tokenget token.v主要任务：读源程序，产生单词符号主要任务：读源程序，产生单词符号v其他任务：其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，追踪换行标志，复制出错源程序，宏展开，宏展开，6盛威网：专业的计算机学习网站一.词法分析程序与语法分析程序的接口方式v词法分析工作可以是独立的一遍，把字符流的源程序词法分析工作可以是独立的一遍，把字符流的源程序变为变为单词序列单词序列，输出在一个，输出在一个中间文件中间文件上，这个文
3、件作上，这个文件作为语法分析程序的为语法分析程序的输入输入而继续编译过程而继续编译过程7盛威网：专业的计算机学习网站v更通常情况，常将词法分析程序设计成一个更通常情况，常将词法分析程序设计成一个子程序子程序，每当语法分析程序需要一个单词时，则调用该子程序。每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止词的第一个字符为止8盛威网：专业的计算机学习网站二.词法分析程序的输出1.单词符号一般可分为下
4、列五种：单词符号一般可分为下列五种：v基本字（关键字）：基本字（关键字）：begin、end、if、while、varv标识符：常量名、变量名、过程名标识符：常量名、变量名、过程名v常数（量）：常数（量）：25、3.1415、true、“ABC”v运算符：、运算符：、*、=v界符：逗点、分号、括号界符：逗点、分号、括号9盛威网：专业的计算机学习网站2.输出表示：输出表示：v（单词种别，单词自身的值）（单词种别，单词自身的值）单词种别：语法分析需要的信息单词种别：语法分析需要的信息单词自身的值：编译其他阶段需要的信息单词自身的值：编译其他阶段需要的信息10盛威网：专业的计算机学习网站v（标识符，
5、指向该标识符所在符号表中位置的指针）（标识符，指向该标识符所在符号表中位置的指针）单词的种别可以用整数编码表示，假如标识符编码为单词的种别可以用整数编码表示，假如标识符编码为1，常数为，常数为2，关键字为，关键字为3，运算符为，运算符为4，界符为，界符为511盛威网：专业的计算机学习网站if i=5 then x:=y关键字关键字if(3, if)标识符标识符i (1，指向指向i的符号表入口的符号表入口)等号等号 (4, = )常数常数5 ( 2, 5 )关键字关键字then ( 3, then )标识符标识符x (4,指向指向x的符号表入口的符号表入口)赋值号赋值号:= ( 4, ：= )标
6、识符标识符y ( 1, 指向指向y的符号表入口的符号表入口 )分号分号; ( 5, ; )12盛威网：专业的计算机学习网站三.将词法分析工作分离的考虑1.使整个编译程序的结构更简洁、清晰和条理化：使整个编译程序的结构更简洁、清晰和条理化：2.编译程序的效率会改进：编译程序的效率会改进：3.增强编译程序的可移植性：增强编译程序的可移植性：13盛威网：专业的计算机学习网站4.2单词的描述工具一.正规文法v程序设计语言中的几类单词可用下述规则描述：程序设计语言中的几类单词可用下述规则描述：l|ll|d|l|dd|d+|-|*|/|=|=,|;|(|)| 其中其中l表示表示az中的任何一个英文字母，中
7、的任何一个英文字母，d表示表示09中中的任何一个数字的任何一个数字14盛威网：专业的计算机学习网站v例例4.1：d|.e d|.e| d e| d | d |s d d | 其中，其中，s表示正或负号表示正或负号(+,-)15盛威网：专业的计算机学习网站二.正规式v正规表达式（正规表达式（regular expression）是说明单词的是说明单词的pattern的一种重要的表示法（记号），是定义正规集的一种重要的表示法（记号），是定义正规集的工具的工具16盛威网：专业的计算机学习网站v定义（正规式和它所表示的正规集）：定义（正规式和它所表示的正规集）：设字母表为设字母表为 ，辅助字母表，辅助
8、字母表 = ， ， ， ， ， ， 和和 都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和 任何任何a ，a是是 上的一个正规式，它所表示的正规集上的一个正规式，它所表示的正规集为为a17盛威网：专业的计算机学习网站假定假定e1和和e2都是都是 上的正规式，它们所表示的正规集分别上的正规式，它们所表示的正规集分别为为L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正也都是正规规式式,它们所表示的正规集分别为它们所表示的正规集分别为L(e1), L(e1) L(e2), L(e1)L(e2)和和(L(e1) 仅由有
9、限词使用上述三步骤而定义的表达式才是仅由有限词使用上述三步骤而定义的表达式才是 上的上的正规式，仅由这些正规式所表示的字集才是正规式，仅由这些正规式所表示的字集才是 上的正规上的正规集集18盛威网：专业的计算机学习网站其中的其中的“ ”读为读为“或或”（也有使用也有使用“+”代替代替 “ ” 的的）；）；“ ”读为读为“连接连接”；“ ”读为读为“闭包闭包”（即，（即，任任意有限次的自重复连接）。在不致混淆时，括号可省去，意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为但规定算符的优先顺序为“ ”、“ ”、“ ”、“ ”、“ ” 。连接符。连接符“ ”一般可省略不写。一
10、般可省略不写。“ ”、“ ”和和“ ” 都是左结合的都是左结合的19盛威网：专业的计算机学习网站v例例4.2 令令 =a，b, 上的正规式和相应的正规集的例子有：上的正规式和相应的正规集的例子有：正规式正规式 正规集正规集a aa b a,bab ab(a b)(a b) aa,ab,ba,bba ,a,a, 任意个任意个a的串的串(a b) ,a,b,aa,ab 所有由所有由a和和b组成的串组成的串(a b) (aa bb)(a b) 上所有含有两个相继的上所有含有两个相继的a或两或两个个相继的相继的b组成的串组成的串20盛威网：专业的计算机学习网站v例例4.3 =d，.，e，+，-,则则
11、上的正规式上的正规式dd (.dd )(e(+ - )dd ) 其中其中d为为09的数字的数字表示的是：表示的是： 无符号数的集合无符号数的集合21盛威网：专业的计算机学习网站v若两个正规式若两个正规式e1和和e2所表示的正规集相同所表示的正规集相同,则说则说e1和和e2等价等价,写写作作e1=e2例如：例如： e1= (a b)， e2 = b a又如：又如： e1= b(ab) , e2 =(ba) be1= (a b) , e2 =(a b ) 22盛威网：专业的计算机学习网站v设设r,s,t为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：r s=s r“或或”服从交
12、换律服从交换律r (s t)=(r s) t“或或”的可结合律的可结合律(rs)t=r(st)“连接连接”的可结合律的可结合律r(s t)=rs rt (s t)r=sr tr分配律分配律 r=rr =r 是是“连接连接”的恒等元素（零一律）的恒等元素（零一律）r r=rr =r rr “或或”的抽取律的抽取律23盛威网：专业的计算机学习网站三.正规文法和正规式的等价性1.将将 上的一个正规式上的一个正规式r转换成文法转换成文法G=(VN,VT,P,S)：令令VT，确定产生式和确定产生式和VN的元素用如下办法的元素用如下办法：24盛威网：专业的计算机学习网站选择一个非终结符选择一个非终结符S生
13、成产生式生成产生式Sr，并将并将S定为定为G的的识别符号。若识别符号。若x和和y都是正规式都是正规式 ， B VN ，则：则：(R1) 对形如对形如 Axy的的正规产生式正规产生式，重写为，重写为： AxB，By (R2)对形如对形如Ax*y的的正规产生式正规产生式，重写为：，重写为： AxA，Ay (R3)对形如对形如Ax y的的正规产生式正规产生式，重写为，重写为:Ax，Ay不断应用不断应用R做变换，直到每个产生式右端只含一个做变换，直到每个产生式右端只含一个VN25盛威网：专业的计算机学习网站例例4.4将将 r=a(a|d)*转换成相应的正规文法转换成相应的正规文法令令S是文法的开始符号
14、，形成是文法的开始符号，形成Sa(a|d)*：R1 SaA A(a|d)*R2S aA A(a|d)A A R3 SaA AaA AdA A 26盛威网：专业的计算机学习网站2.将正规文法转换成正规式：将正规文法转换成正规式：基本上是上述过程的逆过程，最后只剩下一个开始符基本上是上述过程的逆过程，最后只剩下一个开始符号定义的正规式，其转换规则如表号定义的正规式，其转换规则如表4.1所示：所示：27盛威网：专业的计算机学习网站v例例4.5Gs:SaA Sa AaAAdA Aa Ad SaA|a AaA|dA|a|d (a|d)A|(a|d)(a|d)*(a|d)s=a(a|d)*(a|d)|a=
15、a(a|d)*(a|d)|)=a(a|d)*|)r=a(a|d)*28盛威网：专业的计算机学习网站4.3有穷自动机一.确定的有穷自动机（DFA）（有限自动机）vDFA：能准确地识别正规集能准确地识别正规集v一个确定的一个确定的DFA：M=（K，f，S，Z）K K是一个有穷集，它的每个元素称为一个状态是一个有穷集，它的每个元素称为一个状态是一个有穷字母表，它的每个元素称为一个输入符是一个有穷字母表，它的每个元素称为一个输入符号，所以也称号，所以也称为输入符号字母表为输入符号字母表29盛威网：专业的计算机学习网站f是转换函数，是在是转换函数，是在KK上的映射，即，如上的映射，即，如f（ki，a）=
16、kj，（，（kiK，kjK）就意味着，当前状就意味着，当前状态为态为ki，输入符为输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们我们把把kj称作称作k ki的一个后继状态的一个后继状态SK是唯一的一个初态是唯一的一个初态Z K是一个终态集，终态也称可接受状态或结束状态是一个终态集，终态也称可接受状态或结束状态30盛威网：专业的计算机学习网站例例4.6：DFA M=（S，U,V，Q，a，b，f，S，Q）其中其中f定义为：定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q31盛威网：专业的计算
17、机学习网站v一个一个DFA可以表示成一个可以表示成一个状态图状态图（状态转换图）（状态转换图）v假定假定DFAM含有含有m个状态，个状态，n个输入符号，那么这个个输入符号，那么这个状态图含有状态图含有m个结点，每个结点最多有个结点，每个结点最多有n个弧射出，整个弧射出，整个图含有唯一一个初态结点个图含有唯一一个初态结点(、)和若干个终态结和若干个终态结点点(双圈、双圈、+)，若，若f(ki,a)=kj，则从状态结点则从状态结点ki到状态结到状态结点点kj画标记为画标记为a的弧的弧32盛威网：专业的计算机学习网站图图4.1状态图表示状态图表示例例4.6中的中的DFA的状态图表示如图的状态图表示如
18、图4.1所示：所示：33盛威网：专业的计算机学习网站v一个一个DFA可以表示成一个可以表示成一个矩阵表示矩阵表示，该矩阵的行表示状，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符态，列表示输入符号，矩阵元素表示相应状态和输入符号将转换成的新状态，即号将转换成的新状态，即k行行a列为列为f(k,a)的值。用的值。用标明初态；否则第一行即是初态，相应终态行在表的右标明初态；否则第一行即是初态，相应终态行在表的右端标以端标以1，非终态标以，非终态标以034盛威网：专业的计算机学习网站图图4.2矩阵表示矩阵表示v例例4.5中的中的DFA的矩阵表示如图的矩阵表示如图4.2所示：所示：3
19、5盛威网：专业的计算机学习网站v若若t *，f(S，t)=P，其中其中S为为 M的开始状态，的开始状态，P Z，Z为终态集，则称为终态集，则称t为为DFA M所接受所接受（识别）（识别）v设设QK，函数函数f(Q,)=Q，一个一个输入符号串入符号串t（t1tx，t1 ,tx *），在），在DFAM上运行的定义为：上运行的定义为：f(Q,t1tx)=f(f(Q,t1),tx)36盛威网：专业的计算机学习网站v例如，证明例如，证明t=baab被例被例4.6的的DFA所接受所接受f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f
20、（U，a），），b）=f（Q，b）=QQ属于终态属于终态得证得证37盛威网：专业的计算机学习网站vDFA M所能接受的符所能接受的符号号串的全体记为串的全体记为L(M)v结论：结论： 上一个符上一个符号号串集串集V 是正规的，当且仅当存是正规的，当且仅当存在一个在一个 上的确定有穷自动机上的确定有穷自动机M，使得使得V=L(M)vDFA的确定性表现在转换函数的确定性表现在转换函数f:KK是一个单值是一个单值函数，也就是说函数，也就是说,对任何状态对任何状态kK和输入符号和输入符号a ，f(k,a)唯一地确定了下一个状态唯一地确定了下一个状态38盛威网：专业的计算机学习网站二.不确定的有穷自动机
21、NFAv一个一个NFA：M=（K， ，f，S，Z）K是一个有穷集，它的每个元素称为一个状态是一个有穷集，它的每个元素称为一个状态 是一个有穷字母表，它的每个元素称为一个输入符号是一个有穷字母表，它的每个元素称为一个输入符号f是一个从是一个从K * 到到K的子集的映像，即：的子集的映像，即：K* * 2 KS K是一个非空初态集是一个非空初态集Z K是一个终态集是一个终态集39盛威网：专业的计算机学习网站v例例4.7：一个：一个NFA M=（0，1，2，3，4，a，b，f，0，2,4）其中其中f(0,a)=0,3 f(2,b)=2f(0,b)=0,1 f(3,a)=4f(1,b)=2 f(4,a
22、)=4f(2,a)=2 f(4,b)=4它的状态图表示如图它的状态图表示如图4.3所示：所示：40盛威网：专业的计算机学习网站41盛威网：专业的计算机学习网站v一个一个NFA也可以用一个矩阵表示也可以用一个矩阵表示.v*上的符上的符号号串串t在在NFA N上运行上运行.v*上的符上的符号号串串t被被NFA N识别（读出、接受）识别（读出、接受）.vDFA是是NFA的特例的特例v对每个对每个NFA N存在一个存在一个DFA ,使得使得L(M)=L(N)v对于任何两个有穷自动机对于任何两个有穷自动机M和和N，如果如果L(M)=L(N)，则称则称M与与N是等价的是等价的42盛威网：专业的计算机学习网
23、站三.NFA转换为等价的DFAv定理：定理：设设L为一个由不确定的有穷自动机接受的集合，则为一个由不确定的有穷自动机接受的集合，则存在一个接受存在一个接受L的确定的有穷自动机的确定的有穷自动机v将将NFA转换成接受同样语言的转换成接受同样语言的DFA，这种算法称为这种算法称为子集法子集法43盛威网：专业的计算机学习网站v定义对状态集合定义对状态集合I的几个有关运算：的几个有关运算：1.状态集合状态集合I的的 -闭包，表示为闭包，表示为 -closure(I)，定义为一状态定义为一状态集，是状态集集，是状态集I中的任何状态中的任何状态S经任意条经任意条 弧而能到达的状弧而能到达的状态的集合。态的
24、集合。状态集合状态集合I的任何状态的任何状态S都属于都属于 -closure(I)2.状态集合状态集合I的的a弧转换，表示为弧转换，表示为move(I,a)定义为状态集合定义为状态集合J，其中其中J是所有那些可从是所有那些可从I的某一状态经过一条的某一状态经过一条a弧而到达弧而到达的状态的全体的状态的全体44盛威网：专业的计算机学习网站v使用图4.4的NFAN的状态集合来理解上述两个运算： -closure(0)=0,1,2,4,7令令A=0,1,2,4,7, move(A,a)=3,8 -closure(3,8)=1,2,3,4,6,7,8图图4.4NFAN45盛威网：专业的计算机学习网站v
25、对于一个对于一个NFAN=（K， ，f，K0，Kt）来说，若来说，若I是是K的一个子集，设的一个子集，设Is1,s2, ,s sj，a是是中的一个元素，中的一个元素，则则move(I,a)=f(s1,a) f(s2,a) f(sj,a)46盛威网：专业的计算机学习网站v假设假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个按如下办法构造一个DFA M=(S, ,d,S0,St)，使得使得L(M)=L(N)： M的状态集的状态集S由由K的一些子集组成。用的一些子集组成。用S1 S2. Sj表示表示S的元素，其中的元素，其中S1, S2,. Sj是是K的状态。并且约定，状态的状态。并且约
26、定，状态S1, S2,. Sj是按某种规则排列的，即对于子集是按某种规则排列的，即对于子集S1, S2= S2, S1,来说，来说，S的状态就是的状态就是S1 S2M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是 转换函数是这样定义的：转换函数是这样定义的： D(S1 S2,. Sj,a)= R1R2. Ri 其中其中 R1,R2,. , Ri = -closure(move(S1, S2,. Sj,a) 47盛威网：专业的计算机学习网站 S0= -closure(K0)为为M的开始状态的开始状态 St=Sj Sk. Se，其中其中Sj Sk. Se S且且Sj , Sk,. Se
27、 Kt v构造构造NFA N的状态的状态K的子集的算法，见图的子集的算法，见图4.5：假定所构造的子集族为假定所构造的子集族为C，即，即C= (T1, T2,. Ti),其中其中T1, T2,. Ti为状态为状态K的子集的子集48盛威网：专业的计算机学习网站49盛威网：专业的计算机学习网站v例4.8应用图4.5的算法对图4.4的NFAN构造子集步骤如下：1.首先计算首先计算 -closure(0)：令：令T0= -closure(0)=0,1,2,4,7，T0未未被标记，它现在是子集族被标记，它现在是子集族C的唯一成员的唯一成员2.标记标记T0：令：令T1= -closure(move(T0,
28、a)=1,2,3,4,6,7,8，将，将T1加入加入C中，中，T1未被标记。令未被标记。令T2= -closure(move(T0,b)=1,2,4,5,6,7，将，将T2加入加入C中，中，T2未被标记未被标记3.标记标记T1： -closure(move(T1,a)=1,2,3,4,6,7,8，即，即T1，T1已已在在C中。中。T3= -closure(move(T1,b)=1,2,4,5,6,7,9，将，将T3加加入入C中，中，T3未被标记未被标记50盛威网：专业的计算机学习网站4.标记标记T2： -closure(move(T2,a)=1,2,3,4,6,7,8，即，即T1，T1已已在在
29、C中。中。 -closure(move(T2,b)=1,2,4,5,6,7，即，即T2，T2已在已在C中中5.标记标记T3： -closure(move(T3,a)=1,2,3,4,6,7,8，即，即T1。 -closure(move(T3,b)=1,2,4,5,6,7,10,令其为令其为T4，在入在入C中，中，T4未被标记未被标记6.标记标记T4： -closure(move(T4,a)=1,2,3,4,6,7,8，即，即T1。 -closure(move(T4,b)=1,2,4,5,6,7，即，即T251盛威网：专业的计算机学习网站 ab001247T0=01247385381234678
30、5124567T1=12346783859591245679T2=124567385T3=1245679385 105 1012456710T4=1245671038552盛威网：专业的计算机学习网站至此，算法终止共构造了至此，算法终止共构造了5个子集：个子集：T0=0,1,2,4,7T1=1,2,3,4,6,7,8T2=1,2,4,5,6,7T3=1,2,4,5,6,7,9T4=1,2,4,5,6,7,10那么图那么图4.4的的NFAN构造的构造的DFAM为：为：1.S= T0, T1, T2, T3, T4 2. =a,b53盛威网：专业的计算机学习网站3. D(T0,a)=T1 D(T3
31、,a)=T1 D(T0,b)=T2 D(T3,b)=T4 D(T1,a)=T1 D(T4,a)=T1 D(T1,b)=T3 D(T4,b)=T2 D(T2,a)=T1 D(T2,b)=T24.S0=T05.St=T4为便于书写，将为便于书写，将T0、 T1、 T2、 T3、 T4重新命名重新命名为为A、B、C、D、E或用或用0、1、2、3、4分别表示，若采用后分别表示，若采用后者，该者，该DFAM的状态转换图如图的状态转换图如图4.6所示：所示：54盛威网：专业的计算机学习网站图图4.6DFAM55盛威网：专业的计算机学习网站四.DFA的化简v最小状态最小状态DFA：没有多余状态没有多余状态(
32、死状态死状态) )没有两个状态是互相等价（没有两个状态是互相等价（不可区别不可区别）v一个有穷自动机可以通过消除无用状态和合并等价状态一个有穷自动机可以通过消除无用状态和合并等价状态而转换成一个最小的与之等价的有穷自动机而转换成一个最小的与之等价的有穷自动机v有穷自动机的无用状态：从该自动机的开始状态出发，有穷自动机的无用状态：从该自动机的开始状态出发，任何输入串也任何输入串也不能到达不能到达的那个状态或者从这个状态的那个状态或者从这个状态没有没有通路到达通路到达终态终态v例如图例如图4.7的有穷自动机的有穷自动机M中的状态中的状态s4便是无用状态便是无用状态56盛威网：专业的计算机学习网站图
33、图4.7消除多余状态消除多余状态57盛威网：专业的计算机学习网站v在有穷自动机中，两个状态在有穷自动机中，两个状态s和和t等价的条件是：等价的条件是：一致性条件一致性条件必须同是为可接受状态或不可接受状态必须同是为可接受状态或不可接受状态蔓延性条件蔓延性条件对于所有输入符号，必须转换到等价的对于所有输入符号，必须转换到等价的状态里状态里v分割法：分割法：把一个把一个DFA（不含多余状态）的状态分成一些不含多余状态）的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的别的，而同一子集中的任何两个状
34、态都是等价的58盛威网：专业的计算机学习网站vDFAM最小化方法最小化方法：先分成终态集合和非终态集合先分成终态集合和非终态集合对每个集合中的符号分别用输出字母去查看它们到达状对每个集合中的符号分别用输出字母去查看它们到达状 态的集合是否在同一个集合中态的集合是否在同一个集合中如果不在同一个集合，将它们划分在不同的集合中如果不在同一个集合，将它们划分在不同的集合中直到不能再划分为止直到不能再划分为止59盛威网：专业的计算机学习网站v例例4.9将图将图4.8中的中的DFAM最小化最小化P0=(1,2,3,4,5,6,7) aP1=(1,2,3,4,5,6,7) aP2=(1,2,3,4,5,6,
35、7) aP3=(1,2,3,4,5,6,7) b令令1代表代表1,2消去消去2，令，令6代表代表6,7，消去，消去7，得到图，得到图4.8(b)的的DFA M，它是它是4.8(a)的的DFA M的最小化的最小化60盛威网：专业的计算机学习网站图图4.8DFAM和和DFAM61盛威网：专业的计算机学习网站4.4正规式和有穷自动机的等价性v对于对于上的一个上的一个NFA M，可以构造一个，可以构造一个上的正规式上的正规式R,R,使得使得L(R)=L(M)第一步，在第一步，在M的状态转换图上加进两个结，一个为的状态转换图上加进两个结，一个为x结结点，一个为点，一个为y结点。从结点。从x结点用结点用
36、弧连接到弧连接到M的所有初始的所有初始结点，从结点，从M的所有终态结点用的所有终态结点用 弧连接到弧连接到y结点。形成结点。形成一个与一个与M等价的等价的M, M只有一个初态只有一个初态x和一个终态和一个终态y 第二步，逐步消去第二步，逐步消去MM中的所有结点，直至只剩下中的所有结点，直至只剩下x x和和y y结点。在消结过程中，逐步用正规式来标记弧结点。在消结过程中，逐步用正规式来标记弧62盛威网：专业的计算机学习网站其消结的规则如下：其消结的规则如下：最后最后x x和和y y结点间的弧上的标记则为所求的正规式结点间的弧上的标记则为所求的正规式r r63盛威网：专业的计算机学习网站例例4.1
37、04.10以例以例4.74.7的的NFANFAM M为例，为例，M M的状态图在图的状态图在图4.34.3，求，求 正规式正规式r,r,使使L(r)=L(M)L(r)=L(M)64盛威网：专业的计算机学习网站65盛威网：专业的计算机学习网站v对于对于上的一个正规式上的一个正规式R，可以构造一个，可以构造一个上的上的NFA M，似的，似的L(M)=L(R)语法制导方法：按正规式的语法结构指引构造过程，首先语法制导方法：按正规式的语法结构指引构造过程，首先将正规式分解成一系列子表达式，然后使用下面规则为将正规式分解成一系列子表达式，然后使用下面规则为r构造构造NFA，对，对r的各种语法结构的构造规
38、则具体描述如下：的各种语法结构的构造规则具体描述如下：1. 对于正规式对于正规式 ，所构造的所构造的NFA为：为： 66盛威网：专业的计算机学习网站67盛威网：专业的计算机学习网站68盛威网：专业的计算机学习网站69盛威网：专业的计算机学习网站v例4.11为r=(a|b)*abb构造NFAN,使得L(N)=L(r)从左到右分解从左到右分解r,r,令令r r1 1=a,=a,第第1 1个个a,a,则有则有令令r2 2=b,则有则有令令r3 3=r1 1|r2 2,则有则有令令r4=r3，则有：则有：70盛威网：专业的计算机学习网站令令r5=a，令令r6=b，令令r7=b，令令r8=r5r6，令令
39、r9=r8r7，则有：则有：令令r10=r4r9，则最终得到图则最终得到图4.4的的NFA N即为所求。即为所求。其实，分解其实，分解R的方式很多，用图的方式很多，用图4.10(a)(b)(c)(d)分别表明分别表明另一种分解方式和所构造的另一种分解方式和所构造的NFA。 71盛威网：专业的计算机学习网站图图4.10从正规式从正规式r构造构造NFA72盛威网：专业的计算机学习网站4.5正规文法和有穷自动机的等价性v采用下面的规则可以从正规文法采用下面的规则可以从正规文法G直接构造一个有穷直接构造一个有穷自动机自动机NFAM；使得；使得L（M）L（G）：）：M M的字母表与的字母表与G G的终结
40、符集相同的终结符集相同为为G G中的每个非终结符生成中的每个非终结符生成M M的一个状态，的一个状态，G G的开始符的开始符S S是开始状态是开始状态S S73盛威网：专业的计算机学习网站增加一个新状态增加一个新状态Z Z，作为作为NFANFA的终态的终态对对G G中的形如中的形如A AtBtB的规则（其中的规则（其中t t为终结符或为终结符或 ，A A和和B B为为非终结符的产生式），构造非终结符的产生式），构造M M的一个转换函数的一个转换函数f(A,t)=Bf(A,t)=B对对G G中形如中形如A At t的产生式，构造的产生式，构造M M的一个转换函数的一个转换函数f(A,t)=Zf(
41、A,t)=Z74盛威网：专业的计算机学习网站v例例4.12：与文法：与文法GS等价的等价的NFAM如图如图4.11GS: Sa A SbBS AaB AbA BaSBbA B 75盛威网：专业的计算机学习网站v有穷自动机转换成等价的正规文法：有穷自动机转换成等价的正规文法：对转换函数函数f(A,t)=B,可写一可写一产生式：生式：AtB对可接受状可接受状态Z，增加一增加一产生式：生式：Z有有穷自自动机的初机的初态对应文法开始符文法开始符有有穷自自动机的字母表机的字母表为文法的文法的终结符集符集76盛威网：专业的计算机学习网站v例4.13：给出与图4.12的NFA等价的正规文法GG（A，B，C，
42、D，a，b，P，A），），其中其中P为：为：Aa B C AbD DaBBbC DbDCaA D CbD77盛威网：专业的计算机学习网站4.6词法分析程序的自动构造工具v以以LEX为例介绍如何从正规式产生识别该正规式所描述的为例介绍如何从正规式产生识别该正规式所描述的单词的词法分析程序单词的词法分析程序vLEX是一个广泛使用的工具，是一个广泛使用的工具，UNIX系统中使用系统中使用lex命令调命令调用。它用于构造各种各样语言的词法分析程序用。它用于构造各种各样语言的词法分析程序图图 4.13LEX编译系统的作用编译系统的作用 78盛威网：专业的计算机学习网站图图 4.14 使用使用LEX生成词
43、法分析器生成词法分析器 79盛威网：专业的计算机学习网站vLEX程序由三部分组成：程序由三部分组成：说明部分：变量说明、常量说明、正规定义说明部分：变量说明、常量说明、正规定义%转换规则：转换规则：Pn action n%辅助过程：辅助过程：容纳的是容纳的是action所需要的辅助过程所需要的辅助过程80盛威网：专业的计算机学习网站v图图4.15给出一个识别给出一个识别PL/O单词的单词的LEX程序片断：程序片断： IDENTa-zA-Z a-zA-Z0-9*NUMBER0-9 0-9*%(#include stdio.h#include code.h“#include symbol.h“#i
44、nclude y.tab.h“extern int level;int cc=0;%)% cc+;t tablize(); /*adjustcc to tabposition*/n cc=0; line-copy(); /*copy a line of input file*/ cc+; return GT;= cc+; return EQ; 81盛威网：专业的计算机学习网站# cc+; return NE; , cc+; return colon; . cc+; return Period;( cc+; return Lparen;) cc+; return Rparen; = cc+;cc
45、+;return GE; = cc+; cc+;return ASGN; ; cc+; return Semicolon; NUMBER intn;cc += yyleng;sscanf(yytext,%d, &n);yylval.number=n;return NUMBER; 82盛威网：专业的计算机学习网站IDENT Symbol *s;cc += yyleng;if(s=lookup(yytext)=0) /*new identifier*/s=install(yytext,VARIABLE,level,0); /* install symbol*/if (stype=C)yylval.
46、number=s-adr;else /*its a VARIABLE or PROC*/yylval.sym=s;return s-type;%yywrap( ) ; 图图 4.15 LEX程序例子程序例子-识别识别PL/0单词的单词的LEX程序程序 83盛威网：专业的计算机学习网站【本章小结】词法分析程序是编译第一阶段的工作，它读入字符流的源词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词程序，按照词法规则识别单词,交由语法分析程序接下去。交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了正规式和有本章讲述了词法分析程序设计原则，并介绍了正规式和有穷
47、动机分别作为正规集描述和识别机制。在此基础上给出了词穷动机分别作为正规集描述和识别机制。在此基础上给出了词法分析程序自动构造工具如法分析程序自动构造工具如LEX的原理。的原理。词法分析程序的设计技术可应用于其它领域，比如查询语词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想过字符串模式的匹配来引发动作，回想LEX，说明词法分析说明词法分析程序的语言，可以看成是一个模式动作语言。程序的语言，可以看成是一个模式动作语言。词法分析程序的自动构造工具也广泛应用于许多方面，如词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。路设计和文本编辑的自动生成等。
