编译原理实验LL1分析

1、 实验三 语法分析-LL（1）分析器目录一. 实验的目的与思路2（1） 目的2（2） 思路2二. 基本的功能3三总体设计4四详细设计5五.源程序清单6六.源代码6 一. 实验的目的与思路（1） 目的1. 用程序的方法实现语法分析的LL（1）方法。（2） 思路本程序是采用的LL（1）方法进行的语法分析，而LL（1）的分析方法是属于自上而下的方法。自上而下分析的基本思想是：对任意输入串，试图用一切可能的方法，从文法开始符号（根结点）出发，自上而下为输入串建立一棵语法树。从推导的角度看，它是从文法的开始符号出发，反复使用各种产生式，寻找与输入串匹配的推导。在输入之前必须要进行该文法是不是LL（1）文

2、法的判断，然后再构造相应的LL（1）分析表来用预测分析方法进行语法分析，依据下面的文法及分析表来设计程序实现预测分析的分析过程。1. 文法GE： E -> E+T|T T -> T*F|F F -> (E) | i2. 通过观察可知道该文法是一个左递归文法，要进行语法分析就必须消除左递归才能继续判断它是不是LL（1）文法，然后才能用预测分析方法进行语法分析。3. 消除左递归：E ->TMM -> +TM|uT -> FQQ -> *FQ|uF -> (E) | i4. 在进行LL（1）文法的判断：（1.） 各非终结符的FIRST集如下： FIRS

3、T（E）= FIRST（TM）= （ ，i FIRST（M）= + FIRST（T）= （ ，i FIRST（Q）= * FIRST（F）= （ ，i （2.）各非终结符的FOLLOW集如下： FOLLOW（E）= ） ，# FOLLOW（M）= ） ，# FOLLOW（T）= + ， ） ，# FOLLOW（Q）= + ， ） ，# FOLLOW（F）= * ，+ ， ） ，# （3.）各产生式的SELECT集如下： SELECT（EàTM）= ( ,i SELECT（Mà+TM）=+ SELECT（Màu）= , # SELECT（TàFQ）= (

4、,i SELECT（Qà*FQ）= * SELECT（Qàu）= +， ), # SELECT（Fà(E)）= ( )SELECT（Fài）= i 因为： SELECT（Mà+TM） SELECT（Màu）= SELECT（Qà*FQ）SELECT（Qàu）= SELECT（Fà(E)） SELECT（Fài）= 因此可以判断该文法是一个LL（1）文法可以构造预测分析表。 5. 根据可选集构造预测分析表如下：二. 基本的功能 下面主要采用了LL（1）分析方法来进行语法分析，先通过判断该文法是不是

5、LL（1）文法，如果不是先将其改写成LL（1）文法，再将LL（1）文法改造成等价形式-LL（1）分析表，通过分析表来进行语法分析，本程序的主要功能是对一个文法句子的生成过程进行分析。三总体设计 LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析其功能模型图如下：LL（1）语法分析分析表句子语法分析句子LL（1）语法分析功能模型图 本程序是采用预测的分析方法，因此预测分析方法的基本算法如下：(1) 判断该文法是不是LL（1）文法，如果该文法不是LL（1）文法，则修改该文法继续判断该文法是不是LL（1）文法，如果是则进行第

6、二步，否则不运行。（2） 构造预测分析表：1对文法G的每个产生式A->a执行第二步和第三步；2对每个终结符aFIRST(a),把A->a加至LA,a中；3若FIRST(a),则对任意bFOLLOW(A)把A->a 加至LA,b中；4把所有无定义的LA,a标上“出错标志”；上述算法可应用于任何文法G 以构造它的预测分析表L。但是对于某些文法，有些LA,a可能持有若干个产生式，或者说有些LA,a可能是多重定义的。如果G是左递归或是二义的，那么L至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表L。本题是在将文法消除左递归和提取左因子等工作之后的基

