下载文档原格式
LL1实验报告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）分析表代替相应方法来进行分析的。
2.分析LL ( 1) 分析表是一个二维表，它的表列符号是当前符号，包括文法所有的终结和自定义。
的句子结束符号#，它的表行符号是可能在文法符号栈SYN中出现的所有符号，包括所有的非终结符，所有出现在产生式右侧且不在首位置的终结符，自定义的句子结束符号#表项。
Ξ 收稿日期:2007-06-12基金项目:国防科工委纵向课题资助项目(H102006A004).作者简介:曹琼(1979—),女,四川邻水人,硕士,主要从事软件工程方面的研究.【计算机与信息技术】LL(1)预测分析程序设计与实现Ξ曹 琼(重庆工学院,重庆 400050)摘要:讨论了编译原理中理解和实现都比较困难而又在语法分析中占重要位置的LL (1)预测分析方法.从对该方法的理解入手,构造了该方法实现中的关键数据结构,同时阐述了依据此数据结构编程实现的思路.结果表明:该方法可以正确、准确地识别指定文法的句子.关 键 词:LL (1)预测分析;编译原理;文法;句子中图分类号:TP314 文献标识码:A文章编号:1671-0924(2007)08-0142-03Design and R ealization of LL(1)Predicative Analysis ProcedureCAO Qiong(Chongqing Institute of T echnology ,Chongqing 400050,China )Abstract :This paper discusses LL (1)predictive analysis alg orithm ,which is a very im portant in grammat 2ical analysis and is als o hard to understand and realize.Starting with the understanding of this alg orithm ,this paper constructs the key data structure in program ,and expatiates on the realizing routines of program 2ming based on these data structure.Results show that it can correctly ,exactly judge a statement whether a given sentence belongs to a grammar or not.K ey w ords :LL (1)predictive analysis ;com piler principles ;grammar ;sentence 在一个编译器中,语法分析器的位置举足轻重,这是因为有不少编译器,在语法分析阶段都伴随了语义分析直至中间代码生成,囊括了编译器中的大部分内容.常见的语法分析方法主要有自上而下分析方法和自下而上分析方法2种,其中自上而下的分析方法包括有递归下降法和LL (1)预测分析法,自下而上的分析方法包括算符优先分析和LR 分析方法.LL (1)预测分析方法以其执行效率高,便于维护的优点而被广泛采用[1].LL (1)预测分析方法中第1个L 代表从左向右扫描输入,第2个L 代表产生最左推导,1代表在决定语法分析器的每一步动作时(选择推导)向前扫描一个输入符号[2].1 LL (1)预测分析方法 在对文法进行LL (1)预测分析时,要求文法一定要是LL (1)文法.LL (1)文法的判定条件是:①第21卷 第8期V ol.21 N o.8重庆工学院学报(自然科学版)Journal of Chongqing Institute of Technology (Natural Science Edition )2007年8月Aug.2007文法不含左递归;②对文法中的任一个非终结符A的各个产生式的候选首终结符集两两不相交,即若A→α1/α2/…/αn则:Fir st(αi)∩Fir st(αj)= <(i≠j);③对文法中的每个非终结符A,若它的某个首终结符集含有ε,则Fir st(A)∩Follow(A)= <.LL(1)预测分析的分析流程为[6]:若a∈Fir st(A→αi),则使用αi去执行匹配任务.若a不属于任何一个产生式的首终结符集,当ε不属于任何一个Fir st(A→αi)时,则出错,当ε属于某个Fir st(A→αi),同时a∈Follow(A)时,则让A与ε自动匹配,否则,a的出现是一种语法错误.通常是构造一个预测分析表矩阵M[A,a]来存储从非终结符到终结符(包括#)规则的映射[3],其中A为非终结符,a为终结符.矩阵元素M[A,a]中存放着一条关于A的产生式,指出当A面临输入符号a时所应采用的候选.当A根本不可能面临输入符号a时,在M[A,a]中存放出错标志.可以看出,非终结符的Fir st集和Follow集是构造预测分析表的基础,求Fir st集和Follow集可以采取如下算法:求某一非终结符A的首终结符集Fir st(A)的算法[4]为:若有产生式A→aα,且a为终结符,把a加到Fir st(A)中;若有产生式A→ε,把ε加到Fir st(A)中;若有产生式A→Xα,X为非终结符,把Fir st(X)中非ε元素加到Fir st(A)中;若有产生式A→X1X2X3…X kα,其中X1X2X3…X k都是非终结符,则当X1X2X3…X k=>ε(1≤i≤k)时,把Fir st(X i+1…X kα)的所有非ε元素加到Fir st(A)中,当X1X2X3…X k=>ε时,则把Fir st(α)加入Fir st(A)中.重复执行上述过程,直到Fir st(A)不再增大.求某一非终结符A的Follow集的算法如下:如果A是开始符号,#∈Follow(A).若有产生式B→αAaβ,a∈VT,则把a加入到Follow(A)中;若有产生式B→αAXβ,X∈VN,则把Fir st(Xβ)中非ε元素加入Follow(A)中;若B→αA或B→αAβ,β=>ε,则把Follow(B)加入到Follow(A)中.连续使用上述规则,直到Follow(A)不再增大.构造好预测分析表之后,就可以根据预测分析表中的内容和当前输入符号对句子进行分析了.2 LL(1)预测分析方法的设计与实现 预测分析的核心是构造预测分析表,而预测分析表的构造基础是文法非终结符的候选首终结符集Fir st(A)和后随符号集Follow(A).所以,预测分析技术的实现可以划分为如下3个步骤:①求文法非终结符的候选首终结符集和后随符号集;②构造预测分析表;③根据输入符号和预测分析表对句子进行分析.考虑到构造预测分析表的需要,对非终结符的每个候选式求出其对应的候选首终结符集,也就是对于非终结符的Fir st集里的每个元素,都要唯一确定它是由哪一个候选式所推导出来的[5].这样,在以后构造预测分析表的时候,才知道当非终结符A面临输入符号a时,应选用A的哪一个候选式进行匹配.由此,可以这样设计相关的数据结构:struct sponser{char vn;//存放非终结符char first[MAX];//存放Fir st集char follow[MAX];//存放Follow集struct candidate3candidatelist;//对应的产生式的候选式链表struct candidate3followrelation;//和求Follow 集有关的节点struct sponser3next;};//存储文法的产生式struct list{char content[MAX];//节点信息list3next;};//存储关系节点struct candidate{char option[MAX];//候选式char vt[MAX];//由该候选式求出的Fir st集list3firstrelation;//与该候选式相关的节点struct candidate3next;};//候选式的数据结构341曹 琼:LL(1)预测分析程序设计与实现根据这套数据结构,求Fir st集的程序流程如下:①从文件中读取字符串;祛除字符串中的空格等无用字符;根据此生成一个产生式链表.②遍历产生式链表,对每一个非终结符,遍历其候选式链表:如果有产生式A→aα,a∈VT,则把a加入到Fir st(A)中;若有产生式A→ε,则把ε加入到Fir st(A)中;若有产生式A→X1X2X3…X kα(其中也包括了A→Xα的情况),则将X1X2X3…X kα放入Fir st集相关的关系链表中.③再次遍历产生式链表,对于每一个非终结符,去遍历其与Fir st集相关的关系链表.用递归方法,从X1X2X3…X k的头部开始依次查找是否可以推导出ε,直到第一个不能推导出ε的元素X j 为止,停止查找,将后面X j的元素全部舍去.④再次遍历产生式链表,对于每一个非终结符,去遍历其与Fir st集相关的关系链表.如果Fir st(X i)中有元素,则把Fir st(X i)中非ε元素以及Fir st(A)中没有的元素加入到Fir st(A)中;如果X i的关系链表不为空,则把他关系链表中没有在A的关系链表中出现的接点插入到A的关系链表中.Follow集的求法类似.求出了所有非终结符的Fir st集和Follow集之后,就可以依据由此候选式求出的Fir st元素,在预测分析表中的相应位置填上匹配该终结符所用的候选式.如果其Fir st集中含有ε元素,则对该非终结符的Follow集中的每个终结符号或#,填上该非终结符的候选式为ε的产生式,其他未定义元素置为ERROR.这样,就构造好了预测分析表.预测分析表构造好之后,我们就可以根据预测分析表和当前输入符号,利用一个堆栈来存储文法符号,对输入的句子进行分析[7].分析的程序流程[8]如下:首先将‘#’压入堆栈中,将开始符号S也压入堆栈中.读取第一个输入符号到a.循环执行下述操作:栈顶符号弹出放入X中,如果X为终结符号:当X==a!=‘#’时,表明成功匹配a符号,然后读取下一个符号到a,否则出错;当X==a=‘#’时,分析结束,接受句子,跳出循环.如果X!=a,进行出错处理.如果X为非终结符号,则查分析表M:如果M[X,a]为空,进行出错处理;如果M[X,a]=‘X1X2X3…X n’,则将右部X n…X2X1反序压入堆栈中.至此,就完成了LL(1)预测分析方法的全部过程.我们可以任意输入一个句子,根据预测分析表中的内容,来分析该句子.3 结束语 根据以上实现思路,对LL(1)预测分析方法进行了编码实现,结果表明,该方法可以正确识别指定文法的句子.参考文献:[1] 宿云.确定有穷状态自动机最小化算法的三点说明[J].甘肃科技纵横,2005,34(6):41,172.[2] 李文生.编译程序设计原理与技术[M].北京:北京邮电大学出版社,2002.[3] 沈整.LR(0)项目集规范族的一种简易构造算法[J].江汉大学学报,2001,18(6):69-70.[4] 吕映芝,张素琴,蒋维杜.编译原理[M].北京:清华大学出版社,1998.[5] Andrew W A.现代编译原理C语言描述[M].赵克佳,译.北京:人民邮电出版社,2006.[6] Dick G,Henri E.现代编译程序设计[M].北京:人民邮电出版社,2003.[7] 温敬和,温敬平.S LR(1)词/语法分析的自动构造[J].计算机工程,2002,28(3):276-276.[8] 徐红.对确定有限自动机最小化算法的改进[J].桂林航天工业高等专科学校学报,2005(4):14-16.(责任编辑 刘 舸)441重庆工学院学报。
编译原理实验预测分析法姓名**学号**班级**完成日期**1．实验目的加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。
2．实验要求1.对语法规则有明确的定义；2.编写的分析程序能够对实验一的结果进行正确的语法分析；3． 3.对于遇到的语法错误, 能够做出简单的错误处理, 给出简单的错误提示, 保证顺利完成语法分析过程；4． 4.实验报告要求用文法的形式对语法定义做出详细说明, 说明语法分析程序的工作过程, 说明错误处理的实现。
5．实验原理对文法G进行语法分析, 文法G如下所示:*0. S→a */*1. S→.*2. S→(T)*3. T→SW **4..W→,S.*5. W→ε;6．软件设计与编程#include <stdio.h>#include <stdlib.h>#include <string.h>char str[100]; //存储待分析的句子const char T[ ] = "a^(),#"; //终结符, 分析表的列符const char NT[ ] = "STW"; //非终结符, 分析表的行符/*指向产生式右部符号串*/const char *p[] = {/*0. S→a */ "a",/*1.. S→. *. "^",/*2. S→(T) */ "(T)",/*3. T→SW */ "SW",/*4.. W→,S. */ ",SW",/*5. W→ε; */ ""};//设M[i][j]=x, 通过p[M[i][j]]=p[x]获取右部符号串。
const int M[][6] = {/* a ^ ( ) , # *//*S*/ { 0, 1, 2, -1, -1, -1 },/*T*/ { 3, 3, 3, -1, -1, -1 },/*W*/ { -1, -1,-1, 5, 4, -1 }};void init()//输入待分析的句子{printf("请输入待分析的句子(以$结束): \n");scanf("%s",str);}int lin(char c);//非终结符转换为行号int col(char c);//终结转换为列号bool isNT(char c);//isNT判断是否是非终结符bool isT(char c);//isT判断是否是终结符。
国开电大编译原理实验4：语法分析实
验报告
1. 实验目的
本实验的目的是研究和掌握语法分析的原理和实现方法。
2. 实验内容
本次实验主要包括以下内容：
- 设计并实现自顶向下的LL(1)语法分析器；
- 通过语法分析器对给定的输入串进行分析，并输出相应的分析过程；
- 编写测试用例，验证语法分析器的正确性。
3. 实验步骤
3.1 设计LL(1)文法
首先，根据实验要求和给定的语法规则，设计LL(1)文法。
3.2 构建预测分析表
根据所设计的LL(1)文法，构建预测分析表。
3.3 实现LL(1)语法分析器
根据预测分析表，实现自顶向下的LL(1)语法分析器。
3.4 对输入串进行分析
编写程序，通过LL(1)语法分析器对给定的输入串进行分析，并输出相应的分析过程和结果。
3.5 验证语法分析器的正确性
设计多组测试用例，包括正确的语法串和错误的语法串，验证语法分析器的正确性和容错性。
4. 实验结果
经过实验，我们成功设计并实现了自顶向下的LL(1)语法分析器，并对给定的输入串进行了分析。
实验结果表明该语法分析器具有较好的准确性和容错性。
5. 实验总结
通过本次实验，我们对语法分析的原理和实现方法有了更深入的了解。
同时，我们也学会了如何设计并实现自顶向下的LL(1)语
法分析器，并验证了其正确性和容错性。
这对于进一步研究编译原理和深入理解编程语言的语法结构具有重要意义。
6. 参考资料
- 《编译原理与技术》
- 课程实验文档及代码。
预测分析算法设计与实现程序代码:#include "stdio.h"#include "stdlib.h"#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct pRNode /*产生式右部构造*/{int rCursor；struct pRNode *next;};struct pNode{int lCursor；int rLength；/*右部长度*/struct pRNode *rHead；/*右部结点头指针*/ };char Vn[MaxVnNum + 1]；/*非终结符集*/int vnNum;char Vt[MaxVtNum + 1]；/*终结符集*/int vtNum;struct pNode P[MaxRuleNum]；int PNum；char buffer[MaxPLength + 1];char ch；char st[MaxStLength]；/*要分析符号串*/struct collectNode{int nVt；void ShowAT();/*输出分析表*/void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);int main(){char todo,ch;Init();InputVn();InputVt();InputP();getchar()；FirstFollow();printf("所得first集为：");ShowCollect(first);printf("所得follow集为：");ShowCollect(follow);CreateAT();ShowAT();todo = 'y';while('y' == todo){printf("\n与否继续进行句型分析？(y / n):"); todo = getchar();while('y' != todo && 'n' != todo){printf("\n(y / n)?");todo = getchar();}if('y' == todo){int i;InitStack();printf("请输入符号串(以#结束) ：");ch = getchar();i = 0;while('#' != ch && i < MaxStLength) {st[i] = ch;Identify(st);}elseprintf("输入出错！\n");}}getchar();}void Init(){int i,j;vnNum = 0;vtNum = 0;PNum = 0;for(i = 0；i <= MaxVnNum；i++)Vn[i] = '\0';for(i = 0；i <= MaxVtNum；i++)Vt[i] = '\0';for(i = 0；i < MaxRuleNum；i++){P[i].lCursor = NULL;P[i].rHead = NULL;P[i].rLength = 0;}PNum = 0;for(i = 0；i <= MaxPLength；i++)}}int IndexCh(char ch){int n;n = 0；/*is Vn?*/while(ch != Vn[n] && '\0' != Vn[n]) n++;if('\0' != Vn[n])return 100 + n;n = 0；/*is Vt?*/while(ch != Vt[n] && '\0' != Vt[n]) n++;if('\0' != Vt[n])return n;return -1;}/*输出Vn或Vt内容*/void ShowChArray(char* collect){int k = 0;while('\0' != collect[k]){printf(" %c "，collect[k++]);}printf("\n");}/*输入非终结符*/void InputVn(){{Vn[n++] = '\0';}n = 0;while(('#' != ch) && (n < MaxVnNum)){if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) {Vn[n++] = ch;vnNum++;}ch = getchar();}Vn[n] = '#'；/*以"#"标志结束用于判断长度与否合法*/ k = n；if('#' != ch){if( '#' != (ch = getchar())){while('#' != (ch = getchar()));printf("\n符号数目超过限制！\n");inErr = 1;continue;}{printf("输入对的确认?(y/n):");}scanf("%c"，&ch);}if('n' == ch){printf("录入错误重新输入！\n");inErr = 1;}else{inErr = 0;}}}/*输入终结符*/void InputVt(){int inErr = 1;int n,k;char ch;while(inErr){printf("\n请输入所有终结符，注意：");printf("以#号结束:\n")；ch = ' ';n = 0;/*初始化数组*/while(n < MaxVtNum){Vt[n++] = '\0';}n = 0;while(('#' != ch) && (n < MaxVtNum)){if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))Vt[n++] = ch;vtNum++;}ch = getchar();}Vt[n] = '#'；k = n；if('#' != ch){if( '#' != (ch = getchar())){while('#' != (ch = getchar())) ;printf("\n符号数目超过限制！\n"); inErr = 1;continue;}}Vt[k] = '\0';ShowChArray(Vt);ch = ' ';while('y' != ch && 'n' != ch){if('\n' != ch)printf("输入对的确认?(y/n):"); }scanf("%c"，&ch);}if('n' == ch){printf("录入错误重新输入！\n"); inErr = 1;}else{inErr = 0;}}}/*产生式输入*/void InputP(){char ch;int i = 0，n,num;printf("请输入文法产生式个数："); scanf("%d"，&num);PNum = num;getchar()；/*消除回车符*/printf("\n请输入文法%d个产生式,并以回车分隔每个产生式："，num); printf("\n");while(i < num){printf("第%d个："，i);/*初始化*/for(n =0；n < MaxPLength；n++)buffer[n] = '\0';/*输入产生式串*/ch = ' ';n = 0;while('\n' != (ch = getchar()) && n < MaxPLength){if(' ' != ch)buffer[n++] = ch；}buffer[n] = '\0';if(CheckP(buffer)){pRNode *pt，*qt;P[i].lCursor = IndexCh(buffer[0]);pt = (pRNode*)malloc(sizeof(pRNode));pt->rCursor = IndexCh(buffer[3]);pt->next = NULL;P[i].rHead = pt;n = 4;while('\0' != buffer[n]){qt = (pRNode*)malloc(sizeof(pRNode));qt->rCursor = IndexCh(buffer[n]);qt->next = NULL;pt->next = qt;pt = qt;n++;}P[i].rLength = n - 3;i++;}elseprintf("输入符号含非法在成分，请重新输入！\n"); }}/*判断产生式对的性*/bool CheckP(char * st){int n;if(100 > IndexCh(st[0]))return false;if('-' != st[1])return false;if('>' != st[2])return false;for(n = 3；'\0' != st[n]；n ++) {if(-1 == IndexCh(st[n]))return false;}return true;}void First(int U){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);}}}/*加入first集*/void AddFirst(int U，int nCh){struct collectNode *pt，*qt;int ch；/*用于解决Vn*/pt = NULL;qt = NULL;if(nCh < 100){pt = first[U - 100];while(NULL != pt){if(pt->nVt == nCh)break;else{qt = pt;pt = pt->next;}}if(NULL == pt){pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh;pt->next = NULL;if(NULL == first[U - 100]){first[U - 100] = pt;}else{qt->next = pt；/*qt指向first集最后一种元素*/ }pt = pt->next;}}else{pt = first[nCh - 100];while(NULL != pt){ch = pt->nVt;if(-1 != ch){AddFirst(U，ch);}pt = pt->next;}}}bool HaveEmpty(int nVn)if(nVn < 100)return false;struct collectNode *pt;pt = first[nVn - 100];while(NULL != pt){if(-1 == pt->nVt)return true;pt = pt->next;}return false;}void Follow(int V){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 AddFollow(int V，int nCh，int kind) {struct collectNode *pt，*qt;int ch；pt = NULL;qt = NULL;if(nCh < 100) /*为终结符时*/{pt = follow[V - 100];while(NULL != pt){if(pt->nVt == nCh)break;else{qt = pt;pt = pt->next;}}if(NULL == pt){pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh;pt->next = NULL;if(NULL == follow[V - 100]){follow[V - 100] = pt;}else{qt->next = pt；/*qt指向follow集最后一种元素*/}pt = pt->next;}}else{if(0 == kind){pt = follow[nCh - 100];while(NULL != pt){ch = pt->nVt;AddFollow(V，ch，0);pt = pt->next;}}else{pt = first[nCh - 100];while(NULL != pt){ch = pt->nVt;if(-1 != ch){AddFollow(V，ch，1);}pt = pt->next;}}}}/*输出first或follow集*/void ShowCollect(struct collectNode **collect) {int i;struct collectNode *pt;i = 0;while(NULL != collect[i]){pt = collect[i];printf("\n%c:\t"，Vn[i]);while(NULL != pt){if(-1 != pt->nVt){printf(" %c"，Vt[pt->nVt]); }elseprintf(" #");pt = pt->next;}i++;}printf("\n");}/*计算first和follow*/void FirstFollow(){int i;i = 0;while('\0' != Vn[i]){if(NULL == first[i])First(100 + i);i++;}i = 0;while('\0' != Vn[i]){if(NULL == follow[i])Follow(100 + i);i++;}}/*构造预测分析表*/void CreateAT(){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];{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];{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; }}}}}/*输出分析表*/void ShowAT(){int i,j;printf("构造预测分析表如下：\n");printf("\t|\t");for(i = 0；i < vtNum；i++){printf("%c\t"，Vt[i]);}printf("#\t\n");printf("- - -\t|- - -\t");for(i = 0；i <= vtNum；i++)printf("- - -\t");printf("\n");for(i = 0；i < vnNum；i++){printf("%c\t|\t"，Vn[i]);for(j = 0；j <= vtNum；j++){if(-1 != analyseTable[i][j])printf("R(%d)\t"，analyseTable[i][j]);elseprintf("error\t");}printf("\n");}}void Identify(char *st){int current,step,r；/*r表使用产生式序号*/printf("\n%s分析过程：\n"，st);printf("环节\t分析符号栈\t当前批示字符\t使用产生式序号\n"); step = 0;current = 0；printf("%d\t",step);ShowStack();printf("\t\t%c\t\t- -\n"，st[current]);while('#' != st[current]){if(100 > analyseStack[topAnalyse]){if(analyseStack[topAnalyse] == IndexCh(st[current])) {Pop();current++;step++;printf("%d\t"，step);ShowStack();printf("\t\t%c\t\t出栈、后移\n"，st[current]);}else{printf("%c-%c不匹配！"，analyseStack[topAnalyse]，st[current]); printf("此串不是此文法句子！\n");return;}}else /*当为非终结符时*/{r = analyseTable[analyseStack[topAnalyse] - 100][IndexCh(st[current])];if(-1 != r){Push(r)；step++;printf("%d\t"，step);ShowStack();printf("\t\t%c\t\t%d\n"，st[current]，r);}else{printf("此串不是此文法句子！\n");return;}}}if('#' == st[current]){if(0 == topAnalyse && '#' == st[current]){step++;printf("%d\t"，step);ShowStack();printf("\t\t%c\t\t分析成功！\n"，st[current]); printf("%s是给定文法句子！\n"，st);}else{while(topAnalyse > 0){if(100 > analyseStack[topAnalyse]){printf("此串不是此文法句子！\n");return;}else{r = analyseTable[analyseStack[topAnalyse] - 100][vtNum]; if(-1 != r){Push(r)；/*产生式右部代替左部，批示器不移动*/step++;printf("%d\t"，step);ShowStack();if(0 == topAnalyse && '#' == st[current]){printf("\t\t%c\t\t分析成功！\n"，st[current]);printf("%s是给定文法句子！\n"，st);}elseprintf("\t\t%c\t\t%d\n"，st[current]，r);}else{printf("此串不是此文法句子！\n");return;}}}}}}/*初始化栈及符号串*/void InitStack(){int i;/*分析栈初始化*/for(i = 0；i < MaxStLength；i++)st[i] = '\0';analyseStack[0] = -1；/*#(-1)入栈*/analyseStack[1] = 100；/*初始符入栈*/topAnalyse = 1;}/*显示符号栈中内容*/void ShowStack(){int i;for(i = 0；i <= topAnalyse；i++){if(100 <= analyseStack[i])printf("%c"，Vn[analyseStack[i] - 100]); else{if(-1 != analyseStack[i])printf("%c"，Vt[analyseStack[i]]);elseprintf("#");}}}/*栈顶出栈*/void Pop(){topAnalyse--;}void Push(int r){int i;struct pRNode *pt;Pop();pt = P[r].rHead;if(-1 == pt->rCursor)return;topAnalyse += P[r].rLength;for(i = 0；i < P[r].rLength；i++){analyseStack[topAnalyse - i] = pt->rCursor;/*逆序入栈*/ pt = pt->next;}}运营成果演示:。
预测分析程序实验报告题⽬：预测分析法⼀、实验⽬的1、通过实验要学会⽤消除左递归和消除回溯的⽅法来使⽂法满⾜进⾏确定⾃顶向下分析的条件；2、学会⽤C/C++⾼级程序设计语⾔编写⼀个LL（1）分析法程序⼆、实验内容及要求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。
1、给定⽂法S -> a | b | (T)T -> SH | dH -> ,SH | ε2、该⽂法对应的预测分析表3、编写预测分析程序对句⼦进⾏分析三、试验程序设计说明1、相关函数说明分析栈可以采取许多的存储⽅法来设计，在这⾥采⽤的顺序栈。
根据预测分析原理，LL(1)分析程序的实现关键在于分析栈和分析表是采⽤何种数据结构来实现。
分析表是⼀个矩阵，当我们要调⽤分析表来分析时，就根据栈顶的⾮终结符和当前输⼊的终结符来决定执⾏哪种过程。
具体设计思想如下：printStack（）输出分析栈内内容；printinputString（）输出⽤户输⼊的字符串；Pop（）弹出栈顶元素；Push（）向栈内添加⼀个元素；Search（）查找⾮终结符集合VT 中是否存在输⼊的⾮终结符；yuCeFenXi（）进⾏输⼊串的预测分析的主功能函数；M(char A, char a)查看预测分析表M[A,a]中是否存在相应产⽣式。
LL1语法分析程序实验报告实验目的：通过编写LL(1)语法分析程序，加深对语法分析原理的理解，掌握语法分析方法的实现过程，并验证所编写的程序的正确性。
实验准备：1.了解LL(1)语法分析的原理和步骤；2.根据语法规则，构建一个简单的文法；3.准备一组测试用例，包括符合语法规则的输入和不符合语法规则的输入。
实验步骤：1.根据文法规则，构建预测分析表；2.实现LL(1)语法分析程序；3.编写测试用例进行测试；4.分析测试结果。
实验结果：我根据上述步骤，编写了一个LL(1)语法分析程序，并进行了测试。
以下是我的测试结果：测试用例1:输入：9+7*(8-5)分析结果：成功测试用例2:输入：3+*5分析结果：失败测试用例3:输入：(3+5)*分析结果：失败测试用例4:输入：(3+5)*2+4分析结果：成功分析结果符合预期，说明我编写的LL(1)语法分析程序是正确的。
在测试用例1和测试用例4中，分析结果是成功的，而在测试用例2和测试用例3中，分析结果是失败的，这是因为输入不符合文法规则。
实验总结：通过本次实验，我进一步理解了LL(1)语法分析的原理和步骤。
编写LL(1)语法分析程序不仅要根据文法规则构建预测分析表，还要将预测分析表与输入串进行比对，根据匹配规则进行预测分析，最终得到分析结果。
在实验过程中，我发现在构建预测分析表和编写LL(1)语法分析程序时需要仔细思考和调试才能保证正确性。
通过本次实验，我对语法分析方法的实现过程有了更深入的认识，对于将来在编译原理方面的学习和工作有了更好的准备。
