《正规文法和正规式的等价性课件》由会员分享，可在线阅读，更多相关《正规文法和正规式的等价性课件（71页珍藏版）》请在金锄头文库上搜索。
1、编译原理第一章 编译程序概述第二章 PL/0编译程序的实现第三章 文法和语言第四章 词法分析第五章 自顶向下语法分析方法第六章 自底向上优先分析方法第七章 LR分析方法第八章 语法制导翻译和中间代码生成第九章 符号表第一章 代码优化第一一章 代码生成词法分析主要任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。词法分析的基本思路：将单词符号的语法用有效的工具描述；基于该描述建立单词的识别机制；设计和实现词法分析程序词法分析是编译过程的第一个阶段。单词的描述技术正规文法正规式单词的识别机制确定有穷自动机不确定有穷自动机词法分析程序的自动构造原理正规式和有穷自动机的等价性
2、词法分析程序的自动构造工具单词的描述工具某种程序设计语言中的所有单词构成一种语言。该语言的语法都能用正规文法表示。正规文法是描述单词的一种工具。1、正规文法（回顾） 文法G=(VN,VT,P,S)，P中每一规则有AaB或Aa ，A,BVN，aVT*，称G(S)是正规文法。 l|l l|d|l| d d|dl表示a-z中的任何英文字母，d表示0-9中的任何数字由正规文法产生的语言称为正规集2、正规式（正则表达式）是表示正规集的工具，也是用以描述单词符号的方便工具。j正规式与正规集的定义： 设字母表为，辅助字母表=，|，*，（，） ； 和都是上的正规式，表示的正规集分别为和；任何a,a是上的一个正
3、规式，表示的正规集为a;假定e1和e2都是上的正规式，它们所表示 的 正 规 集 分 别 为 L(e1)和 L(e2),则(e1),e1|e2,e1e2和e1*也都是正规式，所表示的正规集分别为L(e1),L(e1)L(e2), L(e1)L(e2)和(L(e1)*。 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。例： a,b， 上的正规式和相应的正规集为：ab-(a) 一个正规式可以表示若干个符号串,(b) 其正规集就是这些符号串的集合a|baba*b*-(a|b)*a*|b*aba*(a|b)*(aa|bb)(a|b)* a ab b-(a
4、) a 一个正规式可以表示若干个符号串,(b) b 其正规集就是这些符号串的集合a|b a,bab aba* ,a,aa,aaa,aaaa,.b* ,b,bb,bbb,bbbb,.-(a|b)* a和b组成的所有串a*|b* ,a,aa,aaa,aaaa,.,b,bb,bbb,bbbb,.aba* 以ab开头后接若干个(包括0个)a组成的串(a|b)*(aa|bb)(a|b)*上所有含有两个相继的a或两个相继的b组成的串例：令d， ，e，则上的正规式d*(.dd*| )(e(+|-|)dd*|)表示的是所有无符号数。 其中d为09中的数字。 比如：2,12.59,3.6e2,471.88e-1
5、等都是正规式表示集合中的元素。设r，s，t为正规式，正规式服从代数规律有：1、r|ss|r交换律2、r|(s|t)(r|s)|t结合律3、(rs)t=r(st)结合律4.r(s|t)=rs|rt分配律(s|t)r=sr|tr分配律5.r=r零一律r=r零一律程序设计语言中的单词既能用正规文法表示，又能用正规式来表示.正规文法: l|l l|d|l| d d|dl表示a-z中的任何英文字母，d表示0-9中的任何数字正规式？4.r(s|t)=rs|rt分配律(s|t)r=sr|tr分配律5.r=r零一律r=r零一律程序设计语言中的单词既能用正规文法表示，又能用正规式来表示.正规文法: l|l l|
6、d|l| d d|dl表示a-z中的任何英文字母，d表示0-9中的任何数字正规式:标识符:e1=字母(字母|数字)*无符号整数:e2=dd*3、正规文法和正规式的等价性、正规文法和正规式的等价性 一个正规语言可以由正规文法定义，也可以用正规式定义。对于任意一个正规文法，存在一个定义同一语言的正规式。对每一个正规式，存在一个生成同一语言的正规文法。即正规式正规文法 正规式正规文法： （把正规式转换为正规文法所要求的规则形式）将上的一个正规式r转换为一个正规文法G=（VN，VT，P，S）的规则：令VT=，对正规式r，选择一个非终结符S生成Sr，S为G的开始符号。不断拆分r直到符合正规文法要求的规则
7、形式： 若x，y都是正规式，对形如Axy的产生式，写成AxB，By。其中B VN 对形如Ax*y的产生式，重写为：Ax A Ay B为新的非终结符，B VN对形如Ax|y的产生式，重写为： Ax Ay 不断利用上述规则进行变换即可。例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。解：S a(a|d)*SaAA(a|d)*A(a|d) AA 最后得到：SaAAaAAdAA 正规文法正规文法正规式：正规式：将一个正规文法转换为正规式的规则：转换规则：转换规则： AxB，By 正规式为：A=xy AxA|y 正规式为：A=x*y w
8、Ax，Ay 正规式为： A=x|y 不断收缩产生式规则，直到剩下一个开始符号定义的正规式不断收缩产生式规则，直到剩下一个开始符号定义的正规式例：文法GS：S aAS aA aAA dAA aA d转换为正规式S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d)根据上述规则3Ax，Ay推出A=x|y将它化为正规文法变成A (a|d)A|(a|d) 再根据上述规则2转换xy (a|d)将A代入SaA|a得到如下：Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a
9、(a|d)* 二、二、有穷自动机有穷自动机 有穷自动机：是一种自动识别装置，能正确识别正规集；是词法分析程序的工具和方法，可自动识别（且是正确识别）正规集。分为确定的有穷自动机（确定的有穷自动机（DFA）不确定的有穷自动机不确定的有穷自动机（NFA） （一）一）确定的有穷自动机确定的有穷自动机DFA 自动自动识别装置识别装置一个确定的有穷自动机M是一个五元组：M=（K，f，S，Z），其中： K是一个有穷集，每个元素表示一个状态；是一个有穷字母表，每个元素是一个输入字符； f是转换函数，是在KK上的映象，如： f(Ki ，a)= Kj (Ki, KjK)； S是初态，SK； ZK，是终态集。 含
10、义：当前状态为Ki，输入字符a，转换为Kj状态1、用状态图表示：方法如下：初始态用“”或“”表示； 终态点用 “” 或“” 表示； 若f(Ki ，a)= Kj ，则从状态点Ki 到Kj画弧，标记为a。例：DFA的M(S,U,V,Q,a,b,f,S,Q)其中f为：f(S,a)=U, f(S,b)=V, f(U,a)=Qf(U,b)=V, f(V,a)=U, f(V,b)=Qf(Q,a)=Q, f(Q,b)=Q画出画出状态图状态图状态图如下：a,baaabbbSUVQ2、用矩阵表示DFA:方法：行表示状态列表示输入字符元素表示相应状态行和输入字符下的新状态。a,b“”标明初态，默认第一行是初态。终
11、态行在表右端标1，非终态标0上例矩阵表示如下：abSUVUQVVUQQQQ字符状态0001例：baSZa,b表示：f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=ZabSZZZZZ01写成正规式是： (a|b)(a|b)*3、接受（识别）的概念： 自动识别单词自动识别单词对于*中的任何字符串t，若存在一条初态到某一终态的路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFA M所接受。 若M的初态同时又是终态，则空字可为M所接受。4、接受（识别）的理解： 设QK，函数f(Q,)=Q，则输入字符串是空串，并停留在原状态上。输入字符串t（t表示成Tt1形式，T，t1
12、 *），在DFA M上运行的定义为：f（Q，Tt1）=f(f(Q,T),t1)，其中QK。 例如：baab字符串被DFA所接受，DFA见上例。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)=Q （Q是终态）DFA M所能接受的字符串的全体记为L（M）称为语言 （也即句子的集合） 5、DFA的确定性： 当当f：kK是一个单值函数，即对任何状态是一个单值函数，即对任何状态K R，输入符号输入符号a K，f(k,a)唯一确定下一状态。唯一确定下一状态。 DFA的行为很容易用程序来模拟.DFAM=（K，f
13、，S，Z）的行为的模拟程序K:=S；c:=getchar;whileceofdoK:=f(K,c);c:=getchar;ifKisinZthenreturn(yes)elsereturn(no)自动识别单词的方法：（1）把单词的结构用正规式描述；（2）把正规式转换为一个NFA；（3）把NFA转换为相应的DFA；（4）基于DFA构造词法分析程序。（二）（二） 不确定的有穷自动机不确定的有穷自动机NFA 一个不确定的有穷自动机NFAM是一个五元组:：M=（K，f，S，Z），其中： K是一个有穷集，每个元素表示一个状态； 是一个有穷字母表，每个元素是一个输入字符； f是一个从K*到K上的子集的映象
14、；f：k* 2k SK，是一个非空初态集； Z K，是一个终态集。与DFA区别：多值函数f(Ki,a)=Kjf(Ki,a)=Kt；允许输入字符为例：一个NFA，M(0,1,2,3,4,a,b,f,0,2,4) 其中：f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4状态图表示如下：03412abbba,ba,ba,b说明：一个初态，二个终态。 DFA是NFA的特例。对于每个NFA M，存在一个DFA M，使得L(M)=L(M)。对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等
15、价的。 NFA转换为等价的DFA从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.定义对状态集合I的几个有关运算：1.状态集合状态集合I I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2.状态集合状态集合I I的的a a弧转换弧转换，表示为move(I,a)定义为状态集合J，其
16、中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。状态集合I的有关运算的例子I=1,-closure(I)=?；I=5,-closure(I)=?；move(1,2,a)=?-closure(5,3,4)=?；12534687aaa状态集合I的有关运算的例子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；12534687aaaNFA确定化算法:假设NFAN=(K,f,K0,Kt)按如下办法构造一个DFAM=(S,d,S0,St)，使得L(M)=L(N)：1.构造DFAM的状态，选择NFAN的状态的一些子集构成：M的状态集S由K K的的一些子集一些子集组成。用S1S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1S2；2M和N的输入字母表是相同的，即是；3构造DFAM的转换函数，根据新构造的状态和字母表中的字符构造：转换函数是这样定
