编译原理语法分析实验报告

编译原理语法分析实验报告

目录

一．语法分析方法 ......................................... 1

1.判断为算符优先文法： ................................ 1

2.求FirstVT集和LastVT集 ............................. 1

3.根据FirstVT和LastVT集构造算符优先表 ............... 1

二．程序设计 ............................................. 2

1.总体设计 ............................................ 2

2.子程序设计 .......................................... 2

三．程序中的结构说明 ..................................... 3

1.重要函数介绍 ........................................ 3

2.函数代码 ............................................ 3

四．程序测试 ............................................ 13

五、 实验总结 ........................................... 15

编译原理语法分析实验报告

一．语法分析方法

有文法G[S]： （0）S’ →#S# （1）S→V （2）V→T|ViT （3）T→F|T+F （4）F→)V*|(

分析的句子为(+(i(

1.判断为算符优先文法：

文法没有A-> BC 且BC均为非终结符，因此它为OG文法 文法没有同时存在

①A-> ab 或A-> .aBb . ②A-> aB 且B＝>b .或B＝>Cb . ③A-> Bb .且B＝> a或B＝> aC 文法为算符优先文法

2.求FirstVT集和LastVT集

有产生式（0）S’ →#S# 可得’#’

’#’

表1-1 非终结符的FIRSTVT和LASTVT集合表

表1-2 G[S]的算符优先关系矩阵表

编译原理语法分析实验报告

二．程序设计

1.总体设计

图2-1 总体设计图

2.子程序设计

创建文法关系表模块

图2-2 子程序设计创建文法关系模块图

编译原理语法分析实验报告

三．程序中的结构说明

1.重要函数介绍

int deal(); //对输入串的分析函数

int zhongjie(char c); //判断字符c是否是终结符函数 int xiabiao(char c); //求字符c在算符优先关系表中的下标

void out(int j,int k,char *s); //打印s栈

void firstvt(char c); //求非终结符c的FIRSTVT集 void lastvt(char c); //void table(); //void prtfun(char biao[10][10]); //2.函数代码

#include "stdio.h" #include "stdlib.h"

char data[20][20]; char s[100]; char lable[20]; char input[100]; char string[20][10]; int k; char a; int j; char q;

int r; int r1; char st[10][30]; char first[10][10]; /char last[10][10]; int fflag[10]={0}; 集是否已求出

int lflag[10]={0}; 是否已求出

int deal(); int zhongjie(char c); int xiabiao(char c); 标

void out(int j,int k,char *s); void firstvt(char c); void lastvt(char c); void table(); void prtfun(char biao[10][10]); int main()

求非终结符c的LASTVT集 创建文法优先关系表

打印firstvt或者lastvt集 //算符优先关系 //模拟符号栈s //文法终结符集 //文法输入符号串 //用于输入串的分析 //文法规则个数

//转化后文法规则个数 //用来存储文法规则

/文法非终结符FIRSTVT集 //文法非终结符LASTVT集

//标志第i个非终结符的FIRSTVT//标志第i个非终结符的LASTVT集 //对输入串的分析

//判断字符c是否是终结符

//求字符c在算符优先关系表中的下//打印s栈

//求非终结符c的FIRSTVT集 //求非终结符c的LASTVT集 //创建文法优先关系表

//打印firstvt或者lastvt集

编译原理语法分析实验报告

{

int i,j,k=0;

printf("请输入文法规则数："); scanf("%d",&r);

printf("请输入文法规则：\n"); for(i=0;i<r;i++) {

scanf("%s",st[i]); //存储文法规则，初始化FIRSTVT集和LASTVT集 first[i][0]=0; //first[i][0]和last[i][0]分别表示st[i][0]非终结

符的FIRSTVT集和LASTVT集中元素的个数*/ last[i][0]=0; }

for(i=0;i<r;i++) //判断文法是否合法 {

for(j=0;st[i][j]!='\0';j++) {

if(st[i][0]<'A'||st[i][0]>'Z') //判断首字母若不是非终结符 { printf("不是算符文法!\n"); exit(-1); }

if(st[i][j]>='A'&&st[i][j]<='Z') //判断两个非终结符相连 {

if(st[i][j+1]>='A'&&st[i][j+1]<='Z') { printf("不是算符文法!\n"); exit(-1); } } } }

for(i=0;i<r;i++) {

for(j=0;st[i][j]!='\0';j++) {

if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|')

lable[k++]=st[i][j]; } }

lable[k]='#'; lable[k+1]='\0'; table();

编译原理语法分析实验报告

printf("每个非终结符的FIRSTVT集为：\n");//输出每个非终结符的FIRSTVT集

prtfun(first);

printf("每个非终结符的LASTVT集为：\n");//输出每个非终结符的LASTVT集 prtfun(last);

printf("算符优先分析表如下:\n"); for(i=0;lable[i]!='\0';i++)

printf("\t%c",lable[i]); //打印优先关系矩阵第一行 printf("\n");

for(i=0;i<k+1;i++) {

printf("%c\t",lable[i]); //打印优先关系矩阵第一列元素 for(j=0;j<k+1;j++) {

printf("%c\t",data[i][j]); //打印每一列的优先关系 }

printf("\n"); }

printf("请输入文法输入符号串以#结束:");

scanf("%s",input); //接受输入分析串

deal(); }

void prtfun(char biao[10][10]) //打印firstvt或者lastvt集 {

int i,j;

for(i=0;i<r;i++) {

printf("%c: ",st[i][0]); //输入对应非终结符 for(j=0;j<biao[i][0];j++) {

printf("%c ",biao[i][j+1]); }

printf("\n"); } }

