编译原理-语法分析实验二(共10页).doc

《编译原理-语法分析实验二(共10页).doc》由会员分享，可在线阅读，更多相关《编译原理-语法分析实验二(共10页).doc（11页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上华北水利水电学院 编译原理 实验报告 20102011学年 第 二 学期 xxxx 级 计算机 专业班级： xxxxx 学号： xxxxx 姓名： xxx 一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。二、实验要求 选择最有代表性的语法分析方法，如LL（1）分析法、算符优先法或LR分析法 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 实习时间为6小时。三、实验内容选题1：使用预测分析法（LL（1）分析法）实

2、现语法分析： （1）根据给定文法，先求出first集合、follow集合和select集合，构造预测分析表（要求预测分析表输出到屏幕或者输出到文件）； （2）根据算法和预测分析表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为： G(E): STEE+TE | TFKK*FK |F(S)|i(4)分析的句子为： (i+i)*i和i+i)*i四、程序源代码专心-专注-专业#include stdafx.h#include SyntaxAnalysis.h#include SyntaxAnalysisDlg.h#ifdef _DEBUG#define ne

3、w DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endif/ CAboutDlg dialog used for App Aboutclass CAboutDlg : public CDialogpublic:CAboutDlg();/ Dialog Data/AFX_DATA(CAboutDlg)enum IDD = IDD_ABOUTBOX ;/AFX_DATA/ ClassWizard generated virtual function overrides/AFX_VIRTUAL(CAboutDlg)protecte

4、d:virtual void DoDataExchange(CDataExchange* pDX); / DDX/DDV support/AFX_VIRTUAL/ Implementationprotected:/AFX_MSG(CAboutDlg)/AFX_MSGDECLARE_MESSAGE_MAP();CAboutDlg:CAboutDlg() : CDialog(CAboutDlg:IDD)/AFX_DATA_INIT(CAboutDlg)/AFX_DATA_INITvoid CAboutDlg:DoDataExchange(CDataExchange* pDX)CDialog:DoD

5、ataExchange(pDX);/AFX_DATA_MAP(CAboutDlg)/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CAboutDlg, CDialog)/AFX_MSG_MAP(CAboutDlg)/ No message handlers/AFX_MSG_MAPEND_MESSAGE_MAP()/ CSyntaxAnalysisDlg dialogCSyntaxAnalysisDlg:CSyntaxAnalysisDlg(CWnd* pParent /*=NULL*/): CDialog(CSyntaxAnalysisDlg:IDD, pParent)/AFX_

6、DATA_INIT(CSyntaxAnalysisDlg)m_strCode = _T();m_strResult = _T();/AFX_DATA_INIT/ Note that LoadIcon does not require a subsequent DestroyIcon in Win32m_hIcon = AfxGetApp()-LoadIcon(IDR_MAINFRAME);void CSyntaxAnalysisDlg:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CSyn

7、taxAnalysisDlg)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_MAPBEGIN_MESSAGE_MAP(CSyntaxAnalysisDlg, CDialog)/AFX_MSG_MAP(CSyntaxAnalysisDlg)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERYDRAGICON()ON_BN_CLICKED(IDC_

8、BTN_Analysis, OnBTNAnalysis)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CSyntaxAnalysisDlg message handlersBOOL CSyntaxAnalysisDlg:OnInitDialog()CDialog:OnInitDialog();ASSERT(IDM_ABOUTBOX & 0xFFF0) = IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX AppendMenu(MF_SEPARATOR);pSysMenu-AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutM

9、enu);SetIcon(m_hIcon, TRUE);/ Set big iconSetIcon(m_hIcon, FALSE);/ Set small icon/ TODO: Add extra initialization here/初始化给定文法m_VN0=S;m_VN1=E;m_VN2=T;m_VN3=K;m_VN4=F;m_VT0=i;m_VT1=+;m_VT2=*;m_VT3=(;m_VT4=);m_Gl0=0;m_Gr0=TE;m_Gl1=1;m_Gr1=+TE;m_Gl2=1;m_Gr2=;m_Gl3=2;m_Gr3=FK;m_Gl4=3;m_Gr4=*FK;m_Gl5=3;

10、m_Gr5=;m_Gl6=4;m_Gr6=(S);m_Gl7=4;m_Gr7=i;Cal_Symbol();Cal_First();Cal_Follow();DrawMList();return TRUE; / return TRUE unless you set the focus to a controlvoid CSyntaxAnalysisDlg:OnSysCommand(UINT nID, LPARAM lParam)if (nID & 0xFFF0) = IDM_ABOUTBOX)CAboutDlg dlgAbout;dlgAbout.DoModal();elseCDialog:O

11、nSysCommand(nID, lParam);void CSyntaxAnalysisDlg:OnPaint() if (IsIconic()CPaintDC dc(this); SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);/ Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;GetClientRect(&rect);i

