编译实验指导书

1、编译原理实验指导书实验一 源程序的输入和预处理一、实验目的掌握字符处理的方法，理解设计为独立子程序的好处，为词法分析做好准备。二、实验内容首先编制一个源程序的输入过程， 从键盘、 文件或文本框输入若干行语句， 依次存入输 入缓冲区（字符型数据） ；然后编制一个预处理子程序，去掉输入串中的回车符、换行符和 跳格符等编辑性文字；把多个空白符号并为一个；去掉注释。假定要处理的语言采用自由格式书写，空白符作为分隔符，可以使用注解，用/*/或者标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到 注释后面的结束标记，自动认为注释也结束。三、实验报告要求1、写出编程思路、源代码；2、写出

2、上机调试时发现的问题，以及解决的过程；3、写出所使用的测试数据；4、谈谈体会。四、上交1、实验报告；2、程序源文件（老师检查） 。实验二词法分析器（设计性实验）、实验目的掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。、实验内容实现PL/O语言的词法分析器， 输入源程序，并对其进行扫描和分解，识别出单词符号PL/O语言词法规则定义如下:1、唯一的数据类型是整型；，'/ ' '' '， ('丿 ' '3、标识符以字母开头，后跟字母和/或数字组成的字符串;2、算符和界符有：'+ ','

3、;-：'* '丿'厂，>'丿'>='丿 丿'丿'<=丿 '=','<> '丿4、关键字作为保留字，如下所示:con st, var, procedure, call, begi n, end, if, the n.while , do, odd三、实验要求1、单词符号输出形式为（种别编码，单词符号自身值）种别编码如下:别 类词 单码 编别 类词 单码 编别 类词 单码 编关键字st con1d11> V21r a V2算符和界符+2223-3/_k32call4*

4、41!724g e b5/552e6>61627=>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;proc

5、edure 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 < f then f := f - g; endend;beginx := m; y :=

6、 n; call multiply;x := 25; y := 3; call divide;x := 34; y := 36; call gcd; end.四、实验报告要求1、写出编程思路；2、写出上机调试时发现的问题，以及解决的过程；3、写出所使用的测试数据及结果；4、谈谈体会。五、上交1、实验报告；2、程序源文件（老师检查）实验三 算符优先分析器(综合性实验)一、实验目的掌握 FirstVT 和 LastVT 集的算法，算符优先分析表的构造算法及其分析过程，并掌握 中间代码产生过程。二、实验内容算术表达式和赋值语句的文法可以是(可以根据需要适当改变) ：St i=EEt E+E|E-E|

7、E*E|E/E| (E) |i根据算符优先分析法， 将赋值语句进行语法语义分析， 翻译成等价的一组基本操作， 每 一基本操作用四元式表示。三、实验过程和指导1、构造 FirstVT 和 LastVT 集合 给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT集和 LastVT 集。算符描述如下：/*求 FirstVT 集的算法 */PROCEDURE insert(P,a);IF not FP,a thenbeginfp,a = true; (P,a) 进栈end;Procedure FirstVT;Beginfor 对每个非终结符 P 和终结符 a doFP,a

8、 = falsefor对每个形如 Pt a或 Pt Qa的产生式 doInsert(P,a)while stack 非空begin栈顶项出栈，记为 (Q,a)for 对每条形如 Pt Q的产生式 doinsert(P,a)end;end.2、构造算符优先分析表依据文法和求出的相应 FirstVT 和 LastVT 集生成算符优先分析表。 算法描述如下：for 每个形如 P->X1X2 Xn 的产生式 dofor i =1 to n-1 dobeginif Xi 和 Xi+1 都是终结符 thenXi = Xi+1if i<= n-2, Xi 和 Xi+2 是终结符 , 但 Xi+1

