编译实验指导书.doc

编译原理实验指导书实验一 源程序的输入和预处理一、实验目的掌握字符处理的方法，理解设计为独立子程序的好处，为词法分析做好准备。二、实验内容首先编制一个源程序的输入过程，从键盘、文件或文本框输入若干行语句，依次存入输入缓冲区（字符型数据）；然后编制一个预处理子程序，去掉输入串中的回车符、换行符和跳格符等编辑性文字；把多个空白符合并为一个；去掉注释；并记录行号。假定 SAMPLE 语言采用自由格式书写，空白符作为分隔符，可以使用注解，用/*/或者标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束。三、实验报告要求1、写出编程思路、源代码；2、写出上机调试时发现的问题，以及解决的过程；3、写出所使用的测试数据；4、谈谈体会。四、上交1、实验报告；2、程序源文件（老师检查）。实验二 词法分析器（设计性实验）一、实验目的掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。二、实验过程和指导（一）词法分析器的结构和主要任务【输入输出接口】词法分析程序的主要任务是从左到右扫描每行源程序，拼成单词，换成统一的内部表示 (token)输出，送给语法分析器。具体包括： 组织源程序的输入； 按规则拼单词，并转换成二元形式； 滤掉空白符，跳过注释、换行符及一些无用的符号(如字符常数的引号) （实验一已完成）；进行行列计数，用于指出出错的行列号，并复制出错部分； 列表打印源程序； 发现并定位词法错误； 生成符号表。token 文件和符号表用作语法分析的输入部分。【条件限制】(1) 假定 SAMPLE 语言采用自由格式书写； (2) 可以使用注解，用/*/或者标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束； (3) 一行可以有多个语句，一个语句也可以分布在多行中，单词之间和语句之间可以插入任意空格，单词中间不能有空白符号，单词中间也不能有回车换行符，即单词不能跨行书写； (4) 关键字都是保留字。（二）词法分析程序的总体设计 图 1-2 是词法分析程序的顶层数据流图，即是词法分析程序的输入输出界面图，由此可以看出词法分析程序的功能就是从源程序中读入一个个字符，依据一定的构词规则，识别出各类有用的单词。其中源程序清单和错误信息从屏幕、打印机或文件输出，其余文件均以顺序文件的形式输出到外存储器上，以供下一阶段使用。由此可以得到更详细的数据流图，如图 1-3。在上面的数据流图中，各个加工处理完成的功能如下： 加工 1.1(读一行并打印)：收到读下一行命令后，从源程序读入一行，装入缓冲区，行计数，并打印。在这里需要注意的是，回车换行在源程序（文本文件）中 用两个字符 0D0AH来表示，而用高级语言（C 语言）读入内存后，就用一个字符 0AH 来表示，这是在用高级语言编写词法分析器时常被忽略导致错误的原因。 加工 1.2(读一非空字符)：收到读一字符命令后，从缓冲区读入一非空字符，列计数。若缓冲区已空，则再读一行，列计数置为0。 加工 1.3(分类)：根据单词的首字符以决定对不同类单词的处理。 加工 1.4(识别标识符)：当输入字母时，开始识别标识符或关键字，边拼写边从缓冲区读入下一符号，当读入一非字母数字符号时，标识符识别完成，但已多读入一个符号，所以列记数回退。然后查关键字表，判断拼出的符号串是否为关键字。若是关键字，输出其种别码，否则识别的单词就是标识符，同时输出标识符及其种别码。 加工 1.5(识别常数)：当输入数字时，开始识别整数或实数。边拼写边读入下一符号，当遇到“.”时，还要继续拼写该常数(实数情况)。如果遇到 E，要识别带指数的常数，当遇到其它非数字符号时，数字常数拼写完毕，列计数也要退 1。输出常数及其种别码。 加工 1.6(处理注解)：当输入“”时，开始识别注解或除号，若是注解时，最后两个连续读出的符号是“*”，不需再读下一符号，列计数不变。当判定是除号“”时，已多读入一字符，列计数减1，输出“/”的种别编码。加工 1.7(识别分界符)：识别其它界符，对于、：、|、等符号，还需要再读入下一符号，判别是否为双界符。若不是，列计数 1，输出单词的种别码。加工 1.8(识别文字常数)：当输入引号时，引号忽略，开始拼写字符常数，不断拼读下一符号，搜索下一个引号，当读入第二个引号时，字符常数拼写结束。最后列计数不减1，后输出该常数。以上加工 1.41.8 都需要从缓冲区 A每次读出一个字符，进行列计数。由于假定每个单词不跨行，所以不用考虑从源程序中读出下一行到缓冲区的功能。加工 1.9(输出 TOKEN)：对各种界符与关键字输出其相应的二元式(TOKEN)，对常数与标识符则让它流入下一个加工。加工 2(查填符号表)：如果是标识符或字符常数，首先查看名字栏和类型栏(字符常数的类型栏中填有“字符常数”；标识符栏的类型栏空白)判断有无同名和同类型的入口。如果有同名入口 P1，则把 P1 作为 TOKEN的自身值填入它的二元式中；如果不同名，则将字符中存入字符串表中，把它的长度和在字符串表中的开始位置及其类型(标识符为空白)填入符号表的新入口 P中，并把 P作为 TOKEN的自身值填入的二元式中。对数字常数的处理如下：先查符号表 VAL 栏，若发现相同的常数则直接输出其二元式。若表内无相同的常数，则将数字常数填入符号表内，在 TYPE 栏内填入整型或实型，然后输出其二元式。二元式中包含该常数在符号表中的入口。（三） 词法分析程序的详细设计图 1-3 的数据流图属于输入-变换-输出形式的变换型数据流图，但加工1.31.9 构成了典型的事务处理型数据流图。根据数据流图，可以得到词法分析程序的总体框架，如图 1-4。（四）实验步骤步骤一 编写词法分析的总控程序步骤二 定义符号表，编写查找和插入函数表（1）单词种别编码每一种已经定义的语言的关键字和界符都是固定的，为了给出单词的种别码，我们在编写 SAMPLE 语言的词法分析器时采取关键字和界符一符一种，标识符、整型常数、实型常数、字符型常数分别给一个种别码，再根据其值定义判断。Sample 语言中的单词(关键字、界符、数的类型)的种别码如表 1-1。（2）定义符号表编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。这些信息通常记录在符号表中。符号表中的每一项一般包含两部分：名字，与此名字有关的信息，如类型，种属，值等。符号表主要在词法或语法分析阶段生成，可能用于语义检查、产生中间代码以及最终生成目标代码等不同阶段。当从源程序中识别出一个标识符或常数，就要检查符号表中是否已经存在该标识符或常数，若不存在，就应将其加入符号表，若存在就不加入。符号表可以和常数表合在一起，这可能增加查填符号表的复杂性。也可以将符号表、常数表分开建立，方便查填。定义 SAMPLE 语言的符号表的格式如下表，其中 name 项包含两个内容，一个是单词本身，一个是它的长度。可以直接将单词放在名字栏，也可以另外使用一个字符串数组，将单词本身放在字符串中，在符号表中填入该单词在字符串中的指针。步骤三 单词识别函数的编写三、输入数据和输出数据 输入源程序名称：Example.src/*this is a sample program writing in sample language*/ program example1; /*used for illustrating compiling process*/ var a,b,c:integer; x:char; begin if (a+c*3 b) and (b3) then c:=3; x:=2+(3*a)-b*c*8; if (2+3 a) and (b3) and (ac) then c:=3; for x := 1+2 to 3 do b:=100; while ab do c:=5; repeat a:=10; until ab; end.下面是对上述输入源程序进行词法分析得到 token 文件(部分内容)和符号表的内容： Token表的内容如下：program example1 ; var a , b , c : integer ; ; end . 符号表的内容如下：(34, example1 ) (34, a ) (34, b ) (34, c ) (34, x ) (35, 3 ) (35, 2 ) (35, 8 ) (35, 1 ) (35, 100 ) (35, 5 ) (34, d ) (35, 15 ) (34, t ) (35, 10 )实验三 算符优先分析器（综合性实验）一、实验目的掌握 FirstVT和 LastVT集的算法，算符优先分析表的构造算法及其分析过程，并掌握中间代码产生过程。各10%，算符优先80%，二、实验内容算术表达式和赋值语句的文法可以是（可以根据需要适 当改变）： Si=EEE+TEE-TETTT*F TT/F TFF(E)Fi Fnum 根据算符优先分析法，将赋值语句进行语法语义分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。三、实验过程和指导1、构造FirstVT和LastVT集合给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的 FirstVT 集和LastVT 集。算符描述如下：/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not FP,a then begin fp,a = true; (P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P和终结符 a do FP,a = false for 对每个形如 Pa或 PQa的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 PQ的产生式 do insert(P,a) end; end.2、构造算符优先分析表依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下：for 每个形如 P-X1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和 Xi+1都是终结符 then Xi = Xi+1 if i= n-2, Xi和 Xi+2 是终结符, 但 Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi Xi+1 ; end;3、构造算符优先分析和中间代码产生过程。四、输入数据和输出数据若输入文法： E-E+T | T T-T*F | F F- (E) | i 将得到如下所示的 FirstVT 集和LastVT数组。输出的优先关系表如下：若输入的语句是 a:=b+c*(e-a)则输出：(-，e,a,T1)(*,c,T1,T2)(+,b,T2,T3)(:=,T3,_,a)实验四 PL/0编译器的分析和理解一、实验目的通过阅读PL/0编译器，理解整个编译过程，掌握编译每一阶段的实现方法；并加深对理论知识的认识。二、实验要求阅读PL/0编译器，完成以下任务：1、画出整个程序流程图及各编译阶段处理的流程图；2、写出每一编译阶段实现中用到的主要理论，及对该理论的理解；3、写出你的心得和体会。4、就上述部分写出实验报告，A4纸（10页以内）。（初步这样定）三、实验提示程序体.（一）PL/0语言的语法图1、程序2、程序体3、语句序列语句;4、语句identcallbeginwhileendident:=ifdothen语句语句表达式语句序列条件条件5、条件表达式odd表达式=表达式6、表达式项项+-+7、项因子因子/*8、因子identnumber表达式()（二）语法分析这里采用递归下降的方法来设计PL/0编译器。以下我们给出该语言的FIRST和FOLLOW集合。非终结符（S）FIRST(S)FOLLOW(S)程序体const var procedure ident call if begin while. ;语句ident call begin if while. ; end条件odd + - ( ident numberthen do表达式+ - ( ident number. ; ) R end then do项ident number (. ; ) R + - end then do因子ident number (. ; ) R + - * / end then do注：表中R代表六个关系运算符。（三）PL/0处理机的指令集根据PL/0语言的要求，它包括以下的指令：（1）LIT /* 将常数置于栈顶 */（2）LOD /* 将变量值置于栈顶 */（3）STO /* 将栈顶的值赋与某变量 */（4）CAL /* 用于过程调用的指令 */（5）INT /* 在数据栈中分配存贮空间 */（6）JMP, JPC /* 用于if, while语句的条件或无条件控制转移指令 */（7）OPR /* 一组算术或逻辑运算指令 */FLA上述指令的格式由三部分组成：其中，f, l, a的含义见下表： FLaINT常 量LIT常 量LOD层次差数据地址STO层次差数据地址CAL层次差程序地址JMP程序地址JPC程序地址OPR运算类别（四）PL/0语言编译器源程序PL/0语言编译器源程序包括如下C程序文件，PL0.h、PL0.c、set.h和set.c。/* PL0.h */#include #define NRW 11 / number of reserved words#define TXMAX 500 / length of identifier table#define MAXNUMLEN 14 / maximum number of digits in numbers#define NSYM 10 / maximum number of symbols in array ssym and csym#define MAXIDLEN 10 / length of identifiers#define MAXADDRESS 32767 / maximum address#define MAXLEVEL 32 / maximum depth of nesting block#define CXMAX 500 / size of code array#define MAXSYM 30 / maximum number of symbols #define STACKSIZE 1000 / maximum storageenum symtypeSYM_NULL,SYM_IDENTIFIER,SYM_NUMBER,SYM_PLUS,SYM_MINUS,SYM_TIMES,SYM_SLASH,SYM_ODD,SYM_EQU,SYM_NEQ,SYM_LES,SYM_LEQ,SYM_GTR,SYM_GEQ,SYM_LPAREN,SYM_RPAREN,SYM_COMMA,SYM_SEMICOLON,SYM_PERIOD,SYM_BECOMES, SYM_BEGIN,SYM_END,SYM_IF,SYM_THEN,SYM_WHILE,SYM_DO,SYM_CALL,SYM_CONST,SYM_VAR,SYM_PROCEDURE;enum idtypeID_CONSTANT, ID_VARIABLE, ID_PROCEDURE;enum opcodeLIT, OPR, LOD, STO, CAL, INT, JMP, JPC;enum oprcodeOPR_RET, OPR_NEG, OPR_ADD, OPR_MIN,OPR_MUL, OPR_DIV, OPR_ODD, OPR_EQU,OPR_NEQ, OPR_LES, OPR_LEQ, OPR_GTR,OPR_GEQ;typedef structint f; / function codeint l; / levelint a; / displacement address instruction;/char* err_msg =/* 0 */ ,/* 1 */ Found := when expecting =.,/* 2 */ There must be a number to follow =.,/* 3 */ There must be an = to follow the identifier.,/* 4 */ There must be an identifier to follow const, var, or procedure.,/* 5 */ Missing , or ;.,/* 6 */ Incorrect procedure name.,/* 7 */ Statement expected.,/* 8 */ Follow the statement is an incorrect symbol.,/* 9 */ . expected.,/* 10 */ ; expected.,/* 11 */ Undeclared identifier.,/* 12 */ Illegal assignment.,/* 13 */ := expected.,/* 14 */ There must be an identifier to follow the call.,/* 15 */ A constant or variable can not be called.,/* 16 */ then expected.,/* 17 */ ; or end expected.,/* 18 */ do expected.,/* 19 */ Incorrect symbol.,/* 20 */ Relative operators expected.,/* 21 */ Procedure identifier can not be in an expression.,/* 22 */ Missing ).,/* 23 */ The symbol can not be followed by a factor.,/* 24 */ The symbol can not be as the beginning of an expression.,/* 25 */ The number is too great.,/* 26 */ ,/* 27 */ ,/* 28 */ ,/* 29 */ ,/* 30 */ ,/* 31 */ ,/* 32 */ There are too many levels.;/char ch; / last character readint sym; / last symbol readchar idMAXIDLEN + 1; / last identifier readint num; / last number readint cc; / character countint ll; / line lengthint kk;int err;int cx; / index of current instruction to be level = 0;int tx = 0;char line80;instruction codeCXMAX;char* wordNRW + 1 =, /* place holder */begin, call, const, do, end,if,odd, procedure, then, var, while;int wsymNRW + 1 =SYM_NULL, SYM_BEGIN, SYM_CALL, SYM_CONST, SYM_DO, SYM_END,SYM_IF, SYM_ODD, SYM_PROCEDURE, SYM_THEN, SYM_VAR, SYM_WHILE;int ssymNSYM + 1 =SYM_NULL, SYM_PLUS, SYM_MINUS, SYM_TIMES, SYM_SLASH,SYM_LPAREN, SYM_RPAREN, SYM_EQU, SYM_COMMA, SYM_PERIOD, SYM_SEMICOLON;char csymNSYM + 1 = , +, -, *, /, (, ), =, , ., ;#define MAXINS 8char* mnemonicMAXINS =LIT, OPR, LOD, STO, CAL, INT, JMP, JPC;typedef structchar nameMAXIDLEN + 1;int kind;int value; comtab;comtab tableTXMAX;typedef structchar nameMAXIDLEN + 1;int kind;short level;short address; mask;FILE* infile;/ EOF PL0.h/* SET.h */#ifndef SET_H#define SET_Htypedef struct snodeint elem;struct snode* next; snode, *symset;symset phi, declbegsys, statbegsys, facbegsys, relset;symset createset(int data, ./* SYM_NULL */);void destroyset(symset s);symset uniteset(symset s1, symset s2);int inset(int elem, symset s);#endif/ EOF set.h/* SET.c */#include #include #include #include set.hsymset uniteset(symset s1, symset s2)symset s;snode* p;s = p = (snode*) malloc(sizeof(snode);while (s1 & s2)p-next = (snode*) malloc(sizeof(snode);p = p-next;if (s1-elem elem)p-elem = s1-elem;s1 = s1-next;elsep-elem = s2-elem;s2 = s2-next;while (s1)p-next = (snode*) malloc(sizeof(snode);p = p-next;p-elem = s1-elem;s1 = s1-next;while (s2)p-next = (snode*) malloc(sizeof(snode);p = p-next;p-elem = s2-elem;s2 = s2-next;p-next = NULL;return s; / unitesetvoid setinsert(symset s, int elem)snode* p = s;snode* q;while (p-next & p-next-elem next;q = (snode*) malloc(sizeof(snode);q-elem = elem;q-next = p-next;p-next = q; / setinsertsymset createset(int elem, ./* SYM_NULL */)va_list list;symset s;s = (snode*) malloc(sizeof(snode);s-next = NULL;va_start(list, elem);while (elem)setinsert(s, elem);elem = va_arg(list, int);va_end(list);return s; / createsetvoid destroyset(symset s)snode* p;while (s)p = s;s = s-next;free(p); / destroysetint inset(int elem, symset s)s = s-next;while (s & s-elem next;if (s & s-elem = elem)return 1;elsereturn 0; / inset/ EOF set.c/* PL0.c */ pl0 compiler source code#include #include #include #include #include set.h#include pl0.h/ print error message.void error(n)int i;printf( );for (i = 1; i = cc - 1; i+)printf( );printf(n);printf(Error %3d: %sn, n, err_msgn);err+; / error/void getch(void)if (cc = ll)if (feof(infile)printf(nPROGRAM INCOMPLETEn);exit(1);ll = cc = 0;printf(%5d , cx);while (!feof(infile) & (ch = getc(infile)!=n)printf(%c, ch);line+ll = ch; / whileprintf(n);line+ll = ;ch = line+cc; / getch/ gets a symbol from input stream.void getsym(void)int i, k;char aMAXIDLEN + 1;while (ch = )getch();if (isalpha(ch) / symbol is a reserved word or an identifier.k = 0;doif (k MAXNUMLEN)error(25); / The number is too great.else if (ch = :)getch();if (ch = =)sym = SYM_BECOMES; / :=getch();elsesym = SYM_NULL; / illegal?else if (ch = )getch();if (ch = =)sym = SYM_GEQ; / =getch();elsesym = SYM_GTR; / else if (ch = )getch();if (ch = =)sym = SYM_LEQ; / )sym = SYM_NEQ; / getch();elsesym = SYM_LES; / CXMAX)printf(Fatal Error: Program too long.n);exit(1);codecx.f = x;codecx.l = y;codecx+.a = z; / gen/ tests if error occurs and skips all symbols that do not belongs to s1 or s2.void test(symset s1, symset s2, int n)symset s;if (! inset(sym, s1)error(n);s = uniteset(s1, s2);while(! inset(sym, s)getsym();destroyset(s); / test/int dx; / data allocation index/ enter object(constant, variable or procedre) into table.void enter(int kind)mask* mk;tx+;strcpy(, id);tabletx.kind = kind;switch (kind)case ID_CONSTANT:if (num MAXADDRESS)error(25); / The number is too great.num = 0;tabletx.value = num;break;case ID_VARIABLE:mk = (mask*) &tabletx;mk-level = level;mk-address = dx+;bre