第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
语法分析器LL(1)文法(c语言).doc
语法分析器 LL(1)文法（C 语言版）(上)
2009-04-16 21:32
该程序能求出任意给定的文法的所有非终极符和终极符的 first 集，所有非终极符
的 follow 集，所有语句的 select 集，能求出能导空的非终极符集合。给定任意字
符串该程序能判定出是否能接受。由于空符号不好输入，在
程序中用到空符号全部用@表示。
例如：给定一文法：
Z->aAcB|Bd
A->cD
D->aBD|d
B->bC
C->BcA|@
能求出其 first 集：
First(Z)={a,b}
First(A)={c}
First(B)={b}
First(C)={b,@}
First(D)={a,d}
First(a)={a}
First(b)={b}
First(c)={c}
First(d)={d}
first(@)={@}
follow 集：
FOLLOW(A) = { c, #, d, a }FOLLOW(B) = { #, d, a, c }FOLLOW(C) = { #, d, a, c }FOLLOW(D) =
{ c, #, d, a }FOLLOW(Z) = { # }
select 集：
SELECT(Z->aAcB) = { a }SELECT(Z->Bd) = { b }SELECT(A->cD) = { c }SELECT(D->aBD) =
{ a }SELECT(D->d) = { d }SELECT(B->bC) = { b }SELECT(C->BcA) = { b }SELECT(C->@) =
{ @ ,#,d,a,c}
给定一字符处让其判定如 acabdcb，结果能接受
程序：
#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];
FOLLOW 集合*/
char first1[50][50];
char select[50][50];
char f[50],F[50];
char empty[20];
char TEMP[50];
int validity=1;
int ll=1;
int M[20][20];
char choose;
char empt[20];
char fo[20];
/*分析表*/
/*用户输入时使用*/
/*求_emp()时使用*/
/*求 FOLLOW 集合时使用*/
/*表示输入文法是否有效*/
/*表示输入文法是否为 LL(1)文法*/
/* 各 产 生 式 右 部 的 FIRST 和 左 部 的
/*所有单个符号的 FIRST 集合*/
/*各单个产生式的 SELECT 集合*/
/*记录各符号的 FIRST 和 FOLLOW 是否已求过*/
/*记录可直接推出@的符号*/
/*求 FOLLOW 时存放某一符号串的 FIRST 集合*/
/*******************************************
判断一个字符是否在指定字符串中
********************************************/
int in(char c,char *p)
{
int i;
if(strlen(p)==0)
return(0);
for(i=0;;i++)
{
if(p[i]==c)
return(1);
if(i==strlen(p))
/*若在，返回1*/
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<=strlen(point)-1;j++)
{
if(point[n]==point[0])
{
for(j=n+1;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]=='|')
{
n=j+1;
break;
left[count]=ch;
right[count][0]='@';
right[count][1]='\0';
count++;
for(j=n;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';
/*如果'|'后的首符号和左部不同*/
}
}
}
else
{
{
}
}
count++;
m=0;
}
}
}
语法分析器 LL(1)文法（C 语言版）(中)
2009-04-16 21:33
/*******************************************
分解不含有左递归的产生式
********************************************/
void non_re(char *point)
{
int m=0,j;
char temp[20];
for(j=3;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]='\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("请输入文法的非终结符号串：");
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<=i;j++)
{
printf("请输入文法的第%d 条（共%d 条）产生式：",j,i);
scanf("%s",p[j-1]);
getchar();
}
for(j=0;j<=i-1;j++)
if(p[j][1]!='-'||p[j][2]!='>')
{ printf("\ninput error!");
validity=0;
return('\0');
}
/*检测输入错误*/
/*分解输入的各产生式*/
for(k=0;k<=i-1;k++)
{
if(p[k][3]==p[k][0])
recur(p[k]);
else
non_re(p[k]);
}
return(s);
}
/*******************************************
将单个符号或符号串并入另一符号串
********************************************/
void merge(char *d,char *s,int type)
{
目串；
/*d 是目标符号串，s 是源串，type＝1，源串中的' @ '一并并入
type＝2，源串中的' @ '不并入目串*/
int i,j;
for(i=0;i<=strlen(s)-1;i++)
if(type==2&&s[i]=='@')
{
;
else
{
for(j=0;;j++)
{
if(j
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)
if(left[i]==c)
{
return(0);
/*找一个左部为 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<=j-1;k++)
if(in(right[i][k],empt)==1)
mark=1;
if(mark==1)
continue;
else
{
for(k=0;k<=j-1;k++)
{
result*=_emp(right[i][k]);
temp[0]=right[i][k];
temp[1]='\0';
merge(empt,temp,1);
}
}
}
if(result==0&&i
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc