语法分析器幻灯片.ppt

语法分析器第1页，共13页，编辑于2022年，星期二词法分析概述词法分析概述l 有关词法分析器的几个问题和处理方法：有关词法分析器的几个问题和处理方法：词法分析器的功能、分类词法分析器的功能、分类 单词的分类、单词的分类、Token表示表示 保留字保留字 空格符、制表符和换行符空格符、制表符和换行符 复合型符号复合型符号 括号类匹配预检括号类匹配预检 字符串空间字符串空间 词法错误校正词法错误校正 词法分析结束词法分析结束第2页，共13页，编辑于2022年，星期二v 词法分析器的功能词法分析器的功能l词法分析器功能：词法分析器功能：l 读源程序的字符序列读源程序的字符序列,逐个拼出单词逐个拼出单词,并构并构造相应的内部表示造相应的内部表示TOKEN.TOKEN.同时检查源程序中的同时检查源程序中的词法错误词法错误.l引入引入TokenToken的原因：的原因：l 编译程序总是用某种程序语言书写的程序，编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各种数据。语言的操作对象只能是该语言规定的各种数据。而编译程序的操作对象是程序中的各种语法单而编译程序的操作对象是程序中的各种语法单位，因此，必须把它们表示成某种数据结构形位，因此，必须把它们表示成某种数据结构形式。式。第3页，共13页，编辑于2022年，星期二词法分析器的两种形式词法分析器的两种形式CharList 独独 立立词法分析器词法分析器语法分析语法分析TokenList 附附 属属词法分析器词法分析器语法分析语法分析callTokenCharList第4页，共13页，编辑于2022年，星期二v Token Token定义定义lTokenToken表示最小的语义单位表示最小的语义单位-单词的信息。单词的信息。即单词内部表示的数据结构形式。即单词内部表示的数据结构形式。单词不是程序设计语言中的语法概念，是编译程序中引进单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。是最小的语义单位，不能分割的一个概念。是最小的语义单位，不能分割lTokenToken中需要记录有关单词的信息：中需要记录有关单词的信息：单词的标志码单词的标志码($id,$intC,($id,$intC,)标识单词的种类标识单词的种类-词法词法信息信息 单词的特征属性（标识符名，符号表地址等）单词的特征属性（标识符名，符号表地址等）-语语义信息义信息第5页，共13页，编辑于2022年，星期二Micro的的单词的分类单词的分类l标识符：字母打头的字母标识符：字母打头的字母/数字串数字串l整常数：数字打头的数字串整常数：数字打头的数字串l实常数：整数实常数：整数.整数整数l保留字：保留字：beginbegin，endend，varvar，readread，writewrite，integerinteger，realreall符号符号 ：+，*，(，)，:，:=:=，;l控制控制 ：(换行符）换行符）第6页，共13页，编辑于2022年，星期二Micro Micro 语言的语言的TokenToken结构结构l标识符的标识符的TokenToken:（$id,$id,标识符）如标识符）如($id,x)($id,x)l整常数的整常数的Token:($intC,Token:($intC,整常数）如整常数）如 （$intC,5)$intC,5)l实常数的实常数的Token:($realC,Token:($realC,实常数）如实常数）如$realC,0.5)$realC,0.5)l保留字的保留字的Token:($begin,-),($end,-)Token:($begin,-),($end,-)l符号词的符号词的Token:($plus,-),($mult,-),Token:($plus,-),($mult,-),($Lparen,-)($Lparen,-)l换行符的换行符的Token:($line,-)Token:($line,-)第7页，共13页，编辑于2022年，星期二 ($begin,-)($var,-)($id,x)($colon,-)($real,-)($semi,-)l例如下述例如下述MicroMicro的代码：的代码：begin var x:real;begin var x:real;经词法分析器处理后，它将转换为如下的经词法分析器处理后，它将转换为如下的 TokenToken序列：序列：第8页，共13页，编辑于2022年，星期二v标识符和常量的处理标识符和常量的处理：词法信息可确定，语义信息形式的确定：词法信息可确定，语义信息形式的确定：a a 语义信息的长度有限制时，直接用语义信息的长度有限制时，直接用 标识符或常量本身标识符或常量本身 b b 没有长度限制时，构造标识符或常没有长度限制时，构造标识符或常 量表，语义信息中为其在表中的地量表，语义信息中为其在表中的地 址（字符串空间址（字符串空间节省存贮空间）节省存贮空间）v保留字的处理保留字的处理：识别保留字的方法：识别保留字的方法：1.建立保留字表；顺序、散列、散列顺序建立保留字表；顺序、散列、散列顺序 2.拼写的同时进行判断拼写的同时进行判断 自动机自动机 第9页，共13页，编辑于2022年，星期二v 运算符的处理运算符的处理：不区分，统一成一类不区分，统一成一类 区分，每个运算符为一类区分，每个运算符为一类v 空格符和制表符以及换行符的处理空格符和制表符以及换行符的处理 1.无用的空格符和制表符要删掉；无用的空格符和制表符要删掉；2.字符串内的空格不能删；字符串内的空格不能删；3.换行符不能删。用于错误定位换行符不能删。用于错误定位v 复合型特殊符，如复合型特殊符，如“:=”的处理的处理 读到读到“:”时不能判断是否为冒号，必须读下时不能判断是否为冒号，必须读下 一字符。一字符。第10页，共13页，编辑于2022年，星期二v括号类配对预检括号类配对预检括号类：括号类：begin begin end,if end,if then,()then,()处理方法：处理方法：对每类括号设置一个计数器（初值对每类括号设置一个计数器（初值=0=0）每当遇到开括号，则计数器加每当遇到开括号，则计数器加1 1 每当遇到闭括号时，计数器减每当遇到闭括号时，计数器减1 1 词法分析结束时，如果计数器词法分析结束时，如果计数器 0 0，则，则 表明括号不匹配。表明括号不匹配。v字符串空间字符串空间目的：减少冗余，节省空间，提高访问速度目的：减少冗余，节省空间，提高访问速度方法：字符数组存放字符串，描述字符串信息：方法：字符数组存放字符串，描述字符串信息：下标下标 长度长度 第11页，共13页，编辑于2022年，星期二v词法错误校正词法错误校正l词法错误种类：词法错误种类：l 语言不允许的符号：语言不允许的符号：#l 括号类配对错误：括号类配对错误：l 单词的后继符错（偶尔）：单词的后继符错（偶尔）：l词法错误校正：词法错误校正：l a a 删除已被读过的字符，并重新扫删除已被读过的字符，并重新扫l 描未被读过的字符描未被读过的字符l b b 删除已读过的第一个字符，重新删除已读过的第一个字符，重新l 扫描它的后继部分的字符。扫描它的后继部分的字符。l校正后的标示校正后的标示第12页，共13页，编辑于2022年，星期二v词法分析的结束词法分析的结束程序结束标志程序结束标志.文件结束符文件结束符Eof.Eof.第13页，共13页，编辑于2022年，星期二