编译原理课程设计

1、编译原理课程设计报告太 原 学 院课程设计报告书课程名称 编译原理 设计题目 构造LR(0)分析法语法分析器 专业班级 计算机科学与技术13-4班 学 号 20130905405 姓 名 王芳芳 指导教师 吴海丽 2016年 12 月 15日1目 录一、课题概述1二、系统分析221 本课程设计的知识点22.1.1 词法编译器功能22.1.2 词法分析器的设计22.1.3 动态模拟算法的基本功能22.1.4 LR分析器的构成22. 2解决问题的基本思路323 需解决的关键技术324 功能模块框图3三、系统设计431 算法描述43. 2 实现方法63.2.1 构造分析表63.2.2程序设计关键63

2、.2.3 LR(0)项目集规范族的构造633 详细流程图7四、代码编写8 4. 1 生成分析表代码8 4. 2分析句子代码10五、调试分析14六、运行与调试15总 结 17参考文献181、 课题概述 编译原理是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。语法分析是编译过程的第二阶段，是编译器前端的核心组成部分，在编译系统中起到了至关重要的作用。自底向上的语法分析与自顶向下的语法分析相比，对将要分析的源程序有着更大的分析空间，从而受到了广泛的

3、运用。 本次课程设计的目标即是利用所学过的编译原理的知识，利用LR(0)分析法，用C语言写出一个简单的LR(0)语法分析器。该语法分析器所要完成的功能是，对录入的文法判断它是否为LR(0)文法，如果是输出LR (0)分析表；在给定文法的情况下，能够利用LR(0)分析表，对用户输入的一串字符串用LR(0)分析法进行分析，判断该字符串是否为符合给定文法的一个句子，建立文法及其LR分析表表示的数据结构，设计并实现一个LR(0)的分析器。编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析

4、过程显示及四元式序列程序。整个编译程序分为三部分：词法分析部分、语法分析处理及四元式生成部分、输出显示部分。一个程序设计语言就是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输人串的k个(k>=0)符号就可惟一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR

5、分析过程是一种规范归约过程。 二、系统分析2.1 本课程设计涉及的知识点2.1.1 词法编译器功能（1）导入任意文法，也可以自己输入。（2）输出文法的分析过程，以及判断是否为LR (0)文法，输出分析表。（3）输入句子，进行语法分析。（4）输出结构树。2.1.2 词法分析器的设计(1)写出该语言的词法规则。(2)把词法规则转换为相应的状态转换图。(3)把各转换图的初态连在一起，构成识别该语言的自动机。(4)设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终态，送出二元式。2.1.3 动态模拟算法的基本功能（1

6、）输入LR分析表和一个句子。（2）输出LR总控程序。（3）输出依据句子构对应的语法树的过程。（4）设计一个给定LR分析表，输入一个句子，能由依据LR分析表输出与句子对应的语法树，能对语法树生成过程进行模拟。（5）输入句子：bccd#。（6）根据文法产生的LR分析表。（7）输出结果2.1.4 LR分析器的构成一个LR分析器由个部分组成（1）总控程序，也可以称为驱动程序。对所有的LR分析器，总控程序都是相同的。（2）分析表或分析函数。不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可以分为动作（ACTION）表和状态（GOTO）表两个部分，它们都可用二维数组表示。（

7、3）分析栈，包括文法符号和相应的状态栈。它们均是先进后出栈。分析器的动作由栈顶状态和当前输入符号所决定（LR(0)分析器不需向前查看输入符号）。2.2解决问题的基本思路1、用构造一个状态转换函数实现状态转换。2、再通过函数构造一个移进归约函数实现移进规约动作。3、采用构造一个打印LR分析器的工作过程函数实现输出。 在规范规约的过程中，一方面记住已移进和规约出的整个符号串，另一方面根据所用的产生式推测可能碰到的输入符号。每一项ACTION(s，a)所规定的动作不外是下述四种可能之一：（1）移进（2）规约（3）接受（4）报错。2.3 需解决的关键技术（1）词法编译器。（2）交互式面向对象的词法编译

