实验二语法分析程序设计与实现范文.docx

实验二语法分析程序设计与实现

16
2020年4月19日
文档仅供参考
实验二 语法分析程序设计与实现
一、实验目的
任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，经过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常见的语法分析方法。
二、基本实验内容与要求
选择对各种常见高级程序设计语言都较为通用的语法结构——算术表示式的一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表示式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。
G2[<算术表示式>]：
<算术表示式> → <项> | <算术表示式>+<项> | <算术表示式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <运算对象> | (<算术表示式>)
若将语法范畴<算术表示式>、<项>、<因式>和<运算对象>分别用E、T、F和i代表，则G2可写成：
G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E)
输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······
输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，而且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，而且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。
要求:
1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。
2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。
3、 供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。
三、问题分析及源程序
LL1文法:
改写文法为:
E- >TG e
G> +TG g
T- >FS t
F- >-TG g1
G- >^ g2
S- >*FS s
T- >/FS s1
S- >^ s2
F- >(E) f
G- >i f1
分析表：

i
+
-
*
/
(
)
#
E
e

e

G

g
g1

g2
g2
T
t

t

S

s2
s2
s
s1

s2
s2
F
f1

f

LL1源程序
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char A[30]; /*分析栈*/
char B[30]; /*剩余串*/
char v1[20]={'i','+','-','*','/','(',')','#'}; /*终结符*/
char v2[20]={'E','G','T','S','F'}; /*非终结符*/
int j=0,b=0,top=0,l; /*L为输入串长度*/
class type /*产生式类型定义*/
{public:
char origin; /*大写字符*/
char array[5]; /*产生式右边字符 */
int length; /*字符个数*/
};
type e,t,g,g1,g2,s,s1,s2,f,f1; /*类对象*/
type C[10][10]; /*预测分析表*/
void print() /*输出分析栈*/
{
int a;
for(a=0;a<=top+1;a++)
cout<<A[a];
cout<<"\t\t";
}
void print1() /*输出剩余串*/
{
int j;
for(j=0;j<b;j++) /*输出对齐符*/
cout<<" ";
for(j=b;j<=l;j++)
cout<<B[j];
cout<<"\t\t\t";
}
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';
strcpy(g1.array,"-TG");
g1.length=3;
g2.origin='G';
g2.array[0]='^';
g2.length=1;
s.origin='S';
strcpy(s.array,"*FS");
s.length=3;
s1.origin='S';
strcpy(s1.array,"/FS");
s1.length=3;
s2.origin='S';
s2.array[0]='^';
s2.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<=4;m++) /*初始化分析表*/
for(n=0;n<=7;n++)
C[m][n].origin='N'; /*全部赋为空*/

/*填充分析表*/
C[0][0]=e;C[0][5]=e;
C[1][1]=g;C[1][2]=g1;C[1][6]=g2;C[1][7]=g2;
C[2][0]=t;C[2][5]=t;
C[3][1]=s2;C[3][2]=s2;C[3][3]=s;C[3][4]=s1;C[3][6]=s2;C[3][7]=s2;
C[4][0]=f1;C[4][5]=f;
cout<<"提示:本程序只能对由'i','+','-','*','/','(',')'构成的以'#'结束的字符串进行分析,\n";
cout<<"请输入要分析的字符串:";
do/*读入分析串*/
{
cin>>ch;
if ((ch!='i') &&(ch!='+')&&(ch!='-')&&(ch!='*')&&(ch!='/')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
{
cout<<"输入串中有非法字符\n";
exit(1); //强制退出程序
}
B[j]=ch;
j++;
}while(ch!='#');
l=j;/*分析串长度*/
ch=B[0];/*当前分析字符*/
A[top]='#'; A[++top]='E';/*'#','E'进栈*/
cout<<"步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n";
do
{
x=A[top--];/*x为当前栈顶字符*/
cout<<k++;
cout<<"\t\t";
for(j=0;j<=7;j++)/*判断是否为终结符*/
if(x==v1[j])
{
flag=1;
break;
}
if(flag==1)/*如果是终结符*/
{
if(x=='#')
{
finish=1;/*结束标记*/
cout<<"acc!"<<endl;/*接受 */
getchar();
exit(1); //退出程序
}/*if*/
if(x==ch)
{
print();
print1();
cout<<"匹配"<<endl;
ch=B[++b];/*下一个输入字符*/
flag=0;/*恢复标记*/
}
else/*出错处理*/
{
print();
print1();
cout<<"出错"<<endl;/*输出出错终结符*/
exit(1);
}
}
else/*非终结符处理*/
{
for(j=0;j<=4;j++)
if(x==v2[j])
{
m=j;/*行号*/
break;
}
for(j=0;j<=7;j++)
if(ch==v1[j])
{
n=j;/*列号*/
break;
}
cha=C[m][n];
if(cha.origin!='N')/*判断是否为空*/
{
print();
print1();
cout<<cha.origin<<"->"; /*输出产生式*/
for(j=0;j<cha.length;j++)
cout<<cha.array[j];
cout<<"\n";
for(j=(cha.length-1);j>=0;j--) /*产生式逆序入栈*/
A[++top]=cha.array[j];
if(A[top]=='^')/*为空则不进栈*/
top--;
}
else/*出错处理*/
{
print();
print1();
cout<<"出错"<<endl;/*输出出错非终结符*/
exit(1);
}
}
}while(finish==0);
}
运行结果：