编译原理文法类型判断实验
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/**//*全局变量定义*/
char inputString[10]; /**//*用来存储用户输入的字符串，最长为20个字符*/
char stack[10]; /**//*用来进行语法分析的栈结构*/
int base=0; /**//*栈底指针*/
int top=1; /**//*栈顶指针*/
char VT[4]={'a','d','b','e'}; /**//*用来存放5个终结符*/
char chanShengShi[10]; /**//*用来存放预测分析表M[A,a]中的一条产生式*/
int firstCharIntex=0; /**//*如果a匹配产生式，则每次firstCharIntex 自增 1 */
/**//*firstCharIntex用来存放用户输入串的第一个元素的下标*/
/**//*自定义函数声明*/
char pop() ; /**//*弹出栈顶元素*/
int push(char) ; /**//*向栈内添加一个元素，成功返回1，若栈已满则返回0*/
int search(char temp) ; /**//*查找非终结符集合VT中是否存在变量temp，存在返回1，不存在返回0*/
int M(char A, char a) ; /**//* 若预测分析表M[A,a]中存在产生式，
则将该产生式赋给字符数组chanShengShi[10]，并返回 1，
若M[A,a]中无定义产生式则返回 0
*/
void init() ; /**//*初始化数组inputString[10] 、栈 stack[10] 和 chanShengShi[10]*/
int yuCeFenXi() ; /**//* 进行输入串的预测分析的主功能函数，
若输入串满足文法则返回 1，不满足则返回0
*/
void printStack(); /**//*打印栈内元素 */
void printinputString(); /**//*打印用户输入串 */
/**//*进入主函数*/
void main()
{
system("cls");
yuCeFenXi(); /**//*调用语法预测分析函数*/
system("pause");
}
/**//*函数的定义*/
int yuCeFenXi()
{
char X; /**//*X变量存储每次弹出的栈顶元素*/
char a; /**//*a变量存储用户输入串的第一个元素*/
int i;
int counter=1; /**//*该变量记录语法分析的步骤数*/
init(); /**//*初始化数组*/
printf("wen fa : \n"); /**//*输出文法做为提示*/
printf("S -> aH \n");
printf("H -> aMd | d \n");
printf("M -> Ab | \n");
printf("A -> aM | e \n");
printf("\ninput string ,'#' is a end sign !!(aaabd#) \n"); /**//*提示用户输入将要测试的字符串*/
scanf("%s",inputString);
push('#');
push('S');
printf("\nCounter-----Stack---------------Input string \n"); /**//*输出结果提示语句*/
while(1) /**//*while循环为语法分析主功能语句块*/
{
printf(" ");
printf(" %d",counter); /**//*输出分析步骤数*/
printf(" "); /**//*输出格式控制语句*/
printStack(); /**//*输出当前栈内所有元素*/
X=pop(); /**//*弹出栈顶元素赋给变量X*/
printinputString(); /**//*输出当前用户输入的字符串*/
if( search(X)==0 ) /**//*在终结符集合VT中查找变量X的值，存在返回 1，否则返回 0*/
{
if(X == '#') /**//*栈已经弹空，语法分析结果正确，返回 1*/
{
printf("success \n"); /**//*语法分析结束，输入字符串符合文法定义*/
return 1;
}
else
{
a = inputString[firstCharIntex];
if( M(X,a)==1 ) /**//*查看预测分析表M[A,a]是否存在产生式，存在返回1，不存在返回0*/
{
for(i=0;i<10;i++) /**//* '$'为产生式的结束符,for循环找出该产生式的最后一个元素的下标*/
{
if( chanShengShi[i]=='$' ) break;
}
i-- ; /**//*因为 '$' 不是产生式，只是一个产生式的结束标志，所以i自减1*/
while(i>=0)
{
push( chanShengShi[i] ); /**//*将当前产生式逆序压入栈内*/
i-- ;
}
}
else
{
printf(" error(1) !!\n"); /**//*若预测分析表M[A,a]不存在产生式，说明语法错误*/
return 0;
}
}
}
else /**//*说明X为终结符*/
{
if( X==inputString[firstCharIntex] ) /**//*如果X等于a,说明a匹配*/
{
firstCharIntex++; /**//*输入串的第一个元素被约去，下一个元素成为新的头元素*/
}
else
{
printf(" error(2) !! \n");
return 0;
}
}
counter++;
}
}
void init()
{
int i;
for(i=0;i<10;i++)
{
inputString[i]=NULL; /**//*初始化数组inputString[10] */
stack[i]=NULL; /**//*初始化栈stack[10] */
chanShengShi[i]=NULL; /**//*初始化数组chanShengShi[10]*/
}
}
int M(char A, char a) /**//*文法定义因实际情况而定，该文法为课本例题的文法*/
{ /**//*该函数模拟预测分析表中的二维数组 */
if( A=='S'&& a=='a' ) { strcpy(&chanShengShi[0],"aH$"); return 1; }
if( A=='H'&& a=='a' ) { strcpy(&chanShengShi[0],"aMd$"); return 1; }
if( A=='H'&& a=='d' ) { strcpy(&chanShengShi[0],"d$"); return 1; }
if( A=='M'&& a=='a' ) { strcpy(&chanShengShi[0],"Ab$"); return 1; }
if( A=='M'&& a=='d' ) { strcpy(&chanShengShi[0],"$"); return 1; }
if( A=='M'&& a=='b' ) { strcpy(&chanShengShi[0],"$"); return 1; }
if( A=='M'&& a=='e' ) { strcpy(&chanShengShi[0],"Ab$"); return 1; }
if( A=='A'&& a=='a' ) { strcpy(&chanShengShi[0],"aM$"); return 1; }
if( A=='A'&& a=='e' ) { strcpy(&chanShengShi[0],"e$"); return 1; }
else return 0; /**//*没有定义产生式则返回0*/
}
char pop() /**//*弹出栈顶元素，用topChar返回*/
{
char topChar;
topChar=stack[--top];
return topChar;
}
int push(char ch)
{
if( top>9 )
{
printf(" error : stack overflow "); /**//*栈空间溢出*/
return 0;
}
else
{
stack[top]=ch; /**//*给栈顶空间赋值*/
top++;
return 1;
}
}
int search(char temp)
{
int i,flag=0; /**//*flag变量做为标志，若找到temp则赋1，否则赋0*/
for(i=0;i<4;i++)
{
if( temp==VT[i] ) /**//*终结符集合中存在temp*/
{
flag=1;
break;
}
}
if(flag==1) return 1; /**//*flag==1说明已找到等于temp的元素*/
else return 0;
}
void printStack() /**//*输出栈内内容*/
{
int temp;
for(temp=1;temp<top;temp++)
{
printf("%c",stack[temp]);
}
}
void printinputString() /**//*输出用户输入的字符串*/
{
int temp=firstCharIntex ;
printf(" "); /**//*该句控制输出格式*/
do{
printf("%c",inputString[temp]);
temp++;
}while(inputString[temp-1]!='#');
printf(" \n");
}
⑵ 编译原理 LR0文法的判定
设G1、G2是两个文法，若L(G1)=L(G2)
，则称G1与G2等价，记作G1≡G2。
即：文法的等价性是指他们所定义的语言是一样的。
文法的化简是指消除如下无用产生式：
⒈
删除
A->A
形式的产生式(自定己)；
⒉
删除不能从其推导出终结符串的产生式(不终结)；
⒊
删除在推导中永不使用的产生式(不可用)。
⑶ 编译原理语法分析实验问题
错误1：在3.txt中，第二个表达式x:=2*3，在编译器里面没有对*符号进行解释，这个应补充，或者改掉*为+。
错误2：代码中出现3次类似syn==15||16的代码，我理解应该是(syn==15)||(syn==16)
改掉这两点后代码可以正常运行。
建议：写代码是一项工作，更是一个创作过程，建议你按照代码写作规范来写，这样的代码清晰易读，易于交流和纠错。
⑷ 编译原理中，形式语言里怎么区分2型文法与3型文法
二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结备运贺符；3型文法从广义上仿派讲包括左线形文法、右线形文法和正规文法悄裤
。
B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。
C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端
。
D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：
1）空串
2）只有一个终结符
3）只有一个终结符后接一个非终结符
E、所有的3型文法都是2型文法。
⑸ 编译原理中如何用c语言来编写程序判断输入的字符串是否符合文法规则
scanf()有返回值，若返回值是0，则不符合文法规则
一般情况下，scanf()返回值是输入的字符数
⑹ 编译原理实验报告
#include<stdio.h>
void main()
{
int m=0,n=0,n1=0,n2=0,n3=0,zg,fzg,flag;
int bz[7]=;/*状态改变控制，1 表示可以改变状态zt值，0 表示不可以*/
int zt[7]=;/*状态值，2表示未定状态，1表示 是，0表示 否*/
char temp[100]="\0";/*用于求first集*/
char z[7];/*非总结符*/
char z1[7];/*总结符*/
char z2[7]="\0";/*gs[]文法中出现的标记个数的辅助字符 01234*/
char gs[100]="\0";/*文法，按顺序排成字符串*/
printf("请依次输入非终结符(不超过7个):");
gets(z);
while(z[m]!='\0')
fzg=m;//zg是非终结符个数
while(n<m)
//生成01234辅助字符
printf("您输入了:");
puts(z);
fflush(stdin);
printf("请依次输入终结符(不超过7个):");
gets(z1);
while(z1[n1]!='\0')
zg=n1;
printf("您输入了:");
puts(z1);
fflush(stdin);
printf("按照正确格式输入所有文法(总长度不超过100格式如下):");
printf("如果文法为(字符'k'表示空):\n");
printf("S-->AB S-->bC A-->k A-->b\n");
printf("输入:0SAB0SbC1Ak1Ab\n");
printf(" (注:数字01234表示第一二三四个非终结符)\n");
gets(gs);
fflush(stdin);
printf("您输入了:");
puts(gs);
m=0;
//对于输入文法字符串的转换，将每个文法式左部去除
while(gs[m]!='\0')
{
n=m;
if(gs[m]>='0'&&gs[m]<='9')
{
m++;
while(gs[m]!='\0')
{
gs[m]=gs[m+1];
m++;
}
//gs[m-1]='\0';
}
m=++n;
}
m=0;
//puts(gs);
/*情况一，直接判定是 形如: (A-->k) */
while(gs[m]!='\0')
{
if(gs[m]=='k')
{
zt[gs[m-1]-48]=1;
bz[gs[m-1]-48]=0;
}
m++;
}
/*情况二，直接判定--否 形如: (D-->aS ,D-->c) */
for(n=0;n<fzg;n++)
{
if(bz[n]==1)
{
m=0;
n2=0;
while(gs[m]!='\0')
{
if(z2[n]==gs[m])
{
if(gs[m+1]>=z1[0]&&gs[m+1]<=z1[n1-1])
zt[n]=0;
else //gs[m+1] 是非终结符n2做标记
}
//跳出循环，无法解决该情况，推到下面情况三
m++;
}
if(n2!=99) //完成所有扫描，未出现非终结符，得出结论zt[n]=0.bz[n]=0不允许再改变zt[n]
}
}
/*情况三，最终判定*/
do
{
flag=0;
for(n=0;n<fzg;n++)
{
if(bz[n]==1) //未得到判定
{ m=0;
while(gs[m]!='\0')
{
if(gs[m]==z2[n]) //判定gs[m]是辅助字符0123
{
m++;
while(gs[m]>='A'&&gs[m]<='Z')
{
n1=0;
for(n2=0;n2<fzg;n2++) //循环查找是gs[m]哪个非终结符
{
if(gs[m]==z[n2])
{
if(zt[n2]==1) //这个非终结符能推出空
zt[n]=1;
else if(bz[n2]==1) //这个非终结符 现在 不能推出空，但它的状态可改即它最终结果还未判定
else
//设 m1 做标记供下一if参考
break; //找到gs[m]是哪个非终结符,for循环完成任务，可以结束
}
}
if(n1==99) break;
m++;
}
}
m++;
}
if(zt[n]==1) bz[n]=0;
if(bz[n]==0) flag=1;//对应for下的第一个if（zt[n]==2）
}
}
}while(flag);
printf("结果是:\n");
for(m=0;m<5;m++)
{
switch(zt[m])
{
case 0:printf("%c---否\n",z[m]);break;
case 1:printf("%c---是\n",z[m]);break;
case 2:printf("%c---未定\n",z[m]);break;
}
}
/*
puts(gs);
puts(zt);
puts(z);
puts(z1);
puts(z2);
printf("%d,,,%d",fzg,zg);
*/
//下面求first集
//下面求first集
for(n=0;n<fzg;n++)
m=0;n=0;n1=0;n2=0;
while(gs[n]>='0'&&gs[n]<='9')
{
for(;m<fzg;m++)
{
if(n2!=m)
n1=0; //m=n2用于第二次以后的for循环中还原上次m的值
if(gs[n]==z2[m])
{
while(gs[n+1]>'9')
{
if(n1==0)
//如果是第一个直接保存
//不是第一个，先与字符数组中其它字符比较，没相同的才保存
else if(gs[n]>='a'&&gs[n]<='z'&&gs[n+1]>='A'&&gs[n+1]<='Z') //gs[n]是终结符 且 gs[n+1]是非终结符
;//什么也不做，程序继续n++，扫描下一个gs[n]
else
{
for(n3=0;n3<=n1;n3++)
{
if(temp[m*13+n3]==gs[n+1])
break;
}
if(n3>n1) //for循环结束是因为n3而不是break
}
n++;
}
break; //break位于if(gs[n]==z2[m]),对于gs[n]已找到z2[m]完成任务跳出for循环
}
}
n2=m; //存放该for循环中m的值
n++;
}
//进一步处理集除去非终结符
m=0;n=0;n1=0;n2=0;
for(m=0;m<fzg;m++)
{
if(flag!=m)
n1=0; //m=flag用于第二次以后的for循环中还原上次m的值
while(temp[m*13+n1]!='\0')
{
while(temp[m*13+n1]>='A'&&temp[m*13+n1]<='Z') //搜索非终结符
{
for(n=0;n<fzg;n++) //确定是哪个非终结符
{if(temp[m*13+n1]==z[n])
break;
}
while(temp[m*13+n1]!='\0') //从temp[n*13+n1]开始每个字符依次往前移动一
n1--;
while(temp[n*13+n2]!='\0') //把z[n]对应的first加入temp[m*13+n1]这个first中，每个字符依次加在最后
{
for(n3=0;n3<n1;n3++) //循环判定是否有相同的字符
{
if(temp[m*13+n3]==temp[n*13+n2])
break;
}
if(temp[n*13+n2]=='k'&&zt[m]==0) //那些不能推出 空，但是因为要加入 其他非终结符的first集 而可能含有 空
n2++;
else if(n3>=n1) //for循环结束是因为n3而不是break ,即无相同字符
else n2++;
}
n1=0;
n2=0;
}
n1++;
}
flag=m; //存放该for循环中m的值
}
//非终结符的first集输出
m=0;n1=0;
for(m=0;m<fzg;m++)
{
n1=0;
printf("非终结符 %c 的first集是: ",z[m]);
while(temp[m*13+n1]!='\0')
{
printf("%c",temp[m*13+n1]);
n1++;
}
printf("\n");
}
}
⑺ 编译原理中,形式语言里怎么区分2型文法与3型文法
通过算法对文法的每一产生式进行分析,如果存在复杂递归,则必是上下文无关文法,否则就是正则文法.
1、像A->Aa|ε这样的文法,虽然存在递归,但却是单一的自递归,可以通过有穷自动机表示和分析处理,所以是正则文法；
2、但是像E->E+T,T->id|(E)这样的文法显然非单一的自递归,而是存在复杂递归,自动机是无法表示和处理的,必然是上下文无关文法.
另外还请注意：
1、正则文法是上下文文法的子集,正则文法也属于上下文无法,但有的上下文文法不一定是正则文法；
2、同时再结合这两个的形式定义认真揣摩必定能悟出一二.
⑻ 四种文法的类型(编译原理)
乔姆斯基（Chomsky）按产生式的类型把文法分为四种类型：0、1、2、3型文法。
*在下文中的产生式中，箭头左边的大写字母为严格的非终结符，而其左边的小写字母不严格要求为非终结符，如[0型文法]中的第2条产生式。
【0型文法】
产生式形式：α→β
要求：箭头左边的α 至少 含有 一个非终结符 ， 其余 不加任何限制
例如，G：C→AaB
aA→a
B→b|Bb
【1型文法】
产生式形式：α→β
要求： |α|≤|β| (产生式左端的长度<=右端的长度)，S→ε除外。
例如G： C→aAB
aA→aBa
B→b|Bb
【2型文法】(上下文无关文法)
产生式形式：A→β，A∈VN(终结符) ，β∈V *(VN∪VT，即可为终结符也可为非终结符)
说明：当以β替换A时，与A的上下文环境无关；
大部分程序设计语言近似于2型文法。
【3型文法】(正规文法 / 右线性文法)
产生式形式：A→a，A→aB，
说明：a∈VT(终结符) ， A，B∈VN(非终结符)，即产生式右端的第一个符号必须为 终结符
例如 G：A→aB
B→b|bB
【其他说明】对于这四种类型的文法：
*包含关系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'译为A包含B)
*严格程度：3 > 2 > 1 > 0
*判断文法所属类型的顺序：3 → 2 → 1 → 0
⑼ 编译原理 文法类型
0型文法(Type-0 Grammar)
1型文法(Type-1 Grammar)
2型文法(Type-2 Grammar)
3型文法(Type-3 Grammar)
无限制文法(Unrestricted Grammar) /短语结构文法(Phrase Structure Grammar, PSG )
∀α → β∈P， α中至少包含1个非终结符
0型语言
由0型文法G生成的语言L(G )
上下文有关文法(Context-Sensitive Grammar , CSG )
∀α → β∈P，｜α｜≤｜β｜
产生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )
上下文有关语言（1型语言）
由上下文有关文法(1型文法) G生成的语言L(G )
上下文无关文法(Context-Free Grammar, CFG )
∀α → β∈P，α ∈ VN
产生式的一般形式：A→β
上下文无关语言（2型语言）
由上下文无关文法(2型文法) G生成的语言L(G )
正则文法(Regular Grammar, RG )
右线性(Right Linear)文法： A→wB 或 A→w
左线性(Left Linear) 文法： A→Bw 或 A→w
左线性文法和右线性文法都称为正则文法
0型文法：α中至少包含1个非终结符
1型文法（CSG） ：｜α｜≤｜β｜
2型文法（CFG） ：α ∈ VN
3型文法（RG）：A→wB 或 A→w (A→Bw 或A→w)
0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法
⑽ 编译原理实现判断是不是一个文法的句子
构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。