编译原理实践 7.PL/0的词法分析程序构造.

Presentation on theme: "编译原理实践 7.PL/0的词法分析程序构造."— Presentation transcript:

1 编译原理实践 7.PL/0的词法分析程序构造

2 词法分析方法的构造方法分类 词法分析程序的任务 词法分析程序的设计

3 1.词法分析程序的构造方法分类 讲述正规式（正则表达式）和有穷自动机理论， 目的是为了介绍词法分析程序自动构造工具Lex 的原理。词法分析程序不是通过编程，而是执行 Lex产生 采用Loop-and-Switch（循环和分支）方法 本课程采用第二种方法，Lex方法将在后续补充介 绍

4 2.词法分析程序的任务 词法分析程序的任务：对源程序进行扫描，提 供一个个符号给语法分析程序。 简称为扫描器(scanner)或扫描程序
词法分析程序实现的2种方案： 1.先单独工作一遍，把字符流源程序先变为符号 序列，输出到一个中间文件上，然后将这个文 件作为语法分析程序的输入继续第二遍的编译 过程 字符串源程序 词法分析 符号串源程序

5 2.有些编译程序将词法分析和语法分析安排在同一遍中， 此时词法分析作为语法分析程序的一个子程序。每当语 法分析需要一个新的符号时，就调用词法分析子程序， 词法分析子程序从字符串源程序中识别出一个具有独立 意义的单词，将其符号返给语法分析。这种方法避免了 中间文件，省去了送取符号工作，有利于提高编译程序 的效率。书中采用这种方案。 字符串源程序 词法分析器 语法分析器 取符号 送符号

6 程序getsym 本课程采用第2种方案，程序名getsym，预先审 视源程序下一个符号，并将读入的符号放在变量 sym中，语法分析的判断分析将以这个读入的符号 为基础 具体任务： 跳过空格字符 识别像begin、end、if、while等这样的保留字 识别非保留字，作为标识符处理 识别数字 识别专用符号组合，如:=、<=、>= 识别特殊的单个字符，如+、-、/、* 跳过注释行（书中例子程序没有体现）

7 辅助过程getch getsym需要一个辅助过程getch，每被调用一次 就读入下一个字符 除此之外的任务: 识别行结束标志，作为空格符处理
拷贝原文输出 在输出文件每行开始添加坐标（书中例子程序没有体 现）

8 3.词法分析程序的设计 每调用一次getsym，首先用循环结构在源程序上 向前读入一个非空格字符，然后对此字符进行分析， 转相应部分处理
处理保留字和标识符 处理常数 处理组合字符和单个字符

9 过程getch的功能：getch被getsym每调用一 次，就在inf输入文件上向前读取一个字符给ch 变量(书中给的pascal代码，本ppt给出c代码)
char ch; /*最近一次从文件中读出的字符*/ int cc; /*行缓冲区指针，初始为0*/ int ll; /*行缓冲区长度，初始为0 */ char line[81]; /*行缓冲区*/

10 void getch() { if (cc == ll) /. 判断缓冲区中是否有字符，若无字符，则读入 下一行字符到缓冲区中
void getch() { if (cc == ll) /* 判断缓冲区中是否有字符，若无字符，则读入 下一行字符到缓冲区中 */ if (feof(fin)) printf("Program incomplete!\n"); exit(1); } ll = 0; cc = 0; ch = ' ';

11 while (ch != 10) {if (EOF == fscanf(fin,"%c", &ch)) { line[ll] = 0; break; } printf("%c", ch); fprintf(foutput, "%c", ch); line[ll] = ch; ll++; ch = line[cc]; cc++;

12 处理保留字和标识符 在词法分析程序getsym中，当读入的字符为a-z 的字母时候，就进入处理保留字和标识符的程序部 分
相关常量和变量说明： #define norw /* 保留字个数 */ #define al /* 标识符的最大长度 */ /* 符号 */ enum symbol { nul, ident, number, plus, minus, … };

13 enum symbol sym; /. 当前的符号. / char id[al+1]; /. 当前ident. / int num; /
enum symbol sym; /* 当前的符号 */ char id[al+1]; /* 当前ident */ int num; /* 当前number */ char a[al+1]; /* 临时符号 */ int i,j,k; /* 临时变量 */ char word[norw][al]; /* 保留字表*/ enum symbol wsym[norw]; /* 保留字对应的符 号值 */ enum symbol ssym[256]; /* 单字符的符号值 */ 注意： 在init()中对word[][]、wsym[]、ssym[]进行了初始 化

14 if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) /* 当前的单词是标识符或是保留字 */ { k = 0; do { if(k < al) { a[k] = ch; k++; } getch(); }while ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')); a[k] = 0; strcpy(id, a);

15 i = 0; j = norw - 1; do { /. 搜索当前单词是否为保留字，使用 二分法查找
i = 0; j = norw - 1; do { /* 搜索当前单词是否为保留字，使用 二分法查找 */ k = (i + j) / 2; if (strcmp(id,word[k]) <= 0) { j = k - 1; } if (strcmp(id,word[k]) >= 0) i = k + 1; } while (i <= j);

16 if (i-1 > j) /. 当前的单词是保留字. / { sym = wsym[k]; } else /. 当前的单词是标识符
if (i-1 > j) /* 当前的单词是保留字 */ { sym = wsym[k]; } else /* 当前的单词是标识符 */ sym = ident;

17 处理常数 相关变量/常量说明 int num; /* 当前number */ #define nmax /* 数字的最大位数 */

18 if (ch >= '0' && ch <= '9') /. 当前的单词是数字
if (ch >= '0' && ch <= '9') /* 当前的单词是数字 */ { k = 0; num = 0; sym = number; do { num = 10 * num + ch - '0'; k++; getch(); } while (ch >= '0' && ch <= '9'); k--; if (k > nmax) /* 数字位数太多 */ { error(30); } }

19 处理组合字符和单个字符 如果读入的字符既不是字母，也不是数字，就进入 余下的处理组合字符和单个字符的程序部分 注意： …
sym = ssym[ch]; /* 当符号不满足上述条件时， 全部按照单字符符号处理 */

20 词法分析过程getsym总结：从源文件中读出若干 有效字符，组成一个token串，识别它的类型 为 保留字/标识符/数字或是其它符号：
如果是保留字，把sym置成相应的保留字类型，如果 是 标识符，把sym置成ident表示是标识符，于此同 时，id变量中存放的即为保留字字符串或标识 符名 字。 如果是数字，把sym置为number,同时num变量中 存放该数字的值。 如果是其它的操作符， 则直接把sym置成相应类型

21 词法分析举例 三个全程量： enum symbol sym; /* 当前的符号 */
char id[al+1]; /* 当前ident */ int num; /* 当前number */ const m=7; 序号 字符串 id num sym 1 const constsym 2 m ident 3 = eql 4 7 number 5 ; semicolon