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

编译原理 实习报告一 191103 魏晓东 编译原理实习报 告学院： 计算机学院 专业：计算机科学与技术 目 录一、题目要求 - 02二、算法思想 - 02三、程序设计 - 03四、运行截图 - 06五、心得体会 - 06右线性文法转换为有限自动机一、题目要求要求编写一个程序，输入一个右线性文法，输出与该文法等价的有限自动机。二、算法思想首先输入变量集、终结符集和开始符，输入变量集和终结符集时用逗号隔开，否则会提示出错。然后输入右线性文法的产生式，输入时即区分出产生式的左部和右部，点击添加产生式按钮提取产生式的左部和右部。如果产生式不符合要求，则提示出错，添加的产生式使用链表存储，每个节点表示一个产生式，每次点击添加后，程序将会新生成一个结点来表示产生式。产生式的具体数据结构如下所示：typedef struct List char leftVar10; /左侧字符char rightVar10; /右侧字符char endVar10; /终结符char endRightVar10; /右侧后部字符List *pNext; /next指针dfaList, *pdfaList;添加完成后，程序将从产生式链表的第一个结点开始扫描，从右部提取出前端的终结符，具体方法是定义一个UCHAR型的指针，从前端向后扫描，如果是小写字母（默认是非终结符），则将小写字母放入终结符集中，当扫描完前端后，指针继续后移，此时判断条件改变，如果不为“0”，即字符串没有结束，则将字符串中剩下的字符存储到右侧后部字符中。转换成自动机时，将先前提取出的各字符串按照正确位置放置，并以函数的形式输出，例如：产生式V0aV1，分别提取出V0，a和V1，然后将提取出来的V0，a和V1输出为f（V0，a）=V1，如果产生式形如V1b类型，则将以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 (*strTmpz | *strTmp=a & *strTmp=z)for (i=0;i20;i+)if (*strTmp=endVarArrayi & endVarArrayi!=)iFind=1;if (1 = iFind)*strTmp+;elsereturn 0;if (*strTmp = 0)return 1;if (*strTmpZ)return 0;CString strRight;while (*strTmp!=0)strRight+=*strTmp;strTmp+;iFind = 0;for (i=0;i=a & *strTmppNext;m_OutPut.Format(G=,m_Variable,m_EndSym,m_StartSym);while (p!=NULL)if (strcmp(p-endRightVar,)=0)temp2.Format(rnf(%s,%s)=Q,p-leftVar,p-endVar); else temp2.Format(rnf(%s,%s)=%s,p-leftVar,p-endVar,p-endRightVar);m_OutPut+=temp2;p = p-pNext;UpdateData(FALSE);四、运行截