void table() //创建文法优先关系表 {

char text[20][10]; int i,j,k,t,l,x=0,y=0;

编译原理语法分析实验报告

int m,n; x=0;

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

{ firstvt(st[i][0]); //求对应非终结符的FIRSTVT集 lastvt(st[i][0]); //求对应非终结符的LASTVT集 }

for(i=0;i<r;i++) //过滤文法规则中的“|” { text[x][y]=st[i][0]; y++;

for(j=1;st[i][j]!='\0';j++) {

if(st[i][j]=='|') {

text[x][y]='\0'; //将“|”前部分作为一条规则 x++; y=0;

text[x][y]=st[i][0]; //将“|”后部分作为另一条规则 y++;

text[x][y++]='-'; text[x][y++]='>'; } else {

text[x][y]=st[i][j]; y++; } }

text[x][y]='\0'; x++; y=0; } r1=x;

printf("转化后的文法为:\n");

for(i=0;i<x;i++) //输出转化后的文法规则串 {

printf("%s\n",text[i]); }

for(i=0;i<x;i++) /*求每个终结符的推导结果(去掉"->"后的转化文法，用于最后的规约)*/

{ string[i][0]=text[i][0];

for(j=3,l=1;text[i][j]!='\0';j++,l++) string[i][l]=text[i][j]; string[i][l]='\0';

编译原理语法分析实验报告

}

for(i=0;i<x;i++) {

for(j=1;text[i][j+1]!='\0';j++) {

if(zhongjie(text[i][j])&&zhongjie(text[i][j+1]))//求“=”关系 {

m=xiabiao(text[i][j]);

n=xiabiao(text[i][j+1]); //求终结符在优先关系表中的下标 data[m][n]='='; }

if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1])) //求“=”关系 {

m=xiabiao(text[i][j]); n=xiabiao(text[i][j+2]); data[m][n]='='; }

if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1])) {

for(k=0;k<r;k++) {

if(st[k][0]==text[i][j+1]) break; }

m=xiabiao(text[i][j]);

for(t=0;t<first[k][0];t++) //求“<”关系 {

n=xiabiao(first[k][t+1]); data[m][n]='<'; } }

if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1])) //求“>”关系 {

for(k=0;k<r;k++) {

if(st[k][0]==text[i][j]) break; }

n=xiabiao(text[i][j+1]); for(t=0;t<last[k][0];t++) {

编译原理语法分析实验报告

m=xiabiao(last[k][t+1]); data[m][n]='>'; } } } }

m=xiabiao('#');

for(t=0;t<first[0][0];t++) {

n=xiabiao(first[0][t+1]); data[m][n]='<'; }

n=xiabiao('#');

for(t=0;t<last[0][0];t++) {

m=xiabiao(last[0][t+1]); data[m][n]='>'; }

data[n][n]='='; }

void firstvt(char c) {

int i,j,k,m,n; for(i=0;i<r;i++) {

if(st[i][0]==c) break; }

if(fflag[i]==0) {

n=first[i][0]+1; m=0; do

{ if(m==2||st[i][m]=='|') {if(zhongjie(st[i][m+1])) {first[i][n]=st[i][m+1]; n++; } else

{ if(zhongjie(st[i][m+2])) {first[i][n]=st[i][m+2]; n++; }

求FIRSTVT集 //

编译原理语法分析实验报告

if(st[i][m+1]!=c) {firstvt(st[i][m+1]); for(j=0;j<r;j++)

{ if(st[j][0]==st[i][m+1]) break; }

for(k=0;k<first[j][0];k++) {

int t;

for(t=0;t<n;t++) {

if(first[i][t]==first[j][k+1]) break; }

if(t==n) {

first[i][n]=first[j][k+1]; n++; } } } } } m++;

}while(st[i][m]!='\0'); first[i][n]='\0'; first[i][0]=--n; fflag[i]=1; } }

