编译原理课程设计LL1文法

1、LL(1) 文法分析及程序设计1. 设计目的通过设计、编制、调试 LL(1) 语法分析程序，加深对 LL(1) 语法分析原理的 理解。2. 设计要求( 1)写出符合 LL(1) 分析方法要求的文法，给出分析的算法思想、步骤、程序 结构以及最终完成语法分析程序设计。( 2)编制完成分析程序后， 选取几个例子， 上机测试并通过所设计的分析程序。3. 设计方案用 LL(1) 分析法判别给定文法是否为 LL(1) 文法，提供其分析过程与结果， 最终根据结果设计算法分析程序，对输入的符号串进行分析。4. 设计内容4.1 设计基本思想设计一个 LL(1) 文法分析器，构造出预测分析表，通过预测分析表，判别

2、用 户输入的字符串是否符合 LL(1) 文法。并给出分析过程与结果。4.2 LL(1) 文法的基本原理与算法一个上下无关的文法是 LL(1) 文法的充要条件时， 对每个非终结符 A 的两个 不同产生式，A-> a ,A-> B满足SELECT(A->a)G SELECT(A-> B) = ©,其中 a和 B不同时推出 E。如果 某个文法满足上述条件，称该文法为 LL(1) 文法。 LL(1) 分析法是一种采用确定 的自顶向下的语法分析技术, 其含义是： 第一个 L 表明自顶向下分析是从左向右 扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个

3、符 号便可以决定如何推导,即便选择哪个产生式规则进行推导。4.3 LL判别分析步骤(1) 将数组 X 中对应的每一个非终结符的标记为“未定” 。(2) 扫描文法中的产生式。1. 删除所有右部含有终结符的产生式。 若使得以某一非终结符为左部的所有 产生式都被删除，则将数组中对应的非终结符的标记值改为“否” ，说明该终结 符不能推出E。2. 若某一非终结符的某一个产生式右部为E,则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。(3) 扫描产生式右部的每一个符号。1. 若所扫描到的非终结符号在数组中对应的标志是“是” ,则删去该非终结 符,若使得产生式右部为空, 则对

4、产生式右部的非终结符在数组中对应的标志改 为“是”,并删除该非终结符为左部的所有的产生式。2. 若所扫描到的非终结符号在数组中对应的标志是“是” ,则删除该产生式。 若这使得产生式左部非终结符的有关产生式都被删除, 则把在数组中该非终结符 对应的标志改为“否” 。(4) 重复( 3),直到扫描完一遍文法的产生式,数组中的非终结符对应的特征 再没有改变为止。1) A->a a 则 a first(A)2) A->Ba 则 first(B) first(A)3) A->A 则 A first(A)1) A-> a Bap 则 a follow (B)2) A-> a

5、BCp 贝U first(C) follow (B)3) A->a B 则 follow( A) follow ( B) 3)由产生式形成( 1)(2)(3)A-> a BDap, D->a，则 a follow (B), a follow (D)4.4 数据结构数组A实现分析栈，数组B存储剩余分析串；一维数组 V1存放文法终结符， 一维数组V2存放文法非终结符。将产生式类型定义为结构体变量。4.5 算法描述1. 首先将#压入堆栈中，将开始符号S也压入堆栈中，读取第一个输入符号到a。循环执行24:2. 栈顶符号弹出放入X中，如果X为终结符号：当X=a! =#时，表明成功匹 配

6、a符号,然后读取下一个符号到a ,否则出错；当X=a=#时，分析结束,接受句 子 , 跳出循环 .3. 如果X!=a,进行出错处理.4. 如果X为非终结符号,则查分析表M:如果MX,a为空,进行出错处理；如果 MX,a=X1 X2 X3.Xn,则将右部 Xn.X2 X1 反序压入堆栈中 .4.6 对给定文法进行 LL(1) 分析的过程 给定文法：E->TGG->+TGFT->FSS->*FSFF->i|(E) 对上述文法进行分析判断：FIRST(E)= FIRST(T)= FIRST(F)=(,iFIRST(G)=+,AFIRST(T) =(,iFIRST(S)

7、=*,AFIRST(F) =(,iFOLLO (WE) =),#FOLLO (WG) = FOLLOW( E) =),#FOLLOWT) = FIRST (G)U FOLLOWE) =+,),#FOLLO(WS) = FOLLOW(T) = +,),#FOLLO(WF) = FIRST(S)U FOLLO(WE)U FOLLO(WT) =*,+,),#SELEC(T E->TG) =(,iSELEC(T G->+TG) =+SELEC(T G->A) =#,)SELEC(T T->FS) =(,iSELEC(T S->*FS) =*SELEC(T S->A)

