本章将讨论词法分析程序的设计原则,单词的描述技术,识别

《本章将讨论词法分析程序的设计原则,单词的描述技术,识别》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。3.1词法分析程序3.2正规表达式与正规集（正规语言）3.3有穷自动机3.4词法分析程序的自动构造第三章词法分析本章重点单词的描述工具单词的识别系统设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。回顾什麽是词法分析程序实现词法分析（lexicalanalysis）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识

2、符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokengettoken….词法分析程序的主要任务：读源程序，产生单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，……常常遇到的术语Token单词,词标，符号lexeme词素，词位pattern模式，式样帮助理解术语Ingeneral，thereisasetofstringsintheinputforw

3、hichthesametokenisproducedasoutput.Thissetofstringsisdescribedbyarulecalledapatternassociatedwiththetoken.Thepatternissaidtomatcheachstringintheset.Alexemeisasequenceofcharactersinthesourceprogramthatismatchedbythepatternforatoken.e.g.Constpi=3.14159；中的pi是token“identifier”的lexeme，其pattern为letter

4、followedbylettersand/ordigit.词法分析工作从语法分析工作独立出来的原因：简化设计改进编译效率增加编译系统的可移植性正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造.首先表述一些基本术语和概念.符号一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号。字母表字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。PAS

5、CAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。符号串由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表=｛0，1｝上的符号串.字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。可以使用字母表示符号串，如x=STR表示“x是由符号S、T和R，并按此顺序组成的符号串”。符号串的长度如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε

6、｜=0。介绍有关符号串的一些运算。符号串的头,尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。举个例子:设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是ε,c,bc。当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法：z=x…；如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到

7、的符号串.由于ε的含义，显然有εx=xε=x。例如x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5符号串的方幂：符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa且a0=ε例；若x=AB则:x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集