编译原理-语法分析实验二.doc

华北水利水电学院 编译原理 实验报告
2010～2011学年 第 二 学期 xxxx 级 计算机 专业
班级： xxxxx 学号： xxxxx 姓名： xxx

一、实验目的
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。
二、实验要求
⑴ 选择最有代表性的语法分析方法，如LL（1）分析法、算符优先法或LR分析法
⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。
⑶ 实习时间为6小时。
三、实验内容
选题1：使用预测分析法（LL（1）分析法）实现语法分析：
（1）根据给定文法，先求出first集合、follow集合和select集合，构造预测分析表（要求预测分析表输出到屏幕或者输出到文件）；
（2）根据算法和预测分析表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）
（3）给定表达式文法为：
G(E): S→TE
E→+TE |
T→FK
K→*FK |
F→(S)|i
(4)分析的句子为：
(i+i)*i和i+i)*i
四、程序源代码

#include "stdafx.h"
#include "SyntaxAnalysis.h"
#include "SyntaxAnalysisDlg.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

///////////////////////////////////////////// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
CAboutDlg();

// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA

// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL

// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

// CSyntaxAnalysisDlg dialog

CSyntaxAnalysisDlg::CSyntaxAnalysisDlg(CWnd* pParent /*=NULL*/)
: CDialog(CSyntaxAnalysisDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CSyntaxAnalysisDlg)
m_strCode = _T("");
m_strResult = _T("");
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CSyntaxAnalysisDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CSyntaxAnalysisDlg)
DDX_Control(pDX, IDC_LIST1, m_ListCtrl);
DDX_Text(pDX, IDC_EDIT_Code, m_strCode);
DDX_Text(pDX, IDC_EDIT_Result, m_strResult);
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CSyntaxAnalysisDlg, CDialog)
//{{AFX_MSG_MAP(CSyntaxAnalysisDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BTN_Analysis, OnBTNAnalysis)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

// CSyntaxAnalysisDlg message handlers

BOOL CSyntaxAnalysisDlg::OnInitDialog()
{
CDialog::OnInitDialog();

ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}

SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon

// TODO: Add extra initialization here
//初始化给定文法
m_VN[0]="S";
m_VN[1]="E";
m_VN[2]="T";
m_VN[3]="K";
m_VN[4]="F";
m_VT[0]="i";
m_VT[1]="+";
m_VT[2]="*";
m_VT[3]="(";
m_VT[4]=")";
m_Gl[0]=0;m_Gr[0]="TE";
m_Gl[1]=1;m_Gr[1]="+TE";
m_Gl[2]=1;m_Gr[2]="ε";
m_Gl[3]=2;m_Gr[3]="FK";
m_Gl[4]=3;m_Gr[4]="*FK";
m_Gl[5]=3;m_Gr[5]="ε";
m_Gl[6]=4;m_Gr[6]="(S)";
m_Gl[7]=4;m_Gr[7]="i";

Cal_Symbol();
Cal_First();
Cal_Follow();
DrawMList();
return TRUE; // return TRUE unless you set the focus to a control
}

void CSyntaxAnalysisDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}

void CSyntaxAnalysisDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this);
SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;

// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
}
}

CSyntaxAnalysisDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}

void CSyntaxAnalysisDlg::Cal_Symbol() //求出能推出ε的非终结符
{
int i,j,k,nEnd;CString Gr[8];
for (i=0;i<5;i++)
m_nFlags[i]=0; //置初值，0表示否
for (i=0;i<8;i++)
{
Gr[i]=m_Gr[i];
if (Gr[i]=="ε")
{
m_nFlags[m_Gl[i]]=1; //1表示是，即能推出ε
}
}
do
{
nEnd=0;
for (i=0;i<5;i++) //检查每一个非终结符
{
if (m_nFlags[i]==1) //如果该非终结符能推出ε，就将所有表达式右部删去该终结符
{
for (j=0;j<8;j++) //查找每一个表达式
{
if (Gr[j].IsEmpty()||Gr[j]=="ε") continue;
for (k=0;k<Gr[j].GetLength();k++) //查找表达式右部的每一个字符
{
if (Gr[j].GetAt(k)==m_VN[i]) //找到该终结符
{
Gr[j]=Gr[j].Left(k)+Gr[j].Right(Gr[j].GetLength()-k-1); //删去该终结符
nEnd=1;
break;
}
}
if (Gr[j].IsEmpty()) m_nFlags[m_Gl[j]]=1; //如果右部为空，就在表中填是
}

}
}
} while(nEnd);
}

void CSyntaxAnalysisDlg::Cal_First() //求各非终结符的First集合
{
int i,j,k,nEnd,n;CString strFirst;
for (i=0;i<5;i++)
{
for (j=0;j<6;j++)
m_First[i][j]=0;
}
for (i=0;i<8;i++)
{
if (m_Gr[i].Left(2)=="ε")
{
m_First[m_Gl[i]][5]=1;
continue;
}
strFirst=m_Gr[i].GetAt(0);
for (j=0;j<5;j++)
{
if (strFirst==m_VT[j]) //如果右部第一个字符是终结符
{
m_First[m_Gl[i]][j]=1;
break;
}
}
}
do
{
nEnd=0;
for (i=0;i<8;i++)
{
n=0;
strFirst=m_Gr[i].GetAt(0);
do
{
for (j=0;j<5;j++)
{
if (strFirst==m_VN[j]) //如果右部第一个字符是非终结符
{
for (k=0;k<6;k++)
{
if (m_First[m_Gl[i]][k]!=m_First[j][k])
{
m_First[m_Gl[i]][k]=m_First[j][k];
nEnd=1;
}
}
if (m_First[j][5]==1&&n<m_Gr[i].GetLength()-1) //前一字符能推出ε，则下一字符的first集也包含于first(x)
strFirst=m_Gr[i].GetAt(++n);
else
strFirst="";
break;
}
}
if (j==5) break;
} while(!strFirst.IsEmpty());
}
} while(nEnd);
}

