编译原理课件()词法分析.ppt

第三章 词法分析 编译程序的结构 第三章 词法分析 词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。 词法分析是编译的基础。 执行词法分析的程序称为词法分析器。 3.1 对词法分析器的要求 3.1.1 词法分析器功能和输出形式 功能：输入源程序，输出单词符号（单词记号文件） 单词符号（token）:具有完整语义的最小的单位，不可分割。 输出形式：根据单词符号的不同，构造表示单词符号的机内表示token,以二元组形式表示，存放在文件中（形成源程序的内码文件）。 二元组形式:(单词种别编码，单词的属性值） 内码文件的形式 for (i=0;i=10,i--) (for ,-)((,-)(i，符号表入口)(=,-)(整形常数,常数表入口)(;-)………. 单词种别编码与单词符号属性值 考虑下述C++代码段： while (i=j) i- -; 经词法分析器处理后，它将转换为如下的单词符号序列： while, - ( , - id ,指向i的符号表项的指针 〉 = , - id ,指向j的符号表项的指针 ) , - id ,指向i的符号表项的指针 - - , - ; , - 3.1.2 词法分析器的构造方式-词法分析器作为独立子程序 词法分析器安排成语法分析的子程序。 好处在于：编译器结构清晰。 3.1.2 词法分析器作为独立子程序 词法分析器作为独立的遍 工作方式：不是任何程序的子程序，独立的完成一遍任务。 缺点：需要保存单词符号文件，占用内存 3.2 词法分析器的设计 3.2.1 输入、预处理 词法分析器的工作 分析器对扫描缓冲区进行扫描一进行单词的识别。 扫描时一般使用两个指示器 扫描缓冲区最好使用如下一分为二的区域：（循环队列的形式）。 词法分析器的结构 关键字的识别 像FORTRAN这样的语言，关键字不加保护（只要不引起矛盾，用户可以用它们作为普通标识符） 借助于超前有哪些信誉好的足球投注网站技术实现。 保留字（关键字不能用作标识符）的识别可以借助于保留字i表进行。 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.10 4 IF(5)=55 标识符的识别 标识符的定义：字母开头，字母和数字的组合 标识符后通常有界符 常数的识别 算术常数有时需要超前有哪些信誉好的足球投注网站 5.EQ. M 逻辑常数：.T. , .F., 有界符，容易识别 算符、界符的识别 +，-，*，/，++，-- 所以需要超前有哪些信誉好的足球投注网站 词法分析器的构造基础小结 构造预处理器，删除非执行代码 注释语句，多余的分隔符，等等 构造扫描器，对预处理结果进行扫描 对常数、标识符、关键字、运算符的识别都要采用超前有哪些信誉好的足球投注网站技术 扫描指针要及时地回退到适当的位置 3.2.3 状态转换图 状态转换图：有限、有向图。用来描述单词规则的一种工具。 一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态（用=表示） ，而且实际上至少要有一个终态（用双圈表示）。 状态图的作用 一个状态转换图可用于识别一定的字符串（描述词法规则）。 终态上打个*号，表示多读进了一个不属于标识符部分的字符，应把它退还给输入串，如果在状态0时输入字符不为“字母”，则意味着这个转换图不工作。 可以使用状态图进行词法分析器的开发 3.2.4 状态转换图的实现 利用转换图容易编写词法分析器 让每个状态结点对应一小段程序。 在编制程序的过程中引进一组全局变量和过程。将它们作为实现转换图的基本成分。例如： Key:记录单词识别过程中已识别到的字符串 扫描指针回退函数 判断读到的符号的类型 等等 对不包含回路的节点 状态i对应的代码： i() { Ch=Getchar() If (isletter(ch)) {j} Else if (isdigit(ch)) {k} Else if(ch=“/”) {l} Else{ 出错处理} } 对包含回路的节点 i() { ch=getchar(); while (isletter(ch) or isdigit(ch)) getchar(); 状态K所对应的程序段； } 对终态节点 K() { Return token; } 3.3 正规表达式与有限自动机 为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要将转换图的概念形式化。 为此我们引入：正规式，正规集，