搜索
《编译原理简明教程》普通高等教育“十二五”规划计算机教材---太原理工大学---计算机科学与技术学院---冯秀芳、崔冬华、段富等•第一章引言•第二章形式语言理论基础•第三章自动机理论基础•第四章词法分析•第五章语法分析—自顶向下分析方法•第六章语法分析—自底向上分析方法•第七章语义分析及中间代码的生成•第八章代码优化•第九章目标代码的生成•第十章符号表•第十一章目标程序运行时的存储组织与分配•第十二章出错处理•第十三章编译程序自动生成工具简介•第十四章面向对象语言的编译•第十五章并行编译技术目录第十三章编译程序自动生成工具简介学习目标了解和掌握高级语言编译程序自动生成工具的种类了解和掌握几种常用的词法分析自动生成工具用法了解和掌握几种常用的语法分析自动生成工具用法词法分析、语法分析、一遍扫描分析和多遍扫描分析等，其实都是非常机械的过程，完全可以由计算机代替人工完成，由此出现了词法和语法分析的自动生成工具，本章简单介绍这种自动生成工具的发展、作用、分类以及目前常用的工具应用。学习本章后，学生应该能够掌握使用编译程序自动生成工具完成高级语言词法和语法分析的基本方法，具有设计、实现、分析和维护编译器的词法和语法分析的初步能力。13.1引言•13.1.1编译程序自动生成工具简介•13.1.2编译程序自动生成工具的种类及常用工具简介13.2词法分析自动生成工具•13.2.1LEX系列词法分析自动生成工具简介•13.2.2其他词法分析自动生成工具简介13.3语法分析自动生成工具•13.3.1YACC系列语法分析自动生成工具简介•13.3.2其他语法分析自动生成工具简介目录13.1引言13.1.1编译程序自动生成工具简介编译程序自动生成工具的实质：就是实现编译器中的词法和语法分析过程，其原理就是本书前几章所介绍的编译过程的词法和语法分析的自动化实现。编译程序自动生成工具的作用：自动识别源程序是否符合该语言所规定的语法规则。编译程序自动生成工具的分类：词法分析和语法分析两个阶段13.1引言13.1.2编译程序自动生成工具的种类及常用工具简介1.由于在编译器实现过程所包含的几个阶段中，词法分析和语法分析的实现原理明确，操作步骤确定，可以借助于计算机来自动完成，所以编译程序自动生成工具主要包含词法分析和语法分析两种类型。2.早期的研究一般是分别给出词法和语法分析的实现工具，如UNIX操作系统平台上的LEX和YACC；3.现在的一些工具则将词法和语法分析的实现集成在一起，而且也不再局限于用C语言实现，出现了很多基于Java语言且可以生成多种目标语言的词法和语法分析工具，比如ANTLR和JavaCC&SableCC等。4.根据语法分析阶段采用“自底向上”或“自顶向下”分析方法的不同，以及分析阶段向前看字符数的差别，可以将编译程序自动生成工具分成若干种类。13.1引言13.1.2编译程序自动生成工具的种类及常用工具简介表13.1几种编译器的词法、语法分析自动生成工具的特性对照表工具名称开发语言生成代码语法规则自动构建ASTUnicode支持开发者(组织)备注Flex/BisonCC或C++LALR(1)无无GNUJlex/CUPJavaJavaLALR(1)无无ElliotJoelBerk/ScottE.Hudson是Flex/Bison的Java版PCCTSC++C++LL(K)有无TerenceParrANTLRJavaJavaLL(K)有无TerenceParrPCCTS的Java版JavaCCJavaJavaLL(K)有有SUNSableCCJavaJavaLALR(1)有有McGillUniversity生成代码框架GrammaticaJavaC#&JavaLL(K)无有GNUGOLDParserC#、C++、C、ASM等LALR(1)有有AdrianMooreRunCCJavaJava、XMLLR(PARSER),LL(LEXER)无有GNU作者：RitzbergerFritz13.2词法分析自动生成工具词法分析工具将源程序看做字符文件类型，由Lex创建的词法分析器与语法分析器类工具按照如下图的方式协同工作(如图13.1所示)：词法分析器读取源程序并将文件分为若干个单词，提交给语法分析阶段使用。图13.1词法分析器与语法分析器之间的交互示意图13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介Lex是美国Bell实验室的M.Lesk等人用C语言研制的词法分析自动生成工具；基本原理：使用正则表达式扫描源程序，并为每一个匹配模式定义一些操作。特点：Lex和C是强耦合的，词法分析过程中，Lex接收一个后缀为.l的文件(描述词法分析规则的规范文件)，分析检查并生成词法分析的可执行版本，通过Lex公用程序来传递并生成基于C语言的输出文件。Lex工具的输入表示方法称为Lex语言，而工具本身(如Flex)则称为Lex编译器。在Lex工具的核心部分，Lex编译器将输入的模式转换成一个状态转换图，并生成相应的实现代码，存放到一个称为1ex.yy.c或1exyy.c的Lex输出文件中，这些代码用来模拟转换后的状态转换图。13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介1、Lex的使用方法用Lex创建一个词法分析器的操作步骤图13.2图13.2用Lex创建一个词法分析器的操作步骤示意图13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介2．正则表达式的Lex约定正则表达式(regularexpression)：是一种可以用于模式匹配和替换的强有力的工具。【例13.1】为“以aa或bb开头，末尾是一个可选的c”描述的串写出两种正则表达式。参考解答：(aa|bb)(a|b)*c?或(aa|bb)(a|b)*c?13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介2．正则表达式的Lex约定正则表达式(regularexpression)：是一种可以用于模式匹配和替换的强有力的工具。【例13.2】为一个带符号的数集写出正则表达式，这个集合可能包含一个小数部分或一个以字母E开头的指数部分。参考解答：(“+”|“-”)？[0-9]+(“.”[0-9]*)?(E(“+”|“”)?[0-9]+)?13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介2．正则表达式的Lex约定正则表达式(regularexpression)：是一种可以用于模式匹配和替换的强有力的工具。【例13.3】定义前面讲述的signednum。参考解答：num=[0-9]+signednum=(+|-)?num也可以定义为num[0-9]+signednum(+|-)?{num}注意，在定义名字时并未出现花括号，它只在使用时出现。13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介3．Lex词法输入文件的格式Lex输入文件的格式如下：{definitions}%%{rules}%%{auxiliaryroutines}Lex输入文件(即Lex程序)由3部分组成：定义(definition)集、规则(rule)集、辅助程序(auxiliaryroutine)集或用户程序(userroutine)集这3部分由位于新一行第1列的双百分号分开。13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介3．Lex词法输入文件的格式1.第1个双百分号之前出现的是：定义(或称声明)部分，包括两部分可选内容：一是包含在分隔符“%{”和“%}”之间的任何函数外部的任意C代码(注意这些字符的顺序)，这些C代码可以插入到生成的C程序中；二是正则表达式名字的定义。2.第1和第2个双百分号之间出现的是：规则部分，由一系列带有C代码的正则表达式组成，每个转换规则的格式为模式｛动作｝；其中每个模式是一个正则表达式，可以使用声明部分给出的正则定义。当匹配相对应的正则表达式时，这些动作对应的C代码片段就会被执行。3.第2个双百分号之后出现的是：规则部分各个动作需要使用的所有辅助函数，这部分是可选内容。通常，当不需要第3个部分的辅助函数时，第2个双百分号就无须出现了，但第1行双百分号总是需要出现的。13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介4．Lex输入文件格式示例【例13.4】以下的Lex输入能够识别表13.2中的各个词法单元并返回，观察这段代码，分析Lex程序的特点。%{/*常量定义(声明)LT,LE,EQ,NE,GT,GE,LT,THEN,ELSE,ID,NUMBER,RELOP*/#includestdio.hintlineno=1;%}/*正则表达式定义*/delim[\t\n]ws{delim}+letter[A-Za-z]digit[0-9]id{letter}({letter}|{digit})*number{digit}+(\.{digit}+?(E[+-]?{digit}+)?line*.\n%%13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介{ws}{/*没有动作或没有返回*/}if{return(IF);}then{return(THEN);}else{return(ELSE);}{id}{yylval=(int)installID().;return(ID);}{number}{yylval=(int)installNum().;return(NUMBER);}“”{yylval=LT;return(RELOP);}“=”{yylval=LE;return(RELOP);}“=”{yylval=EQ;return(RELOP);}“”{yylval=NE;return(RELOP);}“”{yylval=GT;return(RELOP);}“=”{yylval=GE;return(RELOP);}{line}{printf(“%5d%s”,lineno++,yytext);}%%13.2.1LEX系列词法分析自动生成工具简介intinstallID(){/*将词素初始化到符号表中的函数，返回一个指针；其中yytext是指向词素开头的指针，yyleng存放刚找到的词素的长度*/}intinstallID(){/*与installID相似，但初始化和存放的是数字常量*/}main(){yylex();return0;}13.2词法分析自动生成工具13.2词法分析自动生成工具13.2.1LEX系列词法分析自动生成工具简介5．Lex中的冲突解决Lex解决冲突的两个规则，即当输入的多个前缀与一个或多个模式匹配时，Lex用下列规则选择正确的词素：①总是选择最长的前缀。②如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式。13.2词法分析自动生成工具13.2.2其他词法分析自动生成工具简介1．FLexFlex(FastLex)是最常见的Lex开源版本，它是由FreeSoftwareFoundation创建的GnuCompilerPackage的一部分，可以在许多Internet站点上免费得到。与其配套的开源语法分析器编译工具是Bison，这组工具使用C语言来指定动作代码(我们使用属性“动作”来指代由编程人员所写的在词法或语法分析执行部分某个特定点要执行的代码)。13.2词法分析自动生成工具13.2.2其他词法分析自动生成工具简介2．JLexJLex是Lex的一个Java版本，由普林斯顿大学计算机科学系的一个学生ElliotJoelBerk开发。JLex在功能上与Flex非常相似，它接受类似Lex文件格式的词法分析文件，生成Java源代码格式的词法分析器。与其配套的语法分析器编译工具是CUP(ConstructorofUsefulParsers，YACC的Java版本)或BYacc/J(BobJamison对经典BerkeleyYACC的Java扩展)。13.2词