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

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

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

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

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

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

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

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

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

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

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++;

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

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[]进行了初始 化

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);

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);

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

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

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); } }

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

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

词法分析举例 三个全程量： 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