编译原理 第3章课件

第三章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。教学要求.掌握：正规式，DFA的概念，NFA的概念.理解：将 NFA转换为DFA ,正规式、正规文法与有穷自动机间的转换目录3.1 词法分析程序的设计3.2 单词的描述工具3.3 有穷自动机3.4 正规式与有穷自动机的等价性3.5 正规文法和有穷自动机的等价性3.6 词法分析程序的自动构造工具小结3.1.词法分析（lexical analysis） 程序的设计回顾： 1、词法分析的任务：逐个读入源程序字符并按照构词规则切分成一系列单词。2、词法分析程序：实现词法分析的程序。一.词法与语法分析程序的接口方式1、作为独立的一遍 词法分析是编译过程中的一个阶段，在语法分析前进行，把字符流的源程序变为单词序列，输出在一个中间文件上。2、与语法分析结合在一起作为一遍 一般、把词法分析程序设计成一个子程序，由语法分析程序调用词法分析程序来获得当前单词，供语法分析使用。.Token词法分析程序源程序词法分析程序和语法分析程序的关系语法分析程序get token词法分析程序的主要任务：读源程序，产生单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序，宏展开，二、词法分析程序的输出输出是单词符号。单词是语言中具有独立意义的最小单位。单词包括： 保留字 标识符 常量 运算符 界符（标点符号）词法分析程序所输出的单词符号常常采用以下二元式表示：(单词种别，单 词自身的值)。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要 的信息。对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行， 那么可以将单词的二元式表示设计成如下形式：(标识符，指向该标识符所在符号表中位置的指针)单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为 3，运算符为4，界符为5例如：程序段 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，；) 三、词法分析工作从语法分析工作独立出来的原因：简化设计 改进编译效率 增加编译系统的可移植性 3.2 单词的描述工具程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造.描述工具：正规文法和正规式识别工具：有穷自动机一正规文法 多数程序设计语言的单词的语法能用正规文法来描述。正规文法所描述的是VT* 上的正规集。几类单词的规则如下： l|l l|d|l|d d|d +|-|*|/| = ，|；|（|）|二正规式（regular expression）描述单词符号最方便的工具。正规式也称正则表达式,是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。下面是正规式和它所表示的正规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为S，辅助字母表S=F，e，?，*，(，)。1e和F都是S上的正规式，2它们所表示的正规集分别为e和F ； 2 任何a? S，a是S上的一个正规式，它所表示的正规集为a；3 假定e1和e2都是S上的正规式，它们所 表示的正规集分别为L(e1)和L(e2)， 那么，(e1), e1? e2, e1?e2, e1*也都是正规式,它们所表示的正规集分别为L(e1), L(e1)*L(e2), L(e1)L(e2)和(L(e1)*。4 仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式所表示的集合才是S上的正规集正规式中的符号说明“”读为“或” ； “ ”读为“连接”；“*”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“*”、“ ”、“” 。连接符“ ”一般可省略不写。 “*”、“ ”和“” 都是左结合的。例子：令S=a，b， S上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(ab)aa,ab,ba,bba * e ,a,aa,任意个a串正规式:(ab)*正规集: e ,a,b,aa,ab 所有由a和b组成的串正规式:(ab)* (aabb)(ab)* 正规集:S*上所有含有两个相继的a或两个相继的b组成的串 讨论下面两个例子例3.1 令S=l，d，则S上的正规式 r=l(l d) *定义的正规集为: l,ll,ld,ldd, 其中：l代表字母,d代表数字；1 正规式即是字母(字母|数字) * ；2 它表示的正规集中的每个元素的模式是“字母打头的字母数字串”；3 就是多数程序设计语言允许的的标识符的词法规则例3.2S=d，e，+，-,则S上的正规式 ：d*(*dd *? e )(e(+?- e?)dd* e?)其中d为09的数字。 表示的是无符号数的集合。其中d为09的数字。2，22.34,3.2e2,23.8e-3等都是其正规集中的元素。 程序设计语言的单词都能用正规式来定义若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如： e1= (a?b)， e2 = b?a又如： e1= b(ab)* , e2 =(ba)*b再如： e1= (a?b)* , e2 =(a*?b*)*设r,s,t为正规式，正规式服从的代数规律有：r?s=s?r “或”服从交换律r?(s?t)=(r?s)?t “或”的可结合律 (rs)t=r(st) “连接”的可结合律 r(s?t)=rs?rt (s?t)r=sr?tr 分配律er=r, re=r e是“连接”的恒等元素 r?r=rr*=?er?rr? “或”的抽取律 正规文法和正规式一个正规语言可以由正规文法定义，也可以由正规式定义。1、将上的正规式r转换成正规文法G =（VN,VT,P,S）。VT = 对任何正规式r，选择一个非终结符S生成产生式S-r,将S为G的识别符号。若x和y都是正规式， 对A-xy,重写成：A-xB, B-y; 对形如A-x|y,重写成： A-x,A-y; 对形如A-x* y,重写成： A-xB, A-y, B- xB, B-y;不断使用如上规则，直到每个产生式最多含有一个终结符为止。例如：将R=a(a|d) *转换成正规文法S- a(a|d) * 将S是文法的识别符号。根据规则1形成S-aA,A- (a|d) *根据规则3，对第二条重写成A-(a|d)B, A-,B-(a|d)B,B-最后得出正规文法为S-aA,A-aB, A-dB, A-, B-aB, B-dB, B-2、正规文法转换成正规式使用如下规则，最后只剩下一个开始符号定义的产生式，并且右部不含非终结符。规则1 ：A- xB,B-y = A - xy规则2： A-xA|y = A - x * y规则3： A-x, A-y = A - x|y例如：文法GS为：S-aA, S-a, A- aA, A-dA, A-a, A-dS- aA|aA= (aA| dA)|(a|d) =A=(a|d)A|(a|d) =A=(a|d) * (a|d)=(a|d) + A带入S得： S- a (a|d) + |a S- a (a|d) +|） S- a (a|d) *对应正规式为：a (a|d) * 3.3 有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。关于有穷自动机我们将讨论如下题目:确定的有穷自动机DFA NFA的确定化不确定的有穷自动机NFA DFA的最小化3.3.1确定的有穷自动机DFADFA定义：一个确定的有穷自动机（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 .Z K是一个终态集，终态也称可接受状态或结束状态。一个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可以表示成一个状态图(或称状态转换图)。画法为： 1、假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出。 2、整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”。 3、若 f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；bSUVQaaaba，b DFA M 的状态图表示一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。0001DFA M 的矩阵表示为了说明DFA如何作为一种识别机制,我们还要理解下面的定义*上的符号串t在DFA M上运行一个输入符号串t，（将它表示成Tt1的形式，其中T，t1 *）在DFA M=（K，f，S，Z）上运行的定义为：f（Q， Tt1）=f（f（Q，T），t1） 其中QK 扩充转换函数f为 K*K上的映射，且： f（ki，e）= ki*上的符号串t被DFA M接受 M=（K，f，S，Z）若t *，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集。则称t为DFA M所接受（识别）.例：证明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属于终态。得证。DFA的确定性表现在转换函数f:KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。DFA的行为很容易用程序来模拟.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)DFA M所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的.结论： 上一个符号串集V*是正规的，当且仅当存在一个上的确定有穷自动机M，使得 V=L(M)。3.3.2 不确定的有穷自动机NFA定义 NFA M=K，f，S，Z，其中:K为状态的有穷非空集; 为有穷输入字母表;f为K * 到K的子集（2 K）的一种映射;S K是初始状态集;Z K为终止状态集;例子 NFA M=（S，P，Z，0，1，f，S，P，Z）SPZ00,1111状态图表示其中 f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z简化为矩阵表示、 0 1SPSZ 0 PZ 0 Z PP 1 0 1 S P S、Z 0P . Z 0 Z P P 1 类似DFA, 对NFA M=K，f，S，Z也有如下定义*上的符号串t在NFA M上运行一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1 *）在NFA M上运行的定义为：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符号串t被NFA M接受若t? *，f(S0，t)=P，其中S0 S，P ? Z，则称t为NFA M所接受（识别）*上的符号串t被NFA M接受也可以这样理解对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空串可为M所接受。00011110100011100000010001100 NFA M所能接受的符号串的全体记为 L(M).结论： 上一个符号串集V*是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。 (0|1)*(000|111)(0|1)* 3.3.3 NFA-DFA的转换DFA是NFA的特例 对每个NFA N一定存在一个DFA ，使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法.与某一NFA等价的DFA不唯一. 从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.定义对状态集合I的几个有关运算：1状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。 其中: 状态集合I的任何状态S都属于 -closure(I)。2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。12534687aaeeeeea状态集合I的有关运算的例子I=1, e-closure(I)=1,2;I=5, e-closure(I)=5,6,2;move(1,2,a)=5,3,4:e-closure(5,3,4)=2,3,4,5,6,7,8;NFA确定化算法: 假设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)= R1R2. Rt其中: R1,R2,. , Rt = e-closure(move(S1, S2,. Sj,a) 4 S0=e-closure(K0)为M的开始状态；5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKtF构造NFA N的状态K的子集的算法：假定所构造的子集族为C，即C= (T1, T2,. TI),其中T1, T2,. TI为状态K的子集。1 开始，令e-closure(K0)为C中唯一成员，并且它是未被标记的。2 while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= e-closure(move(T,a)；4f35621ieeeeaaaabbbb if U不在C中 then 将U作为未标记的子集加在C中 NFA的确定化 例子 Ia IbI,1,2 S 1,2,3 A1,2,4 B 1,2,3 A 1,2,3,5,6,f C 1,2,4 B 1,2,4 B 1,2,3 A 1,2,4,5,6,f D 1,2,3,5,6,f C 1,2,3,5,6,f C 1,2,4,6,f E 1,2,4,5,6,f D 1,2,3,6,f F1,2,4,5,6,f D 1,2,4,6,f E 1,2,3,6,f F 1,2,4,5,6,f D 1,2,3,6,f F 1,2,3,5,6,f C 1,2,4,6,f E 等价的DFA aCDBAEFSbaaaaabbbbbab3.3.4确定有穷自动机的化简 说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:1.没有多余状态(死状态)2.没有两个状态是互相等价（不可区别）所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。 两个状态s和t等价：满足一致性条件(兼容性)同是终态或同是非终态S和C等价吗？C和D等价吗？蔓延性条件（传播性）从s出发读入某个a(a)?和从t出发读入某个a到达的状态等价。 上图中 S和C不等价，因为C是终态，而S不是终态； C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E.C和F等价；同样D和E也等价；可以推出C和D等价；“分割法”DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.从前面例子可知C、D、E、F等价！ DFA的最小化例子1.将M的状态分成非终态和终态集 见上图DBASaaabbbbS,A,B C,D,E,F2 .寻找子集中不等价状态 S,A,B C,D,E,F A S，B b S B 3. P=S,A,B,D 3.4 正规式和有穷自动机的等价性 对有穷自动机和正规表达式进行了上述讨论之后,我们介绍有穷自动机和正规表达式的等价性,即： 1.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。一.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。我们把状态转换图的概念拓广，令每一条弧可用一个正规式作标记。第一步，在M的状态转换图上加进两个结点，一个为X结点,一个为Y结点，从X结点用e弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y结点，形成一个与M等价的M, M只有一个初态和一个终态.第二步，逐步消去M中的所有结点，直至只剩下X 和Y结点13R1R2其消结规则如下:123R1R2 对于 代之为12R1|R2R112R2对于 代之为13R1R2* R3123R1R2R3 对于 代之为最后X和Y结点间的弧上的标记则为所求的正规式。BC0,110A例：0,1XBC10eeAYYXe0,1A10XY(0|1)*10二.从上的一个正规式R构造上的一个NFA M，使得L(M)=L(R)的方法。下面介绍的方法称为“语法制导”的方法,首先将正规式分解成一系列子表达式,然后使用如下规则为R构造NFA，对R的各种规则具体描述如下：对于正规式e ,构造的NFA 对于正规式R= ,构造的NFAeSSFFX对于正规式x,x ?构造的NFA 对于正规式r, r= R1|R2构造的NFA 对于正规式r, r=R1R2构造的NFA对于正规式r, r=R1*构造的NFAR= (a|b)* 构造为NFA N 还可采用另外的分解方式构造NFA:解：从左到右分解R， R= (a|b)*ab 构造为NFA Nxy(a|b)*abi32a令r1=a,则有 a|byxie iabe54b令r2=b,则有 令r3=a|b,则有 axibey ei bi a32a54b16eeee令r4=(a|b)*,则有 32a54ae2ee01eeb160eeeee7eee将R=(a|ab)* b b*构造为NFA N3.5 正规文法和有穷自动机间的转换1、从正规文法构造NFA M字母表与G的终结符集相同。为G的每个非终结符生成M的一个状态，G的开始符号S是初态。增加一个新状态Z，作为NFA的终态。对G中的形如A-tB的产生式, 其中t为终结符或e，A和B为非终结符，构造M的一个转换函数f(A,t)=B;对G中的形如A-t的产生式,构造M的一个转换函数f(A,t)=Z;ASaaaebbbBZe例如：求文法GS等价的NFA MGS：S-aA S-bB S- e A- aB A- bA B- aS B- bA B- e2、NFA M 转换成正规文法的规则有穷自动机的初态对应文法的开始符号。有穷自动机的字母表为文法的终结符集。对转换函数f(A,t)=B，可写一个产生式A-tB。对可接受状态Z，增加一个产生式Z- eBAaababbDbC例如：给出与下图NFA等价的正规文法GA：A-aB A-bDB-bCC-aA C-bD C- eD-aB D-bD D- e 3.6 词法分析程序的自动构造工具 正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序，LEX是一个广泛使用的工具。 词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作。 词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。 本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。 本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。实验一 使用自己熟悉的语言（C+），结合简单语言的语法编写一个简单的词法分析程序 词法分析程序对给定一个源程序(如C语言的)能够输出单词序列表。 要求输入和输出都通过文件处理。练习 1、将a和b分别进行确定化和最小化2、题：构造正规式1(0|1)*101相应的DFA.DFA XABCY10,1101解：1)2)确定化 ：3)重新命名，令AB为B、AC为C、ABY为DBCDDACBCBBAAAX10ABACABYABYAACABACABABAAAX10