《【教学课件】第二章编译器编写工具.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章编译器编写工具.ppt（19页珍藏版）》请在三一办公上搜索。
1、第二章 编译器编写工具,程序自动生成的条件：建立数学模型形式化描述算法自动构造 语法描述的简单性和数学模型的成熟，使得词/语法分析器编写工具成为可能。LEX/YACC，基于C、UNIX环境。语义仍然需要人工编写。,2.1 词法分析器生成器-LEX 分析器的构造步骤：正规式NFADFA最小化DFA分析表（驱动器）利用工具构造词法分析器实质上成为为所需的词法分析器设计正规式。,2.1.1 LEX概述,工作方式：,2.1.1 LEX概述（续）,lex生成的词法分析器的框架,框架是预先构造好的，根据每个*.l文件的内容，向其中的各部分填写内容。,2.1.2 LEX源程序的基本结构,声明（declara
2、tion）%翻译规则（translation rules）%用户定义子程序（user defined routines）,其中翻译规则可以为空，因此最简单的源程序可以是：%其功能是将输入原封不动搬到输出,2.1.2 LEX源程序的基本结构（续1）,例2.1 下述LEX源程序构造一个计数器，分别为输入文件中的字符、字和行计数。,(1)%(2)#include(3)int nchar,nword,nline;/*分别记录字符个数、字数和行数*/(4)%,(5)%(6)t/*匹配到一个空格或Tab键就“吃”掉它们*/(7)n+nline;/*匹配到一个换行符，行数加1*/(8)tn+nword;nc
3、har+=yyleng;(9)/*匹配到一个不包括空格、Tab键和换行符的字，(10)字数加1，字符数加yyleng(字符长度)*/,(11)%(12)main()(13)yylex();/*调用词法分析器，直到输入结束*/(14)printf(nchar=%d,nword=%d,nline=%dn，nchar,nword,nline);(15),2.1.2 LEX源程序的基本结构（续2）,（1）声明的C语言部分（2）词法分析表（3）分析表的驱动器（yylex()）（4）用户定义子程序,其中：(1)到(4)行被插入到框架的（1）中；(6)(7)(8)三条规则被构造成DFA插入到框架的（2）中；
4、规则里的语义动作被插入到框架的（3）中；最后的mian被插入到框架的（4）中。从而形成一个完整的C程序，经过C编译器编译之后得到可运行的程序。,若输入序列为：I am a student.You are a student,too.则对应输出为：nchar=31，nword=9，nline=2,2.1.2.1 声明,C语言部分：%.%之间，如预编译语句（#define、#include）、声明语句等 辅助定义部分：为正规式起名子，不作为外部匹配模式：名字正规式,例2.2char a-zA-Zdigit 0-9,辅助定义式，不匹配任何模式,char(char|digit)*,规则，匹配标识符,2
5、.1.2.2 用户定义子程序,用户的声明、子程序定义等的具体安排：可以设计为独立的模块，然后在声明部分用#include语句引入，也可以直接写在此处。,注意：C语句在LEX编译器中不被处理，最后由C编译器编译；声明、用户定义子程序要合理安排，否则会出现不一致，如重复定义等。,2.1.2.3 翻译规则,（1）翻译规则的形式：正规式 语义动作（2）LEX的正规集,序号语法 语义,(1)x匹配字符或字符串x。(2)x匹配字符或字符串x。(3)x匹配字符x自身，如+；或C中的转义字符，如t，n等。(4)xy匹配或者字符x或者字符y。,x-z 匹配字符x，y或z，-表示一个范围，并且要求-左边字符 小于
6、右边字符，否则出错。当-表示其本身时，要放在方括 号的最左或最右。,x 匹配除x以外的任何一个字符，x可以是若干字符，如 tn 表示除空格、制表符和换行以外的其它字符。,(7).匹配除换行以外的任何其它字符。(8)x*正规式x的闭包。(9)x+正规式x的正闭包（closure-plus）。(10)x|y匹配或者正规式x或者正规式y。,返回,2.1.2.3 翻译规则（续1）,表2.1 LEX的正规式集,(11)(x)匹配正规式x本身，()用来改变运算优先级。(12)x?正规式x可省略。该正规式与x|等价，其中表示空。(13)x匹配一行开始处的正规式x，如ABCabcABC中第一个ABC。(14)
7、x$匹配一行结束处的正规式x，如ABCabcABC中第二个ABC。,x/y 匹配其后紧跟正规式y正规式x，如0-9+/.EQ.识别输入串35.EQ.I中的35。,(16)x匹配处于开始条件时的正规式x。,xm,n 匹配m到n个正规式x，如ab3，5识别：ababab，abababab，ababababab。,扩充：特殊字符处理：(3)和(7)考虑上下文：(13)到(16)限制重复次数：(17),灵活应用正规式集描述所设计语言的词法模式，是编写LEX源程序所需考虑的重要因素之一。,2.1.2.3 翻译规则（续2）,例2.3 部分LEX正规式与它们所描述的输入序列,LEX正规式被识别的输入序列ab
8、c abcabc+abc.c(至少一个c)，+是LEX正规式的运算符abc+abc+abc+abc+abct abc后跟一个制表符abc abc后跟一个制表符abct是一个错误，不能有双重转义a|b|c|d|e|f|gabcdefg之中的任一个字符a-z abcdefghijklmnopqrstuvwxzy之中的任一个字符ab?c ac或abc(ab)?c c或abc#define 行首的#defineabc$匹配行尾的abcabcn 匹配行尾的abc,2.1.2.4 关于多重入口（左上下文相关处理）,x：在y条件下匹配x。（也被称为入口）这是LEX为用户提供的一种左上下文相关（left co
9、ntext sensitivity）的处理功能，便于用户根据已分析过的内容进行下一步的处理。实际上也可以把它理解为分不同情况选择进入分析表的不同入口。这种方法对于实际的词法分析器设计是十分有用的。,2.1.2.4 关于多重入口（续1）,三个步骤：入口的声明、引用以及进入。入口的声明：在LEX声明部分的辅助定义中，以关键字%start开始，其后可以跟若干个被声明的入口，如：%start entry1 entry2.（特点：与0入口不互斥）入口的引用：在LEX正规式的左边加上相应入口，表示其后紧跟的正规式，只有进入该入口时才起作用。如：rule 入口的进入：LEX为用户提供一个语义过程BEGIN，
10、它表示执行完以BEGIN开始的语句后，下一次的词法分析从所规定的入口开始。如：BEGIN entryi；对于没有入口引导的正规式，均被默认从GEGIN(0)开始。,2.1.2.4 关于多重入口（续2）,例2.4 典型演示多重入口的LEX源程序，并给出了若干输入及其对应的输出。,%start AA BB CC%a|t ECHO;BEGIN AA;b ECHO;BEGIN BB;c ECHO;BEGIN CC;n|(t)+|“”+ECHO;BEGIN 0;magic printf(“zero”);magic printf(“first”);magic printf(“second”);magic
11、printf(“third”);,输入 输出amagic magicamagic magicmagic magicbmagicmagiccmagicmagic,afirst zeroafirstfirstzero zerobsecondfirstcthirdzero,2.1.2.4 关于多重入口（续3）,互斥的入口：将%start换为%x%x需要用语句GEGIN(0)显式地从当前入口退出。,例2.5 C与C+注释的处理,用一个正规式描述：c_comments=/*(*|(*)*/)*(*)*/,识别C语言注释的自动机：,2.1.2.4 关于多重入口（续4）,用多重入口描述：%x comment
12、 c_comment/入口声明%/BEGIN comment;/进入C+注释/*BEGIN c_comment；/进入C注释.,*/BEGIN 0;/C注释结束.;/C注释内容n+linenum;/C注释内容,.;/C+注释结束n BEGIN 0;LineNo+;/C+注释结束,对比：c_comments=/*(*|(*)*/)*(*)*/,2.1.3 LEX程序设计,2.1.3.1 如何从词法分析器返回识别出的记号,yylex()：返回记号的类别（内部是一个整型数），如return ID等。yylval：全局变量，默认类型是int，用它表示所识别记号的值。yytext，yyleng：全局变量
13、，用来存放识别出的输入序列，它们合起来可以表示正文形式的值，如标识符和字符串等。它们的内容是由词法分析器填进的。,2.1.3.1 如何从词法分析器返回识别出的记号,yylex()，yylval，yytext，yyleng：,例2.6 若输入序列为整型数258，整型数编码是40（NUMBER=40），识别整型数的规则为：0-9+sscanf(yytext,%d,则从词法分析器返回时各函数或变量的值分别为：yylex()：40yylval：258yytext：258yyleng：3它们均可以被调用该词法分析器的语法分析器使用。,2.1.3.2 LEX的匹配原则和解决冲突的方法,选择最长的输入序列进行匹配；若几个规则与同一字符串匹配，则选择LEX源程序中第一条出现的规则。,当输入序列可以与LEX的若干个规则相匹配时，就产生了冲突。LEX用以下两条原则来解决它们：,例2.7 对于如下规则：begin printf(keyword)；a-z+printf(id)；,输入序列输出结果begin keywordbeginsid,如果上述两个规则书写位置交换，则无论输入序列是begin还是begins，结果均为id。,本次课结束,
