实验二--语法分析(算符优先)-(2)编译原理实验报告实验名称：语法分析器设计专业：计算机科学与技术姓名：田莉莉学号：201117906语法分析—算符优先分析程序一．实验要求⑴ 选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR 分析法⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。

⑶ 实习时间为6 学时。

二．实验内容及要求（ 1）根据给定文法，先求出 FirstVt 和 LastVt 集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）；（ 2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为：G（E ' ）: E'T #E#E—E+T | TT—T*F |FF—（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];// 终结符 //fristVT 集 //lastVT 集大表示空白1 表示小于0 表示相等1 表示Find m_F[STACK_LEN]; //bool2、为程序设计各个过程，具体设计如下所示：void CreateFristVT(Find* F); 建 FristVT 集void CreateLastVT(Find* F); 建 LastVT 集void SearchPForFirtVT(Find& f); P->Qa ….的产生式void SearchQForFristVT(void); 生式void SearchPForLastVT(Find& f); P->...a 的产生式void SearchQForLastVT(void); 生式OnBnClickedBtnAnasysic();3、对各个过程进行实现；4、调试运行并检验实验结果，结果如图 2.1和 2.2所示：CStrack m_stack; // 堆栈大 于 数组// 为每一个非终// 为每一个非终 // 搜索形如 P // 搜索形如 P->..// 搜索形如 P-> // 搜索形如 P->..图2.1 分析成功图内GrarTiinarABailys £井忻旬子图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(k<STACK_LEN){for(i=0;i<NT_LEN;i++) for(j=0;j<T_LEN;j++) {m_F[k].m_strNTerm = m_strNTElem[i];m_F[k].m_strTerm = m_strTElem[j];m_F[k].m_bIsVT = FALSE;k++;}}}// 查找P->a... 和P->Qa...void CGrammarAnalysisDlg::SearchPForFirtVT(Find& f){CString* str;m_mapProdu.Lookup(f.m_strNTerm,(void*&)str); intnFrist = 0;int nLen = 0; while(nLen+1 < str->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;if(!m_F[i].m_bIsVT)m_stack.PushStack(m_F[for(int i=0;i<T_LEN;i++) if(strProduc.GetAt(nLocat) == m_strTElem[i])return 1;if(strProduc.GetAt(nLocat) == '#')return 1; return 0;void CGrammarAnalysisDlg::SearchQForFristVT(void)void CGrammarAnalysisDlg::SearchPForLastVT(Find& f) CString strNT; CString* str;while(m_stack.m_nTop != 0)m_mapProdu.Lookup(f.m_strNTerm,(void*&)str);int nFrist = 0;m_stack.PopStack(Q);POSITION pos = m_mapProdu.GetStartPosition(); while(nLen+1 < str->GetLength())// P->a... P{// //P->...aQ P->...a}// 判断产生式第 //CreateFristVT(f); m_stack.PushStack(f)位置的字符是否是非终结符BOOL CGrammarAnalysisDlg::IsNT(CString strProduc,int nLocat)for(int i=0;i<NT_LEN;i++) if(strProduc.GetAt(nLocat) == m_strNTElem[i])return 1;return 0;m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str); int nFrist = 0; int nLen = 0;while(nLen+1 < str->GetLength())nFrist = nLen;nLen = str->Find('|',nFrist+1);CString strProduce = str->Mid(nFrist+1,nLen-n if(IsNT(strProduce,0))if(strProduce.GetAt(0) == Q.m_strNTerm)//Q.m_bIsVT = TRUE;for(int i=0;i<STACK_LEN;i++)if(m_F[i].m_strNTerm == strNT &&== Q.m_strTerm) //判断产生式第 nLocat 位置的字符是否是终结符 BOOL CGrammarAnalysisDlg::IsT(CString strProduc, int nLocat){m_F[i].m_bIsVT = TRUE; break;}//遍历所有的产生式 P->Q Find Q; CString* str;int nLen = 0;和 P->Qa...nLen = str->Find('|',nFrist+1);CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1); int nLocat = strProduce.GetLength();m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str); int nFrist = 0; int nLen = 0;while(nLen+1 < str->GetLength()){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);}}}nFrist = nLen;nLen = str->Find('|',nFrist+1);CString strProduce = str->Mid(nFrist+1,nLen-n int nLocat = strProduce.GetLength(); if(IsNT(strProduce,nLocat-1)){if(strProduce.GetAt(nLocat-1) == Q.m_strN{//Q.m_bIsVT = TRUE;for(int i=0;i<STACK_LEN;i++){if(m_F[i].m_strNTerm == strNT &&{if(!m_F[i].m_bIsVT){m_F[i].m_bIsVT = TRUE; m_stack.PushStack(m_F[ b reak;}}}}}Find Q; void CGrammarAnalysisDlg::OnBnClickedBtnAnsysic(){// TODO: 在此添加控件通知处理程序代码// 初始化列表控件 //m_lbResult.AddString(_T("kjl"));m_lst.SetExtendedStyle(LVS_EX_AUTOSIZECOLUMNS|LVS_EX_GRIDLPOSITION pos = m_mapProdu.GetStartPosition(); while(pos) C Rect rc; {m_lst.GetClientRect(rc);if(nLocat-2>0)if(IsNT(strProduce,nLocat-1) && IsT(strProduce,nLocat-2)) == Q.m_strTerm)}} }// //P-> Q }void CGrammarAnalysisDlg::SearchQForLastVT(void) }CString strNT; CString* str;while(m_stack.m_nTop != 0){m_stack.PopStack(Q);int nWidth = rc.Width()/(T_LEN+2);int i = 0;m_lst.InsertColumn(i,_T(""),LVCFMT_CENTER,nWidth); for(i=1;i<T_LEN+1;i++){nFrist = nLen;nLen = str->Find('|',nFrist+1);CString strProduce = str->Mid(nFrist+1,nLen-nFrist int nLocat = strProduce.GetLength(); for(int i=0;i<nLocat-1;i++)m_lst.InsertColumn(i,m_strTElem[i-1],LVCFMT_CENTER,nWidth); { }m_lst.InsertColumn(i,_T("#"),LVCFMT_CENTER,nWidth);for(i=0;i<T_LEN;i++){ m_lst.InsertItem(i,m_strTElem[i]);} m_lst.InsertItem(i,_T("#")); if(IsT(strProduce,i) && IsT(strProduce,i+1)){nItem = FindTLocat(strProduce.GetAt(i));nColumn = FindTLocat(strProduce.GetAt(i+1m_nPriSheet[nItem][nColumn] = 0;m_lst.SetItemText(nItem,nColumn+1,_T("=") }if(i<=nLocat-2 && IsT(strProduce,i) && IsT(s// IsNT(strProduce,i+1))//FirstVTInitFind();//Find f(_T("+"),_T("E"));for(int i=0;i<STACK_LEN;i++)SearchPForFirtVT(m_F[i]); SearchQForFristVT();CreateFristVT(m_F);//LastVTInitFind();//Find f(_T("+"),_T("E"));for(int i=0;i<STACK_LEN;i++)SearchPForLastVT(m_F[i]); 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 <str->GetLength()){{nItem = FindTLocat(strProduce.GetAt(i));nColumn = FindTLocat(strProduce.GetAt(i+2m_nPriSheet[nItem][nColumn] = 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.Getint nVTLen = m_strFristVT[nNTLocat].GetLefor(int j=0;j<nVTLen;j++){nColumn = FindTLocat(m_strFristVT[nNTm_nPriSheet[nItem][nColumn] = -1;m_lst.SetItemText(nItem,nColumn+1,_T }}if(IsNT(strProduce,i) && IsT(strProduce,i+1)){nColumn = FindTLocat(strProduce.GetAt(i+1int nNTLocat = FindNTLocat(strProduce.Getint nVTLen = m_strLastVT[nNTLocat].GetLenfor(int j=0;j<nVTLen;j++){nItem = FindTLocat(m_strLastVT[nNTLom_nPriSheet[nItem][nColumn] = 1;m_lst.SetItemText(nItem,nColumn+1,_T }m_lst.SetItemText(i,nColumn+1,_T(">")); break;}case 1:m_nPriSheet[i][nColumn] = 1;}// 处理‘ #',, 行 nItem = T_LEN; wchar_t ch = '(';for(int i=0;i<T_LEN+1;i++){switch(m_nPriSheet[FindTLocat(ch)][i]){case 0: break; case INFI: break; case -1:m_nPriSheet[nItem][i] = -1; m_lst.SetItemText(nItem,i+1,_T("<")); break; case 1:m_nPriSheet[nItem][i] = 1; m_lst.SetItemText(nItem,i+1,_T(">")); break;}}// 处理‘ #'，，列 nColumn = T_LEN;}// 最后一角nItem = T_LEN; nColumn = T_LEN;m_nPriSheet[nItem][nColumn] = 0;m_lst.SetItemText(nItem,nColumn+1,_T("="));}void CGrammarAnalysisDlg::CreateFristVT(Find* F){for(int i=0;i<STACK_LEN;i++){if(F[i].m_bIsVT){for(int j=0;j<NT_LEN;j++){if(F[i].m_strNTerm == m_strNTElem[j]){m_strFristVT[j] += F[i].m_strTerm; break;}}}}}void CGrammarAnalysisDlg::CreateLastVT(Find* F)ch = ')'; {for(int i=0;i<T_LEN;i++){switch(m_nPriSheet[i][FindTLocat(ch)]){case 0:break; case INFI:break; case -1:m_nPriSheet[i][nColumn] = -1;m_lst.SetItemText(i,nColumn+1,_T("<"));break;for(int i=0;i<STACK_LEN;i++){if(F[i].m_bIsVT){for(int j=0;j<NT_LEN;j++){if(F[i].m_strNTerm == m_strNTElem[j]){m_strLastVT[j] += F[i].m_strTerm; break;}}}int CGrammarAnalysisDlg::FindTLocat(wchar_t strT){for(int i=0;i<T_LEN;i++){if(m_strTElem[i] == strT) return i;}if(strT = '#')return T_LEN;}int CGrammarAnalysisDlg::FindNTLocat(wchar_t strNT){for(int i=0;i<NT_LEN;i++){if(m_strNTElem[i] == strNT) return i;}if(IsT(m_stack.m_Ch[k],0))j = k;else j = k-1;int nItem =FindTLocat(m_stack.m_Ch[j].GetAt(0)); int nColumn = FindTLocat(m_strSen[i]);return 0;}void CGrammarAnalysisDlg::OnBnClickedBtnAnasysic() {// TODO: 在此添加控件通知处理程序代码// 清空列表控件int nCount = m_lbResult.GetCount();for(int i=0;i<nCount;i++)m_lbResult.DeleteString(0);//UpdateData();// 清空栈m_stack.m_nTop = 0;// 初值int j,k = 1;CString Q;m_stack.m_Ch[k] = (_T("#"));////int nLen = m_strSen.GetLength();m_strSen += _T("#");int i = -1;do while(m_nPriSheet[nItem][nColumn] == 1){int nItem1,nColumn1;do{Q = m_stack.m_Ch[j];if(IsT(m_stack.m_Ch[j-1],0))j = j-1;else j= j-2;nItem1 = FindTLocat(m_stack.m_Ch[j].GetAt(0))nColumn1 = FindTLocat(Q.GetAt(0));} while (m_nPriSheet[nItem1][nColumn1] != -1);CString strToProduce;for(int m = j+1;m<=k;m++){strToProduce += m_stack.m_Ch[m];}// 输出产生式POSITION pos = m_mapProduEX.GetStartPosition();CString strNT;CString* str;while(pos){m_mapProduEX.GetNextAssoc(pos,strNT,(void*&)sint nFrist = 0;int nLen = 0;while(nLen+1 < str->GetLength()){nFrist = nLen;nLen = str->Find('|',nFrist+1);CString strProduce = str->Mid(nFrist+1,nLif(strProduce == strToProduce) {i++;CString strResult;strResult += _T("->"); strResult += strToProduce;m_lbResult.AddString(strResult);k = j+1;m_stack.m_Ch[k] = strNT; break;}}}nItem = FindTLocat(m_stack.m_Ch[j].GetAt(0)); nColumn = FindTLocat(m_strSen[i]);}nItem = FindTLocat(m_stack.m_Ch[j].GetAt(0)); nColumn = FindTLocat(m_strSen[i]); }五．结果分析及试验心得：本次实验做起来有点复杂，我认为重点在对教材所给算法的理解及个变量存 储形式的设计。