《词法分析周》PPT课件.ppt

第三章 词法分析,概述,编译程序首先是在单词级别上来分析和翻译源程序的。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析是编译的基础。执行词法分析的程序称为词法分析器。,内容线索,对于词法分析器的要求词法分析器的设计正规表达式与有限自动机词法分析器的自动生成,词法分析器的功能,源程序,扫描器scanner,1、关键字,2、标识符,5、界符,4、运算符,3、常数,由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：C中的int，while，if等。它是确定的。,界符：如逗号、分号、括号、/*，*/等。它是确定的。,运算符：如+、-、*、/等。它是确定的。,常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。,用来表示各种名字，如变量名、数组名、过程名等。它是不限的。,单词符号,单词符号表示形式,词法分析器输出的单词符号常表示成二元式：(单词种别,单词符号的属性值)单词种别是语法分析需要的信息单词符号属性值则是编译其它阶段需要的信息,简称单词值。例.语句const i=25,yes=1，其中，单词25和1的类别都是常数，其值分别为25和1；,分类方法,单词种别:通常用整数编码。一个语言的单词符号如何分类，分成几类，怎样编码取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一类。至于界符一般用一符一种的分法。,单词符号的属性,单词符号的属性是指单词符号的特征或特性。属性值则是反映特性或特征的值。标识符的属性值是存放它符号表项的指针或内部字符串；常数的属性值是存放它的常数表项的指针或二进制形式；关键字、运算符和界符是一符一种，不需给出其自身的值。,例.代码段 while(i=j)i-;词法分析结果,=,逻辑IF（34，_）左括号（2，_）整常数（20，5的二进制表示）等号（6，_）标识符（26，M）右括号（16，_）GOTO（30，_）标号（19，100的二进制表示）,IF为关键字，种别编码34，采用一符一种的编码方式。,常数类型，种别编码20，单词自身的值为5的二进制表示。,(为界符，种别编码2，采用一符一种的编码方式。,等号为运算符，种别编码6，采用一符一种的编码方式。,M为标识符，种别编码26，单词自身值为M。,)为界符，种别编码16，采用一符一种的编码方式。,GOTO为关键字，种别编码30，采用一符一种的编码方式。,100为标号，种别编码19，单词内部的值用100的二进制表示。,FORTRAN编译程序的词法分析器在扫描输入串 IF(5EQM)GOTO 100 后，它输出的单词符号串是：,FORTRAN编译实例,词法分析程序的实现方式,完全独立方式：词法分析程序作为单独一遍来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。编译程序结构简洁、清晰和条理化相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。优点：避免了中间文件生成，可以提高效率。,内容线索,对于词法分析器的要求词法分析器的设计正规表达式与有限自动机词法分析器的自动生成,词法分析器的结构,预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。,预处理子程序,输入缓冲区,源程序,扫描器,单词符号,扫描缓冲区,单词符号的识别：超前搜索,关键字识别 例.在标准FORTRAN中四个合法句子：1、DO99K=1,10 2、IF(5.EQ.M)I=10 3、DO99K=1.10 4、IF(5)=55,其中的DO、IF为关键字,其中的DO、IF为标识符的一部分,单词符号的识别：超前搜索,标识符的识别多数语言的标识符是字母开头的“字母/数字”串，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。常数的识别对于某些语言的常数的识别也需要使用超前搜索。算符和界符的识别对于诸如C+语言中的“+”、“-”，这种复合成的算符，需要超前搜索。,状态转换图,大多数程序设计语言中单词符号的词法规则可以用正规文法描述。如：字母|字母|数字 数字|数字+|;|,|(|)|利用这些规则识别单词符号的过程可用一张称为状态转换图的有限方向图来表示，而状态转换图识别单词符号的过程又可以方便地用程序实现。,状态转换图定义,转换图：是一个有限方向图。结点代表状态，用圆圈表示。初态：一张转换图的启动条件，通常有一个,用圆圈表示。终态：一张转换图的结束条件，至少有一个，用双圈表示。状态之间用方向弧连接。弧上的标记（字符）代表在出射结点状态下可能出现的输入字符或字符类。状态转换图中只包含有限个状态（结点）,在状态1下，若输入字符为X，则读进X并转换到状态2；若输入字符为Y则读进Y并转换到状态3，输入字符Z，状态仍为1。,状态转换图的作用,一个状态转换图可用于接受（或识别）一定的符号串。路:在状态转换图中从初始状态到某一终止状态的弧上的标记序列。对于某一符号串，在状态转换图中，若存在一条路产生，则称状态转换图接受（或识别）该符号串，否则称符号串不能被接受。,状态转换图所能识别的语言,能被状态转换图TG接受的符号串的集合记为L(TG)，我们称它为状态转换图所能识别的语言。,L(TG)=0，1，00，01，11，001，010，,L(TG)=a，b，ab，ba，aaa，bbb，aab，bba，,状态转换图示例,大多数程序语言的单词符号都可以用状态转换图予以识别。,2,0,1,字母,其他,字母或数字,*,（b）识别标识符的转换图,初态,终态,从0状态到1状态可能出现字母,意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串,a.b a.b E(或D)d a.b(a,b,d 为整数常数)a.Ed.b Ed a.bE d aEd,0,1,2,3,4,5,7,数字,.,数字,.,数字,其它,数字,E/D,E/D,+/-,数字,数字,其它,数字,*,6,（d）识别FORTRAN实型常数的转换图,状态转换图识别单词符号的过程,Step1.从初态开始；Step2.从输入串中读一个字符；Step3.判明读入字符与从当前状态出发的哪条弧上 的标记相匹配，便转到相应匹配的那条弧所指向的状态；Step4.重复Step3，均不匹配时便告失败；到达终态时便识别出一个单词符号。,例.设一小语言所有单词符号及其内部表示形式,能识别小语言所有单词的状态转换图,约定（限制）:关键字为保留字;保留字作为标识符处理,并使用保留字表识别；关键字、标识符、常数间若无运算符或界限符则加一空格,0,空白,字母,1,字母或数字,2,非字母与数字,3,4,*,5,6,7,8,9,10,11,12,13,数字,数字,非数字,=,+,*,非*,*,，,(,),其它,*,*,#,状态转换图实现中的变量和过程,ch：字符变量 功能：存放当前读入字符strToken：字符数组 功能：放单词的字符串GetChar：取字符过程 功能：取下一字符到ch；搜 索指针+1GetBC：滤除空字符过程 功能：判ch=空?若是,则调用GetCharConcat：子程序过程 功能：把ch中的字符拼入strToken,IsLetter,IsDigit：布尔函数 功能：ch中为字母、数字时返回.T.Reserve：整型函数 功能：按strToken中字符串查保留字表；查到返回保留字编码;否则返回0Retract：子程序过程 功能：搜索指针回退一字符InsertId：函数 功能：将标识符插入符号表，返回符号表指针InsertConst函数 功能：将常数插入常数表，返回常数表指针,程序段,不含回路的分叉结点对应的程序段可表示为 GetChar();if(IsLetter()状态j的对应程序段 else if(IsDigit()状态k的对应程序段 else if(ch=/)状态l的对应程序段 else错误处理,i,j,k,l,字母,数字,/,程序段,含回路的状态结点对应的程序段可表示为 GetChar();While(IsLetter()or IsDigit()GetChar();状态j的对应程序段终态结点对应一条语句 return(code,value);,i,j,字母或数字,其它,i,int code,value;strToken=“”;GetChar();GetBC()；If(IsLetter()while(IsLetter()or IsDigit()Concat();GetChar();Retract();code=Reserve();if(code=0)value=InsertId(strToken);return($ID,value);else return(code,-);else if(IsDigit()while(IsDigit()Concat();GetChar();Retract();value=InsertConst(strToken);return($INT,value);,else if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);else if(ch=“*”)Getchar();if(ch=*)return($POWER,-);Retract();return($STAR,-);else if(ch=:)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else if(ch=)return($LBRACE,-);else if(ch=)return($RBRACE,-);else ProcError();,扫描器总控程序,