《编译词法分析zss优秀PPT.ppt》由会员分享，可在线阅读，更多相关《编译词法分析zss优秀PPT.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 词法分析词法分析n词法分析的任务：从左至右逐个字符地词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符对源程序进行扫描，产生一个个单词符号。号。n词法分析器词法分析器(Lexical Analyzer)又称扫描又称扫描器器(Scanner)：执行词法分析的程序：执行词法分析的程序2023/4/1413.13.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式n功能功能:输入源程序、输出单词符号输入源程序、输出单词符号n单词符号的种类：单词符号的种类：基本字基本字：如：如 beginbegin，repeatre
2、peat，标识符标识符表示各种名字：如变量名、数组表示各种名字：如变量名、数组名和过程名名和过程名常数常数：各种类型的常数：各种类型的常数运算符运算符：+，-，*，/，界符界符：逗号、分号、括号和空白：逗号、分号、括号和空白2023/4/142n输出的单词符号的表示形式输出的单词符号的表示形式:(单词种别单词种别，单词符号的属性值单词符号的属性值)n单词种别通常用整数编码表示。单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算码就代表该单词符号。假定基本字、运算符和界符都是一符一种。符和界符都是一符一种。若一
3、个种别有多个单词符号，则对于每个若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。单词符号，给出种别编码和自身的值。n标识符单列一种；标识符自身的值表示成标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。按机器字节划分的内部码。n常数按类型分种；常数的值则表示成标准常数按类型分种；常数的值则表示成标准的二进制形式。的二进制形式。2023/4/143例例 C程序代码程序代码 while(i=j)i-;输出单词符号：输出单词符号：id,=,-=,-id,id,-,-2023/4/144二、词法分析器作为一个独立子程序二、词法分析器作为一个独立子程序n词法分析作为一个独
4、立的阶段，是否应词法分析作为一个独立的阶段，是否应当将其处理为一遍呢？当将其处理为一遍呢？n作为独立阶段的优点：结构简洁、清晰作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一和条理化，有利于集中考虑词法分析一些枝节问题。些枝节问题。n不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。n（当语法分析器须要一个单词符号时（当语法分析器须要一个单词符号时就调用这个子程序）就调用这个子程序）2023/4/145词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.2023/4/146词法分析器的结
5、构词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2 词法分析器的设计词法分析器的设计2023/4/147n输入串放在输入缓冲区中。输入串放在输入缓冲区中。n预预处处理理子子程程序序：剔剔除除无无用用的的空空白白、跳跳格格、回车和换行等编辑性字符等回车和换行等编辑性字符等n扫描缓冲区扫描缓冲区 起点起点 搜寻搜寻指示器指示器 指示器指示器一、输入、预处理一、输入、预处理2023/4/148二、单词符号的识别二、单词符号的识别:超前搜寻超前搜寻1 基本字识别基本字识别:例如例如:DO99K=1，10 DO 99 K=
6、1，10 IF(5.EQ.M)GOTO55 IF(5.EQ.M)GOTO 55DO99K=1.10IF(5)=55须要超前搜寻才能确定哪些是基本字须要超前搜寻才能确定哪些是基本字2023/4/1492 标识符识别标识符识别:字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符3 常数识别常数识别:识别出算术常数并将其转变为二进制内码表识别出算术常数并将其转变为二进制内码表示。有些也要超前搜寻。示。有些也要超前搜寻。5.E084 算符和界符的识别算符和界符的识别把多个字符符合而成的算符和界符拼合成一把多个字符符合而成的算符和界符拼合成一个单一单词符号。个单一单词符号。:=，*
7、，.EQ.，+，-，=2023/4/1410三、状态转换图三、状态转换图1 1 概念概念 状态转换图是一张有限方向图。状态转换图是一张有限方向图。213XY结点代表状态，用圆圈表示。结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的标记状态之间用箭弧连结，箭弧上的标记(字字符符)代表射出结代表射出结点点状态下可能出现的输入状态下可能出现的输入字符或字符类字符或字符类。一张转换图只包含有限个状态，其中有一个为一张转换图只包含有限个状态，其中有一个为初初态态，至少要有一个，至少要有一个终态终态。2023/4/1411识别标识符的状态转换图识别标识符的状态转换图012字母字母其他其他字母或数字字
8、母或数字*识别识别整常数整常数的状态转换图的状态转换图012数字数字其他其他数字数字*n一个状态转换图可用于识别一个状态转换图可用于识别(或接受或接受)确定确定的字符串。的字符串。2023/4/14122 2 例子例子q助忆符：干脆用编码表示不便于记忆，助忆符：干脆用编码表示不便于记忆，因此用助忆符来表示编码。因此用助忆符来表示编码。2023/4/14132023/4/14141 12 23 34 45 56 67 78 89 910101111121213130 0空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字=+*非非*,()其它其它*2023/4
9、/1415n几点重要限制几点重要限制不必运用超前搜寻不必运用超前搜寻n全全部部基基本本字字都都是是保保留留字字;用用户户不不能能用用它它们们作作自己的标识符自己的标识符n基基本本字字作作为为特特殊殊的的标标识识符符来来处处理理;不不用用特特殊殊的状态图来识别，只要查保留字表。的状态图来识别，只要查保留字表。n假假如如基基本本字字、标标识识符符和和常常数数(或或标标号号)之之间间没没有有确确定定的的运运算算符符或或界界符符作作间间隔隔，则则必必需需运用一个空白符作间隔。运用一个空白符作间隔。nDO99K=1，10 n要写成要写成 DO 99 K=1，102023/4/14163 状态转换图的实现
10、状态转换图的实现n思想：每个状态结点思想：每个状态结点对应一小段程序对应一小段程序。n做法做法:1)1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASECASE语句或一语句或一组组 if-else if-else 语句实现语句实现GetChar();if(IsLetter()状态状态j的对应程序段的对应程序段;else if(IsDigit()状态状态k的对应程序段的对应程序段;else if(ch=/)状态状态l的对应程序段的对应程序段;else 错误处理错误处理;ijkl字母字母数字数字2023/4/14172)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段
11、由WHILEWHILE结构结构和和IFIF语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar();while(IsLetter()or IsDigit()GetChar();状态状态j的对应程序段的对应程序段2023/4/14183)3)终态结表示识别出某种单词符号，因此，对终态结表示识别出某种单词符号，因此，对应语句为应语句为 RETURN(C，VAL)其中，其中，C C为单词种别，为单词种别，VALVAL为单词自身值为单词自身值.2023/4/1419n全局变量与过程全局变量与过程1)ch 1)ch 字符变量、存放最新读入的源程序字符字符变量、存放最新读入的源程序
12、字符2)strToken 2)strToken 字符数组，存放构成单词符号的字符串字符数组，存放构成单词符号的字符串3)GetChar 3)GetChar 子程序过程，把下一个字符读入到子程序过程，把下一个字符读入到chch中中4)GetBC 4)GetBC 子程序过程，跳过空白符，直至子程序过程，跳过空白符，直至chch中读入中读入一非空白符一非空白符5)Concat 5)Concat 子程序，把子程序，把chch中的字符连接到中的字符连接到 strToken strToken 2023/4/14206)IsLetter6)IsLetter和和 IsDigit IsDigit 布尔函数，推断
13、布尔函数，推断chch中字符中字符是否为字母和数字是否为字母和数字7)Reserve 7)Reserve 整型函数，对于整型函数，对于 strToken strToken 中的字符中的字符串查找保留字表，若它是保留字则给出它的编码，串查找保留字表，若它是保留字则给出它的编码，否则回送否则回送0 08)Retract 8)Retract 子程序，把搜寻指针回调一个字符位子程序，把搜寻指针回调一个字符位置置9)InsertId 9)InsertId 整型函数，将整型函数，将strTokenstrToken中的标识符中的标识符插入符号表，返回符号表指针插入符号表，返回符号表指针10)InsertCo
14、nst 10)InsertConst 整型函数过程，将整型函数过程，将strTokenstrToken中中的常数插入常数表，返回常数表指针。的常数插入常数表，返回常数表指针。2023/4/1421int code,value;strToken:=“”;/*置置strTokenstrToken为空串为空串*/GetChar();GetBC();if(IsLetter()beginwhile(IsLetter()or IsDigit()beginConcat();GetChar();endRetract();/*回调一个字符回调一个字符*/code:=Reserve();if(code=0)/*非
15、保留字非保留字*/beginvalue:=InsertId(strToken);return($ID,value);endelsereturn(code,-);end2023/4/1422else if(IsDigit()beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelse if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);2023/4/1423else 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();/*错误处理*/2023/4/1424