（编译原理）实验二 LL(1)分析法

您所在的位置：网站首页 › 编译原理实验二词法分析 › （编译原理）实验二 LL(1)分析法

（编译原理）实验二 LL(1)分析法

2024-07-10 01:03:43| 来源: 网络整理| 查看: 265

一．实验目的

加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

二．实验要求

1.对语法规则有明确的定义； 2.编写的分析程序能够对实验一的结果进行正确的语法分析； 3.对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程； 4.实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。

三．实验内容

根据LL(1)语法分析算法的基本思想，设计一个对给定文法进行LL(1)语法分析的程序，并用C、C++或Java语言编程实现。要求程序能够对从键盘输入的任意字符串进行分析处理，判断出该输入串是否是给定文法的有效句子，并针对该串给出具体的LL(1)语法分析过程。

实现代码：

#include #include #include /*******************************************/ int count=0; /*分解的产生式的个数*/ int number; /*所有终结符和非终结符的总数*/ char start; /*开始符号*/ char termin[50]; /*终结符号*/ char non_ter[50]; /*非终结符号*/ char v[50]; /*所有符号*/ char left[50]; /*左部*/ char right[50][50]; /*右部*/ char first[50][50],follow[50][50]; /*各产生式右部的FIRST和左部的FOLLOW集合*/ char first1[50][50]; /*所有单个符号的FIRST集合*/ char select[50][50]; /*各单个产生式的SELECT集合*/ char f[50],F[50]; /*记录各符号的FIRST和FOLLOW是否已求过*/ char empty[20]; /*记录可直接推出^的符号*/ char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/ int validity=1; /*表示输入文法是否有效*/ int ll=1; /*表示输入文法是否为LL(1)文法*/ int M[20][20]; /*分析表*/ char choose; /*用户输入时使用*/ char empt[20]; /*求_emp()时使用*/ char fo[20]; /*求FOLLOW集合时使用*/ /******************************************* 判断一个字符是否在指定字符串中 ********************************************/ int in(char c,char *p) { int i; if(strlen(p)==0) return(0); for(i=0;;i++) { if(p[i]==c) return(1); /*若在，返回1*/ if(i==strlen(p)) return(0); /*若不在，返回0*/ } } /******************************************* 得到一个不是非终结符的符号 ********************************************/ char c() { char c='A'; while(in(c,non_ter)==1) c++; return(c); } /******************************************* 分解含有左递归的产生式 ********************************************/ void recur(char *point) { /*完整的产生式在point[]中*/ int j,m=0,n=3,k; char temp[20],ch; ch=c(); /*得到一个非终结符*/ k=strlen(non_ter); non_ter[k]=ch; non_ter[k+1]='\0'; for(j=0;j /*如果‘|’后的首符号和左部相同*/ for(j=n+1;j n=j+1; break; } } } else { /*如果‘|’后的首符号和左部不同*/ left[count]=ch; right[count][0]='^'; right[count][1]='\0'; count++; for(j=n;j left[count]=point[0]; memcpy(right[count],temp,m); right[count][m]=ch; right[count][m+1]='\0'; printf(" count=%d ",count); m=0; count++; } } left[count]=point[0]; memcpy(right[count],temp,m); right[count][m]=ch; right[count][m+1]='\0'; count++; m=0; } } } /******************************************* 分解不含有左递归的产生式 ********************************************/ void non_re(char *point) { int m=0,j; char temp[20]; for(j=3;j left[count]=point[0]; memcpy(right[count],temp,m); right[count][m]='\0'; m=0; count++; } } left[count]=point[0]; memcpy(right[count],temp,m); right[count][m]='\0'; count++; m=0; } /******************************************* 读入一个文法 ********************************************/ char grammer(char *t,char *n,char *left,char right[50][50]) { char vn[50],vt[50]; char s; char p[50][50]; int i,j,k; printf("\n请输入文法的非终结符号串："); scanf("%s",vn); getchar(); i=strlen(vn); memcpy(n,vn,i); n[i]='\0'; printf("请输入文法的终结符号串："); scanf("%s",vt); getchar(); i=strlen(vt); memcpy(t,vt,i); t[i]='\0'; printf("请输入文法的开始符号："); scanf("%c",&s); getchar(); printf("请输入文法产生式的条数："); scanf("%d",&i); getchar(); for(j=1;j printf("\ninput error!"); validity=0; return('\0'); } /*检测输入错误*/ for(k=0;k /*d是目标符号串，s是源串，type＝1，源串中的‘ ^ ’一并并入目串； type＝2，源串中的‘ ^ ’不并入目串*/ int i,j; for(i=0;i for(j=0;;j++) { if(j /*即求所有由‘ ^ ’推出的符号*/ char temp[10]; int i; for(i=0;i temp[0]=left[i]; temp[1]='\0'; merge(empty,temp,1); emp(left[i]); } } } /******************************************* 求某一符号能否推出‘ ^ ’ ********************************************/ int _emp(char c) { /*若能推出，返回1；否则，返回0*/ int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; merge(empt,temp,1); if(in(c,empty)==1) return(1); for(i=0;;i++) { if(i==count) return(0); if(left[i]==c) /*找一个左部为c的产生式*/ { j=strlen(right[i]); /*j为右部的长度*/ if(j==1&&in(right[i][0],empty)==1) return(1); else if(j==1&&in(right[i][0],termin)==1) return(0); else { for(k=0;k result*=_emp(right[i][k]); temp[0]=right[i][k]; temp[1]='\0'; merge(empt,temp,1); } } } if(result==0&&i if(in(left[i],non_ter)==0) { /*若左部不在非终结符中，报错*/ printf("\nerror1!"); validity=0; return(0); } for(j=0;j /*若右部某一符号不在非终结符、终结符中且不为‘ ^ ’，报错*/ printf("\nerror2!"); validity=0; return(0); } } } return(1); } /******************************************* 求单个符号的FIRST ********************************************/ void first2(int i) { /*i为符号在所有输入符号中的序号*/ char c,temp[20]; int j,k,m; c=v[i]; char ch='^'; emp(ch); if(in(c,termin)==1) /*若为终结符*/ { first1[i][0]=c; first1[i][1]='\0'; } else if(in(c,non_ter)==1) /*若为非终结符*/ { for(j=0;j if(in(right[j][0],termin)==1||right[j][0]=='^') { temp[0]=right[j][0]; temp[1]='\0'; merge(first1[i],temp,1); } else if(in(right[j][0],non_ter)==1) { if(right[j][0]==c) continue; for(k=0;;k++) if(v[k]==right[j][0]) break; if(f[k]=='0') { first2(k); f[k]='1'; } merge(first1[i],first1[k],2); for(k=0;k for(m=0;;m++) if(v[m]==right[j][k+1]) break; if(f[m]=='0') { first2(m); f[m]='1'; } merge(first1[i],first1[m],2); } else if(_emp(right[j][k])==1&&k==strlen(right[j])-1) { temp[0]='^'; temp[1]='\0'; merge(first1[i],temp,1); } else break; } } } } } f[i]='1'; } /******************************************* 求各产生式右部的FIRST ********************************************/ void FIRST(int i,char *p) { int length; int j,k,m; char temp[20]; length=strlen(p); if(length==1) /*如果右部为单个符号*/ { if(p[0]=='^') { if(i>=0) { first[i][0]='^'; first[i][1]='\0'; } else { TEMP[0]='^'; TEMP[1]='\0'; } } else { for(j=0;;j++) if(v[j]==p[0]) break; if(i>=0) { memcpy(first[i],first1[j],strlen(first1[j])); first[i][strlen(first1[j])]='\0'; } else { memcpy(TEMP,first1[j],strlen(first1[j])); TEMP[strlen(first1[j])]='\0'; } } } else /*如果右部为符号串*/ { for(j=0;;j++) if(v[j]==p[0]) break; if(i>=0) merge(first[i],first1[j],2); else merge(TEMP,first1[j],2); for(k=0;k for(m=0;;m++) if(v[m]==right[i][k+1]) break; if(i>=0) merge(first[i],first1[m],2); else merge(TEMP,first1[m],2); } else if(_emp(p[k])==1&&k==length-1) { temp[0]='^'; temp[1]='\0'; if(i>=0) merge(first[i],temp,1); else merge(TEMP,temp,1); } else if(_emp(p[k])==0) break; } } } /******************************************* 求各产生式左部的FOLLOW ********************************************/ void FOLLOW(int i) { int j,k,m,n,result=1; char c,temp[20]; c=non_ter[i]; /*c为待求的非终结符*/ temp[0]=c; temp[1]='\0'; merge(fo,temp,1); if(c==start) { /*若为开始符号*/ temp[0]='#'; temp[1]='\0'; merge(follow[i],temp,1); } for(j=0;j for(k=0;;k++) if(right[j][k]==c) break; /*k为c在该产生式右部的序号*/ for(m=0;;m++) if(v[m]==left[j]) break; /*m为产生式左部非终结符在所有符号中的序号*/ if(k==strlen(right[j])-1) { /*如果c在产生式右部的最后*/ if(in(v[m],fo)==1) { merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { FOLLOW(m); F[m]='1'; } merge(follow[i],follow[m],1); } else { /*如果c不在产生式右部的最后*/ for(n=k+1;n /*如果右部c后面的符号串能推出^*/ if(in(v[m],fo)==1) { /*避免循环递归*/ merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { FOLLOW(m); F[m]='1'; } merge(follow[i],follow[m],1); } for(n=k+1;n /*初始化*/ first[j][0]='\0'; follow[j][0]='\0'; first1[j][0]='\0'; select[j][0]='\0'; TEMP[j]='\0'; temp[j]='\0'; f[j]='0'; F[j]='0'; } for(j=0;j fo[0]='\0'; FOLLOW(j); } } printf("\nfirst:"); for(i=0;i for(j=0;;j++) if(v[j]==left[i]) break; merge(select[i],follow[j],1); } } printf("\nselect:"); for(i=0;i merge(temp,select[i],1); if(strlen(temp) int i,j,k,m; for(i=0;i if(in(select[i][j],termin)==1) { for(k=0;;k++) if(termin[k]==select[i][j]) break; /*k为产生式右部终结符的序号*/ M[m][k]=i; } } } } /******************************************* 总控算法 ********************************************/ void syntax() { int i,j,k,m,n,p,q; char ch; char S[50],str[50]; printf("请输入该文法的句型："); scanf("%s",str); getchar(); i=strlen(str); str[i]='#'; str[i+1]='\0'; S[0]='#'; S[1]=start; S[2]='\0'; j=0; ch=str[j]; while(1) { if(in(S[strlen(S)-1],termin)==1) { if(S[strlen(S)-1]!=ch) { printf("\n该符号串不是文法的句型！"); return; } else if(S[strlen(S)-1]=='#') { printf("\n该符号串是文法的句型."); return; } else { S[strlen(S)-1]='\0'; j++; ch=str[j]; } } else { for(i=0;;i++) if(non_ter[i]==S[strlen(S)-1]) break; for(k=0;;k++) { if(termin[k]==ch) break; if(k==strlen(termin)) { printf("\n词法错误！"); return; } } if(M[i][k]==-1) { printf("\n语法错误！"); return; } else { m=M[i][k]; if(right[m][0]=='^') S[strlen(S)-1]='\0'; else { p=strlen(S)-1; q=p; for(n=strlen(right[m])-1;n>=0;n--) S[p++]=right[m][n]; S[q+strlen(right[m])]='\0'; } } } printf("\nS:%s str:",S); for(p=j;p menu(); } } /******************************************* 主函数 ********************************************/ int main() { int i,j; start=grammer(termin,non_ter,left,right); /*读入一个文法*/ printf("count=%d",count); printf("\nstart:%c",start); strcpy(v,non_ter); strcat(v,termin); printf("\nv:%s",v); printf("\nnon_ter:%s",non_ter); printf("\ntermin:%s",termin); printf("\nright:"); for(i=0;i MM(); printf("\n"); for(i=0;i

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

（编译原理）实验二 LL(1)分析法

（编译原理）实验二 LL(1)分析法

今日新闻

点击排行

推荐新闻

图片新闻

专题文章