编译概述语法分析

编译概述语法分析三、编译程序得组成词法分析、语法分析、语义分析、优化、目标代码生成、符号表管理、出错处理。相互关系如下图:源程序字符串词法分析器语法分析器语义分析、中间代码生成器代码优化器目标代码生成器单词流语法单位中间代码序列中间代码序列目标程序符号表管理程序出错处理程序编译程序得结构词法分析: 1)输入字符串,根据词法规则识别出单词符号。

2)二元式结果(单词类别、单词属性)

3)记号(Token):基本字、标识符、常数、运算符、界符

4)词法出错处理2、语法分析:

根据语法规则,将单词符号构成各类语法单位,并进行语法检查。 例:语法单位中有表达式、短语、句子、程序等等。3、语义分析与代码生成: 1)根据语义规则,进行初步实质性翻译。

2)中间代码(对应抽象机)4、优化:对中间代码进行等价变换,以使代码更有效。时间与空间5、目标代码生成:生成机器语言程序或汇编语言程序。6、符号表管理:完成符号表得建立,查找,更新。7、出错处理报告错误性质与出错得地点限制错误得影响到尽可能小得范围,便于其它部分继续编译。§一对词法分析器得要求1、词法分析器得功能与输出形式功能:输入源程序,输出单词符号。单词符号就是一个程序语言得基本语法符号。第8章词法分析程序语言得单词符号一般可分为下列五种:

关键字:具有固定意义得标识符,称为保留字或基本字。如begin,end,if…,通常不用作一般标识符。

标识符:表示各种名字,如变量名、数组名、过程名……

常数:其类型一般有整型、实型、布尔、文字等。如100、3、14159、TRUE、’sample’

运算符:分为算术运算符(如:＋、－、*、/等),逻辑运算符(如:not、and、or),关系运算符(如:<、>、>=、<=、=)等。

界符:逗号,分号,括号,/,/等。一个程序语言得关键字、运算符与界符都就是确定得,一般只有几十个或上百个,标识符与常数则不受限制。大家有疑问的，可以询问和交流可以互相讨论下，但要小声点常采用二元式来表示识别出得单词符号:(单词种别,单词符号得属性值)

单词种别通常用整数编码,如何分种,怎样编码,取决于处理得方便性。标识符一般统归一种常数按类关键字:全体为一种或一字一种运算符:一符一种,或具有共性得为一种界符:一符一种Sample语言得单词编码

对一符一种,可不需属性,但多符一种时必须要有属性信息,属性反映单词符号得特性或特征,而属性值反映特性或特征得值。例如:对标识符,其属性值可为存放它得有关信息得符号表项得指针。若假定关键字、运算符、界符都就是一符一种,标识符单列一种,常数按类,则代码段:while(i>=j)i––;可转换为如下序列: <while,–>

<(,–>

<id,指向i得符号表项得指针>

<>=,–>

<id,指向j得符号表项得指针>

<),–>

<id,指向i得符号表项得指针>

<––,–>

<;,–>词法分析程序得实现方式完全独立方式:词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序,它得输出作为语法分析程序得输入。相对独立方式:把词法分析程序作为语法分析程序得一个独立子程序。语法分析程序需要新符号时调用这个子程序。2、词法分析器作为一个独立子程序完全独立方式采用词法分析工作完全独立得原因:简化设计,降低语法分析得复杂性提高编译效率增加编译系统得可移植性源程序词法分析程序语法分析程序属性字序列…、相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。词法分析器语法分析器符号表源程序单词符号取下一单词...1、单词符号得识别:超前搜索1基本字识别:例如:1DO99K=1,10 DO99K=1,102IF(5、EQ、M)GOTO55IF(5、EQ、M)GOTO553DO99K=1、104IF(5)=55需要超前搜索才能确定哪些就是基本字词法分析程序在读取单词时,为了判断就是否已读入整个单词得全部字符,常采取向前多读取字符并通过读取得字符来判别,即所谓超前搜索技术。二、词法分析器得设计

标识符字母开头得“字母/数字”串。由于后跟算符或界符,所以容易识别。

常数如FORTRAN得5、E08与5、EQ、M也必须超前搜索。

算符与界符多字符复合而成得算符与界符(如:=,**,、EQ、,++,--,>=等)拼合成一个单词符号。就是不可分得整体,同样需要超前搜索。2、状态转换图——设计词法分析器得一个好工具状态转换图就是一张有限方向图。213XY结点代表状态,用圆圈表示。状态之间用箭弧连结,箭弧上得标记(字符)代表射出结状态下可能出现得输入字符或字符类。一张转换图只包含有限个状态,其中有一个为初态,至少要有一个终态。状态转换图可用于识别/接受一定得字符串:210字母字母或数字其它*(a)标识符的识别210数字

