搜索
词法分析(1)---词法分析的有关概念以及转换图词法分析是编译的第一个阶段，前面简介中也谈到过词法分析器的任务就是：字符流------词法记号流这里词法分析和语法分析会交错进行，也就是说，词法分析器不会读取所有的词法记号再使用语法分析器来处理，通常情况下，每取一个词法记号，就送入语法分析器进行分析，图解：词法分析器是编译器中与源程序直接接触的部分，因此词法分析器可以做诸如1).去掉注释，自动生成文档(c#中的///注释)2).提供错误位置(可以通过记录行号来提供)，当字符流变成词法记号流以后，就没有了行的概念3).完成预处理，比如宏定义1.词法记号，词法单元(lexeme)，模式模式是一种规则每个词法单元都有一个特定记号比如inta=3，这里int，a，＝，3都是词法单元，每个词法单元都属于某个词法记号，比如3就是num这个词法记号的一个词法单元，而模式规定了什么样的字符串的词法记号是什么样的(模式是一种规则)某一特定模式规定了某个词法记号下的一类词法单元，比如：模式：用字母开头的包含字母和数字的串上面模式的词法记号：id(所有符合上面模式的字符串的记号都是id)词法单元：a123或者aabc等词法记号举例(简称为记号)：1)每个的关键字都有属于自己的一个记号，比如关键字for，它可以使用记号for；关键字int，可以使用记号int2)所有的关系运算符只有一个记号，比如=,=都用记号relation3)所有的标识符只有一个记号，比如a123,aab使用记号id4)所有的常数只有一个记号，比如123,22,32.3,23E10使用记号num5)所有的字符串只有一个记号，比如123,ab1使用记号literal在实际的编译器设计中，词法记号，一般用一个整形数字表示词法记号的属性：我们喜欢用词法记号,属性这个二元组来描述一个词法单元，比如，对于源代码：position:=initial+rate*60对于词法单元+，我们可以使用add_op,'+'来表示。有些情况，更加复杂一点，比如对于position，我们表示是这样的，id,指向符号表中的position元素的指针，详细来说应该是这样的，假定属性是一个字符串，那么id将指向这样一个字符串position\0，我们把存放这个字符串的地方叫做符号表。有些时候，属性是不必要的，比如:=，表示赋值，我们可以使用assign_op,257这样的表示这个词法单元，不过这个显得有些多于，因为assign_op和词法单元是一对一的，也就是assign_op只对应了:=，所以额外信息(属性)就显得多余的了词法错误：词法分析器是很难(有些错误还是可以检测)检测错误的，因为词法分析器的目的是产生词法记号流，它没有能力去分析程序结构，因此无法检测到和程序结构有关的错误，比如：fi(a==b)词法分析器不会找到这个错误，它认为fi是一个标识符，而不是一个关键字，只有在后面的阶段中，这个错误才会被发现，这是一个与程序结构有关的错误词法分析器，只能检测到词法单元上的问题，比如12.ab，作为一个词法单元，却不没有对应的模式，那么就是产生一个错误。2.正规式：前面说过模式是一种规则，为了使用，我们需要一种规范的方式来表达模式，这就是正规式1)串和语言字符类(又叫字母表)：关于字符的有限集合串：字符类上字符的有穷序列，串这个概念，具体来说是，某个字符类上的串串的长度：串中字符的个数，比如串s=abc，那么串的长度为3，用|s|表示串的长度空串：用ε表示语言：某字符类上的串的集合，属于语言的串，成为语言的句子或字比如：{abc,a}这就是一个语言，abc和a就是句子。另外空集也是属于语言连接：x是串，y是串，x和y连接，结果就是xy这个串。假如x是串，x^3为xxx。对于x^n(n=0),x^0=ε语言的运算(假定L和M是语言)：1.LUM={s|s属于L或者M}，例如：L={1,2}M={3,4}那么LUM={1,2,3,4}2.LM={st|s属于L且t属于M}，例如：L={a,b}M={1,2}那么LM={a1,a2,b1,b2}ML={1a,1b,2a,2b}3.L^n=LLL...LLL(n个L)，例如：L={a,b}那么L^3={aaa,aab,aba,abb,baa,bab,bbb,bba}注意n可以为0，L^0={ε}4.L*=L^0UL^1UL^2UL^3U...L*表示，语言L中，所有的句子(串)以任意数目任意顺序组成的句子的集合，包括ε，例如：{a,b}*={ε,a,b,ab,ba,aab,aba,baa,bba,bab,abb,aaa,bbb...}L*叫做L的闭包5.L+=L^1UL^2UL^3U...L+表示，语言L中，所有的句子(串)以任意数目任意顺序组成的句子的集合，但是不包括εL+中的句子和L*中的句子相比少一个ε那么，我们通过上面的知识就可以表示一个标识符了，我们知道一般语言规定标识符是由字母开头，后接若干个字母或数字，我们可以这样来表示：L={a-zA-Z}N={0-9}，那么标识符就是L(LUN)*2)正规式正规式又叫正规表达式，正规式是模式得一种规范的表达形式，正规式描述了一个集合，这个集合是由串组成的，其实这个集合就是我们前面说过的语言，不过这里大家喜欢使用正规集这个术语。正规式r表示正规集L(r)正规式的运算：1.闭包运算，运算优先级最高，(r)*表示(L(r))*2.连接运算，运算优先集合低于闭包，(r)(s)表示(L(r))(L(s))3.或运算，运算优先集合最低，(r)|(s)表示(L(r))U(L(s))例如：a|b表示集合(语言，正规集){a,b}(a|b)(a|b)表示集合(语言，正规集){aa,ab,ba,bb}a*表示由一切a字符组成的集合(语言，正规集)，包括ε(a|b)表示由a,b组成的集合(语言，正规集)，包括ε等价的正规式：(a|b)=(b|a)正规式的代数性质：1.r|s=s|r2.r|(s|t)=(r|s)|t3.(rs)t=r(st)4.r(s|t)=rs|rt5.εr=r6.r**=r*7.r*=(r|ε)*注意，rs!=sr因为连接运算是有顺序的，记住并理解2个最基本的运算：a|b表示{a,b}，ab表示{ab}3.正规定义我们可以使用名字-正规式这种表示，来说明一个等价的代替，比如：dight-0|1|2|3|4|5|6|7|8|9这里，我们就可以使用名字digit来代替后面的正规表达式我们可以对某个串集进行正规定义，比如我们对标识符集合进行正规定义：letter-A|B|...|Z|a|b|...|zdight-0|1|2|3|4|5|6|7|8|9id-letter(letter|dight)*请通过上面的例子理解正规定义。在我们表达正规表达式的时候，可以使用一些符号使得表达简化1)+，表示一个或者多个实力，比如，a+表示{a,aa,aaa,aaaa,...}。区别一下*,他们的关系是这里r+=r*|ε2)字符组，[abc]表示a|b|c，还可以这样表示[a-zA-Z]表示字母表中的字符4.状态转换图状态转换图是对词法分析器进行分析过程的描述，我们看一个判断关系运算的状态转化图：1)图中圆圈表示状态2)箭头叫做边。X状态的边，一般指的是由X状态出发，指向其他状态的边3)边上的符号叫做标记如何来使用这个图？假定输入字符串是=，那么识别开始时，发现和状态0与状态1间的边上的标记一样，那么就进入1状态，下一个输入字符为=，将进入2状态，识别结束，返回二元组relop,LE上图中2，3，4，5，7，8状态，他们表示识别了一个关系运算符，这个状态叫做接受状态状态4上面有一个*，表示说，输入指针需要回移。所谓的输入指针，就是指向输入字符串中现在被读入的字符的位置，4状态会多读取一个字符，所以需要回移，也就是要注意的是，识别完成之后，输入指针指向的是被识别对象的最后一个字符，而不是待识别对象的第一个字符，这样的规定在实现词法分析器时，是有一定的意义，举例说明：输入字符串为：ab识别的时候，从开始，读入下一个字符b时，进入4状态，这个时候，输入指针指向b，这时候需要回移我们在需要回移的状态上加一个*每个状态后面有一个return(relop,XX)这个是状态的行为，这里具体来说就是返回一个二元组的行为，词法分析器分析的结果就是得到二元组(词法记号和属性的二元组)，这个二元组可以表示一个特定的字符串。其实上面的*，也是表示行为，也就是输入指针回移的行为，我们可以看见，只有在接受状态才会有行为出现对一门典型的语言来说状态可能有几百个5.如何编写一个词法分析器1)根据需要写出正规定义2)根据正规定义画出转换图3)根据转换图写出词法分析器这里详细讨论面向过程的语言来实现一个词法分析器(比如c语言)，并且主要讨论的是第3步1)我们需要一个nextchar()函数，取得缓存中下一个等待分析的字符，这个函数完成年2个任务1.让输入指针向前移动一位2.返回输入指针指向的字符2)定义一个变量token_beginning，在每个状态转换图开始的时候，记录输入指针的位置，定义forward变量作为输入指针3)状态转换图被实现成为代码之后，每个状态都有属于自己的一块代码，这些代码按顺序完成以下工作：1.读取一个字符，通过nextchar()函数2.读取的字符(标志)，如果它和当前状态的边上的标记相同，那么状态将转换到边所指向的状态，具体实现只需要一个语句就是state=xxx(xxx为目标状态)；如果当前状态的所有边的标记和这个读取字符不一样，那么表示没有找到token(词法记号)，这时候需要调用fail()函数3.fail()函数完成这样的功能：a.指针回移，完成forward＝token_beginning的操作b.找到适当的开始状态(也就是寻找另外一个转换图的开始状态)。假定所有的转换图都被尝试过，并且无法匹配，这时候会调用一个发现错误的小程序，来报告错误4.请不要随意添加行为到各个状态所持有的代码中，应该以转换图中表示的行为为准4)定义一个全局变量lexical_value，用于保存一个指针，这个指针由install_id()和install_num()两个函数中的一个返回5)定义两个整形变量start,state，分别表示一个转换图的开始状态和当前的状态6)nexttoken()，这是词法分析器的主程序，可以说，我们通过调用nexttoken()就完成了词法分析，这个函数一定是这样的格式：while(1){switch(state){casexx:...caseyy:...default:...}}关于详细的设计这里就不说了，举例说明一个转换图如何转换成为程序：这是一个识别浮点数的例子，看下面的代码：#includestdio.h#includectype.h#includestring.hchar*nexttoken();charnextchar();voidnext();voidback();char*gettoken();charcbuf[]=12.3*********klj12.2e2jj778;intforward=-1;intmain(){while(1){printf(%s\n,nexttoken());if(forward=strlen(cbuf)-1){getchar();return0;}}}intstate;intstart;char*nexttoken(){charc;state=12;while(1){switch(state){case12:c=nextchar();start=forward;if(isdigit(c)){state=13;}else{next();}break;case13:c=nextchar();if(isdigit(c))state=13;elseif(c=='e'||c=='E')state=16;elseif(c=='.')