词法分析程序的设计教学提纲

1、词法分析程序的设计独立词法分析器独立词法分析器语法分析语法分析Token序列序列源程序源程序附属词法分析器附属词法分析器语法分析语法分析调用调用Token源程序源程序2. 确定单词分类和确定单词分类和TokenToken结构结构设计词法分析器的首要任务是，对于源语言的设计词法分析器的首要任务是，对于源语言的单词进行仔细的分析，并列出所有可能的不同单词进行仔细的分析，并列出所有可能的不同单词，然后再确定单词的内部表示单词，然后再确定单词的内部表示 程序设计语言中的大部分单词，一般可分为以程序设计语言中的大部分单词，一般可分为以下几类：下几类：1基本字（关键字）：如基本字（关键字）：如 begin

2、，end，if 等等2标识符：用来表示常量、变量、过程等名字标识符：用来表示常量、变量、过程等名字3常数：各种类型的常数，如常数：各种类型的常数，如 15，3.14，TRUE4运算符：如运算符：如 +，*，/5界符：如逗号，分号，括号等界符：如逗号，分号，括号等 单词的机内表示单词的机内表示 二元式（二元式（单词种别单词种别，单词自身的值单词自身的值）种别是语法分析需要的信息种别是语法分析需要的信息自身值是编译其他阶段需要的信息自身值是编译其他阶段需要的信息 种别编码种别编码(常用整数编码常用整数编码) 方法一：按单词的方法一：按单词的5大种类每种一个码，例大种类每种一个码，例如标识符为如标识

3、符为l，常数为，常数为2，基本字为，基本字为3，运算，运算符为符为4，界符为，界符为5。方法二：每个基本字一个编码；所有标识符方法二：每个基本字一个编码；所有标识符为一个编码；常数按类型分类，每类一个编为一个编码；常数按类型分类，每类一个编码；每个运算符一个编码；每个界符一个编码；每个运算符一个编码；每个界符一个编码。码。 单词自身值单词自身值对常数对常数,基本字基本字,运算符运算符,界符就是他们本身的值界符就是他们本身的值对标识符对标识符,将标识符的名字登记在符号表将标识符的名字登记在符号表中中,“自身值自身值”是指向该标识符所在符号表中位是指向该标识符所在符号表中位置的指针置的指针. 例如

4、例如 源程序源程序if i=5 then x:=y;种别编码：标识符为种别编码：标识符为l，常数为，常数为2，基本字为，基本字为3，运算符为运算符为4，界符为，界符为5词法分析后输出的单词序列是词法分析后输出的单词序列是:(3,if)(1,指向指向i的符号表入口的符号表入口)(4,=)(2,5)(3,then)(1,指向指向x的符号表入口的符号表入口)(4,:=)(1,指向指向y的符号表入口的符号表入口)(5,;)3. 特殊问题的处理特殊问题的处理v 标识符和保留字的区分标识符和保留字的区分事先构造保留字表，拼出的标识符单词先查事先构造保留字表，拼出的标识符单词先查保留字表，若有，则把它做为保

5、留字处理保留字表，若有，则把它做为保留字处理v 空格符和制表符空格符和制表符(Tab)(Tab)以及换行符的处理以及换行符的处理v 无用的空格符和制表符要删掉；无用的空格符和制表符要删掉；v 字符串内的空格不能删；字符串内的空格不能删；v 换行符不能删，对于错误处理起作用。换行符不能删，对于错误处理起作用。v 复合型特殊符，如复合型特殊符，如“:=”:=”的处理的处理读到读到“:”:”时不能判断是否为冒号，必须读下时不能判断是否为冒号，必须读下一字符。一字符。v括号类配对：括号类配对： “”和和“”、左注释符和右注释符的配、左注释符和右注释符的配对。也可以把对。也可以把begin end ,i

6、f then, , ,( )begin end ,if then, , ,( )等语等语法配对在词法分析中进行处理法配对在词法分析中进行处理处理方法：处理方法： l对每类括号设置一个计数器（初值对每类括号设置一个计数器（初值=0=0）l每当遇到左括号，则计数器加每当遇到左括号，则计数器加1 1l每当遇到右括号时，计数器减每当遇到右括号时，计数器减1 1l词法分析结束时，如果计数器词法分析结束时，如果计数器 0 0，则表明括，则表明括号不匹配。号不匹配。可通过状态转换图来实现词法分析程序的构可通过状态转换图来实现词法分析程序的构造，步骤：造，步骤：画状态转换图。画状态转换图。由正规文法构造状态转

7、换图由正规文法构造状态转换图由正规表达式构造状态转换图由正规表达式构造状态转换图将正规文法或正规表达式转换成将正规文法或正规表达式转换成DFADFA（经历（经历NFANFA的构造，将的构造，将NFANFA确定化，确定化，DFADFA最小化的过最小化的过程），将程），将DAFDAF以状态转换图的形式表现出来。以状态转换图的形式表现出来。4. 用状态转换图构造词法分析程序用状态转换图构造词法分析程序按状态转换图写出词法分析程序按状态转换图写出词法分析程序对于状态图中的每一状态构造一段代码对于状态图中的每一状态构造一段代码具体构造程序时：具体构造程序时：开始结点开始结点开始结点是一个单词识别的开始，

8、单词开始开始结点是一个单词识别的开始，单词开始符是非空白字符，首先把非空白字符读入符是非空白字符，首先把非空白字符读入ch，再按该字符的特征进入不同种类单词的识别再按该字符的特征进入不同种类单词的识别 GetChar()；/*从输入串读一个字符，放入从输入串读一个字符，放入 ch中中*/GetBC()；/*检查检查ch中字符是否空白，若是中字符是否空白，若是则调用则调用GetChar，直至，直至ch中为非空白字符中为非空白字符*/ If (ch=) begin end else if (ch=) begin end else 错误处理；错误处理；不含回路的分叉结点，对应不含回路的分叉结点，对应

9、switch语句或一组语句或一组ifthenelse语句语句ijk数字数字字母字母/l例：状态结点例：状态结点 i 对应的程序段对应的程序段 GetChar()； If (IsLetter() 状态状态 j 的对应程序段的对应程序段; else If (IsDigit() 状态状态 k 的对应程序段的对应程序段; else If（ch=/） 状态状态 l 的对应程序段的对应程序段; else 错误处理错误处理; 其中：其中： IsLetter和和IsDigit：布尔函数，：布尔函数， 分别判别分别判别ch字符是否为字母或数字字符是否为字母或数字终态结点，一般对应一个终态结点，一般对应一个return(code，value)语句，语句，code是单词种是单词种别码别码，value是单词自身值，意为返回调用者：是单词自身值，意为返回调用者：v当词法分析作为语法分析的子程序，返