编译原理第3章课件

第三章词法分析本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。教学要求１.掌握：正规式，DFA的概念，NFA的概念２.理解：将NFA转换为DFA,正规式、正规文法与有穷自动机间的转换目录3.1词法分析程序的设计3.2单词的描述工具3.3有穷自动机3.4正规式与有穷自动机的等价性3.5正规文法和有穷自动机的等价性3.6词法分析程序的自动构造工具小结3.1.词法分析（lexicalanalysis）程序的设计回顾：1、词法分析的任务：逐个读入源程序字符并按照构词规则切分成一系列单词。2、词法分析程序：实现词法分析的程序。一.词法与语法分析程序的接口方式1、作为独立的一遍词法分析是编译过程中的一个阶段，在语法分析前进行，把字符流的源程序变为单词序列，输出在一个中间文件上。2、与语法分析结合在一起作为一遍一般、把词法分析程序设计成一个子程序，由语法分析程序调用词法分析程序来获得当前单词，供语法分析使用。词法分析程序和语法分析程序的关系词法分析程序的主要任务：读源程序，产生单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，……二、词法分析程序的输出输出是单词符号。单词是语言中具有独立意义的最小单位。单词包括：保留字标识符常量运算符界符（标点符号）词法分析程序所输出的单词符号常常采用以下二元式表示：(单词种别，单词自身的值)。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行，源程序词法分析程序Tokengettoken语法分析程序….那么可以将单词的二元式表示设计成如下形式：(标识符，指向该标识符所在符号表中位置的指针)单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5例如：程序段ifi=5thenx∶=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无符号整数运算符→+|-|*|/|等号|等号|……等号→=界符→，|；|（|）|……二．正规式（regularexpression）描述单词符号最方便的工具。正规式也称正则表达式,是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。下面是正规式和它所表示的正规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为，辅助字母表`={，，，，，，}。1和都是上的正规式，2它们所表示的正规集分别为{}和；2任何a，a是上的一个正规式，它所表示的正规集为{a}；3假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。4仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集正规式中的符号说明“读为或；“”读为“连接”；“读为闭包（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“、”、“。连接符“”一般可省略不写。“、”和“都是左结合的。例子：令={a，b}，上的正规式和相应的正规集的例子有：正规式正规集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,aa,…任意个a串}正规式:(ab)正规集:{,a,b,aa,ab……所有由a和b组成的串}正规式:(ab)(aabb)(ab)正规集:{上所有含有两个相继的a或两个相继的b组成的串}讨论下面两个例子例3.1令={l，d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……}其中：l代表字母,d代表数字；1正规式即是字母(字母|数字)；2它表示的正规集中的每个元素的模式是“字母打头的字母数字串”；3就是多数程序设计语言允许的的标识符的词法规则例3.2={d，，e，+，-},则上的正规式：d(dd)(e(+-)dd)其中d为0~9的数字。表示的是无符号数的集合。其中d为0~9的数字。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分配律r=r,r=r是“连接”的恒等元素rr=rr=r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例如：文法G[S]为：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)+|aS-a((a|d)+|ε）S-a(a|d)*对应正规式为：a(a|d)*3.3有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)。关于有穷自动机我们将讨论如下题目:确定的有穷自动机DFANFA的确定化不确定的有穷自动机NFADFA的最小化3.3.1确定的有穷自动机DFADFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表,它的每个元素称为一个输入符号,也称Σ为输入符号表；3.f是转换函数，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.S∈K是唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态或结束状态。一个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一个DFA可以表示成一个状态图(或称状态转换图)。画法为：1、假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出。2、整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”。3、若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；DFAM的状态图表示一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。DFAM的矩阵表示abSUVUQVVUQQQQ为了说明DFA如何作为一种识别机制,我们还要理解下面的定义∑*上的符号串t在DFAM上运行bSUVQaaaba，b0001一个输入符号串t，（将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFAM=（K，Σ，f，S，Z）上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K扩充转换函数f为K×Σ*→K上的映射，且：f（ki，）=ki∑*上的符号串t被DFAM接受M=（K，Σ，f，S，Z）若t∑*，f(S，t)=P，其中S为M的开始状态，PZ，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属于终态。得证。DFA的确定性表现在转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。DFA的行为很容易用程序来模拟.DFAM=（K，Σ，f，S，Z）的行为的模拟程序K:=S；c:=getchar;whileceofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)DFAM所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和ML(M)=L(M′)，则称M与M′是等价的.结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。3.3.2不确定的有穷自动机NFA定义NFAM=K，，f，S，Z，其中:K为状态的有穷非空集;为有穷输入字母表;f为K*到K的子集（2K）的一种映射;SK是初始状态集;ZK为终止状态集;例子NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中f（S，0）={P}f（Z，0）=