算符优先分析程序.doc

编译原理实验报告实验名称：_算符优先分析程序 _实验类型：_设计型实验_指导教师：_何中胜_专业班级：_09计二_姓 名：_周健_学 号：_09030231_电子邮件：_实验地点：_院士楼720_实验成绩：_1、 试验目的和要求通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词 序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。1、选择最有代表性的语法分析方法，如 LL(1) 语法分析程序、算符优先分析程序和LR 分析分析程序，并至少完成两个题目。2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对 象，并且与所选语法分析方法要比较贴切。 实习前的准备 按实习目的和要求，编写语法分析程序，同时考虑相应的数据结构。 调试调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。 输出 对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。 扩充 有余力的同学，可适当扩大分析对象。譬如： 算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等 等。 除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。加强 语法检查，尽量多和确切地指出各种错误。 编写上机实习报告。2、 实验过程1、准备：阅读课本有关章节，确定算术表达式的文法。2、 考虑好设计方案。3、 设计出模块结构、测试数据，初步编制好程序。4、 上机调试，发现错误，分析错误，在修改完善。算符优先文法分为两种：一种是自上而下的，一种是自下而上的，本次采用自上而下的方式。3、 试验结果4、 讨论与分析自下而上分析技术：从输入符号串出发，试图把它规约为识别符号。自下而上分析技 术是一种“移进归约”法。从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进归约”方法。分析器做四种动作：1、移进：将下一输入符号移入栈2、归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄3、接受：分析成功，是归约的一种特殊情况4、出错：栈顶的内容与输入符号相悖，进行出错处理构造FIRESVT和LASTVT，建立算符优先关系表来辅助判断FIRESVT：对每个非终结符 P，FIRSTVT(P)=a|Pa.或 PQa.，a 为终结符，P、Q 为非终结符LASTVT:对每个非终结符 P，LASTVT(P)=a|P.a 或 P. aQ，a 为终结符，P、Q 为非终结符构造优先关系表：1、如果每个非终结符的 FIRSTVT 和 LASTVT 集均已知,则可构造优先关系表。2、若产生式右部有.aP.的形式，则对于每个 bFIRSTVT(P)都有 ab(优先集)；3、若产生式右部有.Pb 的形式，则对于每个 aLASTVT(P)集,都有 a b； 4、若产生是形如：Aab 或 AaBb形式，则有 a b。5、#与其他终结符的优先关系可利用拓广文法 S #S#来获得。五、附录#include stdio.h#include malloc.hstruct Lcharchar char_ch;struct Lchar *next;LLchar,*p,*h,*temp,*top,*base;int table88= 1,1,-1,-1,-1,1,-1,1, 1,1,-1,-1,-1,1,-1,1, 1,1,1,1,-1,1,-1,1, 1,1,1,1,-1,1,-1,1, -1,-1,-1,-1,-1,-1,-1,0, 1,1,1,1,0,1,0,1, 1,1,1,1,0,1,0,1, -1,-1,-1,-1,-1,0,-1,-1;/存储算符优先关系表，大于为1，小于或等于为-1，其它为0表示出错char curchar;char curcmp;int right; /*设置开关项，当出错时为0*/ int i,j; int k; /*比较字符在栈的位置*/void push(char pchar) /*入栈函数*/ temp=(Lchar*)malloc(sizeof(LLchar); temp-char_ch=pchar; temp-next=top; top=temp; void pop(void) /*出栈函数*/ if(top-char_ch!=#) top=top-next; int changchartoint(char ch) /*将字符转为数字，以得到算符优先值*/ int t; switch(ch) case +:t=0;break; case -:t=1;break; case *:t=2;break;case /:t=3;break; case (:t=4;break; case ):t=5;break; case i:t=6;break;case #:t=7; return t; void dosome(void) k=1;for(;) curchar=h-char_ch; temp=top;for(;) if(temp-char_ch=N) temp=temp-next; k+; else curcmp=temp-char_ch; break; printf(n%dt%dt,tableij,k); temp=top; for(;) /*打印栈*/ printf(%c,temp-char_ch); if(temp-char_ch=#) break; else temp=temp-next; printf(t);temp=h; for(;) /*打印待比较的字符*/ printf(%c,temp-char_ch); if(temp-char_ch=#) break; else temp=temp-next; i=changchartoint(curcmp); j=changchartoint(curchar);if(tableij=0) /*算符优先值为空*/ printf(n%dt%dt%ct%cterror1,tableij,k,curcmp,curchar); right=0; break; else /*算符优先值不为空*/ if(tableijnext; else /*算符优先值为1，归约*/ if(curcmp=i) /*当前比较为i,出栈一次*/ pop(); else /*当前比较不为i,出栈三次*/ pop(); pop(); pop(); push(N); /*归约到N*/ k=1; void main(void) char ch; right=1; base=(Lchar*)malloc(sizeof(LLchar); base-next=NULL;base-char_ch=#; top=base; h=(Lchar*)malloc(sizeof(LLchar); h-next=NULL;p=h; do /*输入待比较字符串，以#结束*/ ch=getchar(); putchar(ch);if(ch=i|ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#) temp=(Lchar*)malloc(sizeof(LLchar); temp-next=NULL; temp-char_ch=ch; h-next=temp; h=h-next; else temp=p-next; printf(nInput a wrong char!Input again:n); for(;) if (temp!=NULL) printf(%c,temp-char_ch); else break; temp=temp-next; while(ch!=#); /*输入待比较字符串，以#结束*/ p=p-next; h=p;dosome(); /*开始识别*/ if(right) printf(nOK!n); elseprintf(nError!n); getchar(); 6、 实验者自评通过本次试验队算符优先算法有了进一步的了解，知道了FARST