#include"string.h"
char a[20][10]
char Vn[26]
char Vt[64]
int M=0 //Vn下标
int N=0 //Vt下标
int m=0
int flag=-1 //又穷状态自动机是确定与非确定的标志
void initial() //初始化
{
for(int b=0b<26b++)
Vn[b]='#'
for(int c=0c<64c++)
Vt[c]='#'
for(int d=0d<20d++)
for(int e=0e<10e++)
a[d][e]='#'
}
void group()//判断终结符号与非终结符
{
for(int k=0a[k][0]!='e'k++)
{
for(int f=0a[k][f]!='\0'f++)
{
if((a[k][f]>='A')&&(a[k][f]<='Z'))
{
for(int x=0x<=M&&M<=27x++)
if(Vn[x]==a[k][f])
break
if((x-1)==M)
{
Vn[M]=a[k][f]
M++
}
}
else
{
for(int y=0y<=N&&N<=20y++)
{
if(a[k][f]==':'||a[k][f]=='=')
break
else
{
if(Vt[y]==a[k][f])
break
}
}
if((y-1)==N)
{
Vt[N]=a[k][f]
N++
}
}
}
}
}
void input() //输入文法
{
for(int i=0i<10i++)
a[m][i]='#'
scanf("%s",a[m])
while(strcmp(a[m],"end"))
{
if((a[m][0]>='A')&&(a[m][0]<='Z')) //判断是否为正则文法
{
int h=4
if((a[m][h]>='A')&&(a[m][h]<='Z'))//U::=WT
{
if((a[m][h+1]<'A')||(a[m][h+1]>'Z'))
{
if(a[m][h+2]!='\0')
{
printf("此规则不是正则文法的规则，请重新输入\n")
input()
break
}
}
else
{
printf("此规则不是正则文法的规则，请重新输入\n")
input()
break
}
}
else
{
if(a[m][h+1]!='\0')//U::=T
{
printf("此规则不是正则文法的规则，请重新输入\n")
input()
break
}
}
}
m++
scanf("%s",a[m])
}
}
void recongnise() //判断是确定还是非确定
{
for(int i=0a[i][0]!='e'i++)
{
for(int j=i+1a[j][0]!='e'j++)
{
int n=4
if(a[i][n]==a[j][n])
n++
if(a[i][n]==a[j][n])
break
}
int h=4
if(a[i][h]==a[j][h])
h++
if(a[i][h]==a[j][h]) //U::=T
{
printf("此文法对应的有穷状态自动机是非确定的\n\n")
flag=0
break
}
}
if(a[i][0]=='e') //U::=WT
{
printf("此文法对应的有穷状态自动机是确定的\n\n")
flag=1
}
}
void output() //输出文法相应的有穷状态自动机
{
if(flag==0)
{
printf("NFA N=({")
for(int i=0Vn[i]!='#'i++)
printf("%c,",Vn[i])
printf("S},{")
for(int j=0Vt[j]!='#'j++)
printf("%c,",Vt[j])
printf("},M',{S},{%c})\n",Vn[0])
printf("其中M':\n")
for(int x=0Vn[x]!='#'x++)
{
for(int y=0Vt[y]!='#'y++)
{
printf("M'(%c,%c)=",Vn[x],Vt[y])
for(int z=0a[z][0]!='e'z++)
if(a[z][4]==Vn[x])
if(a[z][5]==Vt[y])
printf("%c",a[z][0])
if(a[z][0]=='e')
printf("\t")
}
printf("\n")
}
for(int u=0Vt[u]!='#'u++)
{
printf("M'(S,%c)=",Vt[u])
for(int k=0a[k][0]!='e'k++)
if(a[k][4]==Vt[u])
printf("%c",a[k][0])
if(a[k][0]=='e')
printf("\t")
}
}
if(flag==1)
{
printf("DFA N=({")
for(int b=0Vn[b]!='#'b++)
printf("%c,",Vn[b])
printf("S},{")
for(int c=0Vt[c]!='#'c++)
printf("%c,",Vt[c])
printf("},M',S,{%c})\n",Vn[0])
printf("其中M':\n")
for(int p=0Vn[p]!='#'p++)
{
for(int q=0Vt[q]!='#'q++)
for(int r=0a[r][0]!='#'r++)
if(a[r][4]==Vn[p])
if(a[r][5]==Vt[q])
printf("M'(%c,%c)=%c\t",Vn[p],Vt[q],a[r][0])
printf("\n")
}
for(int d=0Vt[d]!='#'d++)
{
for(int e=0a[e][0]!='e'e++)
if(a[e][4]==Vt[d])
printf("M'(S,%c)=%c\t",Vt[d],a[e][0])
}
}
}
void main()
{
initial()
printf("请输入文法:\n")
input()
group()
printf("\n")
recongnise()
output()
printf("\n")
}
输入的是形如U::=T和U::=WT这种类型的正则文法，没有U::=TW这种文法的输入。这个程序基本上齐全，如果输入的文法不是正则文法，会给出提示重新输入的。祝君好运，记得给分哦！！！！这可是花了一周才写出来的，而且输出的状态自动机是按非终结符号的顺序输出的，而不是按文法的顺序输出，绝对达标。
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）