void CSyntaxAnalysisDlg::Cal_Follow() //求各非终结符的Follow集合
{

}

void CSyntaxAnalysisDlg::DrawMList() //构造预测分析表
{
int i,j;
for (i=0;i<5;i++)
{
for (j=0;j<6;j++)
{
m_M[i][j]="";
}
}
m_M[0][0]="TE";m_M[0][3]="TE";
m_M[1][1]="+TE";m_M[1][4]="ε";m_M[1][5]="ε";
m_M[2][0]="FK";m_M[2][3]="FK";
m_M[3][1]="ε";m_M[3][2]="*FK";m_M[3][4]="ε";m_M[3][5]="ε";
m_M[4][0]="i";m_M[4][3]="(S)";
m_ListCtrl.SetExtendedStyle(LVS_EX_GRIDLINES);
m_ListCtrl.InsertColumn(0,"",LVCFMT_CENTER,50);
m_ListCtrl.InsertColumn(1,"i",LVCFMT_CENTER,50);
m_ListCtrl.InsertColumn(2,"+",LVCFMT_CENTER,50);
m_ListCtrl.InsertColumn(3,"*",LVCFMT_CENTER,50);
m_ListCtrl.InsertColumn(4,"(",LVCFMT_CENTER,50);
m_ListCtrl.InsertColumn(5,")",LVCFMT_CENTER,50);
m_ListCtrl.InsertColumn(6,"#",LVCFMT_CENTER,50);
for (i=0;i<5;i++)
{
m_ListCtrl.InsertItem(i,m_VN[i]);
for (j=0;j<6;j++)
{
if (!m_M[i][j].IsEmpty())
m_ListCtrl.SetItemText(i,j+1,"→"+m_M[i][j]);
}
}
}

void CSyntaxAnalysisDlg::OnBTNAnalysis()
{
UpdateData(true);
if (m_strCode.IsEmpty())
{
MessageBox("请输入要分析的句子!","提醒");
return;
}
if (Analysis())
m_strResult+="归约过程如下:\r\n\r\n"+m_sPro.Right(m_sPro.GetLength()-3);
UpdateData(false);
}
//主要的程序算法
BOOL CSyntaxAnalysisDlg::Analysis()
{
CString stack[100];int pStack; //定义一个顺序栈
stack[0]="#";stack[1]="S";pStack=1; //初始化栈
int n=0;CString sStack,sCode,str,strCode,strPro;
int i,j;
strCode=m_strCode+"#"; //输入串
m_sPro="<= S";strPro="S";
while (1)
{
if (n==m_strCode.GetLength()&&pStack==0) //分析成功
{
m_strResult="符合给定文法.";
return true;
}
sStack=stack[pStack]; //栈顶字符
sCode=strCode.GetAt(n); //剩余输入串的首字符
if (sStack==sCode) //匹配
{
pStack--;
n++;
continue;
}
for (i=0;i<5;i++)
{
if (sStack==m_VN[i])
break;
}
if (i==5)
{
m_strResult="不符合给定文法!";
return false;
}
for (j=0;j<5;j++)
{
if (sCode==m_VT[j])
break;
}
if (j==5&&sCode!="#")
{
m_strResult="不可识别的字符: "+sCode;
return false;
}
str=m_M[i][j];
if (str.IsEmpty())
{
m_strResult="不符合给定文法!";
return false;
}
if (str=="ε")
{
strPro=strPro.Left(n)+strPro.Right(strPro.GetLength()-n-1);
m_sPro="<= "+strPro+"\r\n"+m_sPro;
pStack--;
continue;
}
strPro=strPro.Left(n)+str+strPro.Right(strPro.GetLength()-n-1);
m_sPro="<= "+strPro+"\r\n"+m_sPro;
pStack--;
for (j=0;j<str.GetLength();j++)
{
pStack++;
stack[pStack]=str.GetAt(str.GetLength()-j-1);
}
}

五、运行结果

分析句子（i+i）*i正确并写出归约
此次实验我继续使用VC++6.0平台编译程序，见面力求简洁，以满足实验功能为主。

输入句子i+i)*i时候 程序判断 不符合给定文法 进行报错。
当输入（i+i）*i@ 时候出现 不合法的字符@ 程序就会报错。

六、小结（不少于100字）

这是第二次编译原理的实验；其主要目的是通过通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。加深对课堂教学的理解，深刻理解语法分析的整个过程，提高语法分析方法的实践能力。经历过第一次的词法分析之后，我决定本次实验继续采用VC++6.0的编译平台；在保持自己编程风格的简洁、朴实的前提下， 尽我所能追求完善程序的界面。
在编写过程中遇到的主要问题就是如何正确分析first集合、follow集合和select集合，构造预测分析表；另外一个难点就是根据算法和预测分析表分析给定表达式是否是该文法识别的正确的算术表达式。在要求程序能够完成以上的功能的同时，正确报告出错类型和错误位置着实很费力气。在编写过程中我的主要精力在于这两项功能的算法实现；最后经过查阅资料和向同学讨论商量使得问题得到了最终的解决。
概括来讲，这一次语法分析程序很有的难度（比第一次的词法分析难一些）， 但是有了上一次实验的经验可以遵循，编写过程倒也还顺利；关键的难题在于将 编译原理课程所学的知识与实际编程操作有机的结合起来。我也通过这次实验得到了这方面的锻炼。在今后的学习中，在课余时间还需要经常加以练习才可以得到更好的提高和更深层次的理解。在此基础上可以根据自己的兴趣 多做课外的延伸和练习。