第四章词法分析.

1盛威网：专业的计算机学习网站指导教师:杨建国二零零七年十一月2盛威网：专业的计算机学习网站词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序。理论基础：有穷自动机理论有穷自动机理论与正规文法、正规式之间在描述语言方面有一一对应的关系。第4章词法分析3盛威网：专业的计算机学习网站1.本章介绍编译第一个阶段词法分析的设计原理和设计方法，要求明确此阶段的任务。2.理解通常的单词分类和构词规则。3.会使用单词的描述和识别机制。4.要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。5.掌握词法分析程序的手工实现方法。学习目标4盛威网：专业的计算机学习网站第一节词法分析程序的设计第二节单词的描述工具第三节有穷自动机第四节正规式和有穷自动机的等价性第五节正规文法和有穷自动机的等价性教学内容5盛威网：专业的计算机学习网站知识结构6盛威网：专业的计算机学习网站词法分析自动构造工具{正规集}正规式有穷自动机（NFADFA)正规文法知识结构①⑤⑥②③④7盛威网：专业的计算机学习网站§4.1词法分析程序的设计词法分析的任务主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序宏展开，……8盛威网：专业的计算机学习网站4.1.1词法分析程序与语法分析程序的接口方式1.把词法分析工作单独作为一趟词法分析是主程序输入流是用高级语言编写的由字符组成的源程序，输出流是由属性字组成的与源程序等价的程序。字符单词源程序词法分析L1程序符号表9盛威网：专业的计算机学习网站2.把词法分析工作作为子程序每当语法分析器需要一个单词符号时就调用词法分析子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号交给语法分析器。回送单词语法分析是主程序源程序词法分析符号表字符单词语法分析10盛威网：专业的计算机学习网站4.1.2词法分析程序的输出输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。一.词法分析程序的功能11盛威网：专业的计算机学习网站（1）关键字：if、for、while（2）标识符：（3）常数：100、3.14159、TRUE、’sample’（4）运算符：（5）分界符：,、;、(、)二.单词的种类具有固定意义的标识符，称为保留字或基本字。通常不用作一般标识符。表示各种名字，如变量名、数组名、过程名……其类型一般有整型、实型、布尔、文字等分为算术运算符（如：＋、－、*、/等），逻辑运算符（如：not、and、or），关系运算符（如：、、=、=、=）等。12盛威网：专业的计算机学习网站三.输出表示-----单词的内部形式词法分析程序的输出形式-----二元式单词种别单词自身的值单词种别：语法分析需要的信息单词自身的值：编译其他阶段需要的信息13盛威网：专业的计算机学习网站单词种别通常用整数编码，如何分种，怎样编码，取决于处理的方便性。标识符一般统归一种常数按类关键字：全体为一种或一字一种运算符：一符一种，或具有共性的为一种界符：一符一种14盛威网：专业的计算机学习网站Sample语言的单词编码15盛威网：专业的计算机学习网站例1.对于if（a=b2）test:=3+a*16.0关键字if（9,‘if’）左括号（（48，’(’）标识符a（36，’a’）等号=（34，’=’）标识符b2（36，’b2’）右括号）（49，’）’）标识符test（36，’test’）赋值号:=（35，’:=’）整常数3（37，’3’）加号+（26，’+’）标识符a（36，’a’）乘号*（28，’*’）实常数16.0（38，’16.0’）16盛威网：专业的计算机学习网站对一符一种，可不需属性，但多符一种时必须要有属性信息，属性反映单词符号的特性或特征，而属性值反映特性或特征的值。例如,对于标识符用它在符号表的入口指针作为它自身值;常数用它在常数表的入口指针作为它自身的值。17盛威网：专业的计算机学习网站例2.intx=10,y=20,sum;词法分析的结果：单词种别单词自身的值int3指向x的符号表入口指针36=341037,42指向y的符号表入口指针36=342037,42指向sum的符号表入口指针36;4118盛威网：专业的计算机学习网站4.1.3将词法分析工作分离的考虑词法分析工作独立的原因：简化设计：词法分析比语法分析简单，如果与语法分析一起，会导致程序结构复杂。改进编译效率：编译的大部分时间花在扫描字符区分单词上，专门的词法分析可加快编译速度。增加编译系统的可移植性。19盛威网：专业的计算机学习网站§4.2单词的描述工具作用:描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造.工具有:正规文法(RegularGrammar)正规式(RegularExpression)20盛威网：专业的计算机学习网站4.2.1正规文法（Chomsky3型文法）正规文法是描述正规集的文法，可用于描述程序设计语言的语法部分。例如：标识符这种单词可以用下面的规则描述。标识符字母|标识符(字母|数字)字母表示任意英文字母，数字表示任意数字正规文法回顾文法的任一产生式α→β的形式为左线性或者右线性。21盛威网：专业的计算机学习网站例3描述无符号数的正规文法：无符号数d余留无符号数|.十进小数e指数部分余留无符号数d余留无符号数|.十进小数|e指数部分|十进小数d余留十进小数余留十进小数e指数部分|d余留十进小数|指数部分d余留整指数|s整指数整指数d余留整指数余留整指数d余留整指数|其中，s表示正或负号(+,-)，d表示0～9中任意数字22盛威网：专业的计算机学习网站正则表达式萌芽于20世纪40年代的神经生理学研究，由著名数学家StephenKleene第一个正式描述。在一篇题为《正则集代数》的论文中定义了“正则集”，并在其上定义了一个代数系统，并且引入了一种记号系统来描述正则集，这种记号系统被他称为“正则表达式”。4.2.2正规式（regularexpression）历史1968年，后来发明了UNIX系统的KenThompson第一个把正则表达式用于计算机领域。1986年，C语言顶级黑客HenrySpencer以源代码形式发布了一个用C语言写成的正则表达式程序库技术怪杰LarryWall横空出世，发布了Perl语言的第一个版本。今天正则表达式的标准和地位是由Perl塑造的。23盛威网：专业的计算机学习网站设A是非空的有限字母表，A={ai|i=1,2,……n},则1.，和ai(i=1,2,……n)都是正规式；2.若、是正规式，则|、•、*、*也是正规式；3.正规式只能通过有限次使用1，2规则获得。注：1)“|”读作为“或”，也可写作为“+”或“,”;“•”读作连接。2)仅由字母表A={ai|i=1,2,……n}上的正规式所组成的语言称作正规集，记作L()。3)利用正规集相同，可用来证明相应正规式等价。一.正规式定义24盛威网：专业的计算机学习网站二.运算的优先和括号的使用前面的内容忽略了选择、连结和重复运算的优先问题。例如对于正则表达式a|b*，是将它解释为(a|b)*还是a|(b*)呢?L((a|b)*)={ε,a,b,aa,ab,ba,bb,...}L(a|(b*))={ε,a,b,bb,bbb,...}标准惯例是重复的优先权较高，所以第2个解释是正确的。实际上，在这3个运算中，*优先权最高，连结·其次，选择︱最末。因此，a|bc*就可解释为a|(b(c*))，而ab|c*d却解释为(ab)|((c*)d)。需指出与默认不同的优先顺序时，就必须使用括号。√25盛威网：专业的计算机学习网站三.正规集定义有字母表,定义在上的正规式和正规集递归定义如下:1．和都是上的正规式，它们所表示的正规集分别为:{}和Φ;2．任何a，a是上的正规式，它所表示的正规集为:{a}；3．假定U和V是上的正规式,它们所表示的正规集分别记为L(U)和L(V)，那么U|V，U•V和U*也都是上的正规式，它们所表示的正规集分别为L(U)L(V)、L(U)•L(V)和L(U)*4．任何上的正规式和正规集均由1、2和3产生。26盛威网：专业的计算机学习网站例4令={a，b}，上的正规式和相应的正规集的例子有：正规式正规集a{a}ab{a,b}ab{ab}ba*{ε,ba,baa,……}（所有以b开头后跟任意多个a的串）(ab)(ab){aa,ab,ba,bb}a{,a,a,……}(任意个a的串)(ab){,a,b,aa,ab……}(所有由a和b组成的串)(ab)(aabb)(ab){上所有含有两个相继的a或两个相继的b组成的串}27盛威网：专业的计算机学习网站例5={d，，e，+，-},则上的正规式d(dd)(e(+-)dd)其中d为0-9的数字表示的是：无符号数的集合。例6令={A,B,0,1}，则正规式正规集(A|B)(A|B|0|1)*上标识符全体(0|1)(0|1)*上数的全体28盛威网：专业的计算机学习网站例7设Σ={a,b,c},则aa*bb*cc*是∑上的一个正规式,它所表示的正规集：={ambnck|m,n,k≥1}a+b+c+L={abc,aabc,abbc,abcc,aaabc,…}总结：正规式是词法规则的描述工具正规集是被描述的词法类29盛威网：专业的计算机学习网站练习1.为下边所描述的串写正规式，∑={a,b}。a)以ab结尾的所有串b)包含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串(a|b)*ab(bb)*(a*ba*ba*)*b*ab*(a|b)*ab(a|b)*b*a*30盛威网：专业的计算机学习网站2.请描述下面正规式定义的串.∑={0,1}。a)0*(100*)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0[答案]a)每个1至少有一个0跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和0结尾的串31盛威网：专业的计算机学习网站两正规式等价两正规式表示的语言相等例8判断下述正规式之间是否等价：(a∣b)*与a*∣b*•(a∣b)*对应的正规集其a、b可任意交替出现，如abbaaaba…；而(a*∣b*)对应的正规集只可出现任意个a或者任意个b；因此两者不等价。32盛威网：专业的计算机学习网站(ab)*与a*b*•(ab)*对应的正规集是以任意个ab对出现的，即ababab…；而a*b*对应的正规集则是先出现任意个a后接任意个b，即a…ab…b；因此两者不等价。33盛威网：专业的计算机学习网站(a∣b)*与(a*b*)*•由于(a∣b)*对应的正规集为a、b可任意交替出现，L((a∣b)*)={ε,a,b,aa,ab,ba,bb,…}L((a*b*)*)=(a*b*)0∪(a*b*)1∪(a*b*)2∪…={ε,a,b,aa,ab,ba,bb,…}因此，(a∣b)*和(a*b*)*等价。34盛威网：专业的计算机学习网站四.正规式的性质零一律:e=e=e交换律:e1|e2=e2|e1结合律:e1|(e2|e3)=(e1|e2)|e3e1(e2e3)=(e1e2)e3设r,s和t均是某字母表上的正规式,则有:分配律:e1(e2|e3)=e1e2|e1e3(e1|e2)e3=e1e3|e2e3抽取律：r|r=r此外:r*=(r|)*（r*）*=r*(r|s)*=(r*s*)*35盛威网：专业的计算机学习网站五.正规式的应用-产品结构建模在产品结构建模中,正规式适合用来反映产品的结