编译技术课程设计班级网络1102学号3110610035姓名徐静指导老师年轶2014年6 月目录一、目的 (2)二、题目 (2)三、要求 (2)四、实验环境 (2)五、系统实现 (2)六、程序运行结果 (8)七、总结 (9)一、目的通过《编译原理》课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，掌握词法分析、语法分析、语义分析、代码生成和报错处理等理论与实践的结合，提高自己的编程能力，培养好的程序设计风格。
同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。
二、题目输入文法，自动生成分析表，并完成语法分析工作三、要求题目3 文法编译器的自动生成器输入文法，自动生成分析表，并完成语法分析工作。
语法分析方法可以是：LL（1）分析法或LR分析法。
为文法构造分析表，并对输入串进行语法分析，判别是否符合语法规则，如果不符合，则输出错误信息。
输入：文法，文法符号串输出：分析表、分析栈、分析结果四、实验环境开发环境Visual Studio6.0语言C++五、系统实现1.分析方法说明所谓LL(1)分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。
实现LL(1)分析的程序又称为LL(1)分析程序或LL(1)分析器。
我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。
当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL(1)分析表，最后利用分析表，根据LL（1）语法分析构造一个分析器。
LL（1）的语法分析程序包含了三个部分，总控制程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写。
2.分析表的构造算法在构造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不再增大为止3.数据结构变量定义：struct pRNode /*产生式右部结构*/struct pNodestruct collectNodestruct collectNode* first[MaxVnNum + 1]; /*first集*/struct collectNode* follow[MaxVnNum + 1]; /*follow集*/char Vn[MaxVnNum + 1]; /*非终结符集*/int vnNum;char Vt[MaxVtNum + 1]; /*终结符集*/int vtNum;struct pNode P[MaxRuleNum];int PNum;char buffer[MaxPLength + 1];char st[MaxStLength]; /*要分析的符号串*/int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];int analyseStack[MaxStackDepth + 1]; /*分析栈*/int topAnalyse; /*分析栈顶*/类关系图：③LL(1)分析过程主要包括以下四个动作：替换：当X∈VN时选相应产生式的右部β去替换X。
此时X出栈，β逆序入栈。
匹配：当X∈VT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。
接受：当格局为（#，空#）时报告分析成功。
报错：出错后，停止分析。
并给出相应的错误提示信息。
驱动程序框图如下：4.函数说明void Init();/*初始化*/int IndexCh(char ch);void InputVt(); /*输入终结符*/void InputVn();/*输入非终结符*/void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/void InputP();/*产生式输入*/bool CheckP(char * st);/*判断产生式正确性*/void First(int U);void AddFirst(int U, int nCh); /*加入first集*/bool HaveEmpty(int nVn);void Follow(int V);/*计算follow集*/void AddFollow(int V, int nCh, int kind);void ShowCollect(struct collectNode **collect);/*输出first或follow集*/ void FirstFollow();/*计算first和follow*/void CreateA T();/*构造预测分析表*/void ShowAT();/*输出分析表*/void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);其中部分函数的具体实现：void First(int U) //构造first集合{int i,j;for(i = 0; i < PNum; i++){if(P[i].lCursor == U){struct pRNode* pt;pt = P[i].rHead;j = 0;while(j < P[i].rLength){if(100 > pt->rCursor){AddFirst(U, pt->rCursor);break;}else{if(NULL == first[pt->rCursor - 100]){First(pt->rCursor);}AddFirst(U, pt->rCursor);if(!HaveEmpty(pt->rCursor)){break;}else{pt = pt->next;}}j++;}if(j >= P[i].rLength) /*当产生式右部都能推出空时*/AddFirst(U, -1);}}}void Follow(int V) //构造follow集合{int i;struct pRNode *pt ;if(100 == V) /*当为初始符时*/AddFollow(V, -1, 0 );for(i = 0; i < PNum; i++){pt = P[i].rHead;while(NULL != pt && pt->rCursor != V)pt = pt->next;if(NULL != pt){pt = pt->next;if(NULL == pt){if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {Follow(P[i].lCursor);}AddFollow(V, P[i].lCursor, 0);}else{while(NULL != pt && HaveEmpty(pt->rCursor)){AddFollow(V, pt->rCursor, 1);pt = pt->next;}if(NULL == pt){if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {Follow(P[i].lCursor);}AddFollow(V, P[i].lCursor, 0);}else{AddFollow(V, pt->rCursor, 1);}}}}}void CreateA T() //构造LL（1）分析表{int i;struct pRNode *pt;struct collectNode *ct;for(i = 0; i < PNum; i++){pt = P[i].rHead;while(NULL != pt && HaveEmpty(pt->rCursor)) {ct = first[pt->rCursor - 100];while(NULL != ct){if(-1 != ct->nVt)analyseTable[P[i].lCursor - 100][ct->nVt] = i;ct = ct->next;}pt = pt->next;}if(NULL == pt){ct = follow[P[i].lCursor - 100];while(NULL != ct){if(-1 != ct->nVt)analyseTable[P[i].lCursor - 100][ct->nVt] = i;elseanalyseTable[P[i].lCursor - 100][vtNum] = i;ct = ct->next;}}else{if(100 <= pt->rCursor) /*不含空的非终结符*/{ct = first[pt->rCursor - 100];while(NULL != ct){analyseTable[P[i].lCursor - 100][ct->nVt] = i;ct = ct->next;}}else/*终结符或者空*/{if(-1 == pt->rCursor){ct = follow[P[i].lCursor - 100];while(NULL != ct){if(-1 != ct->nVt)analyseTable[P[i].lCursor - 100][ct->nVt] = i;else/*当含有#号时*/analyseTable[P[i].lCursor - 100][vtNum] = i;ct = ct->next;}}else/*为终结符*/{analyseTable[P[i].lCursor - 100][pt->rCursor] = i;}}}}}六、程序运行结果七、总结编译是把高级语言翻译成与之等价的低级语言的过程,它包括词法分析,语法分析,语义分析和中间代码生成,优化阶段和目标代码生成。