《编译原理》实验指导书2016

编 译 原 理

实验与课程设计指导书

2016年10月

《编译原理》实验指导书

目录

一、课程简介 ...................................................................................... 2 二、实验目的 ...................................................................................... 2 三、实验环境 ...................................................................................... 2 四、实验任务 ...................................................................................... 2 五、实验项目 ...................................................................................... 2 实验一. 词法分析 ......................................................................... 2 实验二. 自顶向下语法分析 ......................................................... 8 实验三. 自底向上语法分析 ....................................................... 10 实验四. 语义分析 ....................................................................... 11 实验五. 中间代码生成 ............................................................... 12 六、课程设计 .................................................................................... 13 七、考核方式 .................................................................................... 13 八、参考文献 .................................................................................... 14 九、附录——PL0语言编译源程序清单（部分） ........................ 15

《编译原理》课程组 1 of 37

《编译原理》实验指导书

编译原理实验与课程设计指导

一、课程简介

1. 课程名称：编译原理（Principle of Compiler）

2. 课程总学时： 64 学时[理论： 48 学时；实验： 16 学时 3. 课程总学分： 4 学分

二、实验目的

编译原理是计算机类专业特别是计算机软件专业的一门重要专业课。设置该课程的目的在于系统地向学生讲述编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术，使学生通过学习既掌握编译理论和方法方面的基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。编译原理是一门理论性和实践性都比较强的课程。进行上机实验的目的是使学生通过完成上机实验题目加深对课堂教学内容的理解。同时培养学生实际动手能力。

三、实验环境

微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++开发环境。

四、实验任务

用C/C++/Visual C++语言编写某语言的词法分析程序、语法分析程序、语义分析程序、中间代码生成程序。

五、实验项目

实验一. 词法分析 1. 实验目的

《编译原理》课程组 2 of 37

《编译原理》实验指导书

? 根据PL/0语言的文法规范，编写PL/0语言的词法分析程序。 ? 通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；

加深对课堂教学的理解；提高词法分析方法的实践能力。 ? 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示

文件的法。 ? 掌握词法分析的实现方法。 ? 上机调试编出的词法分析程序。

2. 实验准备

微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++.

3. 实验时间

4学时

4. 实验内容

（1） 试用手工编码方式构造识别以下给定单词的某一语言的词法分析

程序。 （2） 语言中具有的单词包括五个有代表性的关键字begin、end、if、

then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。 （3） 单词的分类：构造上述语言中的各类单词符号及其分类码表。

表1 语言中的各类单词符号及其分类码表

单词符号 类别编码 类别码的助记符 begin end if then else 标识符 整常数 < <= = <> > >= 1 2 3 4 5 6 7 8 9 10 11 12 13 BEGIN END IF THEN ELSE ID INT LT LE EQ NE GT GE 单词值 字母打头的字母数字串 数字串 《编译原理》课程组 3 of 37

《编译原理》实验指导书

:= + - * / 14 15 16 17 18 IS PL MI MU DI

5、 实验方法与处理过程

在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、整常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表I中部分单词可以构造一个如图1所示的有限自动机（以状态转换图表示）。在图1中添加了当进行状态转移时，词法分析程序应执行的语义动作。根据图1，可用C语言编写出符合以上几项要求的一个相应的扫描器程序，如程序一所示。

《编译原理》课程组 4 of 37

《编译原理》实验指导书

图1 识别表I所列语言中的部分单词的DFA及相关的语义过程

图1及程序一中所出现的语义变量及语义函数的含义和功能说明如下。 函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。

字符数组TOKEN：用来依次存放一个单词词文中的各个字符。

函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。

函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。

函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。

函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数

《编译原理》课程组 5 of 37

《编译原理》实验指导书

时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。

程序一 根据图1编写的扫描器

# include

# include # include # define ID 6 # define INT 7 # define LT 8 # define LE 9 # define EQ 10 # define NE 11 # define GT 12 # define GE 13 char TOKEN[20]；

extern int lookup (char*); extern void out (int, char*); extern report_error (void);

void scanner_example (FILE *fp) {

char ch; int i, c; ch=fgetc (fp);

if (isalpha (ch)) /*it must be a identifer!*/ {

TOKEN[0]=ch; ch=fgetc (fp); i=1; while (isalnum (ch)) {

TOKEN[i]=ch; i++； ch=fgetc (fp); }

TOKEN[i]= ′＼0′

fseek(fp,-1,1); /* retract*/ c=lookup (TOKEN);

if (c==0) out (ID,TOKEN); else out (c,\； } else

if(isdigit(ch)) {

TOKEN[0]=ch; ch=fgetc(fp); i=1; while(isdigit(ch)) {

TOKEN[i]=ch; i++; ch=fgetc(fp); }

TOKEN[i]= ′＼0′； fseek(fp,-1,1); out(INT,TOKEN); } else

switch(ch) {

case ′＜′: ch=fgetc(fp);

if(ch==′=′)out(LE,\

else if(ch==′＞′) out (NE,\

else {

fseek (fp,-1,1); out (LT,\} break;

case ′=′: out(EQ, \

《编译原理》课程组 6 of 37

《编译原理》实验指导书

case ′＞′: ch=fgetc(fp);

if(ch==′=′)out(GE,\ else {

fseek(fp,-1,1); out(GT,\}

break;

default: report_error( ); break; } return; }

提示：扫描器所用的若干函数以及主程序有待于具体编写，并需事先建立好保留字表，以备查询。另外，在扫描源程序字符串时，一旦识别出关键字、标识符、整常数以及运算符中之一，即以二元式形式（类别编码，值）输出单词。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。

6、 输出结果：以文件形式输入的例子至少应包含两行以上的源代码，并以对

照的形式将扫描器的分析结果输出，必要时给出正误信息。 例：以下例题说明运行时的输入输出效果： 输入：

const a=10; var b,c; begin read(b); c:=a+b; write(c) end. 输出：

(constsym ,const ) (ident , a) (eql , =) (number, 10) (semicolon , ;) (varsym , var ) (ident, b) (comma, , ) (ident, c )

(semicolon , ;) (begins ym,begin) (readsym, read ) (lparen , ( ) (ident, b) (rparen , ) ) (semicolon , ;)

《编译原理》课程组 7 of 37

《编译原理》实验指导书

(ident, c )

(becomes , := ) (ident, a ) (plus , + ) (ident, b )

(semicolon , ;) (writesym ,write ) (lparen , ( ) (ident, c ) (rparen , ) ) (endsym , end )

实验二. 自顶向下语法分析 1. 实验目的

（1）通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。

（2）选择最有代表性的语法分析方法递归子程序法；选择对各种常见程序语言都具备的语法结构，如赋值语句，特别是表达式，作为分析对象。

2. 实验准备

微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++.

3. 实验时间

4学时

4. 实验内容

? 构造递归下降LL(1)语法分析器。完成P87，例4.12

5. 实验要求

? 语法分析器的编写方法采用递归子程序法。扩充完整例4.12的程序

部分。

《编译原理》课程组 8 of 37

《编译原理》实验指导书

? 输入文法的句子，作为表达式语法分析器的输入，进行语法解析，

对于语法正确的表达式，报告“语法正确”；

? 对于语法错误的表达式，报告“语法错误”， 指出错误原因。 ? 把语法分析器设计成一个独立一遍的过程。

6. 输入输出

输入：

至少找到2个句子，其中一个是文法的句子，另一个不是，分别

输入。

输出：

对于语法正确的表达式，报告“语法正确”；

对于语法错误的表达式，报告“语法错误”， 指出错误原因。

《编译原理》课程组 9 of 37

《编译原理》实验指导书

实验三. 自底向上语法分析 1. 实验目的

给出算符优先关系表的构造方法，将FIRSTVT集合和LASTVT集合的算法扩充成程序。

2. 实验准备

微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++.

3. 实验时间

4学时

4. 实验内容

构造求FIRSTVT集合和LASTVT集合的程序。

5. 实验要求

? 扩充P113求FIRSTVT集合的算法。 ? 完成LASTVT集合的算法。

6. 输入输出

输入：

文法。 输出：

FIRSTVT集合和LASTVT集合。

《编译原理》课程组 10 of 37

《编译原理》实验指导书

实验四. 语义分析

1. 实验目的

? 通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析

所识别的语法范畴变换为某种中间代码的语义翻译方法。 ? 掌握目前普遍采用的语义分析方法──语法制导翻译技术。 ? 要求在语法分析程序中添加语义处理，对于语法正确的算术表达式，

输出其计算值。

2. 实验准备

微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++.

3. 实验时间

4学时

4. 实验内容

在表达式的语法分析程序里，添加语义处理部分。

5. 实验要求

? 语义分析对象重点考虑经过语法分析后已是正确的语法范畴，实习

重点是语义子程序。 ? 在实验三“语法分析器”的里面添加PL/0语言“表达式”部分的语

义处理。 ? 计算表达式的语义值。

6. 输入输出

输入：

算术表达式，例如: 2 + 3 * 5作为输入。 输出：

17

《编译原理》课程组 11 of 37

《编译原理》实验指导书

实验五. 中间代码生成

1. 实验目的

要求在语法分析程序中添加语义处理，对于语法正确的表达式，输出其中间代码。

2. 实验准备

微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++.

3. 实验时间

4学时

4. 实验内容

在实验三的表达式语法分析程序里，添加语义处理部分输出表达式的中间代码，用四元式序列表示。

5. 实验要求

? 在实验三“语法分析器”的里面添加PL/0语言“表达式”部分的语

义处理，输出表达式的中间代码。 ? 中间代码用四元式序列表示。

6. 输入输出

输入：

表达式，例如: a * （b + c）。 输出：

( + b c t1 ) ( * a t1 t2 )

《编译原理》课程组 12 of 37

《编译原理》实验指导书

六、课程设计

1、选题（四选一）：

（1）构造递归下降分析程序语法分析器 （2）构造预测分析表语法分析器 （3）构造算符优先分析语法分析器 （4）构造LR(0)分析法语法分析器

2、设计方法：

小组分工，合作完成。从小到大，逐步扩展。按照文法和程序的特点，逐步

完成设计和测试。

3、设计报告：

应包括：报告标题、主要工作概述、具体内容（算法部分）、开发经验等。

七、考核方式

1、实验报告和课程设计报告

实验独立完成，提交实验报告；

课程设计采用分组的形式，3人一组，每个实习小组交一份课程设计报告，格式要求绝对规范！内容应包括以下内容：

? 题目 ? 设计思想 ? 算法

? 调试数据（输入/输出）

2、评分标准

? 由指导教师根据实验验收情况并结合实验报告质量及学习态度等进

行评分。 ? 课程设计作为独立考查课，学分为1。

《编译原理》课程组 13 of 37

《编译原理》实验指导书

八、参考文献

[1]《编译原理》（第二版），张素琴、吕映芝、蒋维杜，清华大学出版社，2005

年出版。

[2]《编译程序设计原理》，杜书敏、王永宁，北京大学出版社，1988年出版。 [3]《计算机编译原理》，张幸儿，科学出版社，1999年出版。

[4]《编译程序原理与技术》，李赣生等，清华大学出版社，版。

《编译原理》课程组 年10月出

14 of 37

1997

《编译原理》实验指导书

九、附录——PL0语言编译源程序清单（部分）

源代码

pl0c.h /* 关键字个数 */ #define norw 13 /* 名字表容量 */ #define txmax 100

/* 所有的add1用于定义数组 */ #define txmaxadd1 101 /* number的最大位数 */ #define nmax 14 /* 符号的最大长度 */ #define al 10 /* 地址上界 */ #define amax 2047

/* 最大允许过程嵌套声明层数 */ #define levmax 3

/* 最多的虚拟机代码数 */ #define cxmax 200 #define cxmaxadd1 201

/* 当函数中会发生fatal error时，返回-1告知调用它的函数，最终退出程序 */ #define getsymdo if(-1==getsym())return -1 #define getchdo if(-1==getch())return -1

#define testdo(a,b,c) if(-1==test(a,b,c))return -1 #define gendo(a,b,c) if(-1==gen(a,b,c))return -1

#define expressiondo(a,b,c) if(-1==expression(a,b,c))return -1 #define factordo(a,b,c) if(-1==factor(a,b,c))return -1 #define termdo(a,b,c) if(-1==term(a,b,c))return -1

#define conditiondo(a,b,c) if(-1==condition(a,b,c))return -1 #define statementdo(a,b,c) if(-1==statement(a,b,c))return -1

#define constdeclarationdo(a,b,c) if(-1==constdeclaration(a,b,c))return -1 #define vardeclarationdo(a,b,c) if(-1==vardeclaration(a,b,c))return -1 typedef enum {false,true} bool; /* 符号 */ enum symbol

{nul,ident,number,plus,minus,times,slash,oddsym,eql,neq,lss,leq,gtr,geq,lparen,rparen,comma,semicolon,period,becomes,beginsym,endsym,ifsym,thensym,whilesym,writesym,readsym,dosym,callsym,constsym,varsym,procsym}; #define symnum 32

/* 名字表中的类型 */

enum object {constant,variable,procedur};

《编译原理》课程组 15 of 37

《编译原理》实验指导书

/* 虚拟机代码 */

enum fct {lit,opr,lod,sto,cal,inte,jmp,jpc}; #define fctnum 8

/* 虚拟机代码结构 */ struct instruction { enum fct f; /* 虚拟机代码指令 */ int l; /* 引用层与声明层的层次差 */ int a; /* 根据f的不同而不同 */

}; FILE* fas;

/* 输出名字表 */

FILE* fa; /* 输出虚拟机代码 */

FILE* fa1; /* 输出源文件及其各行对应的首地址 */ FILE* fa2; /* 输出结果 */

bool listswitch; /* 显示虚拟机代码与否 */ bool tableswitch; /* 显示名字表与否 */ char ch; /* 获取字符的缓冲区，getch 使用 */ enum symbol sym; /* 当前的符号 */ char id[al]; /* 当前ident */ int num; /* 当前number */

int cc,ll,kk; /* getch使用的计数器，cc表示当前字符(ch)的位置 */ int cx; /* 虚拟机代码指针 */ char line[81]; /* 读取行缓冲区 */ char a[al]; /* 临时符号 */

struct instruction code[cxmaxadd1]; /* 存放虚拟机代码的数组 */ char word[norw][al]; /* 保留字 */

enum symbol wsym[norw]; /* 保留字对应的符号值 */ enum symbol ssym[256]; /* 单字符的符号值 */ char mnemonic[fctnum][5]; /* 虚拟机代码指令名称 */ bool declbegsys[symnum]; /* 表示声明开始的符号集合 */ bool statbegsys[symnum]; /* 表示语句开始的符号集合 */ bool facbegsys[symnum]; /* 表示因子开始的符号集合 */ /* 名字表结构 */ struct tablestruct { char name[al];

/* 名字 */

enum object kind; /* 类型：const,var or procedure */ int val; /* 数值，仅const使用 */ int level; /* 所处层，仅const不使用 */ int adr; /* 地址，仅const不使用 */

int size; /* 需要分配的数据区空间，仅procedure使用 */ };

struct tablestruct table[txmaxadd1]; /* 名字表 */

《编译原理》课程组 16 of 37

《编译原理》实验指导书

FILE* fin; FILE* fout; char fname[al];

int err; /* 错误计数器 */ void error(int n); int getsym(); int getch(); void init();

int gen(enum fct x,int y,int z); int test(bool* s1,bool* s2,int n); int inset(int e,bool* s);

int addset(bool* sr,bool* s1,bool* s2,int n); int subset(bool* sr,bool* s1,bool* s2,int n); int mulset(bool* sr,bool* s1,bool* s2,int n); int block(int lev,int tx,bool* fsys); void interpret();

int factor(bool* fsys,int* ptx,int lev); int term(bool* fsys,int* ptx,int lev); int condition(bool* fsys,int* ptx,int lev); int expression(bool* fsys,int* ptx,int lev); int statement(bool* fsys,int* ptx,int lev); void listcode(int cx0);

int vardeclaration(int* ptx,int lev,int* pdx); int constdeclaration(int* ptx,int lev,int* pdx); int postion(char* idt,int tx);

void enter(enum object k,int* ptx,int lev,int* pdx); int base(int l,int* s,int b);

pl0c.c /*

Windows 下c语言PL/0编译程序

在Visual C++ 6.0和Visual C.NET上运行通过 使用方法：

运行后输入PL/0源程序文件名 回答是否输出虚拟机代码 回答是否输出名字表 fa.tmp输出虚拟机代码

fa1.tmp输出源文件及其各行对应的首地址 fa2.tmp输出结果 fas.tmp输出名字表 */

#include #include \#include \/* 解释执行时使用的栈 */

《编译原理》课程组 17 of 37

《编译原理》实验指导书

#define stacksize 500

int main() { bool nxtlev[symnum]; init();

/* 初始化 */

fas=fopen(\ fa1=fopen(\ printf(\ fprintf(fa1,\ scanf(\ /* 输入文件名 */

fin=fopen(fname,\ if(fin) { fprintf(fa1,\ printf(\/* 是否输出虚拟机代码 */

scanf(\

listswitch=(fname[0]=='y'||fname[0]=='Y'); printf(\/* 是否输出名字表 */ scanf(\

tableswitch=(fname[0]=='y'||fname[0]=='Y'); err=0; cc=cx=ll=0; ch=' '; kk=al-1;

if(-1!=getsym()) { fa=fopen(\ fa2=fopen(\

addset(nxtlev,declbegsys,statbegsys,symnum); nxtlev[period]=true;

if(-1==block(0,0,nxtlev)) /* 调用编译程序 */ { fclose(fa); fclose(fa1); fclose(fin); printf(\ return 0;

}

fclose(fa); fclose(fa1);

if(sym!=period)error(9);

if(err==0)interpret(); /* 调用解释执行程序 */

else

《编译原理》课程组 18 of 37

《编译原理》实验指导书

{ printf(\

}

}

fclose(fin);

} else { printf(\ fprintf(fa1,\ fclose(fa1); }

fclose(fas); printf(\ return 0;

}

/* 在适当的位置显示错误 */ void error(int n) { char space[81]; memset(space,32,81);

space[cc-1]=0; /* 出错时当前符号已经读完，所以cc-1 */ printf(\ fprintf(fa1,\ err++; }

/* 词法分析，获取一个符号 */ int getsym() { int i,j,k;

while(ch==' '||ch==10||ch==9) /* 忽略空格、换行和TAB */

{ getchdo;

}

if(ch>='a'&&ch<='z') {

/* 名字或保留字以a..z开头 */

k=0; do { if(k

a[k]=ch; 《编译原理》课程组 19 of 37

《编译原理》实验指导书

k++;

} getchdo;

}

while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9'); a[k]=0; strcpy(id,a); 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 sym=ident; /* 搜索失败则，是名字或数字 */

} else { if(ch>='0'&&ch<='9') {

/* 检测是否为数字：以0..9开头 */

k=0; num=0; sym=number; do { num=10*num+ch-'0'; k++; getchdo;

}

while(ch>='0'&&ch<='9'); /* 获取数字的值 */ k--;

if(k>nmax)error(30);

} else { if(ch==':') /* 检测赋值符号 */

{ getchdo; if(ch=='=') { sym=becomes;

getchdo;

《编译原理》课程组 20 of 37

《编译原理》实验指导书

} else { }

if(ch=='<') { } else { }

if(ch=='>') { } else { }

sym=ssym[ch]; getchdo;

/* 当符号不满足上述条件时，全部按照单字符符号

getchdo; if(ch=='=') { } else { }

sym=gtr; sym=geq; getchdo;

/* 检测大于或大于等于符号 */

getchdo; if(ch=='=') { } else { }

sym=lss; sym=leq; getchdo;

/* 检测小于或小于等于符号 */

} else { }

sym=nul; /* 不能识别的符号 */

处理 */

《编译原理》课程组 21 of 37

《编译原理》实验指导书

}

/* 编译程序主体 */

int block(int lev, /* 当前分程序所在层 */ {

dx=3; tx0=tx;

/* 记录本层名字的初始位置 */

table[tx].adr=cx; gendo(jmp,0,0);

if(lev>levmax)error(32); do {

if(sym==constsym) /* 收到常量声明符号，开始处理常量声明 */ { {

}

while(sym==ident);

constdeclarationdo(&tx,lev,&dx); /* dx的值会被constdeclaration改变，使用指while(sym==comma) { }

if(sym==semicolon) { }

else error(5);

getsymdo; getsymdo;

constdeclarationdo(&tx,lev,&dx);

getsymdo; do

int i;

int dx; /* 名字分配到的相对地址 */ int tx0; /* 保留初始tx */ int cx0; /* 保留初始cx */

bool nxtlev[symnum]; /* 在下级函数的参数中，符号集合均为值参，但由于使用数租实现，

传递进来的是指针，为防止下级函数改变上级函数的集合，开辟新的空间 传递给下级函数，之后所有的nxtlev都是这样 */

int tx, /* 名字表当前尾指针 */ bool* fsys /* 当前模块后跟符号集合 */ ) } return 0;

}

针 */

《编译原理》课程组 22 of 37

《编译原理》实验指导书

}

if(sym==varsym)

/* 收到变量声明符号，开始处理变量声明 */

{ getsymdo; do { vardeclarationdo(&tx,lev,&dx); while(sym==comma) { getsymdo;

vardeclarationdo(&tx,lev,&dx);

}

if(sym==semicolon) { getsymdo; }

else error(5);

}

while(sym==ident);

}

while(sym==procsym) /* 收到过程声明符号，开始处理过程声明 */ { getsymdo; if(sym==ident) { enter(procedur,&tx,lev,&dx); /* 记录过程名字 */

getsymdo;

}

else error(4); /* procedure后应为标识符 */

if(sym==semicolon)

{ getsymdo;

}

else error(5);

/* 漏掉了分号 */

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[semicolon]=true;

if(-1==block(lev+1,tx,nxtlev))return -1; /* 递归调用 */ if(sym==semicolon) { getsymdo;

memcpy(nxtlev,statbegsys,sizeof(bool)*symnum); nxtlev[ident]=true; nxtlev[procsym]=true;

testdo(nxtlev,fsys,6); 《编译原理》课程组 23 of 37

《编译原理》实验指导书

}

/* 初始化 */ void init() {

int i;

/* 设置单字符符号 */

for(i=0;i<=255;i++)ssym[i]=nul; ssym['+']=plus; ssym['-']=minus; ssym['*']=times; ssym['/']=slash; ssym['(']=lparen; ssym[')']=rparen; ssym['=']=eql; ssym[',']=comma; ssym['.']=period; ssym['#']=neq; ssym[';']=semicolon; /* 设置保留字名字 */ }

while(inset(sym,declbegsys));

/* 直到没有声明符号 */

code[table[tx0].adr].a=cx; /* 开始生成当前过程代码 */ table[tx0].adr=cx; /* 当前过程代码地址 */ table[tx0].size=dx; cx0=cx;

gendo(inte,0,dx); /* 生成分配内存代码 */

/* 语句后跟符号为分号或end */

memcpy(nxtlev,fsys,sizeof(bool)*symnum); /* 每个后跟符号集和都包含上层后跟符号集和，以nxtlev[semicolon]=true; nxtlev[endsym]=true;

statementdo(nxtlev,&tx,lev); gendo(opr,0,0);

/* 每个过程出口都要使用的释放数据段指令 */

memset(nxtlev,0,sizeof(bool)*symnum); /*分程序没有补救集合 */ testdo(fsys,nxtlev,8); /* 检测后跟符号正确性 */ listcode(cx0); return 0;

/* 输出代码 */

/* 声明部分中每增加一条声明都会给dx增加1，声明部分已经结束，dx就

}

memcpy(nxtlev,statbegsys,sizeof(bool)*symnum); nxtlev[ident]=true;

testdo(nxtlev,declbegsys,7);

}

else error(5);

/* 漏掉了分号 */

是当前过程数据的size */

便补救 */

《编译原理》课程组 24 of 37

《编译原理》实验指导书

getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[rparen]=true; nxtlev[comma]=true;

/* write的后跟符号为) or , */

/* 调用表达式处理，此处与read不

expressiondo(nxtlev,ptx,lev);

同，read为给变量赋值 */

gendo(opr,0,14); /* 生成输出指令，输出栈顶的值 */

}

while(sym==comma);

if(sym!=rparen)error(33); /* write()中应为完整表达式 */ else { getsymdo; }

}

gendo(opr,0,15); /* 输出换行 */

} else { if(sym==callsym) /* 准备按照call语句处理 */ { getsymdo;

if(sym!=ident)error(14); /* call后应为标识符 */

else { i=postion(id,*ptx);

if(i==0)error(11); /* 过程未找到 */ else { if(table[i].kind==procedur) { gendo(cal,lev-table[i].level,table[i].adr);

call指令 */

}

else error(15);

/* call后标识符应为过程 */

}

getsymdo;

}

} else { if(sym==ifsym) /* 准备按照if语句处理 */

{

getsymdo;

《编译原理》课程组 /* 生成

30 of 37

《编译原理》实验指导书

} else {

/* 循环调用语句处理函数，直到下一个符号不是语句开始符号或收statementdo(nxtlev,ptx,lev);

while(inset(sym,statbegsys)||sym==semicolon) { }

if(sym==endsym) { }

else error(17);

/* 缺少end或； */

getsymdo;

if(sym==semicolon) { }

else error(10);

/* 缺少； */

statementdo(nxtlev,ptx,lev);

getsymdo;

到end */

} else {

if(sym==beginsym) /* 准备按照复合语句处理 */ {

getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[semicolon]=true; nxtlev[endsym]=true;

/* 后跟符号为分号或end */

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[thensym]=true; nxtlev[dosym]=true; if(sym==thensym) { }

else error(16); gendo(jpc,0,0); code[cx1].a=cx;

/* 缺少then */

/* 生成条件跳转指令，跳转地址未知，暂时写0 */ /* 经statement处理后，cx为then后语句执行完的位

cx1=cx; /* 保存当前指令地址 */

statementdo(fsys,ptx,lev); /* 处理then后的语句 */

getsymdo;

/* 后跟符号为then或do */

conditiondo(nxtlev,ptx,lev); /* 调用条件处理（逻辑运算）函数 */

置，它正是前面未定的跳转地址 */

《编译原理》课程组 31 of 37

《编译原理》实验指导书

*/ */ }

/* 表达式处理 */

int expression(bool* fsys,int* ptx,int lev) {

if(sym==plus||sym==minus) /* 开头的正负号，此时当前表达式被看作一个正的或负的项 */ {

addop=sym; getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[plus]=true; nxtlev[minus]=true;

/* 保存开头的正负号 */

enum symbol addop; /* 用于保存正负号 */ bool nxtlev[symnum];

/* 参数意义见block和enter函数 */

} return 0;

}

}

}

}

}

testdo(fsys,nxtlev,19); /* 检测语句结束的正确性 */

}

memset(nxtlev,0,sizeof(bool)*symnum); /* 语句结束无补救集合

if(sym==dosym) { }

else error(18);

/* 缺少do */

statementdo(fsys,ptx,lev); /* 循环体 */ gendo(jmp,0,cx1); /* 回头重新判断条件 */ code[cx2].a=cx;

/* 反填跳出循环的地址，与if类似 */

getsymdo;

if(sym==whilesym) /* 准备按照while语句处理 */ {

cx1=cx; /* 保存判断条件操作的位置 */ getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[dosym]=true;

/* 后跟符号为do */

/* 调用条件处理 */

conditiondo(nxtlev,ptx,lev); gendo(jpc,0,0);

cx2=cx; /* 保存循环体的结束的下一个位置 */

/* 生成条件跳转，但跳出循环的地址未知

《编译原理》课程组 32 of 37

《编译原理》实验指导书

termdo(nxtlev,ptx,lev); /* 处理项 */

if(addop==minus)gendo(opr,0,1); /* 如果开头为负号生成取负指令 */

}

else /* 此时表达式被看作项的加减 */ { memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[plus]=true; nxtlev[minus]=true;

termdo(nxtlev,ptx,lev); /* 处理项 */ }

while(sym==plus||sym==minus) { addop=sym; getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[plus]=true; nxtlev[minus]=true;

termdo(nxtlev,ptx,lev); /* 处理项 */ if(addop==plus) { gendo(opr,0,2);

/* 生成加法指令 */

}

else gendo(opr,0,3);

/* 生成减法指令 */

} return 0;

}

/* 条件处理 */

int condition(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */

{ enum symbol relop; bool nxtlev[symnum]; if(sym==oddsym) /* 准备按照odd运算处理 */

{ getsymdo;

expressiondo(fsys,ptx,lev); gendo(opr,0,6);

/* 生成odd指令 */ } else { /* 逻辑表达式处理 */

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[eql]=true;nxtlev[neq]=true; nxtlev[lss]=true;nxtlev[leq]=true;

nxtlev[gtr]=true;nxtlev[geq]=true; 《编译原理》课程组 33 of 37

《编译原理》实验指导书

expressiondo(nxtlev,ptx,lev);

if(sym!=eql&&sym!=neq&&sym!=lss&&sym!=leq&&sym!=gtr&&sym!=geq)error(20); else { relop=sym; getsymdo;

expressiondo(fsys,ptx,lev); switch(relop) { case eql: gendo(opr,0,8); break;

case neq:

gendo(opr,0,9); break;

case lss:

gendo(opr,0,10); break;

case geq:

gendo(opr,0,11); break;

case gtr:

gendo(opr,0,12); break;

case leq:

gendo(opr,0,13);

break;

}

}

} return 0;

}

/* 项处理 */

int term(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */ { enum symbol mulop; /* 用于保存乘除法符号 */ bool nxtlev[symnum]; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[times]=true; nxtlev[slash]=true;

factordo(nxtlev,ptx,lev); /* 处理因子 */ while(sym==times||sym==slash)

{

《编译原理》课程组 34 of 37

《编译原理》实验指导书

}

/* 因子处理 */

int factor(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */ {

int i;

bool nxtlev[symnum];

testdo(facbegsys,fsys,24); /* 检测因子的开始符号 */ while(inset(sym,facbegsys)) /* 循环直到不是因子开始符号 */ {

if(sym==ident) { }

i=postion(id,*ptx); else { }

getsymdo;

switch(table[i].kind) { }

case constant:

break;

/* 名字为变量 */

/* 找到变量地址并

gendo(lod,lev-table[i].level,table[i].adr); break;

/* 名字为过程 */ /* 不能为过程 */

error(21); break;

/* 名字为常量 */

gendo(lit,0,table[i].val); /* 直接把常量的值入栈 */

/* 查找名字 */

if(i==0)error(11); /* 名字未声明 */

/* 因子为常量或变量 */

} return 0;

mulop=sym; getsymdo;

factordo(nxtlev,ptx,lev); if(mulop==times) { } else { }

gendo(opr,0,5);

/* 生成除法指令 */

gendo(opr,0,4);

/* 生成乘法指令 */

case variable:

将其值入栈 */

case procedur:

《编译原理》课程组 35 of 37

《编译原理》实验指导书

else { if(sym==number) /* 因子为数 */

{ if(num>amax) { error(31); num=0;

}

gendo(lit,0,num); getsymdo;

} else { if(sym==lparen) /* 因子为表达式 */

{ getsymdo;

memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[rparen]=true;

expressiondo(nxtlev,ptx,lev); if(sym==rparen) { getsymdo;

}

else error(22);

/* 缺少右括号 */

}

test(fsys,facbegsys,23);

/* 因子后有非法符号 */

}

}

} return 0;

}

《编译原理》课程组 36 of 37

本文来源：https://www.bwwdw.com/article/a1i.html