编译原理——语法分析

实验报告学院（系）名称：计算机与通信工程学院姓名Sky学号专业计算机科学与技术班级2班实验名称语法分析课程名称编译原理课程代码0668056实验时间2016年4月21日08:00-10:002016年4月26日10:00-13:00实验地点7-220批改意见成绩教师签字：实验内容与要求：实现如下表达式文法的语法分析器，可选择LL1分析法、算符优先分析法、LR分析法之一完成实验，要求输出全部分析过程：（1）E→E+T|E-T|T（2）T→T*F|T/F|F（3）F→P^F|P（4）P→(E)|i实验内容：LL(1)分析法：所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C语言来编写。LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。①FIRST集合的构造算法：（1）若X∈VT，则FIRST（X）={X}。（2）若X∈VN，且有产生式X→a……，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。（3）若X→Y……是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε（即Y1…Yi-1*ε），则把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j=1,2,…，k，则把ε加到FIRST(X)中。连续使用上面的规则，直至每个集合FIRST不再增大为止。②FOLLOW集合的构造算法：（1）对于文法的开始符号S，置#于FOLLOW(S)中；（2）若A→αBβ是一个产生式，则把FIRST(β)|{ε}加至FOLLOW(B)中；（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。连续使用上面的规则，直至每个集合FOLLOW不再增大为止。现在来构造G［E］的LL（1）预测分析表。预测分析表M[A,a]是如下形式的一个矩阵。A为非终结符，a是终结符或‘#’。矩阵元素M[A,a]中存放这一条关于A的产生式，指出当A面临输入符号a是所应采用的规则。M[A,a]也可能存放一条“出错标志”，指出当A根本不该面临输入符号a。程序源码：#includeiostream#includefstream#includestdio.h#includestdlib.h#includestring.h#includevector#includeiomanip#includeLexAnalysis.husingnamespacestd;intleftSmall=0;//左小括号intrightSmall=0;//右小括号intleftMiddle=0;//左中括号intrightMiddle=0;//右中括号intleftBig=0;//左大括号intrightBig=0;//右大括号intlineBra[6][1000]={0};//括号和行数的对应关系，第一维代表左右6种括号intstatic_iden_number=0;//模拟标志符的地址，自增//Token节点NormalNode*normalHead;//首结点//错误节点structErrorNode{charcontent[30];//错误内容chardescribe[30];//错误描述inttype;intline;//所在行数ErrorNode*next;//下一个节点};ErrorNode*errorHead;//首节点//标志符节点structIdentiferNode{charcontent[30];//内容chardescribe[30];//描述inttype;//种别码intaddr;//入口地址intline;//所在行数IdentiferNode*next;//下一个节点};IdentiferNode*idenHead;//首节点vectorpairconstchar*,intkeyMap;vectorpairconstchar*,intoperMap;vectorpairconstchar*,intlimitMap;voidinitNode(){normalHead=newNormalNode();strcpy(normalHead-content,);strcpy(normalHead-describe,);normalHead-type=-1;normalHead-addr=-1;normalHead-line=-1;normalHead-next=NULL;errorHead=newErrorNode();strcpy(errorHead-content,);strcpy(errorHead-describe,);errorHead-line=-1;errorHead-next=NULL;idenHead=newIdentiferNode();strcpy(idenHead-content,);strcpy(idenHead-describe,);idenHead-type=-1;idenHead-addr=-1;idenHead-line=-1;idenHead-next=NULL;}voidcreateNewNode(char*content,char*descirbe,inttype,intaddr,intline){NormalNode*p=normalHead;NormalNode*temp=newNormalNode();while(p-next!=NULL){p=p-next;}strcpy(temp-content,content);strcpy(temp-describe,descirbe);temp-type=type;temp-addr=addr;temp-line=line;temp-next=NULL;p-next=temp;}voidcreateNewError(char*content,char*descirbe,inttype,intline){ErrorNode*p=errorHead;ErrorNode*temp=newErrorNode();strcpy(temp-content,content);strcpy(temp-describe,descirbe);temp-type=type;temp-line=line;temp-next=NULL;while(p-next!=NULL){p=p-next;}p-next=temp;}voidprintNodeLink(){NormalNode*p=normalHead;p=p-next;cout************************************分析表******************************endlendl;coutsetw(30)内容setw(10)描述\t种别码\t地址\t行号endl;while(p!=NULL){if(p-type==IDENTIFER){coutsetw(30)p-contentsetw(10)p-describe\tp-type\tp-addr\tp-lineendl;}else{coutsetw(30)p-contentsetw(10)p-describe\tp-type\t\tp-lineendl;}p=p-next;}coutendlendl;}intgetSymbolPosOfKey(stringt){intpos=-1;for(inti=0;iKEYLENGTH;i++){if(!_stricmp(key[i],t.c_str())){pos=i;break;}}returnpos;}intgetTerminalSymbolPos(stringt){intpos=-1;for(inti=0;iy;i++){strings=terminalSymbol[i];if(s==t){pos=i;break;}}returnpos;}intgetNonTerminalSymbolPos(stringnt){intpos=-1;for(inti=0;ix;i++){if(nonterminalSymbol[i]==nt){pos=i;break;}}returnpos;}//读入chcharGetChar(ifstream&infileStream){charcRet;infileStream.get(cRet);returncRet;}//读入空格charGetBC(ifstream&infileStream){charcRet;infileStream.get(cRet);while(cRet=='')infileStream.get(cRet);returncRet;}//连接单词符号voidConcat(char*str,charc){size_tn=strlen(str);str[n++]=c;str[n]='/0';}//判断是否为保留字intReserve(constchar*str){intbRet=-1;for(inti=0;iKEYLENGTH;i++){if(_stricmp(key[i],str)==0){bRet=i;break;}}returnbRet;}//回调字符charRetract(ifstream&infileStream){infileStream.seekg(-1,ios::cur);return'/0';}lexicalTypelexical(ifstream&infileStream){charch;charstrToken[1024]=;ch=GetChar(infileStream);intpos=-1;//判断标识符的情况if(isalpha(ch)){wh