void lastvt(char c) {

int i,j,k,m,n; for(i=0;i<r;i++) {

if(st[i][0]==c) break; }

if(lflag[i]==0) {

n=last[i][0]+1; m=0; do

//求LASTVT集

编译原理语法分析实验报告

{

if(st[i][m+1]=='\0'||st[i][m+1]=='|') {

if(zhongjie(st[i][m])) {

last[i][n]=st[i][m]; n++; } else {

if(zhongjie(st[i][m-1])) {

last[i][n]=st[i][m-1]; n++; }

if(st[i][m]!=c) {

lastvt(st[i][m]); for(j=0;j<r;j++) {

if(st[j][0]==st[i][m]) break; }

for(k=0;k<last[j][0];k++) {

int t;

for(t=0;t<n;t++) {

if(last[i][t]==last[j][k+1]) break; }

if(t==n) {

last[i][n]=last[j][k+1]; n++; } } } } } m++;

}while(st[i][m]!='\0'); last[i][n]='\0'; last[i][0]=--n;

编译原理语法分析实验报告

lflag[i]=1; } }

int deal() //对输入串的分析 {

int i,j; int x,y;

int z; //输入串的长度 k=1;

s[k]='#'; //栈置初值

for(i=0;input[i]!='\0';i++); //计算输入串的长度 z=i--; i=0;

while((a=input[i])!='\0') {

if(zhongjie(s[k])) j=k; else j=k-1;

x=xiabiao(s[j]); y=xiabiao(a);

if(data[x][y]=='>') {

out(1,k,s); printf("%c",a); out(i+1,z,input); printf("归约\n"); do {

q=s[j];

if(zhongjie(s[j-1])) j=j-1; else j=j-2;

x=xiabiao(s[j]); y=xiabiao(q);

}while(data[x][y]!='<'); int m,n,N;

for(m=j+1;m<=k;m++) {

for(N=0;N<r1;N++)

for(n=1;string[N][n]!='\0';n++) {

if(!zhongjie(s[m])&&!zhongjie(string[N][n])) {

编译原理语法分析实验报告

if(zhongjie(s[m+1])&&zhongjie(string[N][n+1]) &&s[m+1]==string[N][n+1]) {

s[j+1]=string[N][0]; break; } }

else

if(zhongjie(s[m]))

if(s[m]==string[N][n]) {

s[j+1]=string[N][0]; break; } } }

k=j+1; if(k==2&&a=='#') {

out(1,k,s); printf("%c",a); out(i+1,z,input); printf("结束\n");

printf("输入串符合文法的定义！\n");

return 1; } } else

if(data[x][y]=='<'||data[x][y]=='=')

{ out(1,k,s); printf("%c",a); out(i+1,z,input); printf("移进\n"); k++; s[k]=a; i++; } else {

printf("\nflase"); return 0; } }

输入串符合文法的定义 //移进 //

编译原理语法分析实验报告

printf("\nflase"); return 0; }

void out(int j,int k,char *s) {

int n=0; int i;

for(i=j;i<=k;i++) {

printf("%c",s[i]); n++; }

for(;n<15;n++) {

printf(" "); } }

int xiabiao(char c) {

int i;

for(i=0;lable[i]!='\0';i++) {

if(c==lable[i]) return i; }

return -1; }

int zhongjie(char c) {

int i;

for(i=0;lable[i]!='\0';i++) {

if(c==lable[i]) return 1; }

return 0; }

四．程序测试

//求字符c在算符优先关系表中的下标 //判断字符c是否是终结符

编译原理语法分析实验报告

当输入文法首字母不是终结符的情况时，程序提示不是算符文法

图4-1 判断不是算符文法测试

当输入文法分析串没有“#”结束时，分析失败

图4-2 分析失败测试

编译原理语法分析实验报告

当输入文法分析串以“#”结束时，分析成功

图4-3 分析成功测试

五、 实验总结

经过学习实现了算符优先算法，能够对输入的符号串进行算符优先分析，并且能够处理分析过程中遇到的错误。经过这次课程设计的练习，我感觉自己的编程能力得到了很好的锻炼，是一次很好的实践活动，对以后的学习也有很大的帮助。

指导教师签字：

年 月 日

本文来源：https://www.bwwdw.com/article/d9yj.html