右线性文法转换为有限自动机

《右线性文法转换为有限自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理实习报告一191103魏晓东编译原理实习报告学院：计算机学院专业：计算机科学与技术-6-编译原理实习报告一191103魏晓东目录一、题目要求--------------------------02二、算法思想--------------------------02三、程序设计--------------------------03四、运行截图--------------------------06五、心得体会--------------------------06-6-编译原理实习报告一191103魏晓东右线性文法转换为有限自动机一、题目要求要求编

2、写一个程序，输入一个右线性文法，输出与该文法等价的有限自动机。二、算法思想首先输入变量集、终结符集和开始符，输入变量集和终结符集时用逗号隔开，否则会提示出错。然后输入右线性文法的产生式，输入时即区分出产生式的左部和右部，点击添加产生式按钮提取产生式的左部和右部。如果产生式不符合要求，则提示出错，添加的产生式使用链表存储，每个节点表示一个产生式，每次点击添加后，程序将会新生成一个结点来表示产生式。产生式的具体数据结构如下所示：typedefstructList{charleftVar[10];//左侧字符charrightVar[10];//右侧字符char

3、endVar[10];//终结符charendRightVar[10];//右侧后部字符List*pNext;//next指针}dfaList,*pdfaList;添加完成后，程序将从产生式链表的第一个结点开始扫描，从右部提取出前端的终结符，具体方法是定义一个UCHAR型的指针，从前端向后扫描，如果是小写字母（默认是非终结符），则将小写字母放入终结符集中，当扫描完前端后，指针继续后移，此时判断条件改变，如果不为“”，即字符串没有结束，则将字符串中剩下的字符存储到右侧后部字符中。转换成自动机时，将先前提取出的各字符串按照正确位置放置，并以函数的形式输出，

4、例如：产生式V0—>aV1，分别提取出V0，a和V1，然后将提取出来的V0，a和V1输出为f（V0，a）={V1}，如果产生式形如V1—>b类型，则将以f（V1，b）={Q}形式输出。-6-编译原理实习报告一191103魏晓东三、程序设计程序流程图：程序开始载入文法用户输入文法读取文件内容输入终结符集输入变量集输入开始符添加产生式是否继续添加转换为自动机是否程序结束添加结点添加结点-6-编译原理实习报告一191103魏晓东错误判断模块：根据输入的变量集、终结符集和开始符判断输入的文法是否为右线性文法，如果不是右线性文法，返回0，是右线性文法，则返回1。如果

5、不正确，则不能插入结点，如果正确才可以将该产生式插入到链表中。//判断产生式输入是否正确intCDFADlg::ifCorrect(){UpdateData(TRUE);TCHAR*strTmp;inti,iFind=0,ifMeet=0;//ifmeet是否遇到大写字母strTmp=m_Pro2.GetBuffer(0);if(*strTmp>'z'

6、

7、*strTmp<'a')return0;if(*strTmp>='a'&&*strTmp<='z'){for(i=0;i<20;i++){if(*strTmp==endVarArray[i]&&endVa

8、rArray[i]!="")iFind=1;}if(1==iFind)*strTmp++;elsereturn0;}if(*strTmp=='')return1;if(*strTmp<'A'

9、

10、*strTmp>'Z')return0;CStringstrRight;while(*strTmp!=''){strRight+=*strTmp;strTmp++;}iFind=0;for(i=0;i<20;i++){if(strRight==varArray[i]&&varArray[i]!=""){iFind=1;return1;-6-编译原理实习报告一

11、191103魏晓东}}if(0==iFind)return0;}产生式右部拆分：将产生式的右部终结符和非终结符分开，分别存储在链表每个节点的不同属性值中，具体方法就是判断字母符号的大小写，如果是小写，就放入终结符属性中，然后将其后的字符放入非终结符属性中。//产生式右部拆分voidCDFADlg::GetRightStr(CStringstrRightTmp){TCHAR*strTmp;strTmp=strRightTmp.GetBuffer(0);while(*strTmp>='a'&&*strTmp<='z'){dfa.endvar+=*strTmp;

12、strTmp++;}while(*strTmp!=''){df