编译原理实验报告实验二语法分析(算符优先)x
时间:2020-09-26 00:50:54 来源:勤学考试网 本文已影响 人
华北水利水电学院 编译原理 实验报告
2012?2013学年 第一学期 2011 级计算机科学与技术 专业
班级:2011179 学号:2011179 姓名:_
一、 实验题目:语法分析(算符优先分析程序)
(1) 选择最有代表性的语法分析方法算符优先法;
(2) 选择对各种常见程序语言都用的语法结构,如赋值语句(尤指表达式) 作为分析对象, 并且与所选语法分析方法要比较贴切。
二、 实验内容
(1)根据给定文法,先求出 FirstVt和LastVt集合,构造算符优先关系表(要求算符优先
关系表输出到屏幕或者输出到文件);
(2 )根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式(要求
输出归约过程)
(3) 给定表达式文法为:
G(E' ): E't#E#
E+T | T
T t T*F |F
F^(E)|i
(4)分析的句子为:
(i+i)*i 和 i+i)*i
三、 程序源代
#i nclude<stdlib.h>
#i nclude<stdio.h>
#i ncludevstri ng.h>
#i nclude<iostream.h>
#define SIZE 128
char priorit y[ 6][6]; //算符优先关系表数组
char in put[SIZE]; //存放输入的要进行分析的句子
char rema in[ SIZE]; // 存放剩余串
char AnalyseStack[SIZE]; //分析栈
void an alyse();
int testchar(char x); 〃判断字符X在算符优先关系表中的位置
void rema inStrin g(); 〃移进时处理剩余字符串,即去掉剩余字符串第一
个字符
int k;
void init()// 构造算符优先关系表,并将其存入数组中 {
priority[1][0]='>'; priority[1][1]='>'; priority[1][2]='<'; priority[1][3]='<'; priority[1][4]='>'; priority[1][5]='>';
priority[2][0]='>';
priority[2][1]='>';
priority[2][2]='$';// 无优先关系的用 $表示
priority[2][3]='$';
priority[2][4]='>';
priority[2][5]='>';
priority[3][0]='<';
priority[3][1]='<';
priority[3][2]='<';
priority[3][3]='<';
priority[3][4]='=';
priority[3][5]='$';
priority[4][0]='>';
priority[4][1]='>';
priority[4][2]='$';
priority[4][3]='$';
priority[4][4]='>';
priority[4][5]='>';
priority[5][0]='<';
priority[5][1]='<'; priority[5][2]='<';
priority[5][3]='<';
priority[5][4]='$';
priority[5][5]='=';
}
void an alyse()〃对所输入的句子进行算符优先分析过程的函数
{
int i,j,f,z,z1,n,n1,z2,n2;
int cou nt=O;〃操作的步骤数
char a; //用于存放正在分析的字符
char p,Q,p1,p2;
f=strlen(input); //测出数组的长度
for(i=O;i<=f;i++)
{
a=input[i];
if(i==O)
remainString();
if(AnalyseStack[k]=='+'||AnalyseStack[k]=='*'||AnalyseStack[k]=='i'||Analys eStack[k]=='('||AnalyseStack[k]==')'||AnalyseStack[k]=='#') j=k;
else
j=k-1;
z=testchar(AnalyseStack[j]);〃从优先关系表中查出s[j]和a的优先关系 if(a=='+'||a=='*'||a=='i'||a=='('||a==')'||a=='#')
n=testchar(a);
else //如果句子含有不是终结符集合里的其它字符,不合法
{
printf(" 错误!该句子不是该文法的合法句子! \n");
break;
}
p=priority[z][n];
if(p=='$')
{
printf(" 错误!该句子不是该文法的合法句子! \n");
return;
}
if(p=='>')
{ for( ; ; )
{ Q=AnalyseStack[j];
if(AnalyseStack[j-1]=='+'||AnalyseStack[j-1]=='*'||AnalyseStack[j-1]=='i'||Ana lyseStack[j-1]=='('||AnalyseStack[j-1]==')'||AnalyseStack[j-1]=='#')
j=j-1;
else
j=j-2; z1=testchar(AnalyseStack[j]); n1=testchar(Q); p1=priority[z1][n1]; if(p1=='<') //把 AnalyseStack[j+1]~AnalyseStack[k] 归约为 N {
count++;
printf("(%d) %s\t%10c\t%5c%17s\t 归 约 \n",count,AnalyseStack,p,a,remain);
k=j+1;
i--;
AnalyseStack[k]='N';
int r,r1;
r=strlen(AnalyseStack); for(r1=k+1;r1<r;r1++)
AnalyseStack[r1]='\0';
break;
}
else
continue;
else
{
if(p=='<') //表示移进
{
count++;
printf("(%d) %s\t%10c\t%5c%17s\t
\n",count,AnalyseStack,p,a,remain);
k=k+1;
AnalyseStack[k]=a;
remainString();
}
else
{
if(p=='=')
{ z2=testchar(AnalyseStack[j]); n2=testchar('#'); p2=priority[z2][n2]; if(p2=='=')
{
count++;
printf("(%d) %s\t%10c\t%5c%17s\t
\n",count,AnalyseStack,p,a,remain);
printf(" 该句子是该文法的合法句子。
\n"); break;
}
else
{
count++;
printf("(%d) %s\t%10c\t%5c%17s\t
\n",count,AnalyseStack,p,a,remain);
k=k+1;
AnalyseStack[k]=a;
移进接受移进remainString();
移进
接受
移进
}
else
{
\n");printf(" 错误!该句子不是该文法的合法句子! break;
\n");
}
}
}
}
}
int testchar(char x)
{
int m;
if(x=='+')
m=0;
if(x=='*')
m=1;
if(x=='i')
m=2;
if(x=='(')
m=3;
if(x==')')
m=4;
if(x=='#')
m=5;
return m;
}
void remainString()
{
int i,j;
i=strlen(remain);
for(j=0;j<i;j++)
remain[j]=remain[j+1]; remain[i-1]='\0';
}
void main()
{
init();
printf("文法为:\n");
printf("(0)E'->#E#\n");
剩余输入串printf("(1)E->E+T\n"); printf("(2)E->T\n"); printf("(3)T->T*F\n"); printf("(4)T->F\n"); printf("(5)F->(E)\n"); printf("(6)F->i\n");
剩余输入串
printf("
\n");
printf("
算符优先关系表 \n");
printf("
+
*
i
( )
#\n");
printf("
+
>
<
<
< >
>\n");
printf("
*
>
>
<
< >
>\n");
printf("
i
>
>
>
>\n");
printf("
(
<
<
<
< =
\n");
printf("
)
>
>
>
>\n");
printf("
#
<
<
<
<
=\n");
printf("
--\n");
printf(" 请输入要进行分析的句子(以 #号结束输入) :\n");
gets( in put);//将输入的字符串存到数组中
printf(" 步骤 栈 优先关系 当前符号
移进或归约 \n");
k=0;
AnalyseStack[k]='#';
AnalyseStack[k+1]='\0';
int length,i; //初始化剩余字符串数组为输入串
len gth=strle n(i nput);//
for(i=0;i<le ngth;l++) rema in [i]=i nput[i];
rema in [i]='\0';
an alyse();/对所输入的句子进行算符优先分析过程的函数 }
四、测试结果
<ress Anu key to cont inuettCH n<N+ #<N+i tt<N+N tt<H tt<N>UN ttN*HNmN UN剩亲輸入串i>*i#>*1B *i#i# iB栈优先关系当前将号算符优先关系表* ->ttEtt*i+?丄
<
ress Anu key to cont inue
ttCH n<N+ #<N+i tt<N+N tt<H tt<N>
UN ttN*
HNmN UN
剩亲輸入串
i>*i#
>*1B *i#
i# iB
栈
优先关系
当前将号
算符优先关系表
* ->ttEtt
*
i
+
?丄
i tt tt tt
y. ?
约 移
输入串(i+i)*i 的算符优先分析过程
文祛为:
a?E->E+T
<2>E^>T <3>T->JwF
<4>T->F <5>F-XE>
算符优先关系表
+ * i <
> < < <
青输入要进行分析的句子〔如孚吉東输入厂歩骤 栈 优先关系 当前符号tt < iPress
青输入要进行分析的句子〔如孚吉東输入厂
歩骤 栈 优先关系 当前符号
tt < i
Press
4fi 〉 +
ttN < +
#N+ < i
ItN+i 〉 >
UNiN 〉 )
该句子不是该文迭的合法句子! any key to continue
剩余输八串
>*itt
约
13
测进常进约约
移
输入串i+i)*i的算符优先分析过程
五、小结(包括收获、心得体会、存在的问题及解决问题的方法、建议等)
本次实验是算符优先分析法,算符优先分析法是一种简单直观 ,特别方便于 表达式分析,易于手式实现的方法。算符优先法只考虑算符之间的优先关系, 它 是一种自底向上的归约过程,但这种归约未必严格按照句柄归约, 它是一种不规 范归约法。在实验过程中我对编译原理也有了相当程度的理解。
从中能锻炼到不 会的要问;不会的要在书中去寻找;要会运用现代的网络去寻找新知识; 要对新 知识不断的探索;要有勇于探索与创新的精神。经过这次实验 ,使我的编程能力 得到了很大的锻炼。