编译原理-国防科技大学课件Chapt3

国防科技大学计算机系602教研室复习：程序语言的语法描述几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε国防科技大学计算机系602教研室复习：程序语言的语法描述∑*的子集U和V的连接（积）定义为UV＝{|U&V}V自身的n次积记为Vn=VV…V规定V0={}，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记V＋＝VV*，称V+是V的正规闭包。国防科技大学计算机系602教研室复习：程序语言的语法描述上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。国防科技大学计算机系602教研室复习：程序语言的语法描述定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。国防科技大学计算机系602教研室通常，用表示：从1出发，经过一步或若干步，可以推出n。n1n*1用表示：从1出发，经过0步或若干步，可以推出n。*所以：即或*S},|{)(*TVSGL定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。国防科技大学计算机系602教研室复习：程序语言的语法描述最左推导：任何一步都是对中的最左非终结符进行替换。最右推导：任何一步都是对中的最右非终结符进行替换。国防科技大学计算机系602教研室复习：程序语言的语法描述用一张图表示一个句型的推导,称为语法树。E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)国防科技大学计算机系602教研室复习：程序语言的语法描述定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。国防科技大学计算机系602教研室复习：程序语言的语法描述形式语言鸟瞰0型(短语文法，图灵机)：产生式形如：其中：(VTVN)*且至少含有一个非终结符；(VTVN)*1型(上下文有关文法，线性界限自动机)：产生式形如：其中：||||，仅S例外。国防科技大学计算机系602教研室复习：程序语言的语法描述形式语言鸟瞰2型(上下文无关文法，非确定下推自动机)：产生式形如：A其中：AVN；(VTVN)*。3型(正规文法，有限自动机)：产生式形如：AB或A其中：VT*；A，BVN产生式形如：AB或A其中：VT*；A，BVN国防科技大学计算机系602教研室第三章词法分析词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(LexicalAnalyzer)又称扫描器(Scanner)：执行词法分析的程序国防科技大学计算机系602教研室3.1对于词法分析器的要求一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字：如begin，repeat，标识符——表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，界符：逗号、分号、括号和空白国防科技大学计算机系602教研室输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。国防科技大学计算机系602教研室例C程序while(i=j)i--;输出单词符号：while,-(,-id,指向i的符号表项的指针=,-id,指向j的符号表项的指针),-id,指向i的符号表项的指针--,-;,-国防科技大学计算机系602教研室例FORTRAN程序IF(5.EQ.M)GOTO100输出单词符号：逻辑IF(34，-)左括号(2，-)整常数(20，‘5’的二进制)等号(6，-)标识符(26，‘M’)右括号(16，-)GOTO(30，-)标号(19，‘100’的二进制)国防科技大学计算机系602教研室二、词法分析器作为一个独立子程序词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。不作为一遍：将其处理为一个子程序。国防科技大学计算机系602教研室词法分析器词法分析器语法分析器符号表源程序单词符号取下一单词...国防科技大学计算机系602教研室词法分析器的结构预处理子程序扫描器输入缓冲区扫描缓冲区单词符号输入列表3.2词法分析器的设计国防科技大学计算机系602教研室输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区↑↑起点搜索指示器指示器一、输入、预处理国防科技大学计算机系602教研室WhatALong…Word…WhatALong…Wordrd…WhatALong…Word…WhatALong…Wo国防科技大学计算机系602教研室二、单词符号的识别:超前搜索1基本字识别:例如:DO99K=1，10DO99K=1，10IF(5.EQ.M)GOTO55IF(5.EQ.M)GOTO55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字国防科技大学计算机系602教研室2标识符识别:字母开头的字母数字串，后跟界符或算符3常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。5.EQ.M5.E084算符和界符的识别把多个字符符合而成的算符和界符拼合成一个单一单词符号。:=，**，.EQ.，++，--，=国防科技大学计算机系602教研室三、状态转换图1概念状态转换图是一张有限方向图。213XY结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。国防科技大学计算机系602教研室识别标识符的状态转换图123字母其他字母或数字*识别整常数的状态转换图123数字其他数字*一个状态转换图可用于识别(或接受)一定的字符串。国防科技大学计算机系602教研室2例子助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。国防科技大学计算机系602教研室单词符号种别编码助忆符内码值DIM1$DIM-IF2$IF-DO3$DO-STOP4$STOP-END5$END-标识符6$ID内部字符串常数(数)7$INT标准二进制形式=8$ASSIGN-_9$PLUS-*10$STAR-**11$POWER-，12$COMMA-(13$LPAR-)14$RPAR-国防科技大学计算机系602教研室123456789101112130空白字母字母或数字非字母与数字数字非数字数字=+*非*,()其它****国防科技大学计算机系602教研室几点重要限制——不必使用超前搜索所有基本字都是保留字;用户不能用它们作自己的标识符基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。DO99K=1，10要写成DO99K=1，10国防科技大学计算机系602教研室3状态转换图的实现思想：每个状态结对应一小段程序。做法:1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现GetChar();if(IsLetter()){…状态j的对应程序段…;}elseif(IsDigit()){…状态k的对应程序段…;}elseif(ch=‘/’){…状态l的对应程序段…;}else{…错误处理…;}ijkl字母数字\国防科技大学计算机系602教研室3状态转换图的实现2)对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序.i字母或数字其它jGetChar();while(IsLetter()orIsDigit())GetChar();…状态j的对应程序段…国防科技大学计算机系602教研室3状态转换图的实现3)终态结表示识别出某种单词符号，因此，对应语句为RETURN(C，VAL)其中，C为单词种别，VAL为单词自身值.国防科技大学计算机系602教研室全局变量与过程1)ch字符变量、存放最新读入的源程序字符2)strToken字符数组，存放构成单词符号的字符串3)GetChar子程序过程，把下一个字符读入到ch中4)GetBC子程序过程，跳过空白符，直至ch中读入一非空白符5)Concat子程序，把ch中的字符连接到strToken国防科技大学计算机系602教研室6)IsLetter和IsDisgital布尔函数，判断ch中字符是否为字母和数字7)Reserve整型函数，对于strToken中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送08)Retract子程序，把搜索指针回调一个字符位置9)InsertId整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst整型函数过程，将strToken中的常数插入常数表，返回常数表指针。国防科技大学计算机系602教研室intcode,value;strToken:=“”;/*置strToken为空串*/GetChar();GetBC();if(IsLetter())beginwhile(IsLetter()orIsDigit())beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalue:=InsertId(strToken);return($ID,value);endelsereturn(code,-);end国防科技大学计算机系602教研室elseif(IsDigit())beginwhile(IsDigit())beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelseif(ch=‘=’)return($ASSIGN,-);elseif(ch=‘+’)return($PLUS,-);国防科技大学计算机系602教研室elseif(ch=‘*’)beginGetChar();if(ch=‘*’)return($POWER,-);Retract();return($STAR,-);endelseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseProcError();/*错误处理*/国防科技大学计算机系602教研室