7、础上进行的，也就是针对LL（1）文法来构造预测分析表，从而达到预测分析表不含多重定义入口 的效果。本程序的设计只是一个语法分析程序，预测表的部分将被固定在一个二维数。组中，然后进行预测分析过程。（3） 对一个输入串的预测分析过程1. 将开始符和#进栈输入当前符，进行查表比较，如果不匹配，就将所用产生式进栈然后再进行查表。2. 进行查表后如果匹配则将所用的产生式出栈处理3. 如果所用到的产生式是u（表示空符）那么就将所用到的 产生式出栈处理。4. 如果有#与#匹配则表示成功接收字符串，否则就不能成功接收，不能推导 四详细设计（1）算法的模块图： main（）函数模块 （2）主程序的流程图 程序流

8、程图五.测试数据（1）i + i * i # （2）( i * i ) + i # （3）E * i + i #六. 源代码#include "stdafx.h"#include <stdio.h>#include <iostream>#include <string.h>using namespace std; #include <stdlib.h>#define MAX 20 char analyz_sentenceMAX="" char sMAX=""char stackMAX=&

9、quot;" char top; char *tp; char identyMAX="" int n=0; char Vn_array = "EMTQF"char Vt_array = "i+*()#"char Vp_array510="E->TM","M->+TM|u","T->FQ","Q->*FQ|u","F->(E)|i"char *LL1_array6 = "TM",

10、 " ", " ", "TM", " ", " "," ", "+TM", " ", " ", "u", "u","FQ", " ", " ", "FQ", " ", " "," ", "u", "*FQ&qu

11、ot;, " ", "u", "u","i", " ", " ", "(E)", " ", " "void put_setence(); void init_stack(); int ll1_analyzing(); void ll1array_push(char); int is_Vt(); int is_ll1array(char); int Vn_idx(); int Vt_idx(char); void po

12、p(); void push(char); void reve(); int printerror(); void main() int a,b,k,h; cout<<"*请输入一个句子*"<<endl;put_setence();init_stack();ll1_analyzing(); void put_setence() char ch;int i=0;while(ch=cin.get() != '#') analyz_sentencei = ch;i+;analyz_sentencei = '#' void i

13、nit_stack() stack0 = '#' stack1 = Vn_array0; cout << stack1 << "=>" int ll1_analyzing() top = stack1; int error; for (int i=0;i<=strlen(analyz_sentence);i+) int tet; tet = is_Vt(); if (1 = tet) if (top = analyz_sentencei) identyn+ = top; pop(); continue; else prin

14、terror(); break; else if ('#' = top) for (int p=0;p<strlen(analyz_sentence)-1;p+) printf("%c", analyz_sentencep); break; else do int judge=0; judge = is_ll1array(analyz_sentencei); if (judge = 1) if (1 = is_Vt() error=printerror(); break; ll1array_push(analyz_sentencei); else er

15、ror = printerror(); break; while (top != analyz_sentencei); if (error = 1) break; identyn+ = top; if (top != '#') pop(); if(error=1)return 0; else cout << "这是一句合法的句子！" <<"分析成功"<<endl; return 1; void ll1array_push(char cutchar) int i,j; i=Vn_idx(); j=Vt_i

16、dx(cutchar); tp=LL1_arrayij; reve(); pop(); int k; for(k=0;k<strlen(tp);k+) push(tpk); printf("%s", identy); for (int m=strlen(stack)-1;m>0;m-) cout << stackm ; cout << "=>" if (top = 'u') pop(); void pop() int tom; tom = strlen(stack)-1; stacktom = &

17、#39;0' top = stacktom-1; void push(char elt) int tom; tom = strlen(stack); stacktom = elt; top = elt; int is_Vt() int i; int hot=0; for (i=0;i<strlen(Vt_array);i+) if(top = Vt_arrayi) hot = 1; if (top = '#') hot = 0; if (hot = 1) return 1; else return -1; int is_ll1array(char cutchar) int i,j; i=Vn_idx(); j=Vt_idx(cutchar); if (LL1_arrayij = " ") return -1; else return 1; int Vn_idx() for(int i=0;i<strlen(Vn_array);i+) if (top = Vn_arrayi) return i; return -1; int Vt_idx(char idx_array) for(int i=0;i<strlen(Vt_array);i+) if (idx_array = Vt_arrayi) return i; retu