编译原理实验二.doc

编译原理实验报告实验序号：实验二实验项目名称：语法分析（预测分析）学号姓名专业、班软件工程二班实验地点实316指导教师实验时间2011-3-10一、实验目的及要求通过本次实验的学习，学生需要掌握LL(1)语法分析原理和方法的基础上，开发一个简单的预测分析器。二、实验设备（环境）及要求VC+60.三、实验内容与步骤1、完成以下描述算术表达式的LL(1)文法的LL(1)分析程序（LL(1)分析表见教材）。GE: ETE EATE|TFT TMFT|F (E)|i A+|- M*|/说明：终结符号i为用户定义的简单变量,即标识符的定义。四、实验结果与数据处理实验代码：#include#include#include#define Vtn 8#define Vnn 6#define Pn 10#define Pmaxlen 20#define MaxStLength 50#define MaxStackDepth 50char VnVnn=E,e,T,t,F,A;char VtVtn=i,+,-,*,/,(,),$;char PstrPnPmaxlen=ETE,EATE|,TFT,TMFT|,F (E)|i,A+|-,M*|/;int PrlenPn=2,3,3,1,2,3,3,1,3,1;int PintPn3=102,101,1,102,101,2,102,101,-1,104,103,3,104,103,4,104,103,-1,5,100,6,0;int analyseTableVnnVtn+1;int analyseStackMaxStackDepth+1; int topAnalyse; char stMaxStLength; /要分析的符号串/* -初始化-*/void InitanalyseTable()/*-预测分析表存放各个产生式的编号，-1表示找不到相匹配的产生式-*/ for(int i=0;iVnn;i+) for(int j=0;jVtn;j+) analyseTableij=-1; analyseTable00=0; analyseTable05=0; analyseTable11=1; analyseTable12=2; analyseTable16=3; analyseTable17=3; analyseTable20=4; analyseTable25=4; analyseTable31=7; analyseTable32=7; analyseTable33=5; analyseTable34=6; analyseTable36=7; analyseTable37=7; analyseTable40=9; analyseTable45=8;void Init() /分析栈的初始化 analyseStack0=7; /入栈 analyseStack1=100; /初始符入栈 topAnalyse=1; /初始符号串 int i; for(i = 0; i MaxStLength;i+) sti = 0;void Pop()topAnalyse-;/*-产生式入栈操作-*/void Push(int r) int i,len; Pop(); len=Prlenr;/为空时 if(len=1)&(Pintr0=-1) return;/不为空时 topAnalyse+=len; for(i=0;ilen;i+) analyseStacktopAnalyse-i=Pintri; /逆序入栈void ShowStack() int i; for(i =0;i=100) printf(%c,VnanalyseStacki-100);elseprintf(%c, VtanalyseStacki); /*-返回表中的位置，-1表示未找到-*/int Index(char c) int i=0; while(iVtn)&(c!= Vti) i+; if(iVtn)&(c=Vti) return i; else return -1;void Identify()int current,step,r; printf(n%s：nn, st);step = 0;current = 0; printf(%dt,step);ShowStack();printf(tt%stt- -n, st+current);while(1)if(analyseStacktopAnalyse100) if(VtanalyseStacktopAnalyse=stcurrent) Pop();current+;step+;printf(%dt,step);ShowStack();printf(tt%stt出栈、后移n, st+current); elseprintf(字符 %c 与字符 %c 不匹配！, VtanalyseStacktopAnalyse, stcurrent);printf(此串不是此文法的句子n);return;else int n,m;n=analyseStacktopAnalyse - 100; m=Index(stcurrent);if(m=-1) printf( %c 字符不符合输入，输入出错！ ,stcurrent);printf(此串不是此文法的句子n);return; r = analyseTablenm; if( r!=-1) Push(r); step+;printf(%dt, step);ShowStack();printf(tt%stt%sn, st+current,Pstrr); elseprintf(无可用产生式，此串不是此文法的句子！n);return;if(topAnalyse=0&stcurrent=$) break;/void main()InitanalyseTable(); while(1) Init(); printf(请输入符号串(以$结束) : ); int i=0; char c; c=getchar(); while(iMaxStLength) if(c=$) sti=$; break; else if(c!= &c!=n) sti+=c; c=getchar(); if(c=n) printf(请以$结束：); c=getchar(); if(iMaxStLength) Identify(); else printf(输入的符号串超过额定长度); 运行结果：五、分析与讨论实验原理、方法和手段1、基本思想：LL(1)分析器主要由栈、输入缓冲区、预测分析程序、分析表等四大部分组成。其中最重要的两个核心部分是预测分析程序和分析表。预测分析程序又称总控程序，它一方面负责栈中符号的入栈、出栈等功能，另一方面还要读取输入缓冲区中的符号，并不断更新指向输入缓冲区的指针。分析表是预测分析程序的指示灯，它指明了每一个状态下预测分析程序应该执行什么动作。预测分析器的工作模型如图1所示：图1 预测分析器模型2.基本方法:构造预测分析表MA, a：（1）对文法的每个产生式A a，执行(2)和(3)（2）对FIRST(a)的每个终结符a，把A a加入MA, a（3）如果e在FIRST(a)中，对FOLLOW(A)的每个终结符b（包括$）, 把A a加入MA, b（4）M中其它没有定义的条目都是error六、教师评语签名：日期：成绩附源程序清单：#include #include #include #include demo.h#define SIZE 100char stackSIZE;int bottom = 0, top = 0;void push(char ch) char pop() int get_id(FILE *fp) char temp100; int id; fscanf(fp, %d, &id);fgets(temp, 100, fp); return id;void translate(int id, char *a) switch(id) case 0: *a = #; break; case 12: *a = i; break; case 22: *a = +; break; case 23: *a = -; break; case 24: *a = *; break; case 21: *a = /; break; bool is_terminate(char ch) if (ch = i | ch = + | ch = - | ch = * | ch = / | ch = #) return true; return false;void trans(char ch, char a, int *i, int *j) switch (ch) case E: *i = 0; break; case e: *i = 1; break; case T: *i = 2; break; case t: *i = 3; break; case F: *i = 4; break; case A: *i = 5; break; case M: *i = 6; break; switch (a) case i: *j = 0; break; case +: *j = 1; break; case -: *j = 2; break; case *: *j = 3; break; case /: *j = 4; break; case (: *j = 5; break; case ): *j = 6; break; case #: *j = 7; break; void search_table(char ch, char a) int i, j; trans(ch, a, &i, &j);char temp20 = 0; strcpy(temp, TABLEij); if (strcmp(temp, ) = 0) pop(); return; else if (strcmp(temp, ) != 0) pop(); for (unsigned ii = 0; ii strlen(temp); ii+) push(tempii); return; else printf(Error!n); exit(0); void main() FILE *in; int id = 0; char a = 0; in = fopen(result.txt, r); push(#); push(E); id = get_id(in); translate(id, &a); while (true) if (is_terminate(stacktop