数字其它*(b)整数的识别1072345数字数字数字.E或D+或-数字数字其它*6.数字E或D数字其它(c)Fortran实常数的识别几点重要限制——不必使用超前搜索所有基本字都就是保留字;用户不能用它们作自己得标识符基本字作为特殊得标识符来处理;不用特殊得状态图来识别,只要查保留字表。如果基本字、标识符与常数(或标号)之间没有确定得运算符或界符作间隔,则必须使用一个空白符作间隔。

DO99K=1,10

要写成DO99K=1,10123456789101112130空白字母字母或数字非字母与数字数字非数字数字=+*非*,()其它****状态转换图得实现思想:每个状态结点对应一小段程序。做法:1)对不含回路得分叉结,可用一个CASE语句或一组IF-THEN-ELSE语句实现GetChar();if(IsLetter()){…状态j得对应程序段…;}elseif(IsDigit()){…状态k得对应程序段…;}elseif(ch=‘/’){…状态l得对应程序段…;}else{…错误处理…;}ijkl字母数字/2)对含回路得状态结,可对应一段由WHILE结构与IF语句构成得程序、i字母或数字其它jGetChar();while(IsLetter()orIsDigit()) GetChar();…状态j得对应程序段…3)终态结点表示识别出某种单词符号,因此,对应语句为

RETURN(C,VAL)

其中,C为单词种别,VAL为单词自身值、全局变量与过程1)ch字符变量、存放最新读入得源程序字符2)strToken字符数组,存放构成单词符号得字符串3)GetChar子程序过程,把下一个字符读入到ch中4)GetBC子程序过程,跳过空白符,直至ch中读入一非空白符5)Concat子程序,把ch中得字符连接到strToken6)IsLetter与IsDisgital布尔函数,判断ch中字符就是否为字母与数字7)Reserve整型函数,对于strToken中得字符串查找保留字表,若它就是保留字则给出它得编码,否则回送08)Retract子程序,把搜索指针回调一个字符位置9)InsertId整型函数,将strToken中得标识符插入符号表,返回符号表指针10)InsertConst整型函数过程,将strToken中得常数插入常数表,返回常数表指针。intcode,value;strToken:=“”; /*置strToken为空串*/GetChar();GetBC();if(IsLetter())begin while(IsLetter()orIsDigit()) begin Concat();GetChar(); end Retract(); code:=Reserve(); if(code=0) begin value:=InsertId(strToken); return($ID,value); end else return(code,-); endelseif(IsDigit())begin while(IsDigit()) begin Concat();GetChar(); end Retract(); value:=InsertConst(strToken); retrnr($INT,value);endelseif(ch=‘=’)return($ASSIGN,-);elseif(ch=‘+’)return($PLUS,-);elseif(ch=‘*’)begin GetChar(); if(ch=‘*’)return($POWER,-); Retract();return($STAR,-);endelseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseProcError(); /*错误处理*/非法字符不合规则得常数标识符前缀为保留字3、词法错误检查35编译过程中编译程序需要不断汇集与反复查证出现在源程序中各种名字得属性与特征等有关信息。这些信息通常记录在一张或多张符号表中,每一项分两部分:名字(标识符)与此名字得有关信息。每个名字得有关信息一般指种属(如简单变量、数组、过程等)、类型(如整、实、布尔等)等等。这些信息将用于语义检查、产生中间代码以及最终生成目标代码等阶段。36在编译程序中符号表用来存放语言程序中出现得有关标识符得属性信息,这些信息集中反映了标识符得语义特征属性。在词法分析及语法在分析过程中不断积累与更新表中得信息,并在词法分析到代码生成得各阶段,按各自得需要从表中获取不同得属性信息。不论编译策略就是否分趟,符号表得作用与地位就是完全一致得。

①收集符号属性

②上下文语义得合法性检查得依据

③作为目标代码生成阶段地址分配得依据

37收集符号属性

编译程序扫描说明部分收集有关标识符得属性,并在符号表中建立符号得相应属性信息。例如,编译程序分析到下述两个说明语句

intA;

floatB[5];

38上下文语义得合法性检查得依据同一个标识符可能在程序得不同地方出现,而有关该符号得属性就是在这些不同情况下收集得。特别就是在多趟编译及程序分段编译(在PASCAL及C中以文件为单位)得情况下,更需检查标识符属性在上下文中得一致性与合法性。通过符号表中属性记录可进行相应上下文得语义检查。

例如,在一个C语言程序中出现

…

