编译原理课件 第二章 词法分析.ppt

《编译原理课件 第二章 词法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章词法分析词法分析概述词法分析程序的手工实现正规表达式与有限自动机词法分析程序的自动生成12.1词法分析器设计方法词法分析是编译过程中的第一个阶段，其主要任务是：从左到右逐个字符地对源程序进行扫描，产生单词符号，通常用记号（token）表示。最后生成并输出一个单词符号序列，或直接将单词符号作为语法分析模块的输入。源程序（字符串形式）输出单词序列（记号形式）词法分析语法分析tokentokengetNextToken2问题：1、什么是记号（单词符号）？2、记号如何描述？3、记号如何识别？词法分析的其他作用：1、当词法分析程序发现标识符类型的单词时，要将其添加到

2、符号表中；2、过滤注释和空白等字符；3、记录换行符的个数，为每个出错消息赋予一个行号，从而使编译器生成的错误信息与源程序的位置联系起来。31、记号（token）及其描述记号（单词符号）是程序语言的基本语法单位。一般分为下面7种：关键字（基本字）标识符：常量、数组、变量、过程或函数名等。常数：各种类型的常数。运算符：如+、-、*、/、<、>等。分界符：如，、；、（、）等。空白符：如空格符、换行符等。注释4注意：一种语言的单词如何分类、怎样编码，主要取决于技术实现上的方便。52、记号的识别在词法分析中，可以用状态转换图来识别单词。例如状态转换图是有限的有向图，结点表

3、示状态，用圆圈表示；结点之间可以用有向边连接，有向边上可标记字符。6q1q2q3q0例1：字符串100101的识别的过程7q2q3q0q1例1：字符串100101的识别的过程8q2q0q1q3例1：字符串100101的识别的过程9q2q3q0q1例1：字符串100101的识别的过程10q1q2q3q0例1：字符串100101的识别的过程11q1q3q0q2例1：字符串100101的识别的过程12q1q0q2q3例1：字符串100101的识别的过程13q1q2q3q0例2：字符串00识别的过程14q1q3q0q2例2：字符串00识别的过程15q1q2q3q0例

4、2：字符串00识别的过程16q1q2q3q0例3：字符串10101识别的过程17q2q3q0q1例3：字符串10101识别的过程18q2q0q1q3例3：字符串10101识别的过程19q1q3q0q2例3：字符串10101识别的过程20q1q2q3q0例3：字符串10101识别的过程21q2q3q0q1例3：字符串10101识别的过程22状态转换图举例例1：字符串必须以空格开始和结束，中间可以有0个或任意多个由a~z组成的字符串。23例2：Pascal语言中关系运算符识别的状态转换图。051624837return(relop,LE)return(relop,

5、NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始<=>=>=**otherother24例3：标识符识别的状态转换图。123开始letterotherletter或digitreturn(id)*25例4：无符号整数的状态转换图。123开始1~9other0~9return(num)*262.2一个简单的词法分析器示例对于不含回路的分支状态，可以对应一个switch()语句或一组if-else语句。对于含回路的状态，可以对应一条while语句。终态一般对应一个return(

6、)语句。对于词法分析器，一般指返回给语法分析器。以一个C语言子集为例。27单词符号种别编码助记符内码值whileifelseswitchcase标识符常数+-*<=<===;123456789101111111213whileifelseswitchcaseidnum+-*relopreloprelop=;-----num在符号表中的位置---LELTEQ--id在符号表中的位置28201字母字母或数字其它3456数字数字其它+-7*910<=其它=;1415其它12=状态转换图示例**8*1113其它*空白*29设计思路对于状态图中每一个状态构造一段代码，代码

7、功能为：（1）从输入串中读入一个字符；（2）判明读入的字符与由此状态出发的哪条弧上的标记相匹配，则转至相匹配的那条弧所指向的状态。（3）均不匹配时便失败。词法分析程序的手工实现30程序实现子程序scan()输入：字符流输出：单词符号的二元形式31数据结构与子例程（一种实现）数据结构character当前输入字符token输入缓冲区(字符数组)32子例程buildlist():将token存入符号表或常数表，返回入口指针reserve():判别token是关键字？返回关键字种别或0getchar():从输入缓冲区中读入一个字符放入chletter()和digit(

8、):判断当前输入字符是否