编译原理第3章+词法分析讲义.ppt

第三章 词 法 分 析 §3.1 词法分析概述 §3.2 词法分析程序的设计 §3.3 有穷自动机(FA) §3.4 正规表达式与有穷自动机 §3.5 词法分析程序的自动生成 §1.1 词法分析概述 一、词法分析的任务 二、单词的种类及其内部表示 扫描源程序 识别单词 变成内部编码 即从左到右逐个字符地扫描源程序，产生一个个独立的单词，并将其改变成等价内部编码 一、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 5. 分配存贮单元（静态变量） 对简单变量、常量及数组进行静态存贮分配 ? 静态存贮分配：在编译时就可以决定应分配内存的大小。 ? 动态存贮分配：到运行时才进行的存贮分配。 如：变界数组、动态变量。 静态存贮分配可以在词法分析阶段进行，也可以在语法分析阶段进行，随具体编译系统而定。 6. 进行词法检查 将一些单词错误检查出来， 又例如变量是否有说明或是否重复说明等。 词法分析方式 将词法分析和语法分析程序分开 词法分析方式 将词法分析程序编写成一个独立子程序 二、 单词的种类及内部编码 1、单词种类 2、内部编码  1、单词种类 所谓单词，是指那些具有独立含义的最小语法单位 。单词可分为以下几种类型： （１）保留字：PROGRAM, VAR, IF, FOR, AND等 。 （２）标识符：是用户选来表示常量、变量、类型、过程等名字。 （ 3 ）常数：分为整型、实型、布尔型、字符型等，如2，3.1416等。 （４）运算符：分为算术运算符（＋，－，*，／等），逻辑运算符 （ＡＮＤ，ＯＲ，ＮＯＴ），关系运算符（,=,=,=）等。 （５）界限符：如逗号、分号、括号等。 2、内部编码 ① 单词类别 ② 单词自身值 对于单词类别可以用整数表示，用来指示单词的种类 。例如上面的例子，我们可以用５个不同的整数作为它们单词类别的编码 。单词的内部编码是词法分析的输出形式 2、内部编码 单词自身值 可以是单词某种形式内部编码，也可以是该单词在某些表格中地址码。如第一章所讲，保留字、运算符和界限符用内部固定编码值作为单词值；标识符取其在标识符表中的地址码 ；常量取其在常数表中的地址码。 §3.2 词法分析程序设计 一、源程序的输入 二、扫描缓冲区及预处理 三、单词识别 四、正规文法和状态转换图 五、词法分析程序的设计与实现 一、源程序的输入 1. 内存比较大的情况下,直接输入到内存的一个源程序区 (1)一个字符占一个字节 (2)词法分析程序从源程序区读入字符 2. 内存不足的情况下，将源程序以文件的形式存贮在外部 介质上，如磁盘、磁带等 。可以先在内存中开辟一个 大小适宜的缓冲区，这个缓冲区称为 输入缓冲区。词法 分析程序工作时，先从外部介质上将输入 符号串分批读 入缓冲区，单词符号的识别可在这个缓冲区中进行.具 体处理时还要开辟一个扫描缓冲区。 二、扫描缓冲区及预处理 1. 扫描缓冲区 （1）定义：扫描缓冲区就是在内存中开辟一部分单元，供识别 单词用。 注意：扫描缓冲区和缓冲区是不同的，缓冲区是从 外存上读入部分字符，而扫描缓冲区仅是为识别单词用。 （2）工作原理 在扫描缓冲区中一般设两个指示器，一个指向当前正在识别 单词开始位置，另一个用于向前有哪些信誉好的足球投注网站寻找单词的终点。不论 扫描缓冲区定为多大都不能保证单词符号不会被它的边界所打断， 因此，扫描缓冲区最好使用如下所示的一分为二的区域（每半区 可容120个字符 ）： 扫描缓冲区1 扫描缓冲区2