inti[3,5];//定义整型数组i

…

floati[4,2];//定义实型数组i,重定义冲突

…

inti[3,5];//定义整型数组i,重定义冲突39③作为目标代码生成阶段地址分配得依据

每个符号变量在目标代码生成时需要确定其在存储分配得位置(主要就是相对位置)。首先要确定其被分配得区域。在C语言中首先要确定该符号变量就是分配在公共区(extern)、文件静态区(externstatic)、函数静态区(函数中static)、还就是函数运行时得动态区(auto)等。其次就是根据变量出现得次序决定该变量在某个区中所处得具体位置,这通常使用在该区域中相对区头得相对位置确定。而有关区域得标志及相对位置都就是作为该变量得语义信息被收集在该变量得符号表属性中。40§8、1符号表得组织与作用在编译得各个分析阶段,每当遇到一个名字都要查找符号表。若就是新名字或发现已有名字得新信息,则要加入(填入)。因此,合理组织符号表,使其存储占用最少,同时提高编译期间对符号表得访问效率,至关重要。一、符号表的作用41概括地说,符号表得每一项(或称入口)包含两大栏(或称区段、字域),即名字栏与信息栏。表格得形式如下:第1项(入口1)第2项(入口2)第n项(入口n)名字栏(NAME)信息栏(INFORMATION)…42信息栏包含许多子栏与标志位,记录相应名字得种种不同属性。由于查填符号表一般就是通过匹配名字来实现得,故名字栏也称主栏,其内容称为关键字(keyword)。符号表中每一项都就是关于名字得说明。因为所保存得关于名字得信息取决于名字得用途,所以各表项得格式不一定统一,为使表中得每个记录格式统一,可采用指针技术,在记录中设置指针,把某些信息放在表得外边,用指针指向存放另外信息得空间。43对符号表得操作大致可以分为五类:·查询某个名字就是否已在表中。·填入一个新得名字。·添加或更新某个名字得某些信息。·删除一个或一组无用得项。·访问某个名字得某些信息。44对符号表进行操作得时机:定义性出现使用性出现按名字得不同种属建立多张符号表,如常数表、变量名表、过程名表、…符号得组织方式:1、安排各项各栏得存储单元为固定长度2、用间接方式安排各栏存储单元45最简单得组织方式:各项各栏长度固定——易于组织、填写与查找。这种表格,每一栏得内容可直接填写在有关得区段内。例如,对于名字栏,其大小可按标识符最大允许长度来确定。如标准FORTRAN语言规定每一标识符不得超过6个字符,因此就可用6个字符得空间作为名字栏得长度。若标识符长度不足6个字符,则以空白符补齐。二、符号表得组织方式46但就是,有许多语言对标识符得长度几乎不加以限制,或者说,标识符得长度范围很宽。比如说,最长可允许由100个字符组成得名字。此时,如果名字栏得长度设为100个字符,则势必会大量浪费存储空间。因此,最好采用指针技术。用另外一独立得字符串数组,把所有标识符都存放其中。在符号表得主栏放一指示器与一整数,或仅放一指示器,同时在标识符前放一个整数。指示器指出标识符在字符串数组中得位置;整数代表此标识符得长度。47SAMPLELOOPINFORMATIONNAME，6，4在符号表得主栏放一指示器与一整数48INFORMATIONNAME6SAMPLE4LOOP在符号表得主栏放一指示器,同时在标识符前放一个整数49

类似地,如果各种名字所需得信息空间长短不一,则将共同属性直接登记在信息栏中,而特殊属性登记在别得地方。在信息栏中附设一指示器,指向存放特殊属性得地方。

例如对于数组标识符,需存储得信息包含维数等,如果将它们与其它名字全部集中在一张符号表中,处理起来很不方便。因此,常另辟一个信息表区,称数组信息表(或内情向量表),用来保存数组得有关信息。在符号表得地址栏内存入符号表与内情向量表连接得入口地址。当填写或查询数组有关信息时,通过符号表来访问此内情向量表。50

对过程名以及其它一些含信息较多得名字,都可类似地开辟专用信息表,存放那些不宜全部存放在符号表中得信息,而在符号表中保留与信息表相联系得地址信息。51

在编译时,虽然从原则上说,使用一张统一得符号表就够了。但许多编译程序按名字得不同种属分别使用许多符号表。如常数表、变量名表、过程名表等等。这就是因为,不同种属名字得相应信息往往不同,信息栏得长度也各有差异。因而,按不同种属建立不同得符号表在处理上常常就是比较方便得。52例:PASCAL程序段:PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END、53PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END、54PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END、55PROCEDUREINCWAP(M,N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART: