资源描述：
《西安电子科技大学《编译原理》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章词法分析词法分析：x:=y+z*60.0;id1:=id2+id3*60.0;词法的双重含义：<1>规定单词形成的规则，也被称为构词规则或词法规则。它的作用相当于立法，规定什么样的输入序列是语言所允许的合法单词。<2>根据构词规则识别输入序列，也被称为词法分析。它的作用相当于执法，根据规则识别出合法的单词和指出非法的输入序列。本章主要内容：<1>与词法分析有关的基本概念和相关问题<2>模式的形式化描述－正规式<3>记号的识别－有限自动机（NFA，DFA）<4>词法分析器的构造－从正规式到DFA<5>上机作业－第一部分：函数绘图语言的词法分析器12.1词法分析中的若干问题2.1.1记
2、号、模式与单词单词的基本分类：关键字（保留字）kw(keyword)标识符id(identifier)字面量literal特殊符号ks(keysymbol,orspecialsymbol)例2.1语句position:=initial+rate*60idksidksidksnumber注意：称识别出id而不是rate或initial问题：根据什么识别这些词法的基本单位（词法元素）？22.1.1记号、模式与单词（续1）三个术语：模式（patten）：产生和识别元素的规则记号（token）：按照某个模式（或规则）识别出的元素（一组）单词（lexeme）：被识别出的元素自身的值（一个），也称为
3、词值记号的类别单词举例模式的非形式化描述const(01)constconstif(03)ififrelation(81)<,<=,=,<>,>,>=<或<=或=id(82)pi,count,D2字母打头的字母数字串num(83)3.1416,0,6.02E23任何数值常数literal(84)“coredumped”双引号之间的任意字符串Comment{xisaninteger}括号之间的任意字符串返回32.1.2记号的属性记号是按照某个模式识别出的元素。再考察赋值句position:=initial+rate*60position、initial和rate均为标识符，即它们的种类均是
4、id。问题：当识别出一个id时，如何判定是哪个id？同样，当识别出一个relations时，究竟是=还是<？记号＝记号的类别＋记号的属性例2.2表达式mycount>25由三个记号组成类别属性828183“mycount”525记号的类别单词举例记号的非形式化描述if(03)ififrelation(81)<,<=,=,<>,>,>=<或<=或=id(82)pi,count,D2字母打头的字母数字串注意：<1>5与25的区别（根据记号的类别）<2>25与“25”的区别（如何区别？）42.1.3词法分析器的作用与工作方式特征：任务：编译器中唯一与源程序打交道的部分<1>滤掉源程序中的无用成
5、分，如注释、空格、回车等<2>处理与具体平台有关的输入（如文件结束符的不同表示等）<3>识别记号，并交给语法分析器。根据模式识别记号<4>调用符号表管理器或出错处理器，进行相关处理工作方式：<1>单独一遍扫描<2>作为语法分析器的子程序<3>并行方式52.2模式的形式化描述2.2.1字符串与语言从词法分析的角度看程序设计语言，它是由记号组成的集合。从本章开始，我们用定义的方式表示一些重要的概念，目的是希望同学们深刻理解并牢固记忆这些基本概念。由于不同的教材（或出版物）对相同的概念有不同的称谓，因此希望同学们掌握概念的实质，而不是死记几个名词术语。定义2.1语言L是有限字母表∑上有限长度字
6、符串的集合。■字母表是组成字符串的所有字符的集合。换句话说，字符串中的所有字符取自字母表。定义中强调两个有限，因为计算机的表示能力有限：<1>字母表是有限的，即字母表中元素是有限多个；<2>字符串的长度是有限的，即字符串中字符个数是有限多个。由于字符串的有序性，使得以字符串作为元素的集合，与一般意义下的集合有所不同，反映在集合运算上，强调了有序。6字符串的基本概念（表2.2）2.2.1字符串与语言（续1）表示、术语
7、S
8、εS1S2SnS的前缀XS的后缀XS的子串XS的真前缀、真后缀、真子串S的子序列X举例
9、abc
10、=3
11、ε
12、=0“abc”“def”=“abcdef”“abc”3=“abc
13、abcabc”“abc”的前缀可以是：ε，a，ab,abc“abc”的前缀可以是：ε，c，bc,abc“abc”的子串可以是：ε，a，b,c,…“abc”的真前缀可以是：a，ab？？“abdf”是“abcdef”的一个子序列（S中去掉0或若干个不一定连续的字符后形成的字符串）7字符串集合的运算（表2.3）2.2.1字符串与语言（续2）表示、术语Φ{ε}X=L∪MX=L∩MX=LMX=L*X=L+意义空集合，即元素个数为0的集合空串作
