编译原理LL(1)语法分析实验报告

学号 20102798 专业 软件工程 姓名 薛建东 实验日期2013.04.08 教师签字 成绩

实 验 报 告

【实验名称】 LL（1）语法分析

【实验目的】

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。

【实验内容】

 根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。  构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。  分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL

（1）分析表，对输入符号串自上而下的分析过程。

【设计思想】

（1）、LL（1）文法的定义

LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A,A，都要满足下面条件：SELECT(A)∩SELECT(A)=

（2）、预测分析表构造

LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：

M: VN×VTP∪{Error}

M(A, t) = Aα，当tselect(Aα) ，否则 M(A, t) = Error

其中P表示所有产生式的集合。 （3）、语法分析程序构造

LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A 的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。

LL(1)分析过程主要包括以下四个动作：

替换：当XVN时选相应产生式的右部去替换X。此时X出栈，逆序入栈。

匹配：当XVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。

接受：当格局为（#，空#）时报告分析成功。

报错：出错后，停止分析。并给出相应的错误提示信息。

【实验要求】

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。

【流程图】

1. 总体思路分析及流程图

给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集，然后求出Select集，通过Select集判断是否是LL1文法，如果是的话，构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。

功能模块分解图

（1）主程序流程图

（2）核心算法流程图

1.计算非终结符的First集的算法及流程： First集合的构造算法：

（1）若X∈VT，则First（X）={X}。

（2）若X∈VN，且有产生式X→a……，则把a加入到First (X)中；若X→ε也是一条产生式，则把ε也加到First (X)中。

（3）若X→Y……是一个产生式且Y∈VN，则把First (Y)中的所有非ε-元素都加到First (X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，First (Yj)都含有ε（即Y1…Yi-1* ε），则把First (Yj)中的所有非ε-元素都加到First (X)中；特别是，若所有的First (Yj)均含有ε，j=1,2,…，k，则把ε加到First (X)中。

连续使用上面的规则，直至每个集合First不再增大为止。

2.计算非终结符的Follow集： Follow集合的具体构造算法如下：

（1）对于文法的开始符号S，置#于Follow(S)中；

（2）若A→αBβ是一个产生式，则把First(β)|{ε}加至Follow(B)中；

（3）若A→αB是一个产生式，或A→αBβ是一个产生式而β ε（即ε∈First(β)），则把Follow(A)加至Follow(B)中。

连续使用上面的规则，直至每个集合Follow不再增大为止。

3.预测分析控制程序的算法流程

【源代码】

#include #include #include

#include

char A[20];/*分析栈*/ char B[20];/*剩余串*/

char v1[20]={'i','+','*','(',')','#'};/*终结符 */ char v2[20]={'E','G','T','S','F'};/*非终结符 */

int j=0,b=0,top=0,l;/*L为输入串长度 */

typedef struct type/*产生式类型定义 */ {

char origin;/*大写字符 */ char array[5];/*产生式右边字符 */

int length;/*字符个数 */ }type;

type e,t,g,g1,s,s1,f,f1;/*结构体变量 */ type C[10][10];/*预测分析表 */

void print()/*输出分析栈 */ {

int a;/*指针*/

for(a=0;a

void print1()/*输出剩余串*/ {

int j;

for(j=0;j

}/*print1*/

void main() {

int m,n,k=0,flag=0,finish=0; char ch,x;

type cha;/*用来接受C[m][n]*/ /*把文法产生式赋值结构体*/ e.origin='E';

strcpy(e.array,"TG");

e.length=2;

t.origin='T';

strcpy(t.array,"FS"); t.length=2; g.origin='G';

strcpy(g.array,"+TG"); g.length=3; g1.origin='G'; g1.array[0]='^'; g1.length=1;

strcpy(s.array,"*FS"); s.length=3; s1.origin='S'; s1.array[0]='^'; s1.length=1;

f.origin='F';

strcpy(f.array,"(E)"); f.length=3; f1.origin='F'; f1.array[0]='i'; f1.length=1;

for(m=0;m

s.origin='S';

C[m][n].origin='N';/*全部赋为空*/ /*填充分析表*/

C[0][0]=e;C[0][3]=e;

C[1][1]=g;C[1][4]=g1;C[1][5]=g1; C[2][0]=t;C[2][3]=t;

C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1; C[4][0]=f1;C[4][3]=f;

printf("提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,\n");

printf("请输入要分析的字符串:"); do/*读入分析串*/ {

scanf("%c",&ch);

if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')) { printf("输入串中有非法字符\n"); exit(1); }

B[j]=ch;

j++;

}while(ch!='#'); l=j;/*分析串长度*/

ch=B[0];/*当前分析字符*/

A[top]='#'; A[++top]='E';/*'#','E'进栈*/

printf("步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n"); do

{ x=A[top--];/*x为当前栈顶字符*/ printf("%d",k++); printf("\t\t");

for(j=0;j

if(x==v1[j]) {

flag=1; break;

}

if(flag==1)/*如果是终结符*/ {

if(x=='#') {

finish=1;/*结束标记*/

printf("acc!\n");/*接受 */ getchar(); getchar();

exit(1); }/*if*/ if(x==ch) { print();

print1();

printf("%c匹配\n",ch); ch=B[++b];/*下一个输入字符*/ flag=0;/*恢复标记*/

}/*if*/

else/*出错处理*/ {

print(); print1();

printf("%c出错\n",ch);/*输出出错终结符*/ exit(1);

}/*else*/ }/*if*/

else/*非终结符处理*/

{ for(j=0;j",cha.origin);/*输出产生式*/ for(j=0;j

printf("%c",cha.array[j]);

printf("\n"); for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/ A[++top]=cha.array[j]; if(A[top]=='^')/*为空则不进栈*/ top--; }/*if*/ else/*出错处理*/ { print(); print1(); printf("%c出错\n",x);/*输出出错非终结符*/ exit(1); }/*else*/

}/*else*/

}while(finish==0);

}/*main*/

【运行结果】

10

11