《《词法分析副》ppt课件》由会员分享，可在线阅读，更多相关《《词法分析副》ppt课件（81页珍藏版）》请在金锄头文库上搜索。
1、第2章 词法分析,2.1 词法分析器的设计考虑及手工构造,2.1.1 单词类型及二元式编码 单词类型 基本字、标识符、常数、运算符、界符 单词的性质 个数确定和不确定 单字符或多字符构成,2.1 词法分析器的设计考虑及手工构造,单词二元式编码 经词法分析后，单词用二元式 (code,val) 表示。 code表示单词的种别，用整数码表示，在语法分析时使用。 val表示单词的值，在本书中用字符串表示，在语义分析时使用。,2.1 词法分析器的设计考虑及手工构造,编码原则 通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。,2.1 词法分析器的设计考虑及手工构造,实例-设有某一
2、程序设计语言，其部分单词二元式编码如下所示：,2.1 词法分析器的设计考虑及手工构造,2.1 词法分析器的设计考虑及手工构造,用该程序设计语言编制的计算园柱体表面积的源程序（输入输出略）如下所示： Begin/*S=2*3.14* R* R +2*3.14* R*H */ Real r,h,s; s=2*3.14*r*(r+h) End,2.1 词法分析器的设计考虑及手工构造,根据单词二元式编码，上述程序的单词二元式序列应为： (,“NUL“)(c,“NUL“)(i,“r“)(,“NUL“) (i,“h“) (,“NUL“)(i, “s“)(;,“NUL“)(i, “s“)(=,“NUL“)
3、(x, “2“)(*,“NUL“)(y, “3.14“)(*,“NUL“) (i, “r“)(*,“NUL“) (,“NUL“)(i, “r“) (+,“NUL“)(i, “h“)(),“NUL“)(,“NUL“),2.1 词法分析器的设计考虑及手工构造,2.1.2 源程序的输入及预处理 源程序的输入 l 分段读入处理（早期） l 全部读入后处理 设源程序如下所示，其中为续行符。,2.1 词法分析器的设计考虑及手工构造,2.1 词法分析器的设计考虑及手工构造,源程序读入后，输入缓冲区的内容如下所示：,2.1 词法分析器的设计考虑及手工构造,预处理 词法分析器通常由二个部分构成： 预处理程序 扫
4、描器（单词识别程序）,2.1 词法分析器的设计考虑及手工构造,分成二部分的理由 词法分析可在输入缓冲区上直接进行，但从程序进行的角度来讲，若是把输入串预处理一下，则单词识别就会比较容易，故词法分析器通常由预处理程序和扫描器（单词识别程序）两部分组成。,2.1 词法分析器的设计考虑及手工构造,预处理主要工作 1.删除注释 2.删除续行符以及后续换行符（0AH） 3.Tab的作用相当于多个空格，换行符、Tab和空格具有界符作用，预处理时通常予以保留。在后面的分析中可以看到，它们的存在给后续的单词识别带来方便。为了简化判断，可在预处理时将换行符和Tab统一替换为空格。 4.大多数语言（除C语言外）不
5、区分大小写，可在预处理时大写字母变换成小写字母，或相反，以方便后续处理。 5.对于受书写格式限制的语言（如FORTRAN和COBOL），还应识别标号区，正确给出语句标号；识别续行标志，把相继行连接在一起，给出语句结束符。,2.1 词法分析器的设计考虑及手工构造,上述源程序经预处理后，扫描缓冲区中的内容如下所示：,2.1 词法分析器的设计考虑及手工构造,预处理程序 下面用C/C+语言来编写一个预处理程序，其作用是去除源程序中的注释和续行符，将Tab和换行符替换为空格，将大写字母变换成小写字母。每调用一次，将经预处理的源程序全部送入内存中的扫描缓冲区，供扫描区识别单词。,2.1 词法分析器的设计考
6、虑及手工构造,程序实现，由两个函数构成： 主函数main是测试驱动程序，调用预处理函数pro_process，模拟词法分析器工作； 函数pro_process执行预处理任务，借助于传地址获得扫描缓冲区的首址，将经预处理的源程序送入扫描缓冲区。,2.1 词法分析器的设计考虑及手工构造,由于算法需要，在源程序尾部添加字符#，这是一个特殊的单词，表示源程序的结束。 源程序中的注释用/*.*/标记，不允许嵌套使用，这和大多数高级语言的规定一致。,2.1 词法分析器的设计考虑及手工构造,源程序的输入及预处理 #include #include void pro_process(char *); void
7、 main( ) /测试驱动程序 /定义扫描缓冲区 char buf4048=0; /缓冲区清0 /调用预处理程序 pro_process(buf); /在屏幕上显示扫描缓冲区的内容 coutbufendl; ,2.1 词法分析器的设计考虑及手工构造,void pro_process(char *buf) /预处理程序 ifstream cinf(“source.txt“,ios:in); int i=0; /计数器 char old_c=0,cur_c; /前一个字符，当前字符。 bool in_comment=false;/false表示当前字符未处于注释中。 while(cinf.rea
8、d( /在源程序尾部添加字符# ,2.1 词法分析器的设计考虑及手工构造,while(cinf.read( /保留前一个字符 /end of while,2.1 词法分析器的设计考虑及手工构造,数据说明 source.txt（源程序文件） char buf（扫描缓冲区） bool in_comment（状态标志） 若in_comment的值为false，表示当前从文件读入的字符未处于注释中，此时应将读入的字符存入扫描区；若in_comment的值为ture，则表示当前读入的字符处于注释中，此时读入的字符应丢弃。 XXXXX/*XXXXX*/XXXXX f f/t. t/f f 当读入“/*”时
9、，布尔变量in_comment的值由false变为true；当读入“*/”时，布尔变量in_comment的值由ture变为false。,2.1 词法分析器的设计考虑及手工构造,上机练习 用高级语言编写一词法分析预处理程序。从文件读入源程序，去除源程序中的注释（注释用标记），用空格取代源程序中的Tab和换行符，将预处理结果显示在屏幕上。源程序中无续行符，字母无须处理，源程序尾部需要添加字符。,2.1 词法分析器的设计考虑及手工构造,2.1.3 基本字的识别和超前搜索 程序设计语言单词以基本字识别最为困难，原因如下： 有些语言对基本字不加保护，用户可用作普通标识符。 基本字、用户定义的标识符和常
10、数之间没有分隔符。,2.1 词法分析器的设计考虑及手工构造,解决办法： 所有基本字均为保留字(Reserved word)，用户不得使用它们作为标识符。 将空格、TAB和换行符视为界符。在基本字、用户定义的标识符和常数之间，若没有运算符或界符，则至少用一个空格（或TAB、换行符）加以分隔。,2.1 词法分析器的设计考虑及手工构造,遍的基本概念 由外存获得前一遍的工作结果，完成后把结果存于外设。 遍引入的历史背景 早期内存较小，编译程序相对较大 遍和编译程序的结构 1.一遍工作后，内存大部分释放，下一遍后，可以使用全部存储空间 2.使得编译程序的逻辑结构比较清晰 3.但增加了输入输出所耗费时间,
11、2.1 词法分析器的设计考虑及手工构造,2.1.5 状态转换图和词法分析器的手工构造 引入状态转换图的必要性 程序设计语言的无符号实型常数有三种书写形式： 无小数部分形式：134 无整数部分形式：.12 完全形式：3.14 直接编写识别程序有难度，使用状态转换图是构造单词识别程序的好途径。,2.1 词法分析器的设计考虑及手工构造,状态转换图基本概念及应用 状态转换图是一个有向图。 在状态转换图中，结点代表状态，用圆圈表示。 状态之间用箭弧连接 箭弧上的标记代表在射出结点状态下可能出现的合法的输入字符,2.1 词法分析器的设计考虑及手工构造,例1，识别标识符的状态转换图如下所示：,2.1 词法分
12、析器的设计考虑及手工构造,例2，识别实常数和整常数的状态转换图,2.1 词法分析器的设计考虑及手工构造,例3，识别“#“、“+“和“+“的状态转换图,2.1 词法分析器的设计考虑及手工构造,利用状态转换图识别单词 状态转换图每次只能识别一个单词，若源程序中有N个单词，则需使用状态转换图N次。设源程序为“x+y#“（#是预处理程序添加的），单词识别程序（扫描器）共使用状态转换图5次。,2.1 词法分析器的设计考虑及手工构造,1.从初态0出发，读入x进入状态1，在状态1读入+，进入终态2，识别出标识符“x“，退回+； 2. 从初态0出发，读入+进入状态10，在状态10读入+，进入终态11，识别出运
13、算符“+“；,2.1 词法分析器的设计考虑及手工构造,3. 从初态0出发，读入+进入状态10，在状态10读入y，进入终态12，识别出运算符“+“，退回y； 4. 从初态0出发，读入y进入状态1，在状态1读入#，进入终态2，识别出标识符“y“，退回#；,2.1 词法分析器的设计考虑及手工构造,5.从初态0出发，读入#进入状态13，识别出单词“#”，识别出单词“#”意味着整个源程序中字符处理完毕。 为什么在C语言中x+y解释为(x+)+y,2.1 词法分析器的设计考虑及手工构造,根据状态转换图编制程序 （见“识别标识符的状态转换图编制的扫描程序”WORD文件）,2.1 词法分析器的设计考虑及手工构
14、造,词法分析器手工构造实例 1.字符集 az 09 + = * ，； （ ） # 发现集合以外的字符，即非法字符，应终止词法分析器,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例 2.单词集 基本字：begin,end,integer,real 标识符：以字母开始的数字字母串 无符号整常数 无符号实常数 运算符 + * + = 界符 ， ； （ ） # 错误形式 . 前后无数字字符的小数点 出现错误形式，终止词法分析器运行,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例 3.单词编码 基本字：begin(,NUL),end(,NUL),integer(a,NUL
15、),real(c,NUL) 标识符(i,字符串) 无符号整常数(x,字符串) 无符号实常数(y,字符串) 运算符 +(+,NUL) *(*,NUL) +($,NUL) =(=,NUL) 界符 , (,NUL) ; (;,NUL) ( (,NUL) ) (),NUL) # (#,NUL),2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例 4.状态转换图 对单字符单词可以不画状态转换图， 多字符单词需要画出状态转换图,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例 5.程序实现 词法分析器由5个函数构成： 主函数main 预处理函数pro_process 扫描函数sc
16、anner 拼接函数concat 查基本字表函数reserve,2.1 词法分析器的设计考虑及手工构造,主函数先调用预处理函数进行预处理，然后不断调用扫描函数，获得单词二元式编码，然后将输出到文件Lex_r.txt，直到源程序全部处理完成。,2.1 词法分析器的设计考虑及手工构造,void main() char buf4048=0;/扫描缓冲区 pro_process(buf); /预处理 coutbufendl; /显示buf ofstream coutf(“Lex_r.txt“,ios:out); /单词识别 code_val t;/临时变量 dot=scanner(buf);/调用一次扫描器获得一
