编译原理语法分析实验二

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

2、定文法，先求出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 _

3、DEBUG#define new 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(CAb

4、outDlg)protected: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*

5、pDX)CDialog:DoDataExchange(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

6、, pParent)/AFX_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)CDi

7、alog: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_MAPBEGIN_MESSAGE_MAP(CSyntaxAnalysisDlg, CDialog)/AFX_MSG_MAP(CSyntaxAnalysisDlg)ON_WM_SYSCOMMAND()ON_WM_PAI

8、NT()ON_WM_QUERYDRAGICON()ON_BN_CLICKED(IDC_BTN_Analysis, OnBTNAnalysis)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CSyntaxAnalysisDlg message handlersBOOL CSyntaxAnalysisDlg:OnInitDialog()CDialog:OnInitDialog();ASSERT(IDM_ABOUTBOX & 0xFFF0) = IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX < 0xF000);CMenu* pSysMenu = G

9、etSystemMenu(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 iconSetIcon(m_hIcon, FALSE);/ Set small

10、 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_G

11、l2=1;m_Gr2=""m_Gl3=2;m_Gr3="FK"m_Gl4=3;m_Gr4="*FK"m_Gl5=3;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:

12、OnSysCommand(UINT nID, LPARAM lParam)if (nID & 0xFFF0) = IDM_ABOUTBOX)CAboutDlg dlgAbout;dlgAbout.DoModal();elseCDialog:OnSysCommand(nID, lParam);void CSyntaxAnalysisDlg:OnPaint() if (IsIconic()CPaintDC dc(this); SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);/ Center icon in client

13、 rectangleint 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 icondc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPaint();CSyntaxAnalysisDlg:OnQueryD

14、ragIcon()return (HCURSOR) m_hIcon;void CSyntaxAnalysisDlg:Cal_Symbol()/求出能推出的非终结符int i,j,k,nEnd;CString Gr8;for (i=0;i<5;i+)m_nFlagsi=0;/置初值，0表示否for (i=0;i<8;i+)Gri=m_Gri;if (Gri="")m_nFlagsm_Gli=1;/1表示是，即能推出donEnd=0;for (i=0;i<5;i+)/检查每一个非终结符if (m_nFlagsi=1)/如果该非终结符能推出，就将所有表达式右部删

15、去该终结符for (j=0;j<8;j+) /查找每一个表达式if (Grj.IsEmpty()|Grj="") continue;for (k=0;k<Grj.GetLength();k+)/查找表达式右部的每一个字符if (Grj.GetAt(k)=m_VNi)/找到该终结符Grj=Grj.Left(k)+Grj.Right(Grj.GetLength()-k-1);/删去该终结符nEnd=1;break;if (Grj.IsEmpty() m_nFlagsm_Glj=1; /如果右部为空，就在表中填是 while(nEnd);void CSyntaxAna

16、lysisDlg:Cal_First()/求各非终结符的First集合int i,j,k,nEnd,n;CString strFirst;for (i=0;i<5;i+)for (j=0;j<6;j+)m_Firstij=0;for (i=0;i<8;i+)if (m_Gri.Left(2)="")m_Firstm_Gli5=1;continue;strFirst=m_Gri.GetAt(0);for (j=0;j<5;j+)if (strFirst=m_VTj)/如果右部第一个字符是终结符m_Firstm_Glij=1;break;do nEnd=

17、0;for (i=0;i<8;i+)n=0;strFirst=m_Gri.GetAt(0);do for (j=0;j<5;j+)if (strFirst=m_VNj)/如果右部第一个字符是非终结符for (k=0;k<6;k+)if (m_Firstm_Glik!=m_Firstjk)m_Firstm_Glik=m_Firstjk;nEnd=1;if (m_Firstj5=1&&n<m_Gri.GetLength()-1)/前一字符能推出，则下一字符的first集也包含于first(x)strFirst=m_Gri.GetAt(+n);elsestrF

18、irst=""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_Mij=""m_M00="TE"m_M03="TE"m_M11="+TE"m_M

19、14=""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_ListCtr

20、l.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.InsertCo

21、lumn(6,"#",LVCFMT_CENTER,50);for (i=0;i<5;i+)m_ListCtrl.InsertItem(i,m_VNi);for (j=0;j<6;j+)if (!m_Mij.IsEmpty()m_ListCtrl.SetItemText(i,j+1,""+m_Mij);void CSyntaxAnalysisDlg:OnBTNAnalysis() UpdateData(true);if (m_strCode.IsEmpty()MessageBox("请输入要分析的句子!","提醒&

22、quot;);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;CString sStack,sCode,str,strCode,strPro;i

23、nt 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;i&l

24、t;5;i+)if (sStack=m_VNi)break;if (i=5)m_strResult="不符合给定文法!"return false;for (j=0;j<5;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;pStack-;continue;strPro=strPro.Left(n)+str+strPro.Right(strPro.GetLength()-n-1);m_sPro="<= "+str