高等教育编译原理与技术讲义.pptx
《高等教育编译原理与技术讲义.pptx》由会员分享,可在线阅读,更多相关《高等教育编译原理与技术讲义.pptx(93页珍藏版)》请在咨信网上搜索。
1、青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术1主要内容主要内容u词法分析器的设计词法分析器的设计u词法分析器的一种手工实现词法分析器的一种手工实现u正规表达式正规表达式u有限自动机有限自动机u词法分析的自动生成器词法分析的自动生成器Lex青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术2词法分析器在编译中的位置词法分析器在编译中的位置词法分析器语法分析器符号表源程序单词取下一个单词单词记号青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术32.1词法分析器的设计词法分析器的设计u词法分析器的基本功能词法分析器的基本功能按照语言的定义
2、规则,逐个地读入源程序的按照语言的定义规则,逐个地读入源程序的符号,识别出对语言有意义的符号串,即单符号,识别出对语言有意义的符号串,即单词符号;词符号;分析单词记号的属性,并把单词记号及其属分析单词记号的属性,并把单词记号及其属性填写在符号表中;性填写在符号表中;同时把源程序改造成等价的计算机内部表示同时把源程序改造成等价的计算机内部表示单词记号,以便编译的后续阶段使用。单词记号,以便编译的后续阶段使用。还要对源程序进行预处理工作,包括:删除还要对源程序进行预处理工作,包括:删除源程序中的空格、制表符、换行、注释等不源程序中的空格、制表符、换行、注释等不影响程序语法、语义的结构。影响程序语法
3、、语义的结构。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术42.1词法分析器的设计词法分析器的设计u高级程序语言的五种单词记号:高级程序语言的五种单词记号:保留字保留字是程序语言定义的具有固定意义的英文单词,是程序语言定义的具有固定意义的英文单词,有时称为基本字或关键字。例如,在有时称为基本字或关键字。例如,在C+中,中,char、float、extern、friend、switch、new都是关键字。保都是关键字。保留字一般不能另作它用。留字一般不能另作它用。标识符标识符表示各种名字的字符串,如变量名、类型名、表示各种名字的字符串,如变量名、类型名、函数名、对象名等。
4、函数名、对象名等。运算符运算符如如+、=、=等。等。常量常量常量的类型一般有整型、实型、布尔型、文字常量的类型一般有整型、实型、布尔型、文字型等。型等。分界符分界符如分号、括号、注释标记如分号、括号、注释标记/*、*/等。等。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术52.1词法分析器的设计词法分析器的设计u词法分析器的输出词法分析器的输出单词记号一般采用形式为单词记号一般采用形式为的二元式。的二元式。单词的种别是语法分析需要的信息,通常用单词的种别是语法分析需要的信息,通常用整数表示;整数表示;单词的属性值则是编译的语义分析和代码生单词的属性值则是编译的语义分析和代
5、码生成等阶段需要的信息。成等阶段需要的信息。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术62.1词法分析器的设计词法分析器的设计例例2.1:假如保留字的编码是假如保留字的编码是1,标识符的为,标识符的为2,运算符为,运算符为3,分界符为分界符为4,整型常量为,整型常量为10,实型常量为实型常量为11。那么,对于源。那么,对于源程序代码:程序代码:for(i=1,sum=9.8;i=100;i+)sum+=i 3.14;词法分析器产生的结果是单词词法分析器产生的结果是单词记号序列记号序列3,青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术72.1词法分
6、析器的设计词法分析器的设计u词法扫描器与符号表词法扫描器与符号表对符号表的操作主要是填表、查询和更新。对符号表的操作主要是填表、查询和更新。每当词法分析器识别了一个单词的时候,第一项工作每当词法分析器识别了一个单词的时候,第一项工作就是查询符号表。对于不同的单词种别,查询的方式就是查询符号表。对于不同的单词种别,查询的方式和随后的处理完全不同。例如,对于关键字、分界符和随后的处理完全不同。例如,对于关键字、分界符和运算符等,只需在各自的符号表中查询,获得并记和运算符等,只需在各自的符号表中查询,获得并记录其它属性值,生成相应的单词记号。录其它属性值,生成相应的单词记号。处理常量,特别是处理标识
7、符要复杂的多,而且仅仅处理常量,特别是处理标识符要复杂的多,而且仅仅在词法分析阶段是无法获得一个标识符的所有信息。在词法分析阶段是无法获得一个标识符的所有信息。当词法扫描器识别了一个标识符的时候,首先查询关当词法扫描器识别了一个标识符的时候,首先查询关键字表,看它是否是关键字;如果不是,还要在标识键字表,看它是否是关键字;如果不是,还要在标识符表中查询,看它是否已经存在,如果不存在就把它符表中查询,看它是否已经存在,如果不存在就把它填入标识符表,并填入种别、类型等信息。填入标识符表,并填入种别、类型等信息。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术82.1词法分析器的
8、设计词法分析器的设计u词法分析器的两种实现模式词法分析器的两种实现模式完全独立模式和相对独立模式完全独立模式和相对独立模式在完全独立模式下,词法分析器作为编译的在完全独立模式下,词法分析器作为编译的子系统单独地运行一趟,扫描整个源程序,子系统单独地运行一趟,扫描整个源程序,把识别的单词序列以机器内码的形式输出在把识别的单词序列以机器内码的形式输出在一个中间文件上,供为语法分析使用。一个中间文件上,供为语法分析使用。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术92.1词法分析器的设计词法分析器的设计u完全独立模式的好处完全独立模式的好处编译程序结构清晰、条理化而且便于高效
9、地实现;编译程序结构清晰、条理化而且便于高效地实现;在设计高级语言时能独立地研究词法与语法两个方面在设计高级语言时能独立地研究词法与语法两个方面的特性;的特性;增强编译程序的可移植性:可以就同一个语言为不同增强编译程序的可移植性:可以就同一个语言为不同的机器写不同的词法分析器,而只编写一个共同的语的机器写不同的词法分析器,而只编写一个共同的语法分析,使用这些词法分析器相同的单词机内表示;法分析,使用这些词法分析器相同的单词机内表示;把同一个词法由于单词记号的语法可以用较简单的文把同一个词法由于单词记号的语法可以用较简单的文法描述,把词法和语法分开,就能为这种文法建立有法描述,把词法和语法分开,
10、就能为这种文法建立有效的特殊方法和自动构造技术。效的特殊方法和自动构造技术。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术102.1词法分析器的设计词法分析器的设计相对独立模式:词法分析器设计成一个子程相对独立模式:词法分析器设计成一个子程序,每当语法分析需要一个单词的时候,就序,每当语法分析需要一个单词的时候,就调用该子程序。调用该子程序。相对独立模式的好处:词法分析器和语法分相对独立模式的好处:词法分析器和语法分析器被设计在同一趟,省去了存放单词的终析器被设计在同一趟,省去了存放单词的终结文件。结文件。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技
11、术112.1词法分析器的设计词法分析器的设计u词法错误的处理词法错误的处理在词法分析阶段发现的错误统称为词法错误,在词法分析阶段发现的错误统称为词法错误,它们大多是单词拼写错误,这或者是因为书它们大多是单词拼写错误,这或者是因为书写错误、或者因为键入错误,例如把关键字写错误、或者因为键入错误,例如把关键字拼写错。拼写错。对词法错误校正的常用策略是修补尝试,一对词法错误校正的常用策略是修补尝试,一般包括:般包括:l删除一个多余的字符;删除一个多余的字符;l插入一个遗漏的字符;插入一个遗漏的字符;l用一个正确的字符替换一个不正确的字符;用一个正确的字符替换一个不正确的字符;l交换两个相邻的字符。交
12、换两个相邻的字符。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术122.2词法分析器的一种手工实现词法分析器的一种手工实现u输入的预处理输入的预处理对于许多程序语言来说,空格、制表符、换对于许多程序语言来说,空格、制表符、换行符等编辑性字符除了出现在文字常量中,行符等编辑性字符除了出现在文字常量中,在其它任何地方的出现都没有意义,而注释在其它任何地方的出现都没有意义,而注释作为程序的重要文档几乎可以出现在程序中作为程序的重要文档几乎可以出现在程序中的任何地方。它们的存在可以改善程序的可的任何地方。它们的存在可以改善程序的可读性和易理解性,却不影响程序的语法结构读性和易理解
13、性,却不影响程序的语法结构和执行语义。和执行语义。通常在编译的词法分析阶段被预处理过程删通常在编译的词法分析阶段被预处理过程删除掉。除掉。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术132.2词法分析器的一种手工实现词法分析器的一种手工实现u输入的预处理输入的预处理l扫描器对缓冲区进行扫描时一般使用两个指针:一个指向当前正在识别的单词的起始位置,另一个用于向前搜索以寻找该单词的终点,两个指针之间的符号串就是要识别的单词符号。无论扫描缓冲区设计的多大都不能保证单词符号不会超过其边界。扫描缓冲区一分为二的两段置.f o r(s u m=0,i=1.搜索指针起点指针.C a
14、r.e e l.2.青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术142.2词法分析器的一种手工实现词法分析器的一种手工实现u超前搜索和最长匹配超前搜索和最长匹配为了识别一个更有意义的单词符号,在找到了可能是为了识别一个更有意义的单词符号,在找到了可能是单词符号的起点或者构成了单词部分时,扫描器并不单词符号的起点或者构成了单词部分时,扫描器并不满足,还要继续读入输入串,看是否能找到由更多符满足,还要继续读入输入串,看是否能找到由更多符号所组成的单词(即最长匹配),有时可能要扫描到号所组成的单词(即最长匹配),有时可能要扫描到一个可以一个可以“断句断句”的符号(超前搜索),
15、才能决定最的符号(超前搜索),才能决定最后一个扫描的符号不属于之前的符号串所构成的单词。后一个扫描的符号不属于之前的符号串所构成的单词。超前搜索符号通常是最长匹配单词的结束标志,可以超前搜索符号通常是最长匹配单词的结束标志,可以是空格符、回车符、制表符等可以被预处理掉的符号;是空格符、回车符、制表符等可以被预处理掉的符号;也可能是下一个单词记号的起始符。也可能是下一个单词记号的起始符。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术152.2词法分析器的一种手工实现词法分析器的一种手工实现u超前搜索和最长匹配的例子超前搜索和最长匹配的例子在识别在识别“for”的时候,要扫描
16、到左括弧的时候,要扫描到左括弧(时才知道,它不属于标识符的符号;时才知道,它不属于标识符的符号;当读到了当读到了,以便构造出小于等于,以便构造出小于等于“=”或不等于或不等于“”的比较运算符,否则,的比较运算符,否则,就构造小于运算符。就构造小于运算符。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术162.2词法分析器的一种手工实现词法分析器的一种手工实现u状态转换图状态转换图状态转换图是构造词法分析器的一个良好工具,它描状态转换图是构造词法分析器的一个良好工具,它描绘了为得到一个单词记号,词法分析器应该执行的动绘了为得到一个单词记号,词法分析器应该执行的动作。作。状态转
17、换图是一个有向图,结点代表状态,用圆圈表状态转换图是一个有向图,结点代表状态,用圆圈表示,内部用数字表示状态名称;示,内部用数字表示状态名称;状态之间由箭弧连接,箭弧上有符号作为标记,称为状态之间由箭弧连接,箭弧上有符号作为标记,称为从箭弧尾的离开状态读入标记符号以后转换到箭弧头从箭弧尾的离开状态读入标记符号以后转换到箭弧头的进入状态。的进入状态。若离开状态若离开状态s的某个标记为的某个标记为other,则表示离开,则表示离开s的其它的其它箭弧标记以外的任意符号。箭弧标记以外的任意符号。每个状态转换图中的状态数量有限,都有唯一的一个每个状态转换图中的状态数量有限,都有唯一的一个起始状态(本书用
18、一个进入的箭头表示)和至少一个起始状态(本书用一个进入的箭头表示)和至少一个终结状态(用双圈表示)。终结状态(用双圈表示)。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术172.2词法分析器的一种手工实现词法分析器的一种手工实现u状态转换图识别或接受一定的输入符号串状态转换图识别或接受一定的输入符号串从起始状态开始,读进输入符号串的一个符从起始状态开始,读进输入符号串的一个符号号a,沿着状态转换标记为,沿着状态转换标记为a进入下一个状态,进入下一个状态,重复执行直到进入终结状态。重复执行直到进入终结状态。即,如果存在一个从起始状态到终结状态的即,如果存在一个从起始状态到终
19、结状态的路径,路径上的标记用连接运算连接在一起路径,路径上的标记用连接运算连接在一起形成一个符号串,它和输入符号串相同,则形成一个符号串,它和输入符号串相同,则称该输入符号串可以接受。如果不能进入任称该输入符号串可以接受。如果不能进入任何一个终结状态,则称该状态转换图不能识何一个终结状态,则称该状态转换图不能识别或接受这个输入符号串别或接受这个输入符号串青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术182.2词法分析器的一种手工实现词法分析器的一种手工实现digit01letterletter对于符号串var1,有状态序列,例例2.2:标识符一般定义为字母打头的字母数字序
20、列标识符一般定义为字母打头的字母数字序列.青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术192.2词法分析器的一种手工实现词法分析器的一种手工实现5other=1=032例例2.3:类似语言中的关系符的状态转换图。在终结状态加了星号*,表示在状态1、2和3都还不能确定它们是否是符合最长匹配准则的单词记号,还需要在读入一个字符才能确定。而为实现最长匹配的一个超前搜索符号“其它”则不属于这个单词,应该推给扫描缓冲区。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术202.2词法分析器的一种手工实现词法分析器的一种手工实现例例2.4:Pascal语言中数的状
21、态转换图语言中数的状态转换图。在这个复杂的例子中,状态在这个复杂的例子中,状态3、5和和8分别表示识别是整数、不带指数部分分别表示识别是整数、不带指数部分的实数以及带有指数部分的实数,但是,只能在超前搜索一个其它符号以的实数以及带有指数部分的实数,但是,只能在超前搜索一个其它符号以后,才能在状态后,才能在状态9确定识别了一个确定识别了一个Pascal的数。读者可以自己验证例子数的数。读者可以自己验证例子数2005,+1998,81.07,2.003 6,看它们是否能被这个转换图所接受。,看它们是否能被这个转换图所接受。3digitdigitotherdigitdigitdigit9814562
22、+,E7+,digitEdigitotherother*青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术212.2词法分析器的一种手工实现词法分析器的一种手工实现u基于状态转换图的词法分析器的实现基于状态转换图的词法分析器的实现code表示单词记号的种别;表示单词记号的种别;value存放标识符或数在符号表的入口地址;存放标识符或数在符号表的入口地址;过程过程getghar(ch)从扫描缓冲区得到一个搜索符号,从扫描缓冲区得到一个搜索符号,存储在变量存储在变量ch中;中;函数函数isLetter(ch)和和isDigit(ch)分别检查分别检查ch是否是字是否是字母母/数字
23、;数字;函数函数lookup(token,table)在符号表在符号表table中查询是否中查询是否包含单词包含单词token;insert(token,table)在则把单词在则把单词token插入符号表插入符号表table中并返回在符号表的地址;中并返回在符号表的地址;函数函数reporterror()报告并简单处理词法错误。报告并简单处理词法错误。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术222.2词法分析器的一种手工实现词法分析器的一种手工实现u根据状态栈图编写词法扫描器的方法一根据状态栈图编写词法扫描器的方法一让状态转移对应一个读入字符的语句或函数,让状态转
24、移对应一个读入字符的语句或函数,然后与转移上的标记比较,如果相等就进入然后与转移上的标记比较,如果相等就进入转移对应的程序段或子程序;否则,调用错转移对应的程序段或子程序;否则,调用错误处理程序。误处理程序。多个转移就对应分支语句;多个转移就对应分支语句;如果转移返回自身,形成一个圈,对应程序如果转移返回自身,形成一个圈,对应程序段的就是循环语句。段的就是循环语句。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术232.2词法分析器的一种手工实现词法分析器的一种手工实现标识符状态转换图的一个实现标识符状态转换图的一个实现int code,value;char token=”
25、;/在开始状态0do token=token+ch;/不断读入字母或数字,合并成一个标识符 getchar(ch);/保持在状态1 while(!isLetter(ch)|!isDigit(ch);/isLetter(ch)和isDigit(ch)分别检查ch是否是字母/数字/进入结束开始状态2code=lookup(token,keywordsTable);/在关键字表中查询token,若它是关键字就返回1if(code=1)return(1,token);/返回关键字的单词记号,假如关键字种别是1else value=insert(token,identifierTable);/把toke
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高等教育 编译 原理 技术 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。