右线性文法转换为有限自动机[教材]

右线性文法转换为有限自动机[教材]右线性文法转换为有限自动机[教材] 学院: 计算机学院专业:计算机科学与技术目录一、题目要求 -------------------------- 02 二、算法思想 -------------------------- 02 三、程序设计 -------------------------- 03 四、运行截图 -------------------------- 06 五、心得体会 -------------------------- 06 右线性文法转换为有限自动机一、题目要求要求编写...

右线性文法转换为有限自动机[教材] 学院: 计算机学院专业:计算机科学与技术目录一、题目要求 -------------------------- 02 二、算法思想 -------------------------- 02 三、程序设计 -------------------------- 03 四、运行截图 -------------------------- 06 五、心得体会 -------------------------- 06 右线性文法转换为有限自动机一、题目要求要求编写一个程序，输入一个右线性文法，输出与该文法等价的有限自动机。二、算法思想首先输入变量集、终结符集和开始符，输入变量集和终结符集时用逗号隔开，否则会提示出错。然后输入右线性文法的产生式，输入时即区分出产生式的左部和右部，点击添加产生式按钮提取产生式的左部和右部。如果产生式不符合要求，则提示出错，添加的产生式使用链表存储，每个节点表示一个产生式，每次点击添加后，程序将会新生成一个结点来表示产生式。产生式的具体数据结构如下所示: typedef struct List { char leftVar[10]; //左侧字符 char rightVar[10]; //右侧字符 char endVar[10]; //终结符 char endRightVar[10]; //右侧后部字符 List *pNext; //next指针 }dfaList, *pdfaList; 添加完成后，程序将从产生式链表的第一个结点开始扫描，从右部提取出前端的终结符，具体方法是定义一个UCHAR型的指针，从前端向后扫描，如果是小写字母(默认是非终结符)，则将小写字母放入终结符集中，当扫描完前端后，指针继续后移，此时判断条件改变，如果不为“\0”，即字符串没有结束，则将字符串中剩下的字符存储到右侧后部字符中。转换成自动机时，将先前提取出的各字符串按照正确位置放置，并以函数的 a和V1，然后将提取出形式输出，例如:产生式V0—>aV1，分别提取出V0，来的V0，a和V1输出为f(V0，a)={V1}，如果产生式形如V1—>b类型，则将以f(V1，b)={Q}形式输出。三、程序设计程序流程图: 程序开始载入文法用户输入文法输入变量集读取文件内容输入终结符集输入开始符添加结点添加产生式添加结点是否继续添加是否转换为自动机程序结束错误判断模块: 根据输入的变量集、终结符集和开始符判断输入的文法是否为右线性文法，如果不是右线性文法，返回0，是右线性文法，则返回1。如果不正确，则不能插入结点，如果正确才可以将该产生式插入到链表中。 //判断产生式输入是否正确 int CDFADlg::ifCorrect() { UpdateData(TRUE); TCHAR *strTmp; int i,iFind=0,ifMeet=0; //ifmeet是否遇到大写字母 strTmp = m_Pro2.GetBuffer(0); if (*strTmp>'z' || *strTmp<'a') return 0; if (*strTmp>='a' && *strTmp<='z') { for (i=0;i<20;i++) { if (*strTmp==endVarArray[i] && endVarArray[i]!="") iFind=1; } if (1 == iFind) *strTmp++; else return 0; } if (*strTmp == '\0') return 1; if (*strTmp<'A' || *strTmp>'Z') return 0; CString strRight; while (*strTmp!='\0') { strRight+=*strTmp; strTmp++; } iFind = 0; for (i=0;i<20;i++) { if (strRight == varArray[i] && varArray[i]!="") { iFind=1; return 1; } } if (0 == iFind) return 0; } 产生式右部拆分: 将产生式的右部终结符和非终结符分开，分别存储在链表每个节点的不同属性值中，具体方法就是判断字母符号的大小写，如果是小写，就放入终结符属性中，然后将其后的字符放入非终结符属性中。 //产生式右部拆分 void CDFADlg::GetRightStr(CString strRightTmp) { TCHAR *strTmp; strTmp = strRightTmp.GetBuffer(0); while (*strTmp>='a' && *strTmp<='z') { dfa.endvar+=*strTmp; strTmp++; } while (*strTmp != '\0') { dfa.endrightvar += *strTmp; strTmp++; } } 转换自动机函数: 将先前提取出的各字符串按照正确位置放置，然后中间添加大括号，逗号等符号，以函数的形式输出。 //转换函数 void CDFADlg::OnTransfer() { UpdateData(TRUE); CString temp2; pdfaList p=dfa.pHead->pNext; m_OutPut.Format("G=<{%s,Q},{%s},f,%s,Q>",m_Variable,m_EndSym, m_StartSym); while (p!=NULL) { if (strcmp(p->endRightVar,"")==0) temp2.Format("\r\nf(%s,%s)={Q}",p->leftVar,p->endVar); else temp2.Format("\r\nf(%s,%s)={%s}",p->leftVar,p->endVar, p->endRightVar); m_OutPut+=temp2; p = p->pNext; } UpdateData(FALSE); } 四、运行截图五、心得体会

                    本文档为【右线性文法转换为有限自动机[教材]】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

右线性文法转换为有限自动机[教材]

你可能还喜欢