编译原理(4).ppt

编译原理（编译原理（4）山东师范大学信息科学与工程学院山东师范大学信息科学与工程学院山东师范大学信息科学与工程学院山东师范大学信息科学与工程学院本章将讨论与词法分析程序有关的问题，包括单词的描述、识别机制及词法分析程序的自动构造原理。4.1词法分析程序的设计4.2单词的描述工具4.3有穷自动机4.4正规式与有穷自动机的等价4.5正规文法与有穷自动机的等价4.6词法分析程序的自动构造第第4章章 词词 法法 分分 析析4.1 词法分析程序的设计词法分析程序的设计4.1.1 词法分析程序与语法分析程序的接口词法分析程序与语法分析程序的接口词法分析程序读源文件，生成中间文件，语法分析程序读中间文件。词法分析程序作为语法分析的一个子程序。词法分析程序的主要任务：n读源程序，产生单词符号词法分析程序的其他任务：n滤掉空格，跳过注释、换行符n追踪换行标志，复制出错源程序，n宏展开，4.1.2词法分析程序的输出n单词串识别的单词：识别的单词：（类别，值）（类别，值）1 1 保留字保留字：如：如：BEGINBEGIN、END END、IF IF、THEN THEN等等2 2 标识符标识符：用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名3 3 常数常数：如：如：1010、2525、100100、3.123.12等整数等整数4 4 运算符运算符：如：如：+、-、*、/、：、：=、#、=、=等等5 5 界符界符：如：如：,、.、;、(、)等等单词的值？单词的值？例如：ifi=5thenx:=y经词法分析后所获得单词为：if(1,if)I(2,I在标识符表地址）=(5,=)5(3,5)Then(1,then)X(2,x在标识符表地址）:=(5,:=)y(2,y在标识符表地址）n是编译程序结构简单、清晰、条理化是编译程序结构简单、清晰、条理化n改进编译程序效率改进编译程序效率n增加编译系统的可移植性增加编译系统的可移植性（p48)4.1.3 将词法分析工作分离的考虑将词法分析工作分离的考虑4.2单词的描述工具4.2.1正规文法任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T例：l|ll|l l|d|ll|d|l|dd d|d d|d +|-|*|/|=+|-|*|/|=例例4.1 无符号数文法无符号数文法 d d|.|e d|.|e|dd e|d|d|s d dd|4.2.2 正规式正规式n正规式也称正则表达式,正规表达式。下面是正规式和它所表示的正规集的递归定义。n定义（正规式和它所表示的正规集）:设字母表为，辅助字母表=，。1.和都是上的正规式，它们所表示的正规集分别为和；2.任何a，则a是上的一个正规式，它所表示的正规集为a；3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。正规式中的符号正规式中的符号n“”读为“或”（也有使用“+”代替“”的）；n“”读为“连接”；在不致混淆时，括号可省去.n“”读为“闭包”（即，任意有限次的自重复连接）。n但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。n“”、“”和“”都是左结合的。例子4.2令=a，b，上的正规式和相应的正规集的例子有：正规式正规集aaaba,babab(ab)(ab)aa,ab,ba,bba,a,a,任意个a的串(ab),a,b,aa,ab所有由a和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串例4.3令=l，d，则上的正规式r=l(ld)定义的正规集为:l,ll,ld,ldd,其中l代表字母,d代表数字,正规式即是字母(字母|数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则.若令=d，e，+，-,则上的正规式d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为09的数字。程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义.n若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)be1=(ab),e2=(ab)n设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=r4.2.3 正规文法到正规式 正规文法-正规式1.任给上的正规式r,可构造正规文法G,使得L(G)=L(r)构造：取Vn=S,增加产生式：S r,r,注意：注意：S S为文法开始符。为文法开始符。利用下列规则展开：利用下列规则展开：若若A xy,A xy,则替换为则替换为 A xB ByA xB By 若若A xA x*y,y,则替换为则替换为 A xB|yA xB|y BxB|y BxB|y 若若A x|y,A x|y,则替换为则替换为 A x ByA x By例例4.4将将r=a(a|d)*转换成正规文法。S a(a|d)*代换为S aA A (a|d)*,重写为：S aA A (a|d)B|B (a|d)B|2.根据正规文法求出正规式根据正规文法求出正规式转换规则：转换规则：文法产生式文法产生式 正规式正规式 A xB|y A=xyA xB|y A=xy A xA|y A=x A xA|y A=x*y y A x Ay A=x|y A x Ay A=x|y 例例4.5 已给文法已给文法GS,求对应的正规式求对应的正规式S aA|aaA|aA A aAaA|dA|a|ddA|a|d 构造如下：构造如下：S=aA|a A A=aAaA|dA|a|d dA|a|d 可以变为：可以变为：A=A=（a|d)A|a|d a|d)A|a|d 有规则有规则2 2知：知：A=A=（a|d)a|d)+从而有：从而有：S=aS=a（a|d)a|d)+|a|a4.3 有穷自动机有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(DFA,DeterministicFiniteAutomata)和不确定的有穷自动机(NFA,NondeterministicFiniteAutomata)。关于关于有穷自动机我们将讨论如下题目有穷自动机我们将讨论如下题目确定的有穷自动机DFA不确定的有穷自动机NFANFA的确定化DFA的最小化4.3.1 确定的有穷自动机确定的有穷自动机DFA（1）DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；3.f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着:当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态或结束状态。（2）一个）一个DFA 的例子：的例子：DFAM=（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（3）DFA的表示nDFA的状态图表示：假定DFAM含有m个状态，n个输入字符，那么我们可以用含有m个结点，且每个结点最多有n个弧射出的有向图表示，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；DFA 的状态图表示的状态图表示bSUVQaaaba，bnDFA的矩阵表示一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。DFA 的矩阵表示的矩阵表示字符字符状态状态0001（4 4）*上的符号串上的符号串t t在在DFADFA M M上运行上运行n一个输入符号串t，（将它表示成t1tx的形式，其中t1，tx*）在DFAM=（K，f，S，Z）上运行运行的定义为：f（Q，t1tx）=f（f（Q，t1），tx）其中QKn扩充转换函数f为 K*K上的映射，且：f（ki，）=kif（Q，t1tx）=f（f（Q，t1），tx）*上的符号串上的符号串t t被被DFADFA M M接受接受M=（K，f，S，Z）若t*，f(S，t)=P，其中S为M的开始状态，PZ，Z为终态集。则称t为DFAM所接受接受（识别识别）.例例：证明证明t=baab被下图的被下图的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）=QQ属于终态。属于终态。得证。得证。bSUVQabba,baanDFAM所能接受的符号串的全体记为L(M),成为DFA所示别的语言。.n对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的.n结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。nDFA的确定性表现在转换函数f:KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。nDFA的行为很容易用程序来模拟.DFAM=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;whileceofdoK:=f(K,c);c:=getchar;ifKisinZthenreturn(yes)elsereturn(no)例：例：DFADFA =digit,not digit.2.2 不确定的有穷自动机不确定的有穷自动机NFA(1)定义NFAM=K，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2K）的一种映射，SK是初始状态集，ZK为终止状态集.（2）例子NFAM=（S，P，Z，0，1，f，S，P，Z）其中f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z状态图表示SPZ00,1111矩阵表示矩阵表示矩阵表示简化为f为K*到K的子集（2K）的一种映射再如：例再如：例4.7 p54（3）具有转移的不确定的有穷自动机123abc有如下定理有如下定理:对任何一个具有转移的不确定的有穷自动机NFAN，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。与上例等价的一个NFA.2acbb31acacbb（4）对对NFA M=K，f，S，Z 的扩展的扩展*上的符号串t在NFAM上运行.一个输入符号串t，（我们将它表示成at1的形式，其中a，t1*）在NFAM上运行运行的定义为：f（Q，at1）=f（f（Q，a），t1）其中QK.*上的符号串t被NFAM接受若t*，f(S0，t)=P，其中S0S，PZ，则称t为NFAM所接受接受（识别识别）*上的符号串上的符号串t被被NFA M接受也可以这样理解接受也可以这样理解对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFAM所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。例：00011110100011100000010001100NFAM所能接受的符号串的全体记为L(M)结论：上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。(0|1)*(000|111)(0|1)*4.3.3NFA到DFA的转换（1）讨论问题nDFA是NFA的特例.n结论：对每个NFAN一定存在一个DFA，使得L(M)=L(N)。对每个NFAN存在着与之等价的DFAM。n有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法子集法.n与某一与某一NFA等价的等价的DFA不唯一不唯一.（2）NFA确定化算法确定化算法:假设NFAN=(K,f,K0,Kt)按如下办法构造一个DFAM=(S,d,S0,St)，使得L(M)=L(N)：1.M的状态集S由K K的一些子集的一些子集组成。用S1S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1S2；2M和N的输入字母表是相同的，即是；3转换函数是这样定义的：d(S1S2,.Sj,a)=R1R2.Rt其中R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4S0=-closure(K0)为M的开始状态；5St=SiSk.Se，其中SiSk.SeS且Si,Sk,.SeKt（3）定义对状态集合）定义对状态集合I的几个有关运算：的几个有关运算：1.状态集合状态集合I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2.状态集合状态集合I的的a弧转换，弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。（4）状态集合）状态集合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；12534687aaa（5）构造NFAN的状态状态K K的子集的子集的算法：假定所构造的子集族为C，即C=(T1,T2,.TI),其中T1,T2,.TI为状态K的子集。1开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。2while（C中存在尚未被标记的子集T）do标记T；for每个输入字母adoU:=-closure(move(T,a)；ifU不在C中then将U作为未标记的子集加在C中（6）NFA的确定化的确定化例子例4f35621iaaaabbbb4f35621iaaaabbbb 等价的等价的DFAaCDBAEFSbaaaaabbbbbabF例例4.8（p55图图4.4）4.3.4 确定有穷自动机的化简确定有穷自动机的化简一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。(1)DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t可区别：不满足兼容性同是终态或同是非终态传播性从s出发读入某个aa和从t出发读入某个a到达的状态等价。(改为：任意符号串w,f(s,w)Z当且切仅当f(s,w)Z)C和D同是终态,读入a到达C和F,C和F同是终态,C和F读入a都到达C,读入b都到达E.C和D等价aCDBAEFSbaaaaabbbbbabF(2)最小状态最小状态DFA对于一个DFA M=（K,f,k0,kt)，存在一个最小状态DFAM=（K,f,k0,kt)，,使L(M)=L(M).结论接受L的最小状态有穷自动机不计同构是唯一的。(3)“分割法分割法”nDFA的最小化算法的核心把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.n算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.DFA的最小化算法的最小化算法 DFA M=（K,f,k0,kt),最小状态DFAM 1.构造状态的一初始划分：终态kt 和非终态K-两组(group)2.对施用过程过程PPPP 构造新划分new 3.如new =,则令 final=并继续步骤4，否则:=new重复2.4.为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r M 的开始状态是含有S0的那组的代表，M 的终态是含有F的那组的代表 5.去掉M中的死状态.过程过程PP:Construction of newFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a,states s and t have transitions on to states in the same group of;/*at worst,a state will be in a subgroup by itself*/2.replace G in new by the set of all subgroups formed end DFA的最小化的最小化例子例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2:CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaa再如：再如：p58例例4.9(自己做）自己做）4.4有穷自动机和正规表达式的等价性有穷自动机和正规表达式的等价性1.对于上的一个NFAM，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFAM，使的L(M)=L(R)。1.对于上的一个NFAM,构造正规式R，使得L(M)=L(R)的方法。第一步：增加两个状态X,Y,构造相应的弧 第二步：利用下列规则，逐步消去中间第二步：利用下列规则，逐步消去中间节点，最终只剩下节点，最终只剩下X,Y，节点节点X到到Y弧上弧上的标记即为所求得正规式的标记即为所求得正规式R。例例4.10 p592.“对于上的一个正规式R,可以构造一个上的NFAM，使得L(M)=L(R).”(1)R=,构造构造任一具有空终态集的NFAM(2）R=，构造的NFAM=(k0,f,k0,k0):f（k0,a)对于所有a都没定义。(3）R=a,构造构造的NFA M=(k0,k1,f,k0,k1):f(k0,a)=k1(4)R=R1|R2,将步骤（1）（2）（3）分别应用到R1,R2产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造构造NFA M=(K1K2k,f,k,F):k是新增加的状态符号，f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a).若k1F1且k2F2则F=F1F2，否则F=F1F2k(5)R=R1.R2 将步骤（将步骤（1）（）（2）（）（3）分别应用到）分别应用到R1,R2 产生产生M1=(K1,f1,k1,F1),f1,k1,F1),M2=(K2,f2,k2,F2),f2,k2,F2),其中其中K1,K2K1,K2不相交不相交.构造构造的的NFA M=NFA M=(K1 K2,f,k,f,k1 1,F,F2 2):):f f包含包含f1f1和和f2,f2,且且f(k,a)=f1(k,a),f(k,a)=f1(k,a),当当 k K1 时时;f(k,a)=f2(k,a),f(k,a)=f2(k,a),当当 k K2时时;并且并且当当k F1时，时，f(k,f(k,)=k2,)=k2,(6)R=R1*将步骤（将步骤（1）（）（2）（）（3）分别应用到）分别应用到R1,产生产生M1=(K1,f1,k1,F1),f1,k1,F1),构造构造的的NFA M=NFA M=(K1 k0,，F F0,f,k,f,k0 0,F,F0 0)其中其中 k0，,F F0 是新增加的两个状态是新增加的两个状态,f(k,a)=f1(k,a),f(k,a)=f1(k,a),当当 k K1时时;f(f(k0,)=f()=f(F1F1,)=)=k1,F F0,再用状态图说明可用方法再用状态图说明可用方法对于正规式x,x构造的NFA（两种）X对于正规式对于正规式 ,构造的构造的NFA（三种）三种）FSF对于正规式对于正规式R=,构造的构造的NFAFS对于正规式对于正规式r,r=R1|R2构造的构造的NFA对于正规式对于正规式r,r=R1 R2构造的构造的NFA对于正规式对于正规式r,r=R1*构造的构造的NFA例：R=(a|ab)*bb*4.5 正规文法和有限状态自动机的转换正规文法和有限状态自动机的转换1.已给正规文法已给正规文法G=(Vn,Vt,P,S),可够早已可够早已NFA M,使得使得L(M)=L(G)构造：设构造：设M=(K,f,S,Z),其中=Vt,K=Vn Z Z P定义如下：若AtBAtB，其中其中tVtVT T或或t t为为，则由状态A到状态B有一边，其标记为t.若AtAt，其中其中tVtVT T或或t t为为，则由状态A到状态Z有一边，其标记为t.例例4.12（讲（讲,p62)2.将将NFA转换为转换为3型文法（型文法（p63)例例4.134.6词法分析程序的自动构造工具正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序识别识别Pascal单词的单词的FANFA的确定化的确定化 More example