编译原理实验LL1分析.doc

实验三 语法分析-LL（1）分析器目录一. 实验的目的与思路2（1） 目的2（2） 思路2二. 基本的功能3三总体设计4四详细设计5五.源程序清单6六.源代码6 一. 实验的目的与思路（1） 目的1. 用程序的方法实现语法分析的LL（1）方法。（2） 思路本程序是采用的LL（1）方法进行的语法分析，而LL（1）的分析方法是属于自上而下的方法。自上而下分析的基本思想是：对任意输入串，试图用一切可能的方法，从文法开始符号（根结点）出发，自上而下为输入串建立一棵语法树。从推导的角度看，它是从文法的开始符号出发，反复使用各种产生式，寻找与输入串匹配的推导。在输入之前必须要进行该文法是不是LL（1）文法的判断，然后再构造相应的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集如下： FIRST（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（ETM）= ( ,i SELECT（M+TM）=+ SELECT（Mu）= , # SELECT（TFQ）= ( ,i SELECT（Q*FQ）= * SELECT（Qu）= +， ), # SELECT（F(E)）= ( )SELECT（Fi）= i 因为： SELECT（M+TM） SELECT（Mu）= SELECT（Q*FQ）SELECT（Qu）= SELECT（F(E)） SELECT（Fi）= 因此可以判断该文法是一个LL（1）文法可以构造预测分析表。 5. 根据可选集构造预测分析表如下：二. 基本的功能 下面主要采用了LL（1）分析方法来进行语法分析，先通过判断该文法是不是LL（1）文法，如果不是先将其改写成LL（1）文法，再将LL（1）文法改造成等价形式-LL（1）分析表，通过分析表来进行语法分析，本程序的主要功能是对一个文法句子的生成过程进行分析。三总体设计 LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析其功能模型图如下：LL（1）语法分析分析表句子语法分析句子LL（1）语法分析功能模型图 本程序是采用预测的分析方法，因此预测分析方法的基本算法如下：(1) 判断该文法是不是LL（1）文法，如果该文法不是LL（1）文法，则修改该文法继续判断该文法是不是LL（1）文法，如果是则进行第二步，否则不运行。（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。本题是在将文法消除左递归和提取左因子等工作之后的基础上进行的，也就是针对LL（1）文法来构造预测分析表，从而达到预测分析表不含多重定义入口 的效果。本程序的设计只是一个语法分析程序，预测表的部分将被固定在一个二维数。组中，然后进行预测分析过程。（3） 对一个输入串的预测分析过程1. 将开始符和#进栈输入当前符，进行查表比较，如果不匹配，就将所用产生式进栈然后再进行查表。2. 进行查表后如果匹配则将所用的产生式出栈处理3. 如果所用到的产生式是u（表示空符）那么就将所用到的 产生式出栈处理。4. 如果有#与#匹配则表示成功接收字符串，否则就不能成功接收，不能推导 四详细设计（1）算法的模块图： main（）函数模块 （2）主程序的流程图 程序流程图五.测试数据（1）i + i * i # （2）( i * i ) + i # （3）E * i + i #六. 源代码#include stdafx.h#include #include #include using namespace std; #include #define MAX 20 char analyz_sentenceMAX=; char sMAX=;char stackMAX=; 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, , , TM, , , , +TM, , , u, u,FQ, , , FQ, , , , u, *FQ, , 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 pop(); 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 init_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 printerror(); break; else if (# = top) for (int p=0;pstrlen(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 error = 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_idx(cutchar); tp=LL1_arrayij; reve(); pop(); int k; for(k=0;k0;m-) cout stackm ; cout ; if (top = u) pop(); void pop() int tom; tom = strlen(stack)-1; stacktom = 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;istrlen(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;istrlen(Vn_array);i+) if (top = Vn_arrayi) return i; return -1; int Vt_idx(char idx_array) for(int i=0;istrlen(Vt_array);i+) if (idx_array = Vt_arrayi) return i; return -1; void reve() strcpy(s, tp); int i,j; char t; i=0; while (si != 0) +i; -i; if (si = n) -i; j=0; while (ji) t = sj; sj = si; si = t; -i; +j; tp=s; int printerror() cout 这不是一句合法的句子，无法推导！ 分析不成功endl; return 1;