编译实验指导书

编译原理实验指导书实验一 源程序的输入和预处理一、实验目的掌握字符处理的方法，理解设计为独立子程序的好处，为词法分析做好准备。二、实验内容首先编制一个源程序的输入过程， 从键盘、 文件或文本框输入若干行语句， 依次存入输 入缓冲区（字符型数据） ；然后编制一个预处理子程序，去掉输入串中的回车符、换行符和 跳格符等编辑性文字；把多个空白符号并为一个；去掉注释。假定要处理的语言采用自由格式书写，空白符作为分隔符，可以使用注解，用/*/或者标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到 注释后面的结束标记，自动认为注释也结束。三、实验报告要求1、写出编程思路、源代码；2、写出上机调试时发现的问题，以及解决的过程；3、写出所使用的测试数据；4、谈谈体会。四、上交1、实验报告；2、程序源文件（老师检查） 。实验二词法分析器（设计性实验）、实验目的掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。、实验内容实现PL/O语言的词法分析器， 输入源程序，并对其进行扫描和分解，识别出单词符号PL/O语言词法规则定义如下:1、唯一的数据类型是整型；，/ ， (丿 3、标识符以字母开头，后跟字母和/或数字组成的字符串;2、算符和界符有：+ ,-：* 丿厂，丿=丿 丿丿=丿 =, 丿4、关键字作为保留字，如下所示:con st, var, procedure, call, begi n, end, if, the n.while , do, odd三、实验要求1、单词符号输出形式为（种别编码，单词符号自身值）种别编码如下:别 类词 单码 编别 类词 单码 编别 类词 单码 编关键字st con1d11 V21r a V2算符和界符+2223-3/_k32call4*41!724g e b5/552e661627=71278V8符 识 标82g N w9=V9I92o1一一O2附加：1、检查是否有误 单词/ ERROR,编码/ 30）2、词法分析器要求设计成为独立的子程序。3、测试数据举例:const m = 7, n = 85; var x, y, z, q, r;procedure multiply;var a, b;begina := x; b := y; z := 0;while b 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 then beginr := 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 X1X2 Xn 的产生式 dofor i =1 to n-1 dobeginif Xi 和 Xi+1 都是终结符 thenXi = Xi+1if i= n-2, Xi 和 Xi+2 是终结符 , 但 Xi+1 为非终结符 then Xi = Xi+2if Xi 为终结符 , Xi+1 为非终结符 thenfor FirstVT 中的每个元素 a doXi Xi+1 ;end;3、构造算符优先分析和中间代码产生过程。四、输入数据和输出数据若输入文法：E-E+T | TT-T*F | FF- (E) | i+(iE 的 firstVT1111E 的 firstVT1IlE 的 firstVT11输出的优先关系表如下:+*1()n+*i*-u.(Vv)二2若输入的语句是a:=b+c*(e-a)则输出：(-，e,a,T1)(*,c,T1,T2) (+,b,T2,T3)(:=,T3,_,a)实验四 PL/O编译器的分析和理解一、实验目的通过阅读PL/0编译器，理解整个编译过程，掌握编译每一阶段的实现方法; 并加深对理论知识的认识。二、实验要求阅读PL/0编译器，完成以下任务：1、画出整个程序流程图及各编译阶段处理的流程图；2、写出每一编译阶段实现中用到的主要理论，及对该理论的理解；3、写出你的心得和体会。4、就上述部分写出实验报告，A4纸（10页以内）。（初步这样定）三、实验提示3、语句序列语句序列begin4、语句*1“ 一 A表达式ide ntJfcriLcallJide ntjr7Lendj5、条件6、表达式7、项8、因子（二）语法分析这里采用递归下降的方法来设计PL/O编译器。以下我们给出该语言的FIRST和FOLLOW集合。非终结符（S）FIRST(S)FOLLOW(S)程序体const var procedure ide nt call if begi n while语句：ide nt call begi n if while.;end条件odd + - ( ide nt nu mberthe n do表达式+ - ( ide nt nu mber.;)R end then do项ide nt nu mber (.;)R + - end the n do因子ide nt nu mber (.;)R + - * / end then do注：表中R代表六个关系运算符（三）PL/O处理机的指令集根据PL/O语言的要求，它包括以下的指令:(1)LIT(2)LOD(3)STO(4)CAL(5)INT(6)JMP, JPC(7)OPR/*将常数置于栈顶*/*将变量值置于栈顶*/*将栈顶的值赋与某变量*/*用于过程调用的指令*/*在数据栈中分配存贮空间*/*用于if, while语句的条件或无条件控制转移指令*/* 一组算术或逻辑运算指令*/FLA其中，f, I, 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 NRW11 / number of reserved words#define TXMAX500/ length of identifier table#define MAXNUMLEN 14/ maximum number of digits in numbers#define NSYM10 / maximum number of symbols in array ssym and csym#define MAXIDLEN 10/ length of identifiers#define MAXADDRESS 32767#define MAXLEVEL32#define CXMAX500/ maximum address/ maximum depth of nesting block/ size of code array#define MAXSYM30 / 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_V ARIABLE, 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 */IlliJ/*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 */IlliJ/* 27 */IlliJ/* 28 */IlliJ/* 29 */IlliJ/* 30 */IlliJ/* 31 */IlliJ/* 32 */There are too many levels.;/ char ch;/ last character readintsym;/ last symbol readchar idMAXIDLEN+ 1; / last identifier readintnum;/ last number readintcc;/ character countintll;/ line lengthintkk;interr;intcx;/ index of current instruction to be generated.intlevel = 0;inttx = 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#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#include #include #include #include set.h symset 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; / setinsert symset 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 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( );prin tf(An);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; / while printf(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;do if (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(tabletx.name, 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 table.int position(char* id)int i;strcpy(table0.name, id);i = tx + 1;while (strcmp(table-i.name, 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_V ARIABLE);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); / while destroyset(set); / term/void expression(symset fsys)int addop;symset set;set = uniteset(fsys, createset(SYM_PLUS, SYM_MINUS, SYM_NULL); if (sym = SYM_PLUS | sym = SYM_MINUS)addop = sym;getsym();term(set);if (addop = SYM_MINUS)gen(OPR, 0, OPR_NEG);elseterm(set);while (sym = SYM_PLUS | sym = SYM_MINUS)addop = sym; getsym(); term(set);if (addop = SYM_PLUS)gen(OPR, 0, OPR_ADD); else gen(OPR, 0, OPR_MIN); / whiledestroyset(set); / expression/ void condition(symset fsys)int relop; symset set;if (sym = SYM_ODD) getsym(); expression(fsys); gen(OPR, 0, 6);elseset = uniteset(relset, fsys); expression(set); destroyset(set);if (! inset(sym, relset)error(20);else relop = sym; getsym(); expression(fsys);switch (relop)case SYM_EQU:gen(OPR, 0, OPR_EQU); break;case SYM_NEQ:gen(OPR, 0, OPR_NEQ); break;case SYM_LES:gen(OPR, 0, OPR_LES); break;case SYM_GEQ:gen(OPR, 0, OPR_GEQ); break;case SYM_GTR:gen(OPR, 0, OPR_GTR); break;case SYM_LEQ:gen(OPR, 0, OPR_LEQ); break; / switch / else / else / condition/void statement(symset fsys)int i, cx1, cx2;symset set1, set;if (sym = SYM_IDENTIFIER) / variable assignmentmask* mk;if (! (i = position(id)error(11); / Undeclared identifier.else if (tablei.kind != ID_V ARIABLE)error(12); / Illegal assignment.i = 0;getsym();if (sym = SYM_BECOMES)getsym();elseerror(13); / := expected. expression(fsys); mk = (mask*) &tablei;if (i)gen(STO, level - mk-level, mk-address);else if (sym = SYM_CALL) / procedure call getsym(); if (sym != SYM_IDENTIFIER)error(14); / There must be an identifier to follow the call. elseif (! (i = position(id)error(11); / Undeclared identifier.else if (tablei.kind = ID_PROCEDURE)mask* mk;mk = (mask*) &tablei;gen(CAL, level - mk-level, mk-address); elseerror(15); / A constant or variable can not be called. getsym();else if (sym = SYM_IF) / if statement getsym();set1 = createset(SYM_THEN, SYM_DO, SYM_NULL); set = uniteset(set1, fsys);condition(set);destroyset(set1);destroyset(set);if (sym = SYM_THEN)getsym();elseerror(16); / then expected.cx1 = cx;gen(JPC, 0, 0);statement(fsys);codecx1.a = cx;else if (sym = SYM_BEGIN) / blockgetsym();set1 = createset(SYM_SEMICOLON, SYM_END, SYM_NULL); set = uniteset(set1, fsys);statement(set);while (sym = SYM_SEMICOLON | inset(sym, statbegsys)if (sym = SYM_SEMICOLON)getsym();elseerror(10);statement(set); / whiledestroyset(set1);destroyset(set);if (sym = SYM_END)getsym();elseelse if (sym = SYM_WHILE) / while statementcx1 = cx;getsym();set1 = createset(SYM_DO, SYM_NULL); set = uniteset(set1, fsys); condition(set);destroyset(set1); destroyset(set); cx2 = cx; gen(JPC, 0, 0);if (sym = SYM_DO)getsym();els