8、 =+,#SELEC(T F->(E) ) =(SELEC(T F->i ) =i由以上步骤可知，该文法是LL(1)文法。对其建立预测分析表。对于每个终结符或#，用a表示。若a SELECT A-> a),则把A-> a放入MA,a中。把所有无定义的 MA,a标上出错标记。预测分析表如下:i+*()#E->TG->TGG->+TG->A->AT->FS->FSS->A->*FS->A->AF->i->(E)4.7程序函数流程图输出分析栈：输出剩余串： 主函数:4.8程序测试结果1)输入i+i*

9、i#得到分析结果如下 2)如果不适合LL(1)文法，则显示输入错误。例如输入i+i*i# ，分析结果如下:4.9源代码#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>分析栈*/剩余串*/终结符*/非终结符*/为输入串长度*/产生式类型定义*/大写字符*/产生式右边字符*/字符个数*/结构体变量*/预测分析表*/#in clude<dos.h>char A20;/*char B20;/*char v120='i','+','*',

10、9;(',')','-',7','#' /* char v220='E','G',T,'S','F'/*int j=0,b=0,top=0,l;/*ltypedef struct type/*char origi n;/*char array5;/*int len gth;/*type;type e,t,g,g1,s,s1,f,f1;/*type C1010;/*void print() /*int a;for(a=0;a<=top+1;a+) printf(&

11、quot;%c",Aa);printf("tt");void print1() /*int j;for(j=0;j<b;j+) /* printf(" ");for(j=b;j<=l;j+)printf("%c",Bj);printf("ttt");void main()int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/*e.origin='E'/*strcpy(e.array,"TG");e.length=2;

12、t.origin='T'strcpy(t.array,"FS");t.length=2;g.origin='G' strcpy(g.array,"+TG");g.length=3;g1.origin='G'g1.array0='人：g1.length=1;s.origin='S'strcpy(s.array,"*FS");s.length=3;s1.origin='S's1.array0='人：s1.length=1;f.origin=&#

13、39;F'strcpy(f.array,"(E)");f.length=3;f1.origin='F'f1.array0='i'输出分析栈 */输出剩余串 */输出对齐符 */用来接受 Cmn*/ 把文法产生式赋值结构体 */初始化分析表 */全部赋为空 */填充分析表 */读入分析串 */f1.length=1;for(m=0;m<=4;m+) /* for(n=0;n<=7;n+)Cmn.origin='N' /*C00=e;C03=e; /*C11=g;C14=g1;C17=g1;C20=t;C23=

14、t;C31=s1;C32=s;C34=C35=C37=s1;C40=f1;C43=f;printf(" 请输入要分析的字符串 :"); do /* scanf("%c",&ch); if (ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')&&(ch!='-')&

15、amp;&(ch!='/') printf(" 输入串中有非法字符 n");exit(1);Bj=ch;j+;while(ch!='#');l=j; /*分析串长度 */ch=B0; /*当前分析字符 */Atop='#' A+top='E'/*'#','E'进栈 */printf(" 步骤 tt 分析栈 tt剩余字符 tt所用产生式 n");dox=Atop-;/*x为当前栈顶字符 */printf("%d",k+); print

16、f("tt");for(j=0;j<=7;j+)/*判断是否为终结符 */if(x=v1j)flag=1;break;if(flag=1)if(x='#')finish=1;/*如果是终结符 */*结束标记 */printf(" 接受 !n");getchar();下一个输入字符 */恢复标记 */出错处理 */输出出错终结符 */非终结符处理 */判断是否为空 */输出产生式 */产生式逆序入栈 */getchar();exit(1);if(x=ch)print();print1(); printf("%c 匹配 n&q

17、uot;,ch); ch=B+b; /* flag=0; /*else /*print();print1();printf("%c 出错 n",ch); /* exit(1);else /*for(j=0;j<=4;j+)if(x=v2j)m=j;break;for(j=0;j<=7;j+) if(ch=v1j) n=j; break; cha=Cmn; if(cha.origin!='N') /*print();print1();printf("%c->",cha.origin); /* for(j=0;j<ch

18、a.length;j+)printf("%c",cha.arrayj); printf("n");for(j=(cha.length-1);j >=0;j-)/*A+top=cha.arrayj;if(Atop='A')/*为空则不进栈 */top-;else /* 出错处理 */print();print1();printf("%c出错 n",x);/*输出出错非终结符 */exit(1);while(finish=0);5. 总结通过这次的课程设计， 我比原来更加了解了 LL(1) 文法的分析过程及实现方 法，学会设计、编制、调试语法及语义分析程序，加深了对语法及语义分析原理 的理解。在课程设计前，我想过很多种实现 LL(1) 文法的办法