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

编译原理实验报告

实验名称：语法分析器设计

专业：计算机科学与技术
姓名：田莉莉
学号：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] //fristVT集
CString m_strLastVT[NT_LEN]; //lastVT集
int m_nPriSheet[T_LEN+1][T_LEN+1]; //优先表；无穷大表示空白，-1表示小于，0表示相等，1表示大于
Find m_F[STACK_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(krm = 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);
int nFrist = 0;
int nLen = 0;
whilenLen+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)
{
fm_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;i
{
for(int i=0;iQ
void 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 < str->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 {
if(!m_F[i].m_bIsVT)
{
m_F[i].m_bIsVT = TRUE;
m_stack.PushStack(m_F[i]);
break;
}
}
}

}
}
}
}
}
}
// //P->...aQ或P->...a
void CGrammarAnalysisDlg::SearchPForLastVT(Find& f)
{
CString* str;
m_mapProdu.Lookup(f.m_strNTerm,(void*&)str);
int nFrist = 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);
int nLocat = strProduce.GetLength();
ifnLocat-2>0)
{
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->....Q
void 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 < str->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;i strNT && m_F[i].m_strTerm == Q.m_strTerm)
{
if(!m_F[i].m_bIsVT)
{
m_F[i].m_bIsVT = TRUE;
m_stack.PushStack(m_F[i]);
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("E"));
for(int i=0;ig* 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())
{
nFrist = nLen;
nLen = str->Find('|',nFrist+1)
CString strProduce = str->Mid(nFrist+1,nLen-nFrist-1);
int nLocat = strProduce.GetLength();
for(int i=0;i m_nPriSheet[nItem][nColumn] = 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_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.GetAt(i+1));
int nVTLen = m_strFristVT[nNTLocat].GetLength();
for(int j=0;jce.GetAt(i+1));
int nNTLocat = FindNTLocat(strProduce.GetAt(i));
int nVTLen = m_strLastVT[nNTLocat].GetLength();
for(int j=0;jmn+1,_T(">"));
}
}

}
}

}
//处理‘#',,行
nItem = T_LEN;
wchar_t ch = '(';
for(int i=0;i1,_T("<"));
break;
case 1:
m_nPriSheet[nItem][i] = 1;
m_lst.SetItemText(nItem,i+1,_T(">"));
break;
}
}
//处理‘#’，，列
nColumn = T_LEN;
ch = ')';
for(int i=0;iase -1:
m_nPriSheet[i][nColumn] = -1;
m_lst.SetItemText(i,nColumn+1,_T("<"));
break;
case 1:
m_nPriSheet[i][nColumn] = 1;
m_lst.SetItemText(i,nColumn+1,_T(">"));
break;
}
}
//最后一角
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
}
}
}

void CGrammarAnalysisDlg::CreateLastVT(Find* F)
{
for(int i=0;immarAnalysisDlg::FindTLocat(wchar_t strT)
{
for(int i=0;i
return 0;
}
void CGrammarAnalysisDlg::OnBnClickedBtnAnasysic()
{
// TODO: 在此添加控件通知处理程序代码
//清空列表控件
int nCount = m_lbResult.GetCount();
for(int i=0;ik.m_Ch[k] = (_T("#"));
//
//int nLen = m_strSen.GetLength();
m_strSen += _T("#");
int i = -1;
do
{
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]);

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*&)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-nFrist-1);
if(strProduce == strToProduce)
{
CString strResult;
strResult = strNT;
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]);
if(m_nPriSheet[nItem][nColumn] == -1 || m_nPriSheet[nItem][nColumn] == 0)
{
k += 1;
m_stack.m_Ch[k] = m_strSen[i];
}
else
{
MessageBox(_T("错误!"));
return;

}

}while(m_strSen[i] != '#');
MessageBox(_T("成功！"));

}

五．结果分析及试验心得：
本次实验做起来有点复杂，我认为重点在对教材所给算法的理解及个变量存储形式的设计。好的存储形式不仅可简化对数据的操作，也可以精简程序的设计过程。
下面是我的有关变量存储形式的设计：
(1) 产生式：通过分析对已知的产生式进行了扩展，将产生式放入CMapStringToPtr的类型变量中存储，利用‘|’将统一非终结符的产生式隔开。使用时对CString的变量遍历，每次输出一个产生式；
(2) 终结符和非终结符：采用数组的形式存储，利用下标对应每一个字符；
(3) FristVT和LastVT：利CString类型的数组存放，每个位置的元素 对应了一个非终结符；
(4) 算符优先表：利用二维数组存放其中无穷大表示空白，-1表示小于，0表示相等，1表示大于。
虽然在有些结构的设计上还不是太合理，但在实验中这种结构的设计给我完成实验提供了不上的便利。
关于程序的一点思考：
对于算符优先分析我们知道最大的便利就是可以跳过许多单非产生式，但是在程序的实现起来却是不太好处理，一般可采用两种方法：(1)通过每次输入的产生式，寻找扩展文法，在归约是利用扩展文法；这种方法增加了存储空间，但加快了归约过程的时间。（2）在归约过程中对每一产生式进行处理，这样节省了存储空间，但在时间效率上没有第一种的好。本次试验我采用的是第一种方法，但是个人觉得第二种方法更利于实现。
本次实验虽然做完了，但是程序的功能在很多方面还不完善，如不能自动输入产生式、输出的结果不直观等。这些都还需要在以后继续改进！