篇一:LL(1)语法分析实验报告
《编译原理》课程实验报告
课程实验题目:
作者所在系部:
作者所在专业:
作者所在班级:
作 者 学 号:
作 者 姓 名 :
指导教师姓名:
完 成 时 间 :
一、实验目的LL(1)语法分析实验 计算机科学与工程系计算机科学与技术xxx xxxx
理解预测分析表方法的实现原理。
二、实验内容及要求
编写一通用的预测法分析程序,要求有一定的错误处理能力,出错后能够使程序继续运行下去,直到分析过程结束。可通过不同的文法(通过数据表现)进行测试。
给定算术表达式文法,编写程序。
测试数据:
1.算术表达式文法
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num
2. 作业3.10 文法
三、实验程序设计说明
1.实验方案设计
主要函数之间的调用关系如下图所示:
2.程序源代码
源代码如下:
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
struct Node1
{char vn;
char vt;
char s[10];
}MAP[20];//存储分析预测表每个位置对应的终结符,非终结符,产生式 int k;
//用R代表E',W代表T',e代表空
char start='E';
int len=8;
char
G[10][10]={"E->TR","R->+TR","R->e","T->FW","W->*FW","W->e","F->(E)","F->i"};//存储文法中的产生式
char VN[6]={'E','R','T','W','F'};//存储非终结符
char VT[6]={'i','+','*','(',')','#'};//存储终结符
char SELECT[10][10]={"(,i","+","),#","(,i","*","+,),#","(","i"};//存储文法中每个产生式对应的SELECT集
char Right[10][8]={"->TR","->+TR","->e","->FW","->*FW","->e","->(E)","->i"}; //用R代表A',W代表B',e代表空
/*char start='A';
int len=6;
char G[10][10]={"A->aR","R->ABl","R->e","B->dW","W->bW","W->e"}; char VN[6]={'A','R','B','W'};
char VT[6]={'a','d','b','#','l'};
char SELECT[10][10]={"a","a","d,#","d","b","l"};
char Right[10][6]={"->aR","->ABl","->e","->dW","->bW","->e"};*/
stack <char> stak;
bool compare(char *a,char *b)
{int i,la=strlen(a),j,lb=strlen(b);
for(i=0;i<la;i++)
for(j=0;j<lb;j++)
{if(a[i]==b[j])
return 1; }
return 0;}
char *Find(char vn,char vt)
{int i;
for(i=0;i<k;i++)
{ if(MAP[i].vn==vn && MAP[i].vt==vt)
return MAP[i].s;}
return "error";}
char * Analyse(char * word)
{char p,action[10],output[10];
int i=1,j,l=strlen(word),k=0,l_act,m;
while(!stak.empty())
stak.pop();
stak.push('#');
stak.push(start);
printf("___________________________________________________________\n"); printf("\n 对符号串%s的分析过程\n",word); printf(" -----------------------------------------------------------------------\n"); printf("\n");
printf(" 步骤 栈顶元素 剩余输入串动作\n");
printf(" -----------------------------------------------------------------------\n"); p=stak.top();
while(p!='#')
{printf("%7d",i++);
p=stak.top();
stak.pop();
printf("%6c ",p);
for(j=k,m=0;j<l;j++)
output[m++]=word[j];
output[m]='\0';
printf("%10s",output);
if(p==word[k])
{ if(p=='#')
{ printf(" 分析成功 \n");
return "SUCCESS";}
printf(" 匹配终结符“%c”\n",p);
k++;}
else
{ strcpy(action,Find(p,word[k]));
if(strcmp(action,"error")==0)
{printf(" 没有可用的产生式\n");
return "ERROR"; }
printf(" 展开非终结符%c%s\n",p,action);
int l_act=strlen(action);
if(action[l_act-1]=='e')
continue;
for(j=l_act-1;j>1;j--)
stak.push(action[j]);}
} if(strcmp(output,"#")!=0)
return "ERROR";
}
int main ()
{freopen("in1.txt","r",stdin);
//freopen("in2.txt","r",stdin);
char source[100];
int i,j,flag,l,m;
//printf("\n***为了方便编写程序,用R代表E',W代表T',e代表空*****\n\n"); printf("\n****为了方便编写程序,用R代表A',W代表B',e代表空*****\n\n");
printf("该文法的产生式如下:\n");
for(i=0;i<len;i++)
printf("%s\n",G[i]);
printf("___________________________________________________________\n"); printf("\n该文法的SELECT集如下:\n");
for(i=0;i<len;i++)
{ printf("SELECT(%s) = { %s }\n",G[i],SELECT[i]); }
printf("___________________________________________________________\n"); //判断是否是LL(1)文法
flag=1;
for(i=0;i<8;i++)
{ for(j=i+1;j<8;j++)
{if(G[i][0]==G[j][0])
{ if(compare(SELECT[i],SELECT[j]))
{flag=0;break;}
}
} if(j!=8)
break; }
if(flag)
printf("\n有相同左部产生式的SELECT集合的交集为空,所以文法是LL(1)文法。\n");
else
printf("\n有相同左部产生式的SELECT集合的交集不为空,所以文法不是LL(1)文法。\n");
printf("___________________________________________________________\n"); //预测分析表
for(i=0,k=0;i<8;i++)
{l=strlen(SELECT[i]);
for(j=0;j<l;j+=2)
{MAP[k].vn=G[i][0];
MAP[k].vt=SELECT[i][j];
strcpy(MAP[k].s,Right[i]);
k++; }}
printf("\n表达式文法的预测分析表如下:\n\n");
printf(" ");
for(i=0;i<6;i++)
printf("%10c",VT[i]);
printf("\n");
for(i=0;i<5;i++)
{ printf(" ---------------------------------------------------------------\n");printf("%10c",VN[i]);
for(j=0;j<6;j++)
篇二:语法分析器实验报告
曲阜师范大学实验报告
软件工程一班 组 计算机 系 2010年级
日期 2012-11-12
姓名 王战海 学号 2010416596
实验名称: 语法分析实验
一、实验目的:
1、通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系;
2、了解语法分析的功能,掌握语法分析程序设计的原理和构造方法;
3、训练掌握开发应用程序的基本方法。
二、实验内容:
1、根据某一文法编制调试 LL ( 1 )分析程序,以便对任意输入的符号串进行分析;
2、构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序;
3、分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表,对输入符号串自上而下的分析过程。
三、实验要求:
1、编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。
2、如果遇到错误的表达式,应输出错误提示信息。
3、对下列文法,用LL(1)分析法对任意输入的符号串进行分析:
(1)S->TE
(2)E->+TE|$
(3)T->FM
(4)M->*FM|$
(5)F->(E)|i#
四、实验环境:
Windows XP
Eclipse,J2SE1.6
五、实验分析:
(一)设计思想
(1)定义部分:定义常量、变量、数据结构。
(2)初始化:设立LL(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等);
(3)控制部分:从键盘输入一个表达式符号串;
(4)利用LL(1)分析算法进行表达式处理:根据LL(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。
(二)分析的流程图
(三)算法设计
#include<stdio.h>
#include<stdlib.h>
int vnNum,grammarNum,vtNum=6;
int order;
int count=1;
char Grammar[20][10],BlankTerminate[20][2]; char First[5][4]={'S','(','i','\0',
'E','+','$','\0',
'T','(','i','\0',
'M','*','$','\0',
'F','(','i','\0'};
char Follow[5][6]={'S',')','#','\0','\0','\0', 'E',')','#','\0','\0','\0', 'T','+',')','#','\0','\0', 'M','+',')','#','\0','\0', 'F','*','+',')','#','\0'}; char Select[8][4]={'(','i','\0','\0',
'+','\0','\0','\0', ')','#','\0','\0',
'(','i','\0','\0',
'*','\0','\0','\0', '+',')','#','\0',
'(','\0','\0','\0',
'i','\0','\0','\0'}; int IndiBlanket[6][7];
char VT[10]={'i','+','*','(',')','#'};
typedef struct {
char *base;
char *top;
int stacksize;
}AnalStack;
AnalStack S;
int ScanGrammar()
{
FILE *fp=fopen("文法.txt","r"); FILE *tp;
char singleChar,nextChar; int i=0,j=0; while(!feof(fp)) { fscanf(fp,"%c",&singleChar); if(singleChar=='#') {Grammar[i][j]='\0';break; } if(singleChar=='\n') {Grammar[i][j]='\0';i++;j=0;continue; } if(singleChar=='-') {tp=fp;fscanf(tp,"%c",&nextChar);if(nextChar=='>'){ fp=tp; continue;} } if(singleChar=='|') {Grammar[i+1][0]=Grammar[i][0];Grammar[i][j]='\0';i++;j=1;continue; } Grammar[i][j]=singleChar; j++; }
// printf("输入的文法:\n");
for(int k=0;k<=i;k++)
{
j=0;
while(Grammar[k][j]!='\0'){
if(j==1)
{
// printf("->");
}
//printf("%c",Grammar[k][j]); j++;
}
// printf("\n");
}
// printf("%d\n",i);
fclose(fp);
return i;
}
int Fill(char gi,char sij,int grammarOrder) {
int i,j;
for(i=0;i<vnNum;i++)
{
if(First[i][0]==gi)break; }
j=0;
while(VT[j]!='\0')
{
if(VT[j]==sij)break;
j++;
}
IndiBlanket[i][j]=grammarOrder; return 0;
}
int Indicate()
篇三:LL(1)语法分析程序实验报告
《编译原理》
上机实验报告
1.设计要求
(1)对输入文法,它能判断是否为LL(1)文法,若是,则转(2);否则报错并终止;
(2)输入已知文法,由程序自动生成它的LL(1)分析表;
(3)对于给定的输入串,应能判断识别该串是否为给定文法的句型。
2.分析
该程序可分为如下几步:
(1)读入文法
(2)判断正误
(3)若无误,判断是否为LL(1)文法
(4)若是,构造分析表;
(5)由总控算法判断输入符号串是否为该文法的句型。
3.流程图
4.源程序
/*******************************************
语法分析程序
作者:
学号:
********************************************/
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
/*******************************************/
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; size_t i; if(strlen(p)==0) return(0);
} { } if(p[i]==c) return(1); /*若在,返回1*/ if(i==strlen(p)) return(0); /*若不在,返回0*/
/******************************************* 得到一个不是非终结符的符号
********************************************/ char 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;size_t(j)<=strlen(point)-1;j++) {if(point[n]==point[0]) { /*如果'|'后的首符号和左部相同*/for(j=n+1;size_t(j)<=strlen(point)-1;j++) { while(point[j]!='|'&&point[j]!='\0') temp[m++]=point[j++]; left[count]=ch; memcpy(right[count],temp,m); right[count][m]=ch; right[count][m+1]='\0'; m=0; count++; if(point[j]=='|') char c='A'; c++; while(in(c,non_ter)==1) return(c);
} } } else }} n=j+1; break; { /*如果'|'后的首符号和左部不同*/ left[count]=ch; right[count][0]='^'; right[count][1]='\0'; count++; for(j=n;size_t(j)<=strlen(point)-1;j++) { if(point[j]!='|')temp[m++]=point[j]; else } { 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;size_t(j)<=strlen(point)-1;j++)