第一篇：编译原理课程设计报告---集合LASTVT(P)构造算法的程序实现
计算机与信息学院 编译原理课程设计 实验报告
专
业
班
级 学生姓名及学号 课程教学班号 任
课
教
师 实验指导教师 实验地
点
学年第学期
设计目的及要求：
集合LASTVT(P)构造算法的程序实现
设计内容及要求：构造一程序，实现教材P.91的LASTVT(P)集合的构造算法。对任一给定的算符文法G，程序输出所有非终结符P的LASTVT(P)。
设计内容：
实现教材上的算法，对于任意给定的算符文法，输出算符文法中所有的非终结符P的LASTV(P);
主要算法描述：
对于输入的文法，使用一个char型二维数组进行存储，依次对每个非终结符求LASTVT 集。
输入输出形式：
输入： 程序运行后从控制台输入算符文法，要指定输入的文法规则数目，且形式与教材文法相同。
输出：在控制台输出每个非终结符的LASTVT集，且将带有‘|’的文法转换成多个文法。
总结：
本次课程设计我借鉴了第四学期编译原理课程的课程实验，通过本次课程设计我对编译原理课程的相关内容有了复习和巩固，对当时没有弄清楚的问题有了更深的认识，更加掌握了LASTVT集的生成原理，帮助我更好地理解了算符优先分析算法。程序运行结果：
程序源码：
#include
char lable[20];//文法终极符集
char String[20][10];//用于输入串的分析
int r;//文法规则个数
int r1;//转化后文法规则个数
char st[10][30];//用来存储文法规则
char last[10][10];//文法非终结符LASTVT集
int lflag[10] = { 0 };//标志第i个非终结符的LASTVT集是否已求出
//判断是否是终结符
int zhongjie(charc)//判断字符c是否是终极符 {
}
//求lastvt集
void lastvt(charc)//求LASTVT集 {
int i, j, k, m, n;for(i = 0;i } return 0;if(c == lable[i])return 1; } if(lflag[i] == 0){ n = last[i][0] + 1;m = 0;do { if(st[i][m + 1] == ' ' || st[i][m + 1] == '|'){ if(zhongjie(st[i][m])){ } else { if(zhongjie(st[i][m1];n++;last[i][n] = st[i][m];n++; } } } } } } } m++;} while(st[i][m]!= ' ');last[i][n] = ' ';last[i][0] =--n;lflag[i] = 1;//转换 “|” void transform()// 转换 带“|”的文法 { for(i = 0;i text[x][y] = st[i][0];y++;for(j = 1;st[i][j]!= ' ';j++){ if(st[i][j] == '|'){ } else { text[x][y] = st[i][j];y++;text[x][y] = ' ';x++;y = 0;text[x][y] = st[i][0];y++;text[x][y++] = '-';text[x][y++] = '>';char text[20][10];int i, j, l, x = 0, y = 0;x = 0; } } } } text[x][y] = ' ';x++;y = 0;r1 = x;printf(“转化后的文法为:n”);for(i = 0;i { } String[i][0] = text[i][0];for(j = 3, l = 1;text[i][j]!= ' ';j++, l++)String[i][l] = text[i][j];String[i][l] = ' '; 后的转化文法)*/ printf(“%sn”, text[i]);//每个非终结符求lastvt void table2(){ } //判断输入是文法是否规范 void judge(){ int i, j, k = 0;printf(“请输入文法规则数：”);scanf(“%d”, &r);printf(“请输入文法规则：n”);for(i = 0;i for(int i = 0;i } } /*last[i][0]表示LASTVT集中元素的个数*/ last[i][0] = 0;for(i = 0;i } for(i = 0;i } for(j = 0;st[i][j]!= ' ';j++){ } if((st[i][j]<'A' || st[i][j]>'Z')&& st[i][j]!= '-'&&st[i][j]!= lable[k++] = st[i][j];for(j = 0;st[i][j]!= ' ';j++){ } if(st[i][0]<'A' || st[i][0]>'Z'){ } if(st[i][j] >= 'A'&&st[i][j] <= 'Z'){ } if(st[i][j + 1] >= 'A'&&st[i][j + 1] <= 'Z'){ } printf(“不是算符文法!n”);exit(-1);printf(“不是算符文法!n”);exit(-1);'>'&&st[i][j]!= '|')//输出结果 void output(){ printf(“每个非终结符的LASTVT集为：n”);//输出每个非终结符的LASTVT集 for(i = 0;i } { } printf(“%c: ”, st[i][0]);for(j = 0;j } void main(){ } int i = 1;while(i == 1){ } judge();transform();table2();output();initalize();memset(lable, 0, sizeof(lable));memset(String, 0, sizeof(String));memset(st,0,sizeof(st));memset(last, 0, sizeof(last));memset(lflag, 0, sizeof(lflag)); 武 汉 纺 织 大 学 编译原理课程设计实验报告 学院：数学与计算机 专业：计算机 姓名： 班级： 学号： 编译原理 编译原理课设报告 一、实验目的 加强对编译程序的整体认识和了解，巩固《编译原理》课程所学知识。通过本次课程设计掌握编译程序调试技巧和设计编译程序一般的原则，加深对词法分析、语法分析、语义分析等编译阶段及实用编译系统的认识。使学生能将编译理论与实际应用结合起来，提高学生软件开发的能力。 二、实验内容 1）仔细阅读PL/0编译程序文本（编译原理(第二版)张素琴 吕映芝 蒋维杜 戴桂兰 主编 清华大学出版社），并上机调试通过。 2）对PL/0语言进行下列扩充（1）扩充一维整型数组。 扩充var数组：VAR <数组标识名>（<下界>：<上界>）〈下界〉和〈上界〉可用常量标识名。 （2）扩充条件语句的功能使其为：IF<条件>THEN<语句>[ELSE<语句>]（3）增加repeat重复语句: REPEAT<语句>{;<语句>}UNTIL<条件> 可根据自己具体情况从中选择2个以上题目进行扩充。 三、实验原理 PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。 PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。 用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。 当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。 四、实验分析 PL/0语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。语法分析的同时，提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下，调用类PCODE解释程序解释执行生成的类PCODE代码。 词法分析子程序分析： 词法分析子程序名为GETSYM，功能是从源程序中读出一个单词符号（TOTAKEN），把它的信息放入全局变量 SYM、ID和NUM中，字符变量放入CH中，语法分析器需要单词时，直接从这三个变量中获得。Getch过程通过反复调用Getch子过程从源程序过获取字符，并把它们拼成单词。GETCH过程中使用了行缓冲区技术以提高程序运行效率。 词法分析器的分析过程：调用GETSYM时，它通过GETCH过程从源程序中获得一个字符。如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表，如果查到为保留字，则把SYM变量赋成相应的保留字类型值；如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字），把SYM置为IDENT，把这个单词存入ID变量。查保留字表时使用了二分法查找以提高效率。如果Getch获得的字符是数字，则继续用Getch获取数字，并把它们拼成一个整数或实数，然后把SYM置为 INTEGER或REAL，并把拼成的数值放入NUM变量。如果识别出其它合法的符号（比如：赋值号、大于号、小于等于号等），则把SYM则成相应的类型。如果遇到不合法的字符，把SYM置成NUL。 语法分析子程序分析： 语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语义生成相应三元代码，并提供了出错处理的机制。语法分析主要由分程序分析过程（BLOCK）、参数变量分析过程（ParaDeclaration）、参数变量处理过程（ParaGetSub）、数组处理过程（ParaGetSub）、常量定义分析过程（ConstDeclaration）、变量定义分析过程（Vardeclaration）、语句分析过程（Statement）、表达式处理过程（Expression）、项处理过程（Term）、因子处理过程（Factor）和条件处理过程（Condition）构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有出错报告过程（Error）、代码生成过程（Gen）、测试单词合法性及出错恢复过程（Test）、登录名字表过程（Enter）、查询名字表函数（Position）以及列出类 PCODE代码过程（Listcode）作过语法分析的辅助过程。 由PL/0的语法图可知：一个完整的PL/0程序是由分程序和句号构成的。因此，本编译程序在运行的时候，通过主程序中调用分程序处理过程block来分析分程序部分（分程序分析过程中还可能会递归调用block过程），然后，判断最后读入的符号是否为句号。如果是句号且分程序分析中未出错，则是一个合法的PL/0程序，可以运行生成的代码，否则就说明源PL/0程序是不合法的，输出出错提示即可。 if-then-else语句的处理： 按if语句的语法，首先调用逻辑表达式处理过程处理if语句的条件，把相应的真假值放到数据栈顶。接下去记录下代码段分配位置（即下面生成的jpc指令的位置），然后生成 条件转移jpc指令（遇0或遇假转移），转移地址未知暂时填0。然后调用语句处理过程处理 then语句后面的语句或语句块。then后的语句处理完后，如果遇到else，就调用语句处理过程处理else语句后面的语句或语句块，这时当前代码段分配指针的位置就应该是上面的jpc指令的转移位置。通过前面记录下的jpc指令的位置，把它的跳转位置改成当前的代码段指针位置，否则没遇到else，那么此时的当前代码段分配指针的位置也是上面jpc指令的转移位置，也是通过前面记录下的jpc位置指令的位置，把它的跳转到当前的代码段指针位置。 Repeat语句的处理： 首先用CX1变量记下当前代码段分配位置，作为循环的开始位置。然后通过递归调用语句分析过程分析，直到遇到until保留字，如果未对应until则出错。调用条件表达式处理过程生成相应代码把结果放在数据栈顶，再生成条件转移指令，转移位置为上面记录的CX1。 五、相关代码及运行结果 实验代码； PL0.h代码： #include #ifndef WIRTH_ZYC_ #define WIRTH_ZYC_ using namespace std; const int norw = 16; // no.of reserved words 保留字的个数 const int txmax = 100; // length of identifier table 标示符表的长度（容量）const int al = 10; // length of identifiers 标示符的最大长度 const int nmax = 14; // max.no.of digits in numbers 数字的最大长度 const int amax = 2047; // maximum address 寻址空间 const int levmax = 3; // maximum depth of block nesting 最大允许的块嵌套层数 const int cxmax = 200; // size of code array 类PCODE目标代码数组长度（可容纳代码行数） const int lineLength = 82;// 行缓冲区长度 typedef enum {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,ELSESYM,REPEATSYM,UNTILSYM} symbol;// symobl类型标识了不同类型的词汇 typedef char alfa[al+1]; // alfa类型用于标识符 typedef enum {CONSTANT,VARIABLE,PROCEDURE,ARRAY} obj0; // 三种标识符的类型 typedef enum {LIT,OPR,LOD,STO,CAL,INT,JMP,JPC} fct; // functions typedef set struct instruction{ fct f;// function code int l;// level,cann't big than levmax int a;// displacement address,cann't big than amax }; // 类PCODE指令类型，包含三个字段：指令f、层差l和另一个操作数a /******************************************* * lit 0,a: load constant a * * opr 0,a: execute operation a * * lod l,a: load variable l,a * * sto l,a: store variable l,a * * cal l,a: call procedure a at level l * * int 0,a: increment t-register by a * * jmp 0,a: jump to a * * jpc 0,a: jump conditional to a * *******************************************/ typedef struct{ alfa name;obj0 kind;union { struct{int level,adr,size;}inOther; int val;}other;} Table; class PL0 { protected: bool listswitch,sourceEnd;char ch; // last character read symbol sym; // last symbol read alfa id; // last identifier read int num; // last number read int cc; // character count int ll; // line length int kk,err;int cx; // code allocation index int codeNo; // code line no.static string errStr[]; // error string char line[lineLength]; // code line vector // error array alfa a; // 词法分析器中用于临时存放正在分析的词 instruction code[cxmax+1]; // destination code array alfa word[norw+1]; // 保留字表 symbol wsym[norw+1]; // 保留字表中每一个保留字对应的symbol类型 symbol ssym[100]; // 一些符号对应的symbol类型表 合 char mnemonic[8][6]; // 类PCODE指令助记符表 symset declbegsys,statbegsys,facbegsys;// 声明开始、表达式开始和项开始符号集 Table table[txmax+1]; // 符号表 FILE* fin,*fout; public: PL0(char* source,char*destination); ~PL0(){fclose(fin),fclose(fout);} void error(int n); 位置和出错代码 void getsym(); 个单词 void getch(); 个字符 void gen(fct x,int y,int z); 程序区 void test(symset s1,symset s2,int n); 合法 void block(int lev,int tx,symset fsys); void enter(obj0 k,int &tx,int &dx,int lev); int position(alfa id,int tx);的位置 void constdeclaration(int&tx,int&dx,int lev); void vardeclaration(int&tx,int&dx,int lev); void listcode(int cx0); void statement(symset fsys,int tx,int lev); void expression(symset fsys,int tx,int lev); void term(symset fsys,int tx,int lev); void factor(symset fsys,int tx,int lev); void condition(symset fsys,int tx,int lev); void arraydeclaration(int& tx,int& dx,int lev); void interpret(); 执行程序 int base(int l,int b,int s[]); 基地址 void SaveCode(); // 构造函数 // 析构函数 // 出错处理，打印出错 // 词法分析，读取一 // 漏掉空格，读取一// 生成目标代码，并送入目标 // 测试当前单词符号是否 // 分程序分析处理过程 // 登入名字表 // 查找标示符在名字表中 // 常量定义处理 // 变量说明处理 // 列出目标代码清单 // 语句部分处理 // 表达式处理 // 项处理 // 因子处理 // 条件处理 // 数组说明处理 // 对目标代码的解释 // 通过静态链求出数据区的 // 保存代码 };#endif PL0.cpp代码： #include “pl0.h” // 错误字符串数组 string PL0::errStr[]={“",”error 0001: 常数说明中“=”写成“：=”“, ”error 0002: 常数说明中的“=”后应为数字“, ”error 0003: 常数说明中的标识符后应是“=”“, ”error 0004: const,var,procedure后应为标识符“, ”error 0005: 漏掉了‘,’或‘;’“, ”error 0006: 过程说明后的符号不正确（应是语句开始符或过程开始符）“, ”error 0007: 应是语句开始符“, ”error 0008: 过程体内语句部分的后跟符不正确“, ”error 0009: 程序皆为丢了句号‘.’“, ”error 0010: 语句之间漏了‘;’“, ”error 0011: 标识符没说明“, ”error 0012: 赋值语句中，赋值号左部标识符属性应是变量“, ”error 0013: 赋值语句左部标识符应是赋值号:=“, ”error 0014: call后应为标识符“, ”error 0015: call后标识符属性应为过程“, ”error 0016: 条件语句中丢了then“, ”error 0017: 丢了end或;“, ”error 0018: while型循环语句中丢了do“, ”error 0019: 语句后的标识符不正确“, ”error 0020: 应为关系运算符“, ”error 0021: 表达式内标识符属性不能是过程“, ”error 0022: 表达式中漏掉了右括号‘)’“, ”error 0023: 因子后的非法符号“, ”error 0024: 表达式开始符不能是此符号“, ”error 0025: 文件在不该结束的地方结束了“, ”error 0026: 结束符出现在不该结束的地方“, ”error 0027: “,”error 0028: “,”error 0029: “,”error 0030: “, ”error 0031: 数越界“, ”error 0032: read语句括号中标识符不是变量“, ”error 0033: else附近错误“ , ”error 0034: repeat附近错误“}; // PL0构造函数 PL0::PL0(char* source,char*destination){ listswitch=true,sourceEnd=false; strcpy(word[1],”begin“); // 初始化存储保留字 strcpy(word[2],”call“);strcpy(word[3],”const“); strcpy(word[4],”do“);strcpy(word[5],”else“);strcpy(word[6],”end“);strcpy(word[7],”if“);strcpy(word[8],”odd“);strcpy(word[9],”procedure“);strcpy(word[10],”read“); strcpy(word[11],”repeat“);strcpy(word[12],”then“);strcpy(word[13],”until“);strcpy(word[14],”var“); strcpy(word[15],”while“);strcpy(word[16],”write“); wsym[1]= BEGINSYM; wsym[2]= CALLSYM;留字对应的symbol类型 wsym[3]= CONSTSYM; wsym[4]= DOSYM;wsym[5]= ELSESYM; wsym[6]= ENDSYM;wsym[7]= IFSYM; wsym[8]= ODDSYM;wsym[9]= PROCSYM; wsym[10]= READSYM; wsym[11]= REPEATSYM;wsym[12]= THENSYM;wsym[13]= UNTILSYM;wsym[14]= VARSYM; wsym[15]= WHILESYM;wsym[16]= WRITESYM; memset(code,0,sizeof(code));memset(ssym,0,100*sizeof(symbol));memset(table,0,sizeof(table));memset(line,0,sizeof(line)); ssym['+']= PLUS; 类型表 ssym['-']= MINUS;ssym['*']= TIMES;ssym['/']= SLASH;ssym['(']= LPAREN;ssym[')']= RPAREN;ssym['=']= EQL;ssym[',']= COMMA;ssym['.']= PERIOD; // 初始化保留字表中每一个保 // 初始化一些符号对应的symbol ssym['#']= NEQ;ssym['<']= LSS;ssym['>']= GTR;ssym[';']= SEMICOLON; strcpy(mnemonic[LIT],” lit “); // 初始化类PCODE指令助记符表 strcpy(mnemonic[OPR],” opr “);strcpy(mnemonic[LOD],” lod “);strcpy(mnemonic[STO],” sto “);strcpy(mnemonic[CAL],” cal “);strcpy(mnemonic[INT],” int “);strcpy(mnemonic[JMP],” jmp “);strcpy(mnemonic[JPC],” jpc “); declbegsys.insert(CONSTSYM),declbegsys.insert(VARSYM),declbegsys.insert(PROCSYM);// 初始化声明开始符号集合 statbegsys.insert(BEGINSYM),statbegsys.insert(CALLSYM),statbegsys.insert(IFSYM),statbegsys.insert(WHILESYM);// 初始化表达式开始符号集合facbegsys.insert(IDENT),facbegsys.insert(NUMBER),facbegsys.insert(LPAREN);// 初始化项开始符号集合 err= 0;cc= 0; // 行缓冲区指针 cx= 0; // 代码分配指针，代码生成模块总在cx所指位置生成新的代码 ll= 0; // 行缓冲区长度 ch= ' '; // last character read } kk= al; // 引入此变量是出于程序性能考虑 codeNo=0; // code line no.fin=fopen(source,”r“);fout=fopen(destination,”w“);// 出错处理，打印出错位置和出错代码 void PL0::error(int n){ char s[10];sprintf(s,”第 %d 行:“,codeNo);errorString.push_back(s+errStr[n]);err= err+1;//error count }//error end // 词法分析，读取一个单词 void PL0::getsym(){ if(sourceEnd) return;int i,j,k;while(ch ==' '||ch==9) getch(); // cls space and tab if(isalpha(ch))// id or reserved word { k=0; memset(a,0,al+1); // 检测一个单词长度 do{ if(k < al){ a[k]= ch; k= k+1;} getch();if(sourceEnd) return;}while(isalpha(ch)||isdigit(ch));if(k >= kk)kk = k;else { do{ a[kk]= ' '; kk= kk-1;}while(kk > k);} strcpy(id,a);i= 1;j= norw;// 判断是否是关键字（二分搜索）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(isdigit(ch))// number { k= 0;num= 0;sym= NUMBER;do{ num= 10 * num + ch-'0'; k= k+1; getch();}while(isdigit(ch));if(k > nmax) error(30);} else if(ch == ':'){ getch();if(ch == '='){ sym= BECOMES; getch();} else sym= NUL;} else if(ch == '<') // extra stuff added to support <= { getch();if(ch== '='){ sym= LEQ; getch();} else sym= LSS;} else if(ch == '>'){ getch();if(ch == '='){ sym= GEQ; getch();} else sym= GTR;} else // end of extra stuff { sym= ssym[ch];// 其它符号的赋值 getch();} } // 漏掉空格，读取一个字符 void PL0::getch(){ if(cc == ll){ if(feof(fin)) { if(sym!=PERIOD) error(25); sourceEnd=true; return; } cc= 0; fgets(line,lineLength,fin); codeNo++; ll=strlen(line); if(line[ll-1]==10)ll--;} ch= line[cc];cc= cc+1;} // 生成目标代码，并送入目标程序区void PL0::gen(fct x,int y,int z){ if(cx > cxmax){ cout<<”Program too longn“; return;} code[cx].f= x;code[cx].l= y;code[cx].a= z; cx= cx+1;}//gen end // 测试当前单词符号是否合法 void PL0::test(symset s1,symset s2,int n){ if(sourceEnd) return;if(s1.find(sym)==s1.end()){ error(n); symset::iterator it; for(it=s2.begin();it!=s2.end();it++) s1.insert(*it);//s1=s1+s2 while(s1.find(sym)==s1.end()) getsym();} }//test end // 分程序分析处理过程 void PL0::block(int lev,int tx,symset fsys){ if(sourceEnd) return;int dx;// data allocation index int tx0;// initial table index int cx0;// initial code index dx= 3; // 变量的个数 tx0= tx;// 表指针 table[tx].other.inOther.adr= cx;gen(JMP,0,0);if(lev>levmax)error(32);do{ if(sym == CONSTSYM) // 处理常量声明 { getsym(); do{ constdeclaration(tx,dx,lev); while(sym == COMMA) { } getsym(); constdeclaration(tx,dx,lev);} if(sym ==SEMICOLON) getsym();else error(5);}while(sym==IDENT);if(sym == VARSYM) // 处理变量声明 { getsym();do{ vardeclaration(tx,dx,lev); while(sym == COMMA){ getsym(); vardeclaration(tx,dx,lev); } if(sym ==SEMICOLON) getsym(); else error(5);}while(sym==IDENT);} while(sym ==PROCSYM) // 处理过程的声明 { getsym();if(sym ==IDENT){ enter(PROCEDURE,tx,dx,lev); getsym();} else error(4);if(sym ==SEMICOLON) getsym();else error(5);symset tmp = fsys;tmp.insert(SEMICOLON);block(lev+1,tx,tmp);if(sym == SEMICOLON){ getsym(); symset tmp = statbegsys; for(int i= IDENT;i<=PROCSYM;i++) tmp.insert((symbol)i); test(tmp,fsys,6); } else error(5); } symset tmp=statbegsys; tmp.insert(IDENT); test(tmp,declbegsys,7);}while(declbegsys.find(sym)!=declbegsys.end()); code[table[tx0].other.inOther.adr].a= cx;table[tx0].other.inOther.adr= cx;// start adr of code table[tx0].other.inOther.size=dx; cx0= cx;gen(INT,0,dx);symset tmp=statbegsys;for(int i=SEMICOLON;i <= ENDSYM;i++) tmp.insert((symbol)i);statement(tmp,tx,lev);gen(OPR,0,0);// return symset s2;test(fsys,s2,8);listcode(cx0);}// block end // 登入名字表 void PL0::enter(obj0 k,int &tx,int &dx,int lev){ tx= tx+1;strcpy(table[tx].name,id);table[tx].kind=k;switch(k){ case CONSTANT: if(num>amax) { error(31); num=0; } table[tx].other.val=num; break;case VARIABLE: table[tx].other.inOther.level=lev; table[tx].other.inOther.adr=dx; dx++; break;case PROCEDURE: table[tx].other.inOther.level=lev; break;case ARRAY: table[tx].other.inOther.size = lev; break;} }//enter end // 查找标示符在名字表中的位置 int PL0::position(alfa id,int tx)//find identifier id in table { int i;strcpy(table[0].name, id);i= tx;while(strcmp(table[i].name,id)!=0)i--;return i;}//position end // 常量定义处理 void PL0::constdeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){ getsym(); if(sym>=EQL&&sym<=BECOMES) { if(sym ==BECOMES) error(1); getsym(); if(sym == NUMBER) { enter(CONSTANT,tx,dx,lev); getsym(); } else error(2); } else error(3);} else error(4);}// constdeclaration end // 变量说明处理 void PL0::vardeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){ enter(VARIABLE,tx,dx,lev); getsym();} else error(4);}//vardeclaration end // 数组说明处理 void PL0::arraydeclaration(int&tx,int&dx,int lev){ int upscript=0,downscript=0;getsym();if(sym == NUMBER || sym == CONSTSYM){ if(num == 0) { upscript = num; getsym(); } else error(32);} if(sym == COMMA) getsym();else error(32);if(sym == NUMBER || sym == CONSTSYM){ downscript = num; getsym();} if(sym!= RPAREN) } error(32);else { enter(ARRAY,tx,dx,downscript+1);getsym();} // 列出目标代码清单 void PL0::listcode(int cx0)//list code generated for this block { int i;if(listswitch) for(i= cx0;i cout<<”“< <<”“< // 语句部分处理 void PL0::statement(symset fsys,int tx,int lev){ if(sourceEnd) return;int i,cx1,cx2;if(sym ==IDENT){ i= position(id,tx); if(i == 0) error(11); else if(table[i].kind!=VARIABLE) { error(12); i= 0; } getsym(); if(sym ==BECOMES) getsym(); else error(13); expression(fsys,tx,lev); if(sym!= SEMICOLON) error(10); if(i!= 0) gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr); } else if(sym == READSYM){ getsym();if(sym!=LPAREN) error(34);else do{ getsym(); if(sym==IDENT) i=position(id,tx); else i=0; if(i==0) error(35); else { gen(OPR,0,16); gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr); } getsym(); }while(sym == COMMA); if(sym!= RPAREN) { error(33); while(fsys.find(sym)!=fsys.end())getsym(); } else getsym();} else if(sym == WRITESYM){ getsym();if(sym==LPAREN){ do{ getsym(); symset tmp=fsys; for(int t=RPAREN;t<=COMMA;t++) tmp.insert((symbol)t); expression(tmp,tx,lev); gen(OPR,0,14); }while(sym==COMMA); if(sym!=RPAREN) error(33); else getsym();} gen(OPR,0,15);} else if(sym ==CALLSYM){ getsym();if(sym!=IDENT) error(14);else { i= position(id,tx); if(i == 0) error(11); else if(table[i].kind = PROCEDURE) gen(CAL,lev-table[i].other.inOther.level,table[i].other.inOther.adr); else error(15); getsym();} } else if(sym ==IFSYM){ getsym();symset tmp=fsys;for(int i = THENSYM;i<= DOSYM;i++) tmp.insert((symbol)i);condition(tmp,tx,lev);if(sym == THENSYM) getsym();else error(16);cx1= cx;gen(JPC,0,0);tmp.insert(ELSESYM);statement(tmp,tx,lev);getsym(); code[cx1].a= cx; if(sym == ELSESYM){ getsym(); cx2=cx; gen(JMP,0,0); code[cx1].a=cx; statement(fsys,tx,lev); code[cx2].a=cx;} } else if(sym ==BEGINSYM){ getsym();symset tmp=fsys;for(int i=SEMICOLON;i<=ENDSYM;i++) tmp.insert((symbol)i);statement(tmp,tx,lev);tmp=statbegsys;tmp.insert(SEMICOLON);while(tmp.find(sym)!=tmp.end()){ if(sourceEnd)return; if(sym ==SEMICOLON||sym ==ENDSYM) getsym(); else if(sym=PERIOD) { error(26); getsym(); } else error(10); tmp=fsys; for(i=SEMICOLON;i<=ENDSYM;i++) tmp.insert((symbol)i); if(sourceEnd)return; if(sym==ENDSYM) break; statement(tmp,tx,lev);} if(sym ==ENDSYM) getsym();else if(!sourceEnd) error(17);} else if(sym ==WHILESYM){ cx1= cx; // 记下当前代码分配位置，这是while循环的开始位置 getsym();symset tmp=fsys;tmp.insert(DOSYM);condition(tmp,tx,lev); cx2= cx; // 记下当前代码分配位置，这是while的do中的语句的开始位置 gen(JPC,0,0); if(sym ==DOSYM) getsym(); else error(18); statement(fsys,tx,lev); gen(JMP,0,cx1); code[cx2].a= cx;} else if(sym == REPEATSYM){ symset temp1, temp2; temp1= fsys,temp1.insert(SEMICOLON),temp1.insert(UNTILSYM); cx1= cx; getsym(); statement(temp1,tx,lev); temp2 = statbegsys; temp2.insert(SEMICOLON); while(temp2.find(sym)!= temp2.end()) { if(sym == SEMICOLON) getsym(); else error(34); statement(temp1,tx,lev); } if(sym == UNTILSYM) { getsym(); condition(fsys,tx,lev); gen(JPC,0,cx1); } else error(34); } symset setT;test(fsys,setT,19);}//statement end // 表达式处理 void PL0::expression(symset fsys,int tx,int lev){ symbol addop;symset tmp=fsys;for(int t=PLUS;t<=MINUS;t++) tmp.insert((symbol)t);if(sym>=PLUS&&sym<=MINUS){ addop= sym; getsym(); term(tmp,tx,lev); if(addop ==MINUS) gen(OPR,0,1);} else term(tmp,tx,lev);while(sym >=PLUS&&sym<=MINUS){ addop= sym; getsym(); term(tmp,tx,lev); if(addop ==PLUS) gen(OPR,0,2); else gen(OPR,0,3);} }// expression end // 项处理 void PL0::term(symset fsys,int tx,int lev){ if(sourceEnd) return;symbol mulop;symset tmp=fsys;for(int t=TIMES;t<=SLASH;t++) tmp.insert((symbol)t);factor(tmp,tx,lev);while(sym>=TIMES && sym<=SLASH){ mulop= sym; getsym(); factor(tmp,tx,lev); if(mulop ==TIMES) gen(OPR,0,4); else gen(OPR,0,5);} }// term end // 因子处理 void PL0:: factor(symset fsys,int tx,int lev){ int i;test(facbegsys,fsys,24);while(facbegsys.find(sym)!=facbegsys.end()){ if(sym ==IDENT) { i= position(id,tx); if(i == 0) error(11); else switch(table[i].kind) { case CONSTANT: gen(LIT,0,table[i].other.val); break; case VARIABLE: gen(LOD,lev-table[i].other.inOther.level,table[i].other.inOther.adr); break; case PROCEDURE: error(21); break; } getsym(); } else if(sym ==NUMBER) { if(num>amax) { error(31); num= 0; } gen(LIT,0,num); getsym(); } else if(sym ==LPAREN) { getsym(); symset tmp=fsys; tmp.insert(RPAREN); expression(tmp,tx,lev); if(sym == RPAREN) getsym(); else error(22); } test(fsys,facbegsys,23);} }//factor end // 条件处理 void PL0::condition(symset fsys,int tx,int lev){ symbol relop;symset tmp=fsys;tmp.insert(EQL),tmp.insert(NEQ),tmp.insert(LSS),tmp.insert(LEQ),tmp.insert(GTR),tmp.insert(GEQ); if(sym == ODDSYM){ getsym(); expression(fsys,tx,lev); gen(OPR,0,6);} else { expression(tmp,tx,lev); if(tmp.find(sym)==tmp.end()) error(20); else { relop= sym; getsym(); expression(fsys,tx,lev); switch(relop) { case EQL: gen(OPR,0,8); break; case NEQ: gen(OPR,0,9); break; case LSS: gen(OPR,0,10); break; case GEQ: gen(OPR,0,11); break; case GTR: gen(OPR,0,12); break; case LEQ: gen(OPR,0,13); break; } } } }//condition end // 对目标代码的解释执行程序 void PL0::interpret(){ int err1=errorString.size();if(err1>0){ cout<<”存在%d个错误:“< cout< t= t+1; s[t]= i.a; break;case OPR: switch(i.a)//operator { case 0:// return t= b-1; p= s[t+3]; b= s[t+2];break;case 1: s[t]=-s[t];break;case 2: t= t-1;s[t]= s[t]+s[t+1];break;case 3: t= t-1;s[t]= s[t]-s[t+1];break;case 4: t= t-1;s[t]= s[t]*s[t+1];break;case 5: t= t-1;s[t]= s[t] / s[t+1];break;case 6: if(s[t]%2) s[t]=1;else s[t]=0;break;case 8: t= t-1;if(s[t]==s[t+1]) s[t]=1;else s[t]=0;break;case 9: t= t-1;if(s[t]==s[t+1]) s[t]=0;else s[t]=1;break; case 10: t= t-1;if(s[t] s[t]=1;else s[t]=0;break;case 11: t= t-1;if(s[t]>=s[t+1]) s[t]= 1;else s[t]=0;break;case 12: t= t-1;if(s[t]>s[t+1]) s[t]= 1;else s[t]=0;break;case 13: t= t-1;if(s[t]<=s[t+1]) s[t]= 1;else s[t]=0;break;case 14: cout<<”“< t= t+1; s[t]= s[base(i.l,b,s)+i.a]; break; case STO: s[base(i.l,b,s)+i.a]= s[t]; t= t-1; break; case CAL:// generate new block mark s[t+1]= base(i.l,b,s); s[t+2]= b; s[t+3]= p; b= t+1; p=i.a; break; case INT: t= t+i.a; break; case JMP: p= i.a; break; case JPC: if(s[t] == 0) p= i.a; t= t-1; break; }//switch end }while(p!=0); cout<<” End PL/0n“;} // interpret end // 通过静态链求出数据区的基地址 int PL0::base(int l,int b,int s[]){ int b1;b1= b;//find base l levels down while(l>0){ b1= s[b1]; l= l-1;} return b1;} // 保存代码 void PL0::SaveCode(){ if(fout) for(int i=0;i fprintf(fout,”%d %s %d %dn “,i,mnemonic[code[i].f],code[i].l,code[i].a);} TestPL0.cpp代码： #include ”pl0.h“ void main(){ PL0 cp(”testPas2.txt“,”nasm.txt"); symset fsys; fsys.insert(PERIOD);fsys.insert(CONSTSYM),fsys.insert(VARSYM),fsys.insert(PROCSYM);fsys.insert(BEGINSYM),fsys.insert(CALLSYM),fsys.insert(IFSYM),fsys.insert(WHILESYM);cp.getsym(); // 词法分析，分析一个词 cp.block(0,0,fsys); // 分程序分析处理功能 cp.SaveCode(); // 保存代码 cp.interpret(); // 对目标代码的解释执行程序 } 实验运行结果： 运行的的文件见下图右侧：实验中我是固定了文件名的，可以是改写成动态输入，由于在测试中我把所有的测试语句都放在同一个文件中了，没有太多的必要。 六、心得体会 在编译程序实现的过程中反复使用了递归调用的思想，且也使用了模块化处理问题的思想，使用模块化的思想关键是在抽象阶段要抽象出对应的模块，且模块的层次必须是清晰的。 在实现此程序中，由于要实现关键字和符号表中字段的搜索，实现中就必须注意快速查找的方法，而在实现的过程中多次用到了二分搜索的方法，这是个比较快的搜索方法。 由于此程序的实现相对比较复杂，且不方便调试，改进时可以把此程序的词法分析，语法分析和执行原代码作为单独的测试程序来测试，这样也方便大家来调试。 通过本次的课设我知道了一个算法的设计是需要静下心来仔细的研究的，且实现中必须先了解程序的整个流程，也就是说在编程中首先必须看懂那些对应的UML图，只有在图的指导下，编程中才不会盲目，也有一定的方向性。同样在编程中必须注意代码的规范，多写一些对应的注释是很必要的，要时刻想这代码并不是给你自己看的，而是必须要给别人看，因此我觉得代码的规范是相当重要的。 编译原理课程设计报告 课题名称： 提交文档学生姓名：提交文档学生学号：同组 成 员 名 单：无指导 教 师 姓 名： 指导教师评阅成绩：指导教师评阅意见： 提交报告时间：年月日 1.课程设计目标 构造的编译器的组成部分，能实现的功能。 2.分析与设计 实现方法：编程语言、编程方法 系统总图，各部分的实现原理、方法、中间结果、最后输出 扫描器：各单词的状态转换图、转换表 分析器：分析表 代码设计说明：程序结构图，文件和函数的设计说明，关键数据结构 3.程序代码实现 按文件列出主要程序代码, 添加必要的注释。 4.测试结果 标准测试程序的分析结果 修改后的测试程序分析结果（正确和错误）词法分析和语法分析的结果输出（P79,P182） 5.总结 收获 不足 201X-201X学年第x学期 《编译原理》课程设计报告 院 系： 计算机科学与技术 班 级： XX级XX 班 学生姓名： XXXXXX 学 号： XXXXXXXX 指导老师： XXXXXX 计算机科学与技术学院监制 20XX年X月 目录 1.课程设计的目的 2.课程设计的内容和要求 3.问题分析和相关知识介绍 4.设计思路和关键问题及其解决方案 5.测试和结果分析 6.总结和心得体会 附件1：参考文献 附件2：核心源代码 1.课程设计的目的（1）编写词法分析器 （2）加深对词法分析器工作原理的了解和认识 2.课程设计的内容和要求 编写词法分析器，词法分析器能够识别关系算符，词法分析器能够识别标识符和关键字，词法分析器能够识别无符号数。 3.问题分析和相关知识介绍 构成词法分析器的一种简单方法是用状态转换图来描述源语言词法记号的结构，然后手工把这种状态转换图翻译成为识别词法记号的程序。词法分析器的任务是把构成源程序的字符流翻译成词法记号流。 4.设计思路和关键问题及其解决方案 把自然语言构造成正规式，把正规式构造成有限自动机NFA，然后根据子集构造法把有限自动机构造成无限自动机DFA，根据极小化DFA状态数算法把DFA构造成最简DFA,其次根据最简DFA画出转换表，根据转换表画出装换图，最后根据装换图就可以编写词法分析器。 5.测试和结果分析 6.总结和心得体会 通过本次试验，不仅仅是我学会了C#基础知识，而且还是我对词法分析器有了更深入的认识，虽然在编写词法分析器过程中遇到了很多困难，例如：C#语言不熟悉，对此法分析器的工作原理分析的不透彻，但在老师和同学的帮助下，我有了很大的提高，通过不断的努力最终顺利的完成了课程设计，很感谢帮助我的XX同学和XX老师。附件1：参考文献 《编译原理（第2版）》 高等教育出版社； 《C#程序设计及应用教程（第2版）》 人民教育出版社。附件2： 1．Code文档截图 2.程序源代码 using System;using System.Collections.Generic;using System.Text;using System.IO; namespace LexicalAnalysis { class Program { static string[] keys = { “static”, “true”, “return”, “string”, “Length”, “break”, “Console”, “WriteLine”, “bool”, “false”, “ture”, “void”, “if”, “else”, “while”, “int”, “float”, “for”, “enum”, “default”, “case”, “double”, “do” }; static List static List static List static List static List //数字，标识符，空白，关系符,运算符 static void Main(string[] args){ string[] date = File.ReadAllLines(@“d:code.txt”);//路径，并存入data for(int i = 0;i < date.Length;i++){ Console.WriteLine(“第” +(i + 1)+ “行code: ” + date.GetValue(i));analysisByLine(date[i]); } //分别输出存储在四个List中的String Console.WriteLine(“关键字，输入回车”);//输出所有的关键字 Console.ReadLine(); foreach(string id in key){ Console.WriteLine(id); } Console.WriteLine(“标识符，输入回车”);//输出所有的标识符 Console.ReadLine();foreach(string id in bsf){ Console.WriteLine(id); } Console.WriteLine(“数字，输入回车”);Console.ReadLine();foreach(string id in sz){ Console.WriteLine(id); } Console.WriteLine(“关系运算符，输入回车”);Console.ReadLine();foreach(string id in gx){ Console.WriteLine(id); } Console.WriteLine(“算数运算符，输入回车”);Console.ReadLine();foreach(string id in ys){ Console.WriteLine(id); } Console.WriteLine(“输入回车退出”); Console.ReadLine(); } static void analysisByLine(string code) //输出所有的数字 //输出所有的关系运算符//输出所有的算数运算符 { char a = ' ';string temp = “";int j = 0;while(j < code.Length){ a = code[j];temp = ”“;if(Char.IsLetter(a)|| a == '_')//是否为标识符 { temp = temp + a.ToString();j++;a = code[j];while(Char.IsLetterOrDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} if(isKey(temp)){ //Console.WriteLine(”保留字：“+temp); if(!key.Contains(temp)){ // Console.WriteLine(”添加成功“);key.Add(temp);} } else { //Console.WriteLine(”标识符：“+temp); if(!bsf.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);bsf.Add(temp);} } } else if(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j]; } //判断是否是小数 if(a.Equals('.')){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} //判读是否是科学记数法 if(a.Equals('E')|| a.Equals('e')){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} } } // Console.WriteLine(”数字:“+temp);if(!sz.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);sz.Add(temp);} } else if(a == '<'){ temp = temp + a.ToString();j++;a = code[j];if(a == '='){ temp = temp + a.ToString();j++;a = code[j];} else if(a == '>'){ temp = temp + a.ToString();j++;a = code[j];} //Console.WriteLine(”关系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);gx.Add(temp);} } else if(a == '='){ temp = temp + a.ToString();j++; a = code[j];// Console.WriteLine(”关系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功关系==“);gx.Add(temp);} } else if(a == '>'){ temp = temp + a.ToString();j++;a = code[j];if(a == '='){ temp = temp + a.ToString();j++;a = code[j];} // Console.WriteLine(”关系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);gx.Add(temp);} } else { if(a == '+' || a == '-' || a == '/' || a == '*'){ temp = temp + a.ToString();j++;a = code[j];//Console.WriteLine(”运算符“+temp);if(!ys.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);ys.Add(temp);} } else { j++;} } } } //判断是不是保留字的IsKey方法 static bool isKey(string key){ bool flag = false;for(int i = 0;i < keys.Length;i++) if(keys[i] == key){ flag = true;//Console.WriteLine(key+”是不是key“+flag);break;} else { flag = false; } //Console.WriteLine(key+”是不是key“);// Console.WriteLine(flag+”是不是key");return flag; } } }第二篇：编译原理课程设计报告
第三篇：编译原理课程设计报告(格式)
第四篇：《编译原理》课程设计报告--词法分析器
点击咨询 