编译实验指导书-pl0.doc

编译原理实验指导书实验一 源程序的输入和预处理一、实验目的掌握字符处理的方法，理解设计为独立子程序的好处，为词法分析做好准备。二、实验内容首先编制一个源程序的输入过程，从键盘、文件或文本框输入若干行语句，依次存入输入缓冲区（字符型数据）；然后编制一个预处理子程序，去掉输入串中的回车符、换行符和跳格符等编辑性文字；把多个空白符合并为一个；去掉注释。假定要处理的语言采用自由格式书写，空白符作为分隔符，可以使用注解，用/*/或者标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束。三、实验报告要求1、写出编程思路、源代码；2、写出上机调试时发现的问题，以及解决的过程；3、写出所使用的测试数据；4、谈谈体会。四、上交1、实验报告；2、程序源文件（老师检查）。实验二 词法分析器的设计（设计性实验）一、实验目的掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。二、实验内容实现PL/0语言的词法分析器，输入源程序，并对其进行扫描和分解，识别出单词符号。PL/0语言词法规则定义如下：1、唯一的数据类型是整型；2、算符和界符有： +， -， *， /， ， =， ， =， =， ，. ，（，），；，：=3、标识符以字母开头，后跟字母和/或数字组成的字符串；4、关键字作为保留字，如下所示：const，var，procedure，call，begin，end，if，then，while，do，odd三、实验要求1、单词符号输出形式为（种别编码，属性值）种别编码如下：类别单词编码类别单词编码类别单词编码关键字const1odd1121var2算符和界符+12.22procedure3-13(23call4*14)24begin5/15,25end616;26if7=17:=27then818标识符id28while9 0 dobeginif odd b then z := z + a;a := 2 * a; b := b / 2;endend;procedure divide;var w;beginr := x; q := 0; w := y;while w y dobeginq := 2 * q; w := w / 2;if w = r thenbeginr := r - w;q := q + 1;end;endend;procedure gcd;var f, g;beginf := x;g := y;while f g dobeginif f g then g := g - f;if g 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+;break;case ID_PROCEDURE:mk = (mask*) &tabletx;mk-level = level;break; / switch / enter/ locates identifier in symbol position(char* id)int i;strcpy(, id);i = tx + 1;while (strcmp(, id) != 0);return i; / position/void constdeclaration()if (sym = SYM_IDENTIFIER)getsym();if (sym = SYM_EQU | sym = SYM_BECOMES)if (sym = SYM_BECOMES)error(1); / Found := when expecting =.getsym();if (sym = SYM_NUMBER)enter(ID_CONSTANT);getsym();elseerror(2); / There must be a number to follow =.elseerror(3); / There must be an = to follow the identifier.error(4); / There must be an identifier to follow const, var, or procedure. / constdeclaration/void vardeclaration(void)if (sym = SYM_IDENTIFIER)enter(ID_VARIABLE);getsym();elseerror(4); / There must be an identifier to follow const, var, or procedure. / vardeclaration/void listcode(int from, int to)int i;printf(n);for (i = from; i level, mk-address);break;case ID_PROCEDURE:error(21); / Procedure identifier can not be in an expression.break; / switchgetsym();else if (sym = SYM_NUMBER)if (num MAXADDRESS)error(25); / The number is too great.num = 0;gen(LIT, 0, num);getsym();else if (sym = SYM_LPAREN)getsym();set = uniteset(createset(SYM_RPAREN, SYM_NULL), fsys);expression(set);destroyset(set);if (sym = SYM_RPAREN)getsym();elseerror(22); / Missing ).test(fsys, createset(SYM_LPAREN, SYM_NULL), 23); / while / factor/void term(symset fsys)int mulop;symset set;set = uniteset(fsys, createset(SYM_TIMES, SYM_SLASH, SYM_NULL);factor(set);while (sym = SYM_TIMES | sym = SYM_SLASH)mulop = sym;getsym();factor(set);if (mulop = SYM_TIMES)gen(OPR, 0, OPR_MUL);elsegen(OPR, 0, OPR_DIV); / whiledestroy