12、nt x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;/ Draw the icondc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPaint();CSyntaxAnalysisDlg:OnQueryDragIcon()return (HCURSOR) m_hIcon;void CSyntaxAnalysisDlg:Cal_Symbol()/求出能推出的非终结符int i,j,k,nEnd;CString Gr8;for (i=0;i5;i+)m_nFla

13、gsi=0;/置初值，0表示否for (i=0;i8;i+)Gri=m_Gri;if (Gri=)m_nFlagsm_Gli=1;/1表示是，即能推出donEnd=0;for (i=0;i5;i+)/检查每一个非终结符if (m_nFlagsi=1)/如果该非终结符能推出，就将所有表达式右部删去该终结符for (j=0;j8;j+) /查找每一个表达式if (Grj.IsEmpty()|Grj=) continue;for (k=0;kGrj.GetLength();k+)/查找表达式右部的每一个字符if (Grj.GetAt(k)=m_VNi)/找到该终结符Grj=Grj.Left(k)+G

14、rj.Right(Grj.GetLength()-k-1);/删去该终结符nEnd=1;break;if (Grj.IsEmpty() m_nFlagsm_Glj=1; /如果右部为空，就在表中填是 while(nEnd);void CSyntaxAnalysisDlg:Cal_First()/求各非终结符的First集合int i,j,k,nEnd,n;CString strFirst;for (i=0;i5;i+)for (j=0;j6;j+)m_Firstij=0;for (i=0;i8;i+)if (m_Gri.Left(2)=)m_Firstm_Gli5=1;continue;str

15、First=m_Gri.GetAt(0);for (j=0;j5;j+)if (strFirst=m_VTj)/如果右部第一个字符是终结符m_Firstm_Glij=1;break;do nEnd=0;for (i=0;i8;i+)n=0;strFirst=m_Gri.GetAt(0);do for (j=0;j5;j+)if (strFirst=m_VNj)/如果右部第一个字符是非终结符for (k=0;k6;k+)if (m_Firstm_Glik!=m_Firstjk)m_Firstm_Glik=m_Firstjk;nEnd=1;if (m_Firstj5=1&nm_Gri.GetLen

16、gth()-1)/前一字符能推出，则下一字符的first集也包含于first(x)strFirst=m_Gri.GetAt(+n);elsestrFirst=;break;if (j=5)break; while(!strFirst.IsEmpty(); while(nEnd);void CSyntaxAnalysisDlg:Cal_Follow()/求各非终结符的Follow集合void CSyntaxAnalysisDlg:DrawMList()/构造预测分析表int i,j;for (i=0;i5;i+)for (j=0;j6;j+)m_Mij=;m_M00=TE;m_M03=TE;m_

17、M11=+TE;m_M14=;m_M15=;m_M20=FK;m_M23=FK;m_M31=;m_M32=*FK;m_M34=;m_M35=;m_M40=i;m_M43=(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,*,L

18、VCFMT_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;i5;i+)m_ListCtrl.InsertItem(i,m_VNi);for (j=0;j6;j+)if (!m_Mij.IsEmpty()m_ListCtrl.SetItemText(i,j+1,+m_Mij);void CSyntaxAnalysisDlg:OnB

19、TNAnalysis() UpdateData(true);if (m_strCode.IsEmpty()MessageBox(请输入要分析的句子!,提醒);return;if (Analysis()m_strResult+=归约过程如下:rnrn+m_sPro.Right(m_sPro.GetLength()-3);UpdateData(false);/主要的程序算法 BOOL CSyntaxAnalysisDlg:Analysis()CString stack100;int pStack;/定义一个顺序栈stack0=#;stack1=S;pStack=1;/初始化栈int n=0;CSt

20、ring 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=stackpStack;/栈顶字符sCode=strCode.GetAt(n);/剩余输入串的首字符if (sStack=sCode)/匹配pStack-;n+;continue;for (i=0;i5;i+)if (sStack=m_VNi)

21、break;if (i=5)m_strResult=不符合给定文法!;return false;for (j=0;j5;j+)if (sCode=m_VTj)break;if (j=5&sCode!=#)m_strResult=不可识别的字符: +sCode;return false;str=m_Mij;if (str.IsEmpty()m_strResult=不符合给定文法!;return false;if (str=)strPro=strPro.Left(n)+strPro.Right(strPro.GetLength()-n-1);m_sPro= +strPro+rn+m_sPro;pS

22、tack-;continue;strPro=strPro.Left(n)+str+strPro.Right(strPro.GetLength()-n-1);m_sPro= +strPro+rn+m_sPro;pStack-;for (j=0;jstr.GetLength();j+)pStack+;stackpStack=str.GetAt(str.GetLength()-j-1);五、运行结果分析句子（i+i）*i正确并写出归约此次实验我继续使用VC+6.0平台编译程序，见面力求简洁，以满足实验功能为主。输入句子i+i)*i时候 程序判断 不符合给定文法 进行报错。当输入（i+i）*i 时候出

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