第78章编译概述语法分析.ppt

第78章编译概述语法分析现在学习的是第1页，共64页二.编译执行和解释执行1.编译执行 源程序 目标程序 计算结果 汇编语言程序 目标程序 2.解释执行:一边翻译一边解释执行编译编译运行汇编程序初始数据现在学习的是第2页，共64页三.编译程序的组成1.词法分析、语法分析、语义分析、优化、目标代码生成、符号表管理、出错处理。2.相互关系如下图：现在学习的是第3页，共64页源程序字符串词法分析器语法分析器语义分析、中间代码生成器代码优化器目标代码生成器单词流语法单位中间代码序列中间代码序列目标程序符 号 表 管 理 程 序出 错 处 理 程 序编译程序的结构编译程序的结构现在学习的是第4页，共64页1.1.词法分析词法分析词法分析词法分析:1）输入字符串，根据词法规则识别出单词符号。2）二元式结果（单词类别、单词属性）3）记号（Token）：基本字、标识符、常数、运算符、界符4）词法出错处理现在学习的是第5页，共64页2.语法分析语法分析语法分析语法分析:根据语法规则，将单词符号构成各类语法单位，并进行语法检查。例：语法单位中有表达式、短语、句子、程序等等。现在学习的是第6页，共64页3.语义分析与代码生成语义分析与代码生成:1）根据语义规则,进行初步实质性翻译。2）中间代码（对应抽象机）现在学习的是第7页，共64页4.优化优化:对中间代码进行等价变换,以使代码更有效。时间与空间5.目标代码生成目标代码生成:生成机器语言程序或汇编语言程序。现在学习的是第8页，共64页6.符号表管理符号表管理符号表管理符号表管理:完成符号表的建立,查找,更新。7.出错处理出错处理出错处理出错处理报告错误性质和出错的地点限制错误的影响到尽可能小的范围，便于其它部分继续编译。现在学习的是第9页，共64页一一 对词法分析器的要求对词法分析器的要求1.词法分析器的功能和输出形式词法分析器的功能和输出形式功功能能：输输入入源源程程序序，输输出出单单词词符符号号。单单词词符符号号是一个程序语言的基本语法符号。是一个程序语言的基本语法符号。第8章 词法分析现在学习的是第10页，共64页程序语言的单词符号一般可分为下列五种：程序语言的单词符号一般可分为下列五种：关关键键字字：具具有有固固定定意意义义的的标标识识符符，称称为为保保留留字字或或基基本本字字。如如begin,end,if ，通通常常不不用用作一般标识符。作一般标识符。标标识识符符：表表示示各各种种名名字字，如如变变量量名名、数数组组名名、过程名过程名现在学习的是第11页，共64页 常数：常数：其类型一般有整型、实型、布尔、文字等。如其类型一般有整型、实型、布尔、文字等。如100、3.14159、TRUE、sample 运运算算符符：分分为为算算术术运运算算符符（如如：、*、/等等），逻逻辑辑运运算算符符（如如：not、and、or），关关系系运运算算符符（如如：、=、=j)i;可转换为如下序列：可转换为如下序列：=，现在学习的是第17页，共64页词法分析程序的实现方式词法分析程序的实现方式完全独立方式完全独立方式：词法分析程序作为：词法分析程序作为单独一趟单独一趟来实现。来实现。词法分析程序读入整个源程序，它的输出作为语法词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。分析程序的输入。相对独立方式相对独立方式：把词法分析程序作为语法分析程：把词法分析程序作为语法分析程序的一个独立序的一个独立子程序子程序。语法分析程序需要新符号时调。语法分析程序需要新符号时调用这个子程序。用这个子程序。2.词法分析器作为一个独立子程序词法分析器作为一个独立子程序现在学习的是第18页，共64页完全独立方式完全独立方式采用词法分析工作完全独立的原因：采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性简化设计，降低语法分析的复杂性提高编译效率提高编译效率增加编译系统的可移植性增加编译系统的可移植性 源程序词法分析程序语法分析程序属性字序列属性字序列.现在学习的是第19页，共64页相对独立方式相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。用这种方式。词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.现在学习的是第20页，共64页1.单词符号的识别：超前搜索单词符号的识别：超前搜索1 基本字识别:例如:1 DO99K=1，10 DO 99 K=1，10 2 IF(5.EQ.M)GOTO55 IF(5.EQ.M)GOTO 553 DO99K=1.104 IF(5)=55需要超前搜索才能确定哪些是基本字词法分析程序在读取单词时，为了判断是否已读入整词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓取的字符来判别，即所谓超前搜索技术超前搜索技术。二、二、词法分析器的设计词法分析器的设计现在学习的是第21页，共64页 标识符标识符字字母母开开头头的的“字字母母/数数字字”串串。由由于于后后跟跟算算符符或或界界符符，所所以以容易识别。容易识别。常数常数如如FORTRAN的的5.E08与与5.EQ.M也必须超前搜索。也必须超前搜索。算符和界符算符和界符多多字字符符复复合合而而成成的的算算符符与与界界符符(如如:=，*，.EQ.，+，-，=等等)拼拼合合成成一一个个单单词词符符号号。是是不不可可分分的的整整体体，同同样样需要需要超前搜索。超前搜索。现在学习的是第22页，共64页2.状态转换图状态转换图设计词法分析器的一个好工具设计词法分析器的一个好工具状态转换图是一张有限方向图。213XY结点代表状态，用圆圈表示结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的状态之间用箭弧连结，箭弧上的标记标记(字符字符)代表射出结状态下可代表射出结状态下可能出现的输入字符或字符类。能出现的输入字符或字符类。一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。有一个为初态，至少要有一个终态。现在学习的是第23页，共64页状态转换图可用于识别状态转换图可用于识别/接受一定的字符串：接受一定的字符串：210字母字母或数字其它*(a)标识符的识别标识符的识别210数字 数字其它*(b)整数的识别整数的识别1072345数字数字数字.E或D+或-数字数字其它*6.数字E或D数字其它(c)Fortran实常实常数的识别数的识别现在学习的是第24页，共64页几点重要限制几点重要限制不必使用超前搜索不必使用超前搜索所所有有基基本本字字都都是是保保留留字字;用用户户不不能能用用它它们们作作自自己的标识符己的标识符基基本本字字作作为为特特殊殊的的标标识识符符来来处处理理;不不用用特特殊殊的的状态图来识别，只要查保留字表。状态图来识别，只要查保留字表。如如果果基基本本字字、标标识识符符和和常常数数(或或标标号号)之之间间没没有有确确定定的的运运算算符符或或界界符符作作间间隔隔，则则必必须须使使用用一一个个空白符作间隔。空白符作间隔。DO99K=1，10 要写成要写成 DO 99 K=1，10现在学习的是第25页，共64页123456789101112130空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字=+*非非*,()其它其它*现在学习的是第26页，共64页状态转换图的实现状态转换图的实现思想：每个状态结思想：每个状态结点点对应一小段程序。对应一小段程序。做法做法:1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASE语句或语句或一组一组IF-THEN-ELSE语句实现语句实现GetChar();if(IsLetter()状态状态j的对应程序的对应程序段段;else if(IsDigit()状态状态k的对应的对应程序段程序段;else if(ch=/)状态状态l的对应程的对应程序段序段;else 错误处理错误处理;ijkl字母字母数字数字/现在学习的是第27页，共64页2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILE结构和结构和IF语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar();while(IsLetter()or IsDigit()GetChar();状态状态j的对应程序段的对应程序段3)终态结点终态结点表示识别出某种单词符号表示识别出某种单词符号，因此，对，因此，对应语句为应语句为 RETURN(C，VAL)其中，其中，C为单词种别，为单词种别，VAL为单词自身值为单词自身值.现在学习的是第28页，共64页全局变量与过程全局变量与过程1)ch 字符变量、存放最新读入的源程序字字符变量、存放最新读入的源程序字符符2)strToken 字符数组，存放构成单词符号字符数组，存放构成单词符号的字符串的字符串3)GetChar 子程序过程，把下一个字符读子程序过程，把下一个字符读入到入到 ch 中中4)GetBC 子程序过程，跳过空白符，直至子程序过程，跳过空白符，直至 ch 中读入一非空白符中读入一非空白符5)Concat 子程序，把子程序，把ch中的字符连接到中的字符连接到 strToken 现在学习的是第29页，共64页6)IsLetter和和 IsDisgital 布尔函数，判断布尔函数，判断ch中字符是否为字母中字符是否为字母和数字和数字7)Reserve 整型函数，对于整型函数，对于 strToken 中的中的字符串查找保留字表，字符串查找保留字表，若它是若它是保留字则给保留字则给出它的编码出它的编码，否则回送，否则回送08)Retract 子程序，把搜索指针回调一个字子程序，把搜索指针回调一个字符位置符位置9)InsertId 整型函数，将整型函数，将strToken中的标识中的标识符插入符号表，返回符号表指针符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将整型函数过程，将strToken中的常数插入常数表，返回常数中的常数插入常数表，返回常数表指针。表指针。现在学习的是第30页，共64页int code,value;strToken:=“”;/*置置strToken为空串为空串*/GetChar();GetBC();if(IsLetter()beginwhile(IsLetter()or IsDigit()beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalue:=InsertId(strToken);return($ID,value);endelsereturn(code,-);end现在学习的是第31页，共64页else if(IsDigit()beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);retrnr($INT,value);endelse if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);现在学习的是第32页，共64页else if(ch=*)beginGetChar();if(ch=*)return($POWER,-);Retract();return($STAR,-);endelse if(ch=;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else ProcError();/*错误处理错误处理*/现在学习的是第33页，共64页非法字符不合规则的常数标识符前缀为保留字3.词法错误检查词法错误检查现在学习的是第34页，共64页35编编译译过过程程中中编编译译程程序序需需要要不不断断汇汇集集和和反反复复查查证证出出现现在在源源程程序序中中各各种种名名字字的的属属性性和和特特征征等等有有关关信信息息。这这些些信信息息通通常常记记录录在在一一张张或或多多张张符符号号表表中中，每每一一项项分分两两部部分分：名名字字(标标识识符符)和和此此名名字字的的有有关关信信息息。每每个个名名字字的的有有关关信信息息一一般般指指种种属属(如如简简单单变变量量、数数组组、过过程程等等)、类类型型(如如整整、实实、布布尔尔等等)等等等等。这这些些信信息息将将用用于于语语义义检检查查、产产生生中中间间代代码码以以及及最最终终生生成成目目标标代代码码等等阶段。阶段。现在学习的是第35页，共64页36在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法在分析过程中不断积累和更新表中的信息，并在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。不论编译策略是否分趟，符号表的作用和地位是完全一致的。收集符号属性收集符号属性 上下文语义的合法性检查的依据上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据 现在学习的是第36页，共64页37收集符号属性收集符号属性 编译程序扫描说明部分收集有关标识符的属性，并在符号表中建立符号的相应属性信息。例如，编译程序分析到下述两个说明语句int A;float B5;现在学习的是第37页，共64页38上下文语义的合法性检查的依据上下文语义的合法性检查的依据 同一个标识符可能在程序的不同地方出现，而有关该符号的属性是在这些不同情况下收集的。特别是在多趟编译及程序分段编译（在PASCAL及C中以文件为单位）的情况下，更需检查标识符属性在上下文中的一致性和合法性。通过符号表中属性记录可进行相应上下文的语义检查。例如，在一个C语言程序中出现int i 3,5;/定义整型数组ifloat i4,2;/定义实型数组i,重定义冲突int i 3,5;/定义整型数组i,重定义冲突 现在学习的是第38页，共64页39 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据 每个符号变量在目标代码生成时需要确定其在存储分配的位置（主要是相对位置）。首先要确定其被分配的区域。在C语言中首先要确定该符号变量是分配在公共区（extern）、文 件静态区（extern static）、函数静态区（函数中static）、还是函数运行时的动态区（auto）等。其次是根据变量出现的次序决定该变量在某个区中所处的具体位置，这通常使用在该区域中相对区头的相对位置确定。而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中。现在学习的是第39页，共64页408.1 8.1 8.1 8.1 符号表的组织与作用符号表的组织与作用符号表的组织与作用符号表的组织与作用在在编编译译的的各各个个分分析析阶阶段段，每每当当遇遇到到一一个个名名字字都都要要查查找找符符号号表表。若若是是新新名名字字或或发发现现已已有有名名字字的的新新信信息息，则则要要加加入入(填填入入)。因因此此，合合理理组组织织符符号号表表，使使其其存存储储占占用用最最少少，同同时时提提高高编编译译期期间间对对符符号号表表的的访访问问效效率率，至关重要。至关重要。一、符号表的作用一、符号表的作用现在学习的是第40页，共64页41概括地说，符号表的每一项(或称入口)包含两大栏(或称区段、字域)，即名名字字栏栏和信信息息栏栏。表格的形式如下：第1项(入口1)第2项(入口2)第n项(入口n)名字栏(NAME)信息栏(INFORMATION)现在学习的是第41页，共64页42信息栏包含许多子栏和标志位，记录相应名字的种种不同属性。由于查填符号表一般是通过匹配名字来实现的，故名字栏也称主主栏栏，其内容称为关键字关键字(keyword)。符号表中每一项都是关于名字的说明。因为所保存的关于名字的信息取决于名字的用途，所以各表项的格式不一定统一，为使表中的每个记录格式统一，可采用指针技术，在记录中设置指针，把某些信息放在表的外边，用指针指向存放另外信息的空间。现在学习的是第42页，共64页43对符号表的操作大致可以分为五类：对符号表的操作大致可以分为五类：查询某个名字是否已在表中。查询某个名字是否已在表中。填入一个新的名字。填入一个新的名字。添加或更新某个名字的某些信息。添加或更新某个名字的某些信息。删除一个或一组无用的项。删除一个或一组无用的项。访问某个名字的某些信息。访问某个名字的某些信息。现在学习的是第43页，共64页44对符号表进行操作的时机：对符号表进行操作的时机：定义性出现定义性出现使用性出现使用性出现按名字的不同种属建立多张符号表，如常按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表、数表、变量名表、过程名表、符号的组织方式符号的组织方式:1.1.安排各项各栏的存储单元为固定长度安排各项各栏的存储单元为固定长度2.2.用间接方式安排各栏存储单元用间接方式安排各栏存储单元现在学习的是第44页，共64页45最最简简单单的的组组织织方方式式：各项各栏长度固定易于组织、填写和查找。这种表格，每一栏的内容可直接填写在有关的区段内。例例如如，对于名字栏，其大小可按标识符最大允许长度来确定。如标准FORTRAN语言规定每一标识符不得超过6个字符，因此就可用6个字符的空间作为名字栏的长度。若标识符长度不足6个字符，则以空白符补齐。二、符号表的组织方式二、符号表的组织方式现在学习的是第45页，共64页46但是，有许多语言对标识符的长度几乎不加以限制，或者说，标识符的长度范围很宽。比如说，最长可允许由100个字符组成的名字。此时，如果名字栏的长度设为100个字符，则势必会大量浪费存储空间。因此，最好采用指针技术。用另外一独立的字符串数组，把所有标识符都存放其中。在符号表的主栏放一指示器和一整数，或仅放一指示器，同时在标识符前放一个整数。指示器指出标识符在字符串数组中的位置；整数代表此标识符的长度。现在学习的是第46页，共64页47SAMPLELOOPINFORMATIONNAME，6，4在符号表的主栏放一指示器和一整数现在学习的是第47页，共64页48INFORMATIONNAME6SAMPLE4LOOP在符号表的主栏放一指示器，同时在标识符前放一个整数现在学习的是第48页，共64页49 类似地，如果各种名字所需的信息空间长短不一，则将共同属性直接登记在信息栏中，而特殊属性登记在别的地方。在信息栏中附设一指示器，指向存放特殊属性的地方。例如对于数组标识符，需存储的信息包含维数等，如果将它们与其它名字全部集中在一张符号表中，处理起来很不方便。因此，常另辟一个信息表区，称数组信息表(或内内情情向向量量表)，用来保存数组的有关信息。在符号表的地址栏内存入符号表与内情向量表连接的入口地址。当填写或查询数组有关信息时，通过符号表来访问此内情向量表。现在学习的是第49页，共64页50 对过程名以及其它一些含信息较多的名字，都可类似地开辟专用信息表，存放那些不宜全部存放在符号表中的信息，而在符号表中保留与信息表相联系的地址信息。现在学习的是第50页，共64页51 在编译时，虽然从原则上说，使用一张统一的符号表就够了。但许多编译程序按名字的不同种属分别使用许多符号表。如常数表、变量名表、过程名表等等。这是因为，不同种属名字的相应信息往往不同，信息栏的长度也各有差异。因而，按不同种属建立不同的符号表在处理上常常是比较方便的。现在学习的是第51页，共64页52例例:PASCAL:PASCAL程序段：程序段：PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.现在学习的是第52页，共64页53PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.现在学习的是第53页，共64页54PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.现在学习的是第54页，共64页55PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.现在学习的是第55页，共64页56PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.现在学习的是第56页，共64页57现在学习的是第57页，共64页58PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.现在学习的是第58页，共64页598.2 8.2 8.2 8.2 整理与查找整理与查找整理与查找整理与查找构造符号表最简单、最容易的办法是按关键字出现的顺序依次填写各个项。用一个一维数组或多个一维数组来存放名字及有关信息。当碰到一个新名字时就按顺序将它填入表中，若需要了解一个名字的有关信息，则就从第一项开始顺序查找。这种构 造 方 式 称 为 线 性 表，其 结 构 如 下：(其 中AVAILABLE总是指向空白区的首地址)一、线性表一、线性表现在学习的是第59页，共64页60项数1AVAILABLE234NAMEINFORMATIONJ1XYZIBC现在学习的是第60页，共64页61线性表中每一项的先后顺序是按先来者先填的原则安排的，编译程序不做任何整理次序的工作。如果是显式说明的程序设计语言，则根据各名字在说明部分出现的先后顺序填入表中(表尾)；如果是隐式说明的程序设计语言，则根据各名字首次引用的先后顺序填入表中。当需要查找某个名字时，就从第一项开始顺序查找，若一直查到AVAILABLE还未找到这个名字，就说明该名字不在表中。现在学习的是第61页，共64页62按照编程习惯，新定义的名字往往要立即使用。所以，反序查找效率也许更高。当需要填进一个新说明的名字时，必须先对这个名字进行查找，如果已在表中，则不重新填入(通常要报告重名错误)。如果不在表中，则填入AVAILABLE所指位置，然后累增AVAILABLE，使其指向下一空白项的单元地址。现在学习的是第62页，共64页63对一张含N项的线性表，欲从中查找一项，则平均比较次数为 n/2，所以效率很低，但由于结构简单且节省存储空间，所以许多编译程序仍采用。提高效率方法之一：提高效率方法之一：每项附设一指示器，按“最新最近”访问原则，建立一链表，使得在任何时候，链的第一元素指向最新最近查询过的项自适应线性表。现在学习的是第63页，共64页64按名字大小建立有序表，则可采用对折查找法(折半查找)最多比较次数 1+log2N(对数查找)。要保持有序，需要每次填入新名字时都进行排序，因此采用二叉树组织法，左大右小。查找效率比对折查找低了一些，且所需存储空间增大，但其所需顺序化的时间要少得多，且比较次数仍和log2N 成比例，因此可取。二、对折查找与二叉树二、对折查找与二叉树现在学习的是第64页，共64页