自上而下预测分析控制程序实验报告

一，实验题目

自上而下预测分析控制程序

二、实验目的

根据文法规则进行语法分析，如字串是句子，写出文法的最左推导

三、实验内容

（1）源代码

#include <fstream.h>

#include <iostream.h>

#include <stdlib.h>

#include <string.h>

struct code_val{

char code;char val[20];

};

const char *p[ ]={ //指向产生式右部符号串 "TD","+TD","","FS","*FS","","(E)","i","x","y"

};

//0. E→TD D代表E'

//1. D→+TD

//2. D→ε

//3. T→FS S代表T'

//4. S→*FS

//5. S→ε

//6. F→(E)

//7. F→i

//8. F→x

//9. F→y

const char T[ ]="+*()ixy#"; //分析表的列符

const char NT[ ]="EDTSF"; //分析表的行符，行符为EE'TT'F。 const int M[ ][8]={

/*在预测分析表M中存放指针数组p的下标x，设M[i][j]=x，通过p[M[i][j]]=p[x]获取右部符号串。*/

{-1,-1,0,-1,0,0,0,-1},//p[0]指向第0个产生式右部符号串"TD"，-1表示出错。 {1,-1,-1,2,-1,-1,-1,2},

{-1,-1,3,-1,3,3,3,-1},

{5,4,-1,5,-1,-1,-1,5},

{-1,-1,6,-1,7,8,9,-1}

};

//函数原型

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

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

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

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

{

int i,j=0;

ifstream cinf("lex_r.txt",ios::in); //从文件lex_r.txt输入数据

ofstream cout("par_r.txt",ios::out); //结果输出至文件par_r.txt（cout重定义） struct code_val t; //定义结构变量，存放单词二元式。 cinf>>t.code>>t.val; //读一个单词的二元式

char stack[20]={'#','E'};int top=1; //栈赋初值

char X=' '; //用于显示，并非必要。

cout<<"step"<<'\t'<<"stack"<<'\t'<<"X"<<'\t'<<"t.code"<<endl; //用于显示，并非必要。

cout<<j<<')'; //用于显示，并非必要。

while(1){

cout<<'\t'; //用于显示，并非必要。 for(i=0;i<=top;i++) cout<<stack[i]; //用于显示，并非必要。

cout<<'\t'<<' '<<'\t'<<t.code<<endl;//用于显示，并非必要。

X=stack[top--]; //出栈

cout<<++j<<')'<<'\t'; //用于显示，并非必要。 for(i=0;i<=top;i++) cout<<stack[i]; //用于显示，并非必要。 cout<<'\t'<<X<<'\t'<<t.code<<endl; //用于显示，并非必要。 if(X=='#'){

if(X==t.code){

cout<<"\tAcc"<<endl;break; //跳出循环

}

else{

cout<<"Err in #>"<<X<<'\t'<<t.code<<endl;exit(0);

}

}//end of if(X=='#')

if(isT(X)){ //是否是终结符

if (X== t.code)

cinf>>t.code>>t.val; //读下一单词二元式

else{

cout<<"Err in T>"<<X<<'\t'<<t.code<<endl;exit(0);

}

continue;

}//end of if(isT(X))

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

if(M[lin(X)][col(t.code)]==-1){

cout<<"Err in NT>"<<X<<'\t'<<t.code<<endl;exit(0);

}

else{

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

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

cout<<X<<"->"<<p[M[lin(X)][col(t.code)]]<<endl;

}

continue;

}//end of if(isNT(X))

cout<<"Err in main( )>"<<X<<endl;exit(0);

}//end of while

}//end of main

int lin(char c) //将EDTSF分别转换为01234 {

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

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

cout<<"Err in lin( ) >"<<c<<endl;exit(0);

}

int col(char c) //将+* ()ixy#分别转换为01234567 {

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

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

cout<<"Err in col( )>"<<c<<endl;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;

}

（2）从文件lex_r.txt输入数据

i a + nul i b # nul

（3）结果输出至文件par_r.txt

step stack X t.code

0) #E i

1) # E i

E->TD

#DT i

2) #D T i

T->FS

#DSF i

3) #DS F i

F->i

#DSi i

4) #DS i i

#DS +

5) #D S +

S->

#D +

6) # D +

D->+TD

#DT+ +

7) #DT + +

#DT i

8) #D T i

T->FS

#DSF i

9) #DS F i

F->i

#DSi i

10) #DS i i

#DS #

11) #D S #

S->

#D #

12) # D #

D->

# #

13) # #

Acc

四、实验心得：

通过此次的实验，让我了解到如何设计、编制并调试语法分析程序，加深对语法分析原理的理解；熟悉了构造语法分析程序的手工方式的相关原理，使用c语言直接编写此法分析程序。而且让我重新熟悉了c语言的各种操作。

第二篇：预测分析程序实验报告

题目：预测分析法

一、实验目的

1、通过实验要学会用消除左递归和消除回溯的方法来使文法满足进行确定自顶向下分析的条件；

2、学会用C/C++高级程序设计语言编写一个LL（1）分析法程序

二、实验内容及要求

LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：

（１）若X = a =‘#’，则宣布分析成功，停止分析过程。

（２）若X = a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。

（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。

1、给定文法

S -> a | b | (T)

T -> SH | d

H -> ,SH | ε

2、该文法对应的预测分析表

3、编写预测分析程序对句子进行分析

三、试验程序设计说明

1、相关函数说明

分析栈可以采取许多的存储方法来设计，在这里采用的顺序栈。根据预测分析原理，LL(1)分析程序的实现关键在于分析栈和分析表是采用何种数据结构来实现。分析表是一个矩阵，当我们要调用分析表来分析时，就根据栈顶的非终结符和当前输入的终结符来决定执行哪种过程。具体设计思想如下：

