编译原理实验报告
实验名称：语法分析器设计
专业：计算机科学与技术 姓名：田莉莉 学号：201117906
语法分析—算符优先分析程序
一．实验要求
⑴ 选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR分析法
⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。
⑶ 实习时间为6学时。
二．实验内容及要求
（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表 输出到屏幕或者输出到文件）；
（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）
（3）给定表达式文法为： G(E’): E’→#E#
E→E+T | T T→T*F |F F→(E)|i
(4)分析的句子为: (i+i)*i和i+i)*i
三．程序设计思想及实现步骤
程序的设计思想：
按照编译原理教材提供的算法，本程序的设计主要实现三个主要的过程： （1） 求解FristVT集和LastVT集：利用CString数组存放VT集，利用数组
下标对应非终结符关系；
（2） 输出算符优先分析表：利用MFC中的ClistCtrl控件输出显示算符表，
比利用二维数组对应其在内存中的关系。
（3） 利用算符优先分析表进行归约：根据教材所给算法，并对其进行实现在
屏幕上输出归约过程。
实现步骤：
1、为程序各变量设计存储形式，具体设计如下所示：
CString m_strTElem[T_LEN]; CString m_strNTElem[NT_LEN]; CMapStringToPtr m_mapProdu;
//终结符 //非终结符 //存放产生式
CMapStringToPtr m_mapProduEX; CString m_strFristVT[NT_LEN]; CString m_strLastVT[NT_LEN]; int m_nPriSheet[T_LEN+1][T_LEN+1]; Find m_F[STACK_LEN]; CStrack m_stack;
//存放扩展产生式 //fristVT集 //lastVT集
//优先表；无穷大表示空白，-1表示小于，0表示相等，1表示大于 //bool数组 //堆栈
2、为程序设计各个过程，具体设计如下所示：
void CreateFristVT(Find* F); //为每一个非终结符创建FristVT集 void CreateLastVT(Find* F); //为每一个非终结符/创建LastVT集 void SearchPForFirtVT(Find& f); //搜索形如P->a….或P->Qa…. 的产生式 void SearchQForFristVT(void); //搜索形如P->....Q的产生式 void SearchPForLastVT(Find& f); //搜索形如P->...aQ或P->...a的产生式 void SearchQForLastVT(void); //搜索形如P->....Q的产生式 OnBnClickedBtnAnasysic(); //点击按钮启动分析
3、对各个过程进行实现；
4、调试运行并检验实验结果，结果如图2.1和2.2所示：
图2.1 分析成功图
图2.2 分析失败图
四．程序源码
产生式初始化：
//产生式
CString* str = new CString; *str = _T(\
m_mapProdu.SetAt(_T(\ CString* str1 = new CString; *str1 = _T(\
m_mapProdu.SetAt(_T(\CString* str2 = new CString ; *str2 = _T(\
m_mapProdu.SetAt(_T(\CString* str3 = new CString;
*str3 = _T(\ m_mapProduEX.SetAt(_T(\CString* str4 = new CString; *str4 = _T(\
m_mapProduEX.SetAt(_T(\CString* str5 = new CString ; *str5 = _T(\
m_mapProduEX.SetAt(_T(\
程序主要代码：
void CGrammarAnalysisDlg::InitFind(void) {
int i,j; int k = 0;
while(k { for(i=0;i for(j=0;j m_F[k].m_strNTerm = m_strNTElem[i]; } //查找 P->a... 和 P->Qa... void CGrammarAnalysisDlg::SearchPForFirtVT(Find& f) { CString* str; int nFrist = 0; int nLen = 0; { } nFrist = nLen; nLen = str->Find('|',nFrist+1); if(IsNT(strProduce,0) && IsT(strProduce,1)) { } if(IsT(strProduce,0)) { } if(strProduce.GetAt(0) == f.m_strTerm) { } if(!f.m_bIsVT) { } f.m_bIsVT = TRUE; //CreateFristVT(f); m_stack.PushStack(f); if(strProduce.GetAt(1) == f.m_strTerm) { } if(!f.m_bIsVT) { } f.m_bIsVT = TRUE; //CreateFristVT(f); m_stack.PushStack(f); m_mapProdu.Lookup(f.m_strNTerm,(void*&)str); } } m_F[k].m_strTerm = m_strTElem[j]; m_F[k].m_bIsVT = FALSE; k++; } //判断产生式第nLocat位置的字符是否是非终结符 BOOL CGrammarAnalysisDlg::IsNT(CString strProduc,int nLocat) { } BOOL CGrammarAnalysisDlg::IsT(CString strProduc, int nLocat) { } //遍历所有的产生式 P->Q void CGrammarAnalysisDlg::SearchQForFristVT(void) { POSITION pos = m_mapProdu.GetStartPosition(); while(pos) { m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str); int nFrist = 0; int nLen = 0; while(nLen+1 < str->GetLength()) { Find Q; CString strNT; CString* str; while(m_stack.m_nTop != 0) { m_stack.PopStack(Q); for(int i=0;i if(strProduc.GetAt(nLocat) == '#') return 1; return 0; if(strProduc.GetAt(nLocat) == m_strTElem[i]) return 1; return 0; for(int i=0;i if(strProduc.GetAt(nLocat) == m_strNTElem[i]) return 1; while(nLen+1 < str->GetLength())// P->a... P和 P->Qa... //判断产生式第nLocat位置的字符是否是终结符 CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1); {