}
// //P->...aQ或P->...a
void CGrammarAnalysisDlg::SearchPForLastVT(Find& f) {
CString* str; int nFrist = 0; int nLen = 0; {
nFrist = nLen;
nLen = str->Find('|',nFrist+1); int nLocat = strProduce.GetLength(); if(nLocat-2>0)
m_mapProdu.Lookup(f.m_strNTerm,(void*&)str); }
}
}
}
}
}
nFrist = nLen;
nLen = str->Find('|',nFrist+1); if(IsNT(strProduce,0)) {
{
//Q.m_bIsVT = TRUE; {
{ }
}
{
break;
}
// //P->....Q
void CGrammarAnalysisDlg::SearchQForLastVT(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(IsT(strProduce,nLocat-1)) { } { } if(!f.m_bIsVT) { } f.m_bIsVT = TRUE; m_stack.PushStack(f); 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); CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1); { if(strProduce.GetAt(0) == Q.m_strNTerm) if(m_F[i].m_strNTerm == strNT && m_F[i].m_strTerm == Q.m_strTerm) if(!m_F[i].m_bIsVT) m_F[i].m_bIsVT = TRUE; if(strProduce.GetAt(nLocat-1) == f.m_strTerm) m_stack.PushStack(m_F[i]); while(nLen+1 < str->GetLength())// P->a... P和 P->Qa... CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1); } void CGrammarAnalysisDlg::OnBnClickedBtnAnsysic() { S); CRect rc; m_lst.GetClientRect(rc); int nWidth = rc.Width()/(T_LEN+2); // TODO: 在此添加控件通知处理程序代码 //初始化列表控件 //m_lbResult.AddString(_T(\ } } } } } } { nFrist = nLen; nLen = str->Find('|',nFrist+1); int i = 0; m_lst.InsertColumn(i,_T(\for(i=1;i m_lst.InsertColumn(i,_T(\for(i=0;i //Find f(_T(\ SearchPForFirtVT(m_F[i]); m_lst.InsertItem(i,m_strTElem[i]); m_lst.InsertColumn(i,m_strTElem[i-1],LVCFMT_CENTER,nWidth); CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1); { int nLocat = strProduce.GetLength(); if(IsNT(strProduce,nLocat-1)) { { //Q.m_bIsVT = TRUE; { { } } { break; //遍历产生式构造算符优先表 CString* str; POSITION pos =m_mapProdu.GetStartPosition(); CString strNT; int nColumn; int nItem; while(pos) { int nFrist = 0; int nLen = 0; while(nLen+1 < str->GetLength()) { nFrist = nLen; //LastVT InitFind(); //Find f(_T(\for(int i=0;i SearchPForLastVT(m_F[i]); SearchQForLastVT(); CreateLastVT(m_F); for(int i=0;i if(strProduce.GetAt(nLocat-1) == Q.m_strNTerm) if(m_F[i].m_strNTerm == m_lst.InsertItem(i,_T(\strNT && m_F[i].m_strTerm == Q.m_strTerm) if(!m_F[i].m_bIsVT) InitFind(); m_F[i].m_bIsVT = TRUE; for(int i=0;i SearchQForFristVT(); CreateFristVT(m_F); m_stack.PushStack(m_F[i]); m_lst.SetExtendedStyle(LVS_EX_AUTOSIZECOLUMNS|LVS_EX_GRIDLINE m_mapProdu.GetNextAssoc(pos,strNT,(void*&)str); nLen = str->Find('|',nFrist+1); int nLocat = strProduce.GetLength(); for(int i=0;i { } if(i<=nLocat-2 { } { } { } int int && FindTLocat(m_strLastVT[nNTLocat].GetAt(j)); } } } m_nPriSheet[nItem][nColumn] = 1; nItem = FindTLocat(strProduce.GetAt(i)); nColumn = FindTLocat(strProduce.GetAt(i+1)); } m_nPriSheet[nItem][nColumn] = 0; m_lst.SetItemText(nItem,nColumn+1,_T(\ } //处理‘#',,行 wchar_t ch = '('; for(int i=0;i IsT(strProduce,i) nItem = T_LEN; && CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1); m_lst.SetItemText(nItem,nColumn+1,_T(\ if(IsT(strProduce,i) && IsT(strProduce,i+1)) IsT(strProduce,i+2) && IsNT(strProduce,i+1)) nItem = FindTLocat(strProduce.GetAt(i)); { nColumn = FindTLocat(strProduce.GetAt(i+2)); switch(m_nPriSheet[FindTLocat(ch)][i]) m_nPriSheet[nItem][nColumn] = 0; nNTLocat nVTLen nColumn { } break; break; = m_nPriSheet[nItem][i] = -1; m_lst.SetItemText(nItem,i+1,_T(\= break; m_nPriSheet[nItem][i] = 1; m_lst.SetItemText(nItem,i+1,_T(\= break; m_lst.SetItemText(nItem,nColumn+1,_T(\ case 0: case INFI: if(IsT(strProduce,i) && IsNT(strProduce,i+1)) nItem = FindTLocat(strProduce.GetAt(i)); case -1: FindNTLocat(strProduce.GetAt(i+1)); m_strFristVT[nNTLocat].GetLength(); for(int j=0;j case 1: FindTLocat(m_strFristVT[nNTLocat].GetAt(j)); m_nPriSheet[nItem][nColumn] = -1; } //处理‘#’，，列 nColumn = T_LEN; ch = ')'; for(int i=0;i switch(m_nPriSheet[i][FindTLocat(ch)]) 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)); case 0: int nVTLen = m_strLastVT[nNTLocat].GetLength(); break; for(int j=0;j nItem case INFI: break; case -1: = } void CGrammarAnalysisDlg::CreateFristVT(Find* F) { } void CGrammarAnalysisDlg::CreateLastVT(Find* F) { for(int i=0;i if(F[i].m_bIsVT) { for(int j=0;j { for(int i=0;i if(F[i].m_bIsVT) { } for(int j=0;j { } break; } //最后一角 nItem = T_LEN; nColumn = T_LEN; m_nPriSheet[nItem][nColumn] = 0; m_lst.SetItemText(nItem,nColumn+1,_T(\ } m_nPriSheet[i][nColumn] = -1; break; m_nPriSheet[i][nColumn] = 1; break; } } } } break; m_lst.SetItemText(i,nColumn+1,_T(\ case 1: m_lst.SetItemText(i,nColumn+1,_T(\} int CGrammarAnalysisDlg::FindTLocat(wchar_t strT) { } int CGrammarAnalysisDlg::FindNTLocat(wchar_t strNT) { if(F[i].m_strNTerm == m_strNTElem[j]) m_strFristVT[j] += F[i].m_strTerm; } void CGrammarAnalysisDlg::OnBnClickedBtnAnasysic() { if(F[i].m_strNTerm == m_strNTElem[j]) m_strLastVT[j] += F[i].m_strTerm; // TODO: 在此添加控件通知处理程序代码 //清空列表控件 int nCount = m_lbResult.GetCount(); for(int i=0;i UpdateData(); //清空栈 m_stack.m_nTop = 0; //初值 int j,k = 1; CString Q; m_stack.m_Ch[k] = (_T(\// //int nLen = m_strSen.GetLength(); m_lbResult.DeleteString(0); for(int i=0;i if(m_strNTElem[i] == strNT) return i; for(int i=0;i if(strT = '#') return T_LEN; if(m_strTElem[i] == strT) return i; m_strSen += _T(\int i = -1; do { { nFrist = nLen; nLen = str->Find('|',nFrist+1); CString strProduce = i++; str->Mid(nFrist+1,nLen-nFrist-1); if(IsT(m_stack.m_Ch[k],0)) if(strProduce == strToProduce) j = k; { else j = k-1; CString strResult; int nItem = FindTLocat(m_stack.m_Ch[j].GetAt(0)); strResult = strNT; int nColumn = FindTLocat(m_strSen[i]); strResult += _T(\ strResult += strToProduce; m_lbResult.AddString(strResult); while(m_nPriSheet[nItem][nColumn] == 1) { k = j+1; int nItem1,nColumn1; m_stack.m_Ch[k] = strNT; do break; { } Q = m_stack.m_Ch[j]; } if(IsT(m_stack.m_Ch[j-1],0)) } j = j-1; nItem = FindTLocat(m_stack.m_Ch[j].GetAt(0)); else j= j-2; nColumn = FindTLocat(m_strSen[i]); // nItem1 = FindTLocat(m_stack.m_Ch[j].GetAt(0)); } nColumn1 = FindTLocat(Q.GetAt(0)); nItem = FindTLocat(m_stack.m_Ch[j].GetAt(0)); nColumn = FindTLocat(m_strSen[i]); } while (m_nPriSheet[nItem1][nColumn1] != -1); if(m_nPriSheet[nItem][nColumn] == -1 m_nPriSheet[nItem][nColumn] == 0) CString strToProduce; { for(int m = j+1;m<=k;m++) k += 1; { m_stack.m_Ch[k] = m_strSen[i]; strToProduce += m_stack.m_Ch[m]; } } else //输出产生式 { MessageBox(_T(\错误!\ POSITION pos = m_mapProduEX.GetStartPosition(); return; CString strNT; CString* str; } while(pos) { }while(m_strSen[i] != '#'); m_mapProduEX.GetNextAssoc(pos,strNT,(void*&)str); MessageBox(_T(\成功！\ int nFrist = 0; int nLen = 0; } while(nLen+1 < str->GetLength()) || 五．结果分析及试验心得： 本次实验做起来有点复杂，我认为重点在对教材所给算法的理解及个变量存储形式的设计。好的存储形式不仅可简化对数据的操作，也可以精简程序的设计过程。 下面是我的有关变量存储形式的设计： (1) 产生式：通过分析对已知的产生式进行了扩展，将产生式放入CMapStringToPtr的类型变量中存储，利用‘|’将统一非终结符的产生式隔开。使用时对CString的变量遍历，每次输出一个产生式； (2) 终结符和非终结符：采用数组的形式存储，利用下标对应每一个字符； (3) FristVT和LastVT：利CString类型的数组存放，每个位置的元素 对应了一个非终结符； (4) 算符优先表：利用二维数组存放其中无穷大表示空白，-1表示小于，0表示相等，1表示大于。 虽然在有些结构的设计上还不是太合理，但在实验中这种结构的设计给我完成实验提供了不上的便利。 关于程序的一点思考： 对于算符优先分析我们知道最大的便利就是可以跳过许多单非产生式，但是在程序的实现起来却是不太好处理，一般可采用两种方法：(1)通过每次输入的产生式，寻找扩展文法，在归约是利用扩展文法；这种方法增加了存储空间，但加快了归约过程的时间。（2）在归约过程中对每一产生式进行处理，这样节省了存储空间，但在时间效率上没有第一种的好。本次试验我采用的是第一种方法，但是个人觉得第二种方法更利于实现。 本次实验虽然做完了，但是程序的功能在很多方面还不完善，如不能自动输入产生式、输出的结果不直观等。这些都还需要在以后继续改进！