文档库

最新最全的文档下载
当前位置:文档库 > 编译原理预测分析法实验报告(C语言编写)

编译原理预测分析法实验报告(C语言编写)

编译原理

实验名称:预测分析法

姓名:

专业班级:计科

学号:

指导老师:

日期:2011年6月1日

目的要求

1.构造文法的语法分析程序,要求采用预测分析法对输入的字符串进行语法

分析。

2.加深对预测分析LL(1)分析法的理解和掌握。

实验内容

对文法G进行语法分析,文法G如下所示:

*0. S→a */

*1. S→^

*2. S→(T)

*3. T→SW *

*4. W→,SW

*5. W→ε;

并对任给的一个输入串进行语法分析检查。程序要求能对输入串进行预测分析,能判别程序是否符合已知的语法规则,如果不符合(编译出错),则输出错误信息。

程序输入/输出示例:

输入:一个以 # 结束的符号串:例如:(a,a)#

输出:

步数分析栈输入串所用规则

(1) #S (a,a))# 2

源程序:

//LL(1)预测分析控制程序

#include

#include

#include

char str[100]; //存储待分析的句子

const char T[ ] = "a^(),#"; //终结符,分析表的列符

const char NT[ ] = "STW"; //非终结符,分析表的行符

/*指向产生式右部符号串*/

const char *p[] = {

/*0. S→a */ "a",

/*1. S→^ */ "^",

/*2. S→(T) */ "(T)",

/*3. T→SW */ "SW",

/*4. W→,SW */ ",SW",

/*5. W→ε; */ ""

};

//设M[i][j]=x,通过p[M[i][j]]=p[x]获取右部符号串。

const int M[][6] = {

/* a ^ ( ) , # */

/*S*/ { 0, 1, 2, -1, -1, -1 },

/*T*/ { 3, 3, 3, -1, -1, -1 },

/*W*/ { -1, -1,-1, 5, 4, -1 }

};

void init()//输入待分析的句子

{

printf("请输入待分析的句子(以$结束):\n");

scanf("%s",str);

}

int lin(char c);//非终结符转换为行号

int col(char c);//终结转换为列号

bool isNT(char c);//isNT判断是否是非终结符

bool isT(char c);//isT判断是否是终结符。

void main(void)

{

int i,j=0;

int flag=1,flag2=0;

char A; //设置指示句子的当前字符

char stack[20]= {'#','S'}; //栈赋初值

int top = 1 ; //设置栈顶指针

char X = ' ' ; //存储栈顶字符

init();

A=str[0];

printf("\t步数\t分析栈\t输入串\t所用规则\n");//在屏幕上输出列表标题while ( 1 )

{

printf("\n\t(%d)\t",++j); //输出当前执行步数

for ( i = 0 ; i <= top ; i++ ) //输出当前栈的内容(出栈前)

{

printf("%c",stack[i]);

}

printf("\t");

for ( i = flag-1 ; str[i]!='$' ; i++ )

{

printf("%c",str[i]);

}

if(flag2==1)

{

printf("\t%d",M[ lin(X) ][col(A)]);

flag2=0;

}

//出栈

X = stack[top--] ;

if (X=='#')//是结束符

{

if (X==A)//是结束符

{

printf("\tAcc\n");

}

else printf("\tERROR\n");

break;

}

else if (isT(X))//是终结符

{

A=str[flag++];

}

else if (isNT(X))//是否是非终结符

{

flag2=1;

//逆序入栈

for( i = strlen( p[ M[ lin(X) ][col(A)] ] ) - 1; i >= 0; i--)

{

stack[++top] = *(p[M[lin(X)][col(A)]] + i ) ;

}

}

else

{

printf("Error in main()>%c\n",X);

exit(0);

}

}

}

int lin(char c)

{

for(int i = 0; i < (int)strlen(NT); i ++ )

{

if (c == NT[i])

{

return i ;

}

}

printf("Error in lin()>%c\n",c);

exit(0) ;

}

int col(char c)

{

for (int i=0; i<(int)strlen(T); i ++ )

{

if (c == T[i]) return i;

}

printf("Error in col()>%c\n",c);

exit(0);

}

bool isNT(char c) //是否是非终结符

{

for (int i = 0; i < (int)strlen(NT); i ++ )

{

if (c==NT[i])

return true;

}

return false;

}

bool isT(char c) //是否是终结符(不包括'#'){

for (int i = 0; i < (int)strlen(T) - 1; i ++ )

{

if (c == T[i])

{

return true;

}

}

return false;

}

程序运行截图

当输入为(a,a)#$ 时

编译原理预测分析法实验报告(C语言编写)

当输入为(a,a)))#$ 时

编译原理预测分析法实验报告(C语言编写)

经过分析,实验运行的结果与期望的结果相同,故知程序正确。

实验总结

这次的预测分析程序实验同样要求文法必须是LL(1)文法,相对来说比上次的递归下降分析程序难些。我是参照了别人的程序,然后经过自己的理解和修改,把课本上的例4.10中文法作为例子设计出了预测分析程序。在实验当中,由于用到了类似栈的处理,出现了不少的错误。不过经过不断的调试和对其基本原理的理解,总算基本解决了,并且使输出显示的比较详细,显示了对输入块的分析过程。

经过此实验使我更加深刻的理解预测分析程序的基本原理和过程。从程序中可以看出,该程序由一张预测分析表,一个先进后出分析栈和一个总控程序三部分组成,实现起来较为繁琐,但分析效率较高。