8、器基本功能是。（3）根据规约规则对字符进行归约。 （4）符合条件时采取移进动作。2.4 功能模块框图运行程序给出该程序所运用的文法和LR分析表用户输入字符串程序给出结果图1 功能模块框图三、系统设计3.1 算法描述1、已知文法G(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi2、LR(0)分析表的构造算法如下：假设已构造出LR(0)项目集规范族为：C=I0,I1, , In，其中Ik为项目集的名字，k为状态名，令包含S·S项目的集合Ik的下标k为分析器的初始状态。那么分析表的ACTION表和GOTO表构造步骤为：(1) 若项目A·a属于I

9、k且转换函数GO(Ik,a)= Ij，当a为终结符时则置ACTIONk,a为Sj，其动作含意为将终结符a移进符号栈，状态j进入状态栈，(相当状态k时遇a转向状态j)。(2) 若项目A· 属于Ik，则对任何终结符a 和'#'号置ACTIONk,a和ACTIONk,#为"rj"，j为在文法G中某产生式A的序号。rj动作的含义是把当前文法符号栈顶的符号串归约为A，并状态栈指针从栈顶向下移动|的长度 , 文法符号栈从栈顶弹出|个符号，非终结符A变为当前面临的符号。(3) 若GO(Ik,A)Ij，则置GOTOk,A为"j"，其中A为非终结

10、符，表示当前状态为"k"时，遇文法符号A时状态应转向j，因此A移入文法符号栈，j移入状态栈。(4) 若项目SS·属于Ik，则置ACTIONk,#为"acc"，表示接受。(5) 凡不能用上述方法填入的分析表的元素，均应填上"报错标志"。为了表的清晰我们仅用空白表示错误标志。根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分析表为LR(0)分析表，能用LR(0)分析表的分析器称为LR(0)分析器，能构造LR(0)分析表的文法称为LR(0)文法。3、 产生如下所示的LR分析表 STATEACTIONGOTOabcd#ET

11、F0S2S311acc2S4S1063S5S474S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6 表 1 LR分析表这张分析表包括两个部分，一是“动作”（ACTION）表，另一是“状态转换”（GOTO）表。ACTION(S,a)规定了当状态S面临输入符号a时应采取什么动作。GOTO（S，X）规定了状态S面对文法符号X（终结符或非终结符）时下一状态是什么。显然，GOTO(S，X)定义了一个以文法符号为字母表的DFA。其中，S0为分析器的初态；为句子的左括号；a1a2an为输入串；其

12、后的为结束符（句子右括号）。分析过程每步的结果可表示为：（S0S1Sm，#X1X2Xm ai, ai+1an#）。3.2 实现方法3.2.1 构造分析表LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。构造一个int型二维数组table139,用于存放LR分析表。并初始化。作者这样规定：011 表示 状态Sj，其中0对应S0，1对应S12126 表示 规约Rj，其中21对应R1，22对应R212 表示 “接受”。-1 表示 规约出错，报错。3.2.2程序设计关键（1）在输入串(句子)输入的过程中，涉及到一个压栈的问题

13、。但是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反，这样需要先弹出的反而在栈底。为了既要保证字符串输入，又要让输入的字符串存储顺序与输入的字符串相反。采取以下措施：先将输入的字符串压入符号栈symbol中，然后符号栈弹出的字符再压入输入串栈instr中，这样实现了输入串的倒序存储。（2）状态栈和符号栈输出（遍历）过程均采取自栈底到栈顶的顺序，而输入串栈则是采取自栈顶到栈底的顺序输出。3.2.3 LR(0)项目集规范族的构造识别活前辍的NFA我们可以利用子集法将其确定化。对确定化后的DFA如果把每个子集中所含状态集对应的项目写在新的状态中。对于构成识别一个文法活前缀的DFA项目集(状态)

14、的全体称为这个文法的LR(0)项目集规范族，我们可以分析每个状态中项目集的构成，不难发现如下规律：若状态中包含形如A·B的项目，则形如B·的项目也在此状态内。例如：0状态中项目集为S·E，E·aA, E·bB。回顾由NFA确定化到DFA时，E·aA和E·bB正是属于S·E的闭包中。因而，可引入闭包函数(CLOSURE)来求DFA一个状态的项目集。若文法G已拓广为G，而S为文法G的开始符号，拓广后增加产生式SS。如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE(I)如下：(1) I的项目均在CLOSURE

15、(I)中。(2) 若A·B属于CLOSURE(I)，则每一形如B·的项目也属于CLOSURE(I)。(3) 重复(2)直到不出现新的项目为止。即CLOSURE(I)不再扩大。由此，我们可以很容易构造出初态的闭包，即S·S属于I，再按上述三点求其闭包。3.3 详细流程图初始化状态栈，符号栈，输入串栈输入串各字符压栈 求下一状态符号ii = goto_char(status_p,instr_p)规约出错！异常中止！i = = -1 ?规约成功！退出i = = 12 ?规约动作：1 求出i对应规约规则右部字符串长度x = ri-21.y2 在符号栈和状态栈中弹出x个字符

16、。然后将该规约规则左部压入输入串栈i>0 && i<=11 移进动作：1 将现状态i压栈push(status_p,i)2 将当前输入串字符压入符号栈a = pop(instr_p)push(symbol_p,a)打印该步工作过程图3.1 LR分析器设计流程图图2 LR分析器设计流程图四、代码编写4.1 生成分析表代码void CLR0ForWinDlg:OnGtable() CTableDlg dlg;dlg.SetControlInfo(IDC_EXPLORER1, RESIZE_BOTH);dlg.SetControlInfo(IDOK, ANCHORE_BO

17、TTOM | ANCHORE_RIGHT);dlg.SetControlInfo(IDC_EXPORT, ANCHORE_BOTTOM | ANCHORE_RIGHT);dlg.SetControlInfo(IDC_ANALYZE, ANCHORE_BOTTOM | ANCHORE_RIGHT);string temp = ""CString t;for(int i = 0; i < m_vtlist.GetCount(); i+)m_vtlist.GetText(i,t);/temp.push_back(t.GetAt(0);temp += t.GetAt(0);d

18、lg.g.SetVt(temp);temp = ""for(i = 0; i < m_vnlist.GetCount(); i+)m_vnlist.GetText(i,t);/temp.push_back(t.GetAt(0);temp += t.GetAt(0);dlg.g.SetVn(temp);m_startedit.GetWindowText(t);if (t = "")MessageBox("输入的文法有误，请检查！", "错误",MB_OK | MB_ICONSTOP);return;dlg.g.

19、SetStart(t.GetAt(0);temp = ""for(i = 0; i < m_plist.GetCount(); i+)temp = ""m_plist.GetText(i,t);for(int j = 0; j < t.GetLength(); j +)/temp.push_back(t.GetAt(j);temp += t.GetAt(j);dlg.g.AddPrecept(temp);if(dlg.g.IsGrammarLegal()dlg.g.GenerateLR0Table();dlg.DoModal();elseMe

20、ssageBox("输入的文法有误，请检查！", "错误",MB_OK | MB_ICONSTOP);4.2分析句子代码void CAnalyzeDlg:OnButton1() / TODO: Add your control notification handler code hereUpdateData(TRUE);m_pTree->m_tree.DeleteAllItems();for(int i = 0; i < m_input.GetLength(); i +)if (!m_g.IsInVt(m_input.GetAt(i)Mess

21、ageBox("输入的句子不全部由终结符组成", "错误", MB_OK | MB_ICONSTOP);return;assert(TreeStack.empty();m_input += "#"char szTempPathMAX_PATH; char szTempNameMAX_PATH; if (m_strTempFilename != ""):DeleteFile(m_strTempFilename.c_str();:GetTempPath(100,szTempPath);:GetTempFileName(

22、szTempPath,"LR0",0,szTempName);m_strTempFilename = szTempName;CStdioFile out;out.Open(szTempName, CFile:modeCreate | CFile:modeWrite);out.WriteString("<html>n");out.WriteString("<head>n");out.WriteString("<title>Untitled Document</title>n&qu

23、ot;);out.WriteString("<meta http-equiv="Content-Type" content="text/html; charset=gb2312">n");out.WriteString("</head>n");out.WriteString("<body bgcolor="#FFFFFF" text="#000000">n");out.WriteString("<tabl

24、e border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111">n");out.WriteString("<tr>n<td nowrap>&nbsp;步骤&nbsp;</td>n<td nowrap>&nbsp;状态栈</td>n<td nowr

25、ap>&nbsp;符号栈&nbsp;</td>n<td nowrap>&nbsp;输入串&nbsp;</td>n<td nowrap>&nbsp;ACTION&nbsp;</td>n<td nowrap >&nbsp;GOTO&nbsp;</td>n </tr>n");vector <int> Status;vector <char> Symbol;int iStep = 1;int iPos =

26、 0;Status.push_back(0);Symbol.push_back('#');Pair ToDo;bool bErrorFlag = false;bool bGoOn = true;while (bGoOn) && (!bErrorFlag)assert(iPos < m_input.GetLength();assert(Status.size() = Symbol.size();ToDo = m_g.GetAction(Status.back(), m_input.GetAt(iPos);int i, j;switch (ToDo.one)c

27、ase 'S':out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, -1);Symbol.push_back(m_input.GetAt(iPos);Status.push_back(ToDo.two);iPos+;break;case 'R':j = m_g.GetGoTo(StatusStatus.size()-m_g.GetPrecept(ToDo.two).GetRight().length()-1, m_g

28、.GetPrecept(ToDo.two).GetLeft()0);assert(j != -1);out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, j);for(i = 0; i < m_g.GetPrecept(ToDo.two).GetRight().length(); i+)Status.pop_back();Symbol.pop_back();Symbol.push_back(m_g.GetPrecept(ToDo.two).Ge

29、tLeft()0);Status.push_back(j);TreeStack.push(ToDo.two);break;case 'a':if (m_input.GetAt(iPos) = '#')out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, -1);bGoOn = false;elsebErrorFlag = true;break;case 0:bErrorFlag = true;break;default

30、:assert(false);iStep+;out.WriteString("</table>");if (bErrorFlag)out.WriteString("<p><font color="#FF3300">分析失败，输入的字符串是不符合预定文法的！</font></p>n");/m_pTree->m_tree.DeleteAllItems();while(!TreeStack.empty()TreeStack.pop();elseout.WriteString("<p><font color="#009900">分析完成，输入的字符串是预定文法的句子</font></p>n");/HTREEITEM h = m_pTree->m_tree.GetRootItem();/ExpandTree(h);MakeTree();out.WriteString("</body>n</html>