《语法分析器doc》由会员分享，可在线阅读，更多相关《语法分析器doc（12页珍藏版）》请在金锄头文库上搜索。
1、语法分析器语法分析器 docdoc语法分析器主要任务1. 明确语法分析器的原理及功能2. 理解自上而下分析方法的原理3. 对输入的文法可以消除左递归并提取公共左因子4. 求出文法的非终结集合-FIRST 和 FOLLOW 集5. 对输入的算符优先文法，构造算符优先关系表一明确语法分析器的原理及功能语法分析器通过接受词法分析程序识别出来的单词符号串，判断它们是否由某种语言的文法产生，即判断被识别符号串是否为某语法成分，同时进行语法检查，为后面的语义分析和代码生成作准备。二理解自上而下分析方法的原理自上而下分析法是语法分析分析方法两大类中的其中一个大类，还有一个大类是自下向上的分析方法。所谓自上而
2、下的分析方法，是指对任意输入的符号串，用一切可能的方法，从树根节点，即识别符号出发，根据文法自上而下地为输入串建立一颗语法树。自上而下的分析过程本质上是一种试探过程，该过程反复使用不同规则来谋求匹配输入的符号串。所以，为什么要称为是自上而下的分析方法，原因就在于，这一过程是从识别符号开始，然后建立语法树。这类分析方法有两大特点：1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后再根据语法成分的文法建立语法树。2.自上而下的分析方法可分为确定的和非确定的两种。确定的分析方法需对文法有一定的限制，这种方法相对简单、直观，是目前常用的一种方法。非确定的分析方法对任何输入串试图用一切可
3、能的办法，是一个试探的过程，所以会有失败，故该分析过程需要进行回溯。其具体的算法为：使用一个用于存放文法符号的先进后出栈，并利用优先关系可以确定最左素短语是否已形成来决定分析器的动作。如果当前栈顶的终结符号和待输入符号之间的优先关系是，则表示已经找到了最左素短语的尾，再从栈顶开始，按优先关系在栈内向左(向前)寻找最左素短语的头，然后分析器将归约最左素短语。如果出现两个终结符号之间不存在优先关系，则表示存在语法错误，分析器将调用出错处理程序。3）程序设计及调试对输入的文法可以消除左递归并提取公共左因子求出文法的非终结符集合-first 集和 follow 集三部分代码输入非终结符：void In
4、putVn()int inErr = 1;int n,k;char ch;while(inErr)printf(“n 请输入所有的非终结符,并以#号作为结束符，“);printf(“注意：将开始符放在第一位:n“); scanf(“%c“, n = 0;输入终结符:void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf(“n 请输入所有的终结符，并以#号作为结束符：n“);ch=getchar();n = 0;产生式输入：void InputP()char ch;int i = 1, n,num;printf(“n 请输入文
5、法产生式的个数：“);scanf(“%d“, /cinnum;PNum = num;getchar(); /*消除回车符*/printf(“n 请输入文法的%d 个产生式,并以回车分隔：“, num);printf(“n“);while(i nVt = nCh)break;elseqt = pt;pt = pt-next;if(NULL = pt)pt = (struct collectNode *)malloc(sizeof(struct collectNode);pt-nVt = nCh;pt-next = NULL;if(NULL = firstU - 100)firstU - 100
6、= pt;elseqt-next = pt; pt = pt-next;elsept = firstnCh - 100;while(NULL != pt)ch = pt-nVt;if(-1 != ch)AddFirst(U, ch);pt = pt-next;判断 first 集中是否有空：bool HaveEmpty(int nVn) if(nVn nVt)return true;pt = pt-next;return false;计算 follow 集：void Follow(int V)int i;struct pRNode *pt ;if(100 = V) /*当为初始符时*/AddF
7、ollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能处理：U-xVyVz 的情况*/pt = pt-next;if(NULL != pt)pt = pt-next; /*V 右侧的符号*/if(NULL = pt) /*当 V 后为空时 V-xV，将左符的 follow 集并入 V 的 follow 集中*/if(NULL = followPi.lCursor - 100 AddFollow(V, Pi.lCursor, 0);else /*不为空时 V-xVy,(注意：y-)，调用 AddFollow 加入 Vt或 y 的 first 集*/w
8、hile(NULL != pt /*y 的前缀中有空时，加如first 集*/pt = pt-next;if(NULL = pt) /*当后面的字符可以推出空时*/if(NULL = followPi.lCursor - 100 AddFollow(V, Pi.lCursor, 0);else /*发现不为空的字符时*/AddFollow(V, pt-rCursor, 1); 输出 first 或 follow 集：void ShowCollect(struct collectNode *collect)int i;struct collectNode *pt;i = 0;while(NULL
9、 != collecti)pt = collecti;printf(“n%c:t“, Vni);while(NULL != pt)if(-1 != pt-nVt)printf(“ %c“, Vtpt-nVt);elseprintf(“ #“);pt = pt-next;i+;printf(“n“);计算 first 和 follow：void FirstFollow()int i;i = 0;while(0 != Vni)if(NULL = firsti)First(100 + i);i+;i = 0;while(0 != Vni)if(NULL = followi)Follow(100 +
10、i);i+;构造预测分析表：void CreateAT()int i;struct pRNode *pt;struct collectNode *ct;for(i = 0; i rCursor) /*处理非终结符，当为终结符时，定含空为假跳出*/ct = firstpt-rCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;pt = pt-next;if(NULL = pt)/*NULL = pt，说明 xyz-,用到 follow 中的符号*/ct
11、= followPi.lCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;else /*当含有#号时*/analyseTablePi.lCursor - 100vtNum = i;ct = ct-next;elseif(100 rCursor) /*不含空的非终结符*/ct = firstpt-rCursor - 100;while(NULL != ct)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;else /*终结
12、符或者空*/if(-1 = pt-rCursor) /*-1 为空产生式时*/ct = followPi.lCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;else /*当含有#号时*/analyseTablePi.lCursor - 100vtNum = i;ct = ct-next;else /*为终结符*/analyseTablePi.lCursor - 100pt-rCursor = i;四程序运行结果1）语法分析的界面如下图所示：2）分别输入所有的非终结符以及终结符，确认后，输入各个表达式：3）得到 first 集与 follow 集，并得到预测分析表：五语法分析实验体会语法分析是编译过程的核心部分,它的主要功能是按照程序语言的语法规则,从由词法分析输出的源程序符号串中识别出各类语法成分,同时进行语法检查,为语义分析和代码生成作准备。从这次语法分析实验中我感到语法分析的过程很复杂,其中涉及到文法规则,自顶向下分析方法和许多编程的细节问题,有一处不正确,语法分析也不能成功。通过这次的语法分析实验,我对如何将文法规则转换为实际的程序代码有了进一步的认识,并且对语法分析过程有了更深入的认识。
