m6pifChapt3.ppt

国防科技大学计算机系602教研室,复习：程序语言的语法描述,几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字,国防科技大学计算机系602教研室,复习：程序语言的语法描述,*的子集U和V的连接（积）定义为UV|U 记 VVV*，称V+是V的正规闭包。,国防科技大学计算机系602教研室,复习：程序语言的语法描述,上下文无关文法的定义：一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT VN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VT VN)*开始符S至少必须在某个产生式的左部出现一次。,国防科技大学计算机系602教研室,复习：程序语言的语法描述,定义：称A直接推出，即A 仅当A 是一个产生式，且，(VT VN)*。如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。,国防科技大学计算机系602教研室,通常，用 表示：从1出发，经过一步或若干步，可以推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,所以：即 或,定义：假定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，BVN 产生式形如：A B 或 A 其中：VT*；A，BVN,国防科技大学计算机系602教研室,第三章 词法分析,词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer)又称扫描器(Scanner)：执行词法分析的程序,国防科技大学计算机系602教研室,3.1 对于词法分析器的要求,一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字：如 begin，repeat，标识符表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，界符：逗号、分号、括号和空白,国防科技大学计算机系602教研室,输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。,国防科技大学计算机系602教研室,例 C程序,while(i=j)i-;输出单词符号：=,-,国防科技大学计算机系602教研室,例 FORTRAN程序,IF(5.EQ.M)GOTO 100输出单词符号：逻辑IF(34，-)左括号(2，-)整常数(20，5的二进制)等号(6，-)标识符(26，M)右括号(16，-)GOTO(30，-)标号(19，100的二进制),国防科技大学计算机系602教研室,二、词法分析器作为一个独立子程序,词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。不作为一遍：将其处理为一个子程序。,国防科技大学计算机系602教研室,词法分析器,国防科技大学计算机系602教研室,词法分析器的结构,预处理子程序,扫描器,输入缓冲区,扫描缓冲区,单词符号,输入,列表,3.2 词法分析器的设计,国防科技大学计算机系602教研室,输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区,起点 搜索指示器 指示器,一、输入、预处理,国防科技大学计算机系602教研室,WhatALongWord,WhatALongWo,rd,rd,WhatALongWo,rd,WhatALongWo,国防科技大学计算机系602教研室,二、单词符号的识别:超前搜索,1 基本字识别:例如:DO99K=1，10 DO 99 K=1，10 IF(5.EQ.M)GOTO55 IF(5.EQ.M)GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字,国防科技大学计算机系602教研室,2 标识符识别:字母开头的字母数字串，后跟界符或算符3 常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。5.EQ.M 5.E084 算符和界符的识别把多个字符符合而成的算符和界符拼合成一个单一单词符号。:=，*，.EQ.，+，-，=,国防科技大学计算机系602教研室,三、状态转换图,1 概念状态转换图是一张有限方向图。,结点代表状态，用圆圈表示。,状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。,一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。,国防科技大学计算机系602教研室,识别标识符的状态转换图,1,2,3,字母,其他,字母或数字,*,识别整常数的状态转换图,一个状态转换图可用于识别(或接受)一定的字符串。,国防科技大学计算机系602教研室,2 例子,助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,几点重要限制不必使用超前搜索所有基本字都是保留字;用户不能用它们作自己的标识符基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。DO99K=1，10 要写成 DO 99 K=1，10,国防科技大学计算机系602教研室,3 状态转换图的实现思想：每个状态结对应一小段程序。做法:1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现,GetChar();if(IsLetter()状态j的对应程序段;else if(IsDigit()状态k的对应程序段;else if(ch=/)状态l的对应程序段;else 错误处理;,国防科技大学计算机系602教研室,3 状态转换图的实现2)对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序.,GetChar();while(IsLetter()or IsDigit()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教研室,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,国防科技大学计算机系602教研室,else if(IsDigit()beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelse if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);,国防科技大学计算机系602教研室,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();/*错误处理*/,国防科技大学计算机系602教研室,3.3 正规表达式与有限自动机,几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如:设=a，b，则*=,a,b,aa,ab,ba,bb,aaa,.,国防科技大学计算机系602教研室,*的子集U和V的连接（积）定义为UV|U 记 VVV*，称V+是V的正规闭包。,国防科技大学计算机系602教研室,3.3.1 正规式和正规集,正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。,国防科技大学计算机系602教研室,冯-诺伊曼构造自然数的方案,01,2,3,国防科技大学计算机系602教研室,正规式和正规集的递归定义：对给定的字母表1)和都是上的正规式，它们所表示的正规集为和;2)任何a，a是上的正规式，它所表示的正规集为a;,