9、 为非终结符 then Xi = Xi+2if Xi 为终结符 , Xi+1 为非终结符 thenfor FirstVT 中的每个元素 a doXi < a ;if Xi 为非终结符 , Xi+1 为终结符 thenfor LastVT 中的每个元素 a doa > Xi+1 ;end;3、构造算符优先分析和中间代码产生过程。四、输入数据和输出数据若输入文法：E->E+T | TT->T*F | FF-> (E) | i+(iE 的 firstVT1111E 的 firstVT1IlE 的 firstVT11输出的优先关系表如下:+*1()n+>*>&

10、gt;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

11、“ 一 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 n

12、u 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常量

13、LIT常量LOD层次差数据地址STO层次差数据地址CAL层次差程序地址JMP程序地址JPC程序地址OPR运算类别四） PL/0 语言编译器源程序PL/0 语言编译器源程序包括如下 C 程序文件， PL0.h、PL0.c、set.h 和 set.c。*PL0.h*#include <stdio.h>#define NRW11 / number of reserved words#define TXMAX500/ length of identifier table#define MAXNUMLEN 14/ maximum number of digits in numbers#def

14、ine 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/ ma

15、ximum 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_C

16、ALL,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 co

17、deint 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 */"

18、;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

19、 */"'.' expected.",/* 10 */"'' expected.",/* 11 */"Undeclared identifier.",/* 12 */"Illegal assignment.",/* 13 */"':=' expected.",/* 14 */"There must be an identifier to follow the 'call'.",/* 15 */"A co

20、nstant 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

21、 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

22、/* 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

23、 instruction to be level = 0;inttx = 0;char line80;instruction codeCXMAX;char* wordNRW + 1 ="", /* place holder */"begin", "call", "const", "do", "end","if","odd", "procedure", "then", &q

24、uot;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_SE

25、MICOLON;char csymNSYM + 1 =' ', '+', '-', '*', '/', '(', ')', '=', ',', '.', ''#define MAXINS 8char* mnemonicMAXINS ="LIT", "OPR", "LOD", "STO", "CAL", "INT&

26、quot;, "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; sn

27、ode, *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 <stdlib.h>#include <stdio.h>#include <stdarg.h>#in

28、clude "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 < s2->elem)p->elem = s1->elem; s1 = s1->next;elsep->elem = s2->

29、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(

30、symset s, int elem) snode* p = s; snode* q;while (p->next && p->next->elem < elem)p = p->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*)

31、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 &&

32、; s->elem < elem) s = s->next;if (s && s->elem = elem)return 1;elsereturn 0; / inset/ EOF set.c/ pl0 compiler source code#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>#include "set.h"#include "pl0.h"/ print e

33、rror 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

34、= 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 (c

35、h = ' ')getch();if (isalpha(ch) / symbol is a reserved word or an identifier.k = 0;do if (k < MAXIDLEN) ak+ = ch; getch();while (isalpha(ch) | isdigit(ch); ak = 0;strcpy(id, a);word0 = id;i = NRW;while (strcmp(id, wordi-);if (+i)sym = wsymi; / symbol is a reserved word elsesym = SYM_IDENT

36、IFIER;/ symbol is an identifierelse if (isdigit(ch) / symbol is a number.k = num = 0;sym = SYM_NUMBER;donum = num * 10 + ch - '0' k+; getch();while (isdigit(ch);if (k > MAXNUMLEN)error(25);/ The number is too great.else if (ch = ':')getch();if (ch = '=')sym = SYM_BECOMES;

37、/ :=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;/ <=getch();else if (ch = '>')sym = SYM_NEQ;/ <>getc

38、h();elsesym = SYM_LES;/ <else / other tokensi = NSYM; csym0 = ch; while (csymi- != ch); if (+i) sym = ssymi; getch();elseprintf("Fatal Error: Unknown character.n"); exit(1); / getsym/ generates (assembles) an instruction.void gen(int x, int y, int z)if (cx > CXMAX)printf("Fatal

39、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();d

40、estroyset(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.val

41、ue = 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

42、;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();else

43、error(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_IDENTIFIE

44、R)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 < to; i+)printf("%5d %st%dt%dn", i, mnemoniccodei.f,

45、codei.l, codei.a);printf("n"); / listcode/void factor(symset fsys)void expression();int i;symset set;test(facbegsys, fsys, 24); / The symbol can not be as the beginning of an expression.while (inset(sym, facbegsys)if (sym = SYM_IDENTIFIER)if (i = position(id) = 0)error(11); / Undeclared id

46、entifier.elseswitch (tablei.kind)mask* mk;case ID_CONSTANT: gen(LIT, 0, tablei.value);break; case ID_VARIABLE: mk = (mask*) &tablei;gen(LOD, level - mk->level, mk->address); break;case ID_PROCEDURE: error(21); / Procedure identifier can not be in an expression. break; / switchgetsym();else

47、 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 

48、9;)'.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

49、, 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);elset

50、erm(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)

51、;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