实验二 语法分析(算符优先) (2).doc

编译原理实验报告实验名称：语法分析器设计专业：计算机科学与技术姓名：田莉莉学号：201117906语法分析算符优先分析程序一实验要求 选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR分析法 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 实习时间为6学时。二实验内容及要求（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表 输出到屏幕或者输出到文件）；（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为： G(E): E#E#EE+T | TTT*F |FF(E)|i(4)分析的句子为: (i+i)*i和i+i)*i三程序设计思想及实现步骤程序的设计思想： 按照编译原理教材提供的算法，本程序的设计主要实现三个主要的过程：（1） 求解FristVT集和LastVT集：利用CString数组存放VT集，利用数组下标对应非终结符关系；（2） 输出算符优先分析表：利用MFC中的ClistCtrl控件输出显示算符表，比利用二维数组对应其在内存中的关系。（3） 利用算符优先分析表进行归约：根据教材所给算法，并对其进行实现在屏幕上输出归约过程。实现步骤：1、为程序各变量设计存储形式，具体设计如下所示：CString m_strTElemT_LEN; /终结符CString m_strNTElemNT_LEN; /非终结符CMapStringToPtr m_mapProdu; /存放产生式CMapStringToPtr m_mapProduEX; /存放扩展产生式CString m_strFristVTNT_LEN;/fristVT集CString m_strLastVTNT_LEN;/lastVT集int m_nPriSheetT_LEN+1T_LEN+1;/优先表；无穷大表示空白，-1表示小于，0表示相等，1表示大于Find m_FSTACK_LEN;/bool数组CStrack m_stack;/堆栈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(|E+T|T|);m_mapProdu.SetAt(_T(E),(void*)str);CString* str1 = new CString;*str1 = _T(|T*F|F|);m_mapProdu.SetAt(_T(T),(void*)str1);CString* str2 = new CString ;*str2 = _T(|(E)|i|);m_mapProdu.SetAt(_T(F),(void*)str2);CString* str3 = new CString;*str3 = _T(|E+T|F+F|F*F|E+F|T|F|);m_mapProduEX.SetAt(_T(E),(void*)str3);CString* str4 = new CString;*str4 = _T(|T*F|F|);m_mapProduEX.SetAt(_T(T),(void*)str4);CString* str5 = new CString ;*str5 = _T(|(E)|i|(F)|);m_mapProduEX.SetAt(_T(F),(void*)str5);程序主要代码：void CGrammarAnalysisDlg:InitFind(void)int i,j;int k = 0;while(kSTACK_LEN)for(i=0;iNT_LEN;i+)for(j=0;ja. 和 P-Qa.void CGrammarAnalysisDlg:SearchPForFirtVT(Find& f)CString* str;m_mapProdu.Lookup(f.m_strNTerm,(void*&)str);int nFrist = 0;int nLen = 0;while(nLen+1 GetLength()/ P-a. P和 P-Qa.nFrist = nLen;nLen = str-Find(|,nFrist+1);CString strProduce = str-Mid(nFrist+1,nLen-nFrist-1);if(IsNT(strProduce,0) & IsT(strProduce,1)if(strProduce.GetAt(1) = f.m_strTerm)if(!f.m_bIsVT)f.m_bIsVT = TRUE;/CreateFristVT(f);m_stack.PushStack(f);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);/判断产生式第nLocat位置的字符是否是非终结符BOOL CGrammarAnalysisDlg:IsNT(CString strProduc,int nLocat)for(int i=0;iNT_LEN;i+)if(strProduc.GetAt(nLocat) = m_strNTElemi)return 1;return 0;/判断产生式第nLocat位置的字符是否是终结符BOOL CGrammarAnalysisDlg:IsT(CString strProduc, int nLocat)for(int i=0;iQvoid CGrammarAnalysisDlg:SearchQForFristVT(void)Find Q;CString strNT;CString* str;while(m_stack.m_nTop != 0)m_stack.PopStack(Q);POSITION pos = m_mapProdu.GetStartPosition();while(pos)m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str);int nFrist = 0;int nLen = 0;while(nLen+1 GetLength()nFrist = nLen;nLen = str-Find(|,nFrist+1);CString strProduce = str-Mid(nFrist+1,nLen-nFrist-1);if(IsNT(strProduce,0)if(strProduce.GetAt(0) = Q.m_strNTerm)/Q.m_bIsVT = TRUE;for(int i=0;i.aQ或P-.avoid CGrammarAnalysisDlg:SearchPForLastVT(Find& f)CString* str;m_mapProdu.Lookup(f.m_strNTerm,(void*&)str);int nFrist = 0;int nLen = 0;while(nLen+1 GetLength()/ P-a. P和 P-Qa.nFrist = nLen;nLen = str-Find(|,nFrist+1);CString strProduce = str-Mid(nFrist+1,nLen-nFrist-1);int nLocat = strProduce.GetLength();if(nLocat-20)if(IsNT(strProduce,nLocat-1) & IsT(strProduce,nLocat-2)if(strProduce.GetAt(nLocat-2) = f.m_strTerm)if(!f.m_bIsVT)f.m_bIsVT = TRUE;m_stack.PushStack(f);if(IsT(strProduce,nLocat-1)if(strProduce.GetAt(nLocat-1) = f.m_strTerm)if(!f.m_bIsVT)f.m_bIsVT = TRUE;m_stack.PushStack(f);/ /P-.Qvoid CGrammarAnalysisDlg:SearchQForLastVT(void)Find Q;CString strNT;CString* str;while(m_stack.m_nTop != 0)m_stack.PopStack(Q);POSITION pos = m_mapProdu.GetStartPosition();while(pos)m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str);int nFrist = 0;int nLen = 0;while(nLen+1 GetLength()nFrist = nLen;nLen = str-Find(|,nFrist+1);CString strProduce = str-Mid(nFrist+1,nLen-nFrist-1);int nLocat = strProduce.GetLength();if(IsNT(strProduce,nLocat-1)if(strProduce.GetAt(nLocat-1) = Q.m_strNTerm)/Q.m_bIsVT = TRUE;for(int i=0;iSTACK_LEN;i+)if(m_Fi.m_strNTerm = strNT & m_Fi.m_strTerm = Q.m_strTerm)if(!m_Fi.m_bIsVT)m_Fi.m_bIsVT = TRUE;m_stack.PushStack(m_Fi);break;void CGrammarAnalysisDlg:OnBnClickedBtnAnsysic()/ TODO: 在此添加控件通知处理程序代码/初始化列表控件/m_lbResult.AddString(_T(kjl);m_lst.SetExtendedStyle(LVS_EX_AUTOSIZECOLUMNS|LVS_EX_GRIDLINES);CRect rc;m_lst.GetClientRect(rc);int nWidth = rc.Width()/(T_LEN+2);int i = 0;m_lst.InsertColumn(i,_T(),LVCFMT_CENTER,nWidth);for(i=1;iT_LEN+1;i+)m_lst.InsertColumn(i,m_strTElemi-1,LVCFMT_CENTER,nWidth);m_lst.InsertColumn(i,_T(#),LVCFMT_CENTER,nWidth);for(i=0;iT_LEN;i+)m_lst.InsertItem(i,m_strTElemi);m_lst.InsertItem(i,_T(#);/FirstVTInitFind();/Find f(_T(+),_T(E);for(int i=0;iSTACK_LEN;i+)SearchPForFirtVT(m_Fi);SearchQForFristVT();CreateFristVT(m_F);/LastVTInitFind();/Find f(_T(+),_T(E);for(int i=0;iSTACK_LEN;i+)SearchPForLastVT(m_Fi);SearchQForLastVT();CreateLastVT(m_F);/遍历产生式构造算符优先表CString* str;POSITION pos =m_mapProdu.GetStartPosition();CString strNT;int nColumn;int nItem;while(pos)m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str);int nFrist = 0;int nLen = 0;while(nLen+1 GetLength()nFrist = nLen;nLen = str-Find(|,nFrist+1);CString strProduce = str-Mid(nFrist+1,nLen-nFrist-1);int nLocat = strProduce.GetLength();for(int i=0;inLocat-1;i+)if(IsT(strProduce,i) & IsT(strProduce,i+1)nItem = FindTLocat(strProduce.GetAt(i);nColumn = FindTLocat(strProduce.GetAt(i+1);m_nPriSheetnItemnColumn = 0;m_lst.SetItemText(nItem,nColumn+1,_T(=);if(i=nLocat-2 & IsT(strProduce,i) & IsT(strProduce,i+2) & IsNT(strProduce,i+1)nItem = FindTLocat(strProduce.GetAt(i);nColumn = FindTLocat(strProduce.GetAt(i+2);m_nPriSheetnItemnColumn = 0;m_lst.SetItemText(nItem,nColumn+1,_T(=);if(IsT(strProduce,i) & IsNT(strProduce,i+1)nItem = FindTLocat(strProduce.GetAt(i);int nNTLocat = FindNTLocat(strProduce.GetAt(i+1);int nVTLen = m_strFristVTnNTLocat.GetLength();for(int j=0;jnVTLen;j+)nColumn = FindTLocat(m_strFristVTnNTLocat.GetAt(j);m_nPriSheetnItemnColumn = -1;m_lst.SetItemText(nItem,nColumn+1,_T();if(IsNT(strProduce,i) & IsT(strProduce,i+1)nColumn = FindTLocat(strProduce.GetAt(i+1);int nNTLocat = FindNTLocat(strProduce.GetAt(i);int nVTLen = m_strLastVTnNTLocat.GetLength();for(int j=0;j);/处理#,行nItem = T_LEN;wchar_t ch = (;for(int i=0;iT_LEN+1;i+)switch(m_nPriSheetFindTLocat(ch)i)case 0:break;case INFI:break;case -1:m_nPriSheetnItemi = -1;m_lst.SetItemText(nItem,i+1,_T();break;/处理#，列nColumn = T_LEN;ch = );for(int i=0;iT_LEN;i+)switch(m_nPriSheetiFindTLocat(ch)case 0:break;case INFI:break;case -1:m_nPriSheetinColumn = -1;m_lst.SetItemText(i,nColumn+1,_T();break;/最后一角nItem = T_LEN;nColumn = T_LEN;m_nPriSheetnItemnColumn = 0;m_lst.SetItemText(nItem,nColumn+1,_T(=);void CGrammarAnalysisDlg:CreateFristVT(Find* F)for(int i=0;iSTACK_LEN;i+)if(Fi.m_bIsVT)for(int j=0;jNT_LEN;j+)if(Fi.m_strNTerm = m_strNTElemj)m_strFristVTj += Fi.m_strTerm;break;void CGrammarAnalysisDlg:CreateLastVT(Find* F)for(int i=0;iSTACK_LEN;i+)if(Fi.m_bIsVT)for(int j=0;jNT_LEN;j+)if(Fi.m_strNTerm = m_strNTElemj)m_strLastVTj += Fi.m_strTerm;break;int CGrammarAnalysisDlg:FindTLocat(wchar_t strT)for(int i=0;iT_LEN;i+)if(m_strTElemi = strT)return i;if(strT = #)return T_LEN;int CGrammarAnalysisDlg:FindNTLocat(wchar_t strNT)for(int i=0;iNT_LEN;i+)if(m_strNTElemi = strNT)return i;return 0;void CGrammarAnalysisDlg:OnBnClickedBtnAnasysic()/ TODO: 在此添加控件通知处理程序代码/清空列表控件int nCount = m_lbResult.GetCount();for(int i=0;inCount;i+)m_lbResult.DeleteString(0);/UpdateData();/清空栈m_stack.m_nTop = 0;/初值int j,k = 1;CString Q;m_stack.m_Chk = (_T(#);/int nLen = m_strSen.GetLength();m_strSen += _T(#);int i = -1;doi+;if(IsT(m_stack.m_Chk,0)j = k;else j = k-1;int nItem = FindTLocat(m_stack.m_Chj.GetAt(0);int nColumn = FindTLocat(m_strSeni);while(m_nPriSheetnItemnColumn = 1)int nItem1,nColumn1;do Q = m_stack.m_Chj;if(IsT(m_stack.m_Chj-1,0)j = j-1;else j= j-2;nItem1 = FindTLocat(m_stack.m_Chj.GetAt(0);nColumn1 = FindTLocat(Q.GetAt(0); while (m_nPriSheetnItem1nColumn1 != -1);CString strToProduce;for(int m = j+1;m=k;m+)strToProduce += m_stack.m_Chm;/输出产生式POSITION pos = m_mapProduEX.GetStartPosition();CString strNT;CString* str;while(pos)m_mapProduEX.GetNextAssoc(pos,strNT,(void*&)str);int nFrist = 0;int nLen = 0;while(nLen+1 GetLength()nFrist = nLen;nLen = str-Find(|,nFrist+1);CString strProduce = str-Mid(nFrist+1,nLen-nFrist-1);if(strProduce = strToProduce)CString strResult;strResult = strNT;strResult += _T(-);strResult += strToProduce;m_lbResult.AddString(strResult);k = j+1;m_sta