printStack（）输出分析栈内内容；printinputString（）输出用户输入的字符串；Pop（）弹出栈顶元素；Push（）向栈内添加一个元素；Search（）查找非终结符集合VT中是否存在输入的非终结符；yuCeFenXi（）进行输入串的预测分析的主功能函数；M(char A, char a)查看预测分析表M[A,a]中是否存在相应产生式。

2、程序流程图

四、实验结果

语法分析的任务就是识别词法分析程序输出的单词序列是否为给定方法的正确句子。现在我们若从键盘上输入的是有正确的句子，例如：(a,a)#, 显示“success”。运行结果如下：

五、实验小结

本次实验完成了语法分析-预测分析法的实现过程，通过本次实验巩固了以前所学过的知识，对语法分析有了更深入的了解，掌握了预测分析法的原理及其实现过程。

附：#include"stdio.h"

#include"string.h"

char inputString[10];

char stack[10];

int base=0,top=1;

char VT[6]={'a','b','(',')',',','d'}; /*用来存放6个终结符*/

char chanShengShi[10]; /*用来存放预测分析表M[A,a]中的一条产生式*/

int firstCharIntex=0; /*firstCharIntex用来存放用户输入串的第一个元素的下标*/

int M(char A, char a);

void init()

{

int i;

for(i=0;i<10;i++)

{

inputString[i]=NULL; /*初始化数组*/

stack[i]=NULL; /*初始化栈 */

chanShengShi[i]=NULL; /*初始化数组*/

}

printf("\t\t1>文法G[S]:"); /*输出文法做为提示*/

printf("\n\t\t\tS -> a | b | (T)\n");

printf("\t\t\tT -> SH | d \n");

printf("\t\t\tH -> ,SH | ε \n");

printf("\t\t2>该文法对应的预测分析表:\n");

printf("\t\t | a | b | ( | ) | , | # |\n");

printf("\t\tS | S->a | S->b | S->(T)| | | |\n");

printf("\t\tT | T->SH | T->SH | T->SH | | | |\n");

printf("\t\tH | | | | H->ε| H->,SH | |\n");

}

void printStack() /*输出栈内内容*/

{

for(int i=1;i<top;i++)

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

}

void printinputString() /*输出用户输入的字符串*/

{

int temp=firstCharIntex;

printf("\t\t"); /*该句控制输出格式*/

do{

printf("%c",inputString[temp]);

temp++;

}while(inputString[temp-1]!='#');

printf(" \n");

}

char Pop() /*弹出栈顶元素，用topChar返回*/

{

char topChar;

topChar=stack[--top];

return

topChar;

}

void Push(char ch)

{

if( top>9 )

printf(" error : stack overflow \n");

else

{

stack[top]=ch; /*给栈顶空间赋值*/

top++;

}

int search(char temp)

{

int i,flag=0;

for(i=0;i<6;i++)

{

if( temp==VT[i] ) /*终结符集合中存在temp*/

{

flag=1;

break;

}

if(flag==1)

return 1; /*flag==1说明已找到等于temp的元素*/

else

return 0;

}

int yuCeFenXi()

{

char X; /*X变量存储每次弹出的栈顶元素*/

char a; /*a变量存储用户输入串的第一个元素*/

int i;

int counter=1; /*该变量记录语法分析的步骤数*/

init(); /*初始化数组*/

printf("\t\t请输入待分析字符串以#结束: ");

scanf("%s",inputString);

printf("\t\t3>对输入串 (a,a)# 的分析过程\n");

Push('#');

Push('S');

printf("\t\t 步骤\t\t分析栈\t\t输入串\n"); /*输出结果提示语句*/

while(1) /*while循环为语法分析主功能语句块*/

{

printf("\t\t%4d",counter); /*输出分析步骤数*/

printf("\t\t"); /*输出格式控制语句*/

printStack();

X=Pop();

printinputString();

if( search(X)==0 )

{

if(X == '#')

{

printf("\t\t\tsuccess ... \n");

return 1;

}

else

{

a = inputString[firstCharIntex];

if( M(X,a)==1 )

{

for(i=0;i<10;i++)

{

if( chanShengShi[i]=='$' )

break;

}

i-- ;

while(i>=0)

{

Push(chanShengShi[i]);

i-- ;

}

else

{

printf("\t\t\terror(1) !!\n");

return 0;

}

else /*说明X为终结符*/

{

if( X==inputString[firstCharIntex] )

firstCharIntex++;

else

{

printf("\t\t\terror(2) !! \n");

return 0;

}

counter++;

}

int M(char A, char a)

{

if( A=='S'&& a=='a' )

{

strcpy(&chanShengShi[0],"a$");

return 1;

}

if( A=='S'&& a=='b' )

{

strcpy(&chanShengShi[0],"b$");

return 1;

}

if( A=='S'&& a=='(' )

{

strcpy(&chanShengShi[0],"(T)$");

return 1;

}

if( A=='T'&& a=='a' )

{

strcpy(&chanShengShi[0],"SH$");

return 1;

}

if( A=='T'&& a=='b' )

{

strcpy(&chanShengShi[0],"SH$");

return 1;

}

if( A=='('&& a=='b' )

{

strcpy(&chanShengShi[0],"SH$");

return 1;

}

if( A=='H'&& a==')' )

{

strcpy(&chanShengShi[0],"$");

return 1;

}

if( A=='H'&& a==',' )

{

strcpy(&chanShengShi[0],",SH$");

return 1;

}

else

return 0; /

}

void main()

{

yuCeFenXi();

getchar();

}

相关推荐

自上而下预测分析控制程序实验报告

第二篇：预测分析程序实验报告

专栏推荐