LR0语法分析器.docx

西 安 邮 电 大 学 （计算机学院）课内实验报告实验名称： LR(0)语法分析器 专业名称： 计算机科学与技术班 级： 计科1304 学生姓名： 裴世宇学号（8位）：12）指导教师： 陈燕实验日期：2016年05月15日一、实验目的.1.巩固对语法分析的基本功能和原理的认识。通过对语法分析表的自动生成加深语法分析表的认识。3.理解并处理语法分析中的异常和错误。二、实验环境VC++6.0Windows 7三、实验内容 大多数用上下文无关文法描述的程序语言都可用LR分析器予以识别。LR分析法比算符优先分析法或其他的“移进-规约”技术更加广泛，而且分析效率并不比他们差。规范规约的关键问题是寻找句柄。一个LR分析器实质上是一个带先进后出的存储器（栈）点确定有限状态自动机。通过设计、编制、陶氏一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。选择对各种常见程序语言都用的语法结构，如赋值语句（尤其是表达式）作为分析对象，并且与所选语法分析方法要比较贴切。四、实验功能LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。我们将把“历史”和“展望”材料综合地抽象成某些“状态”。我们把栈的结构看成是：LR分析器模型LR分析器的核心部分是一张分析表。这张分析表包括两部分，意识“动作”（ACTION）表，另一个是“状态转换”（GOTO）表。他们都是二维数组。ACTION[ s , a ]规定了当状态s面临符号a时应采取什么动作。GOTO[ s ,X ]规定了状态。面对文法符号X（终结符或非终结符）时下一个状态是什么。显然，GOTO[s,X]定义了一个以文法符号为字母表的DFA。?对于任一文法G[S]，若S’αAωαβω，若γ是αβ的前缀，则称γ是G的一个活前缀。?活前缀与句柄的关系： ① 活前缀已含有句柄的全部符号，表明产生式A→β的 右部β已出现在栈顶。② 活前缀只含句柄的一部分符号如β1表明A→β1β2的右部子串β1已出现在栈顶，当前期待从输入串中看到β2推出的符号。 ③ 活前缀不含有句柄的任何符号，此时期望产生式A→β的右部所推出的符号串。（1）ACTON表和GOTO表的构建每一项ACTION[ s , a ]所规定的动作不外是下述四种可能之一：① 移进 ?把Sj=GOTO[Si，a]移入到状态栈，把a移入到文法符号栈。其中i，j表示状态号。 ② 归约 ?当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即文法中有A→β的产生式，若β的长度为r(即|β|=r)，则从状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈指针SP减去r。并把A移入文法符号栈内，Sj=GOTO[Si，A]移进状态栈，其中Si为修改指针后的栈顶状态。 ③ 接受acc?当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。 ④ 报错 当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。 ① 若项目A→α·aβ属于Ik且转换函数GO(Ik,a)= Ij，当a为终结符时则置ACTION[k,a]为Sj，其动作含意为将终结符a移进符号栈，状态j进入状态栈，(相当状态k时遇a转向状态j)。?（2）LR(0)项目?在文法G中每个产生式的右部适当位置添加一个圆点构成LR(0)项目。我们也可以根据圆点所在的位置和圆点后是终结符还是非终结符把LR(0)项目分为以下几种： ① 移进项目?形如A→α·aβ,其中α，β∈V*，a ∈VT，即圆点后面为终结符的项目为移进项目，对应状态为移进状态。分析时把a移进符号栈。② 待约项目?形如A→α·Bβ，其中α,β∈V* ，B∈VN，即圆点后面为非终结符的项目称待约项目，它表明所对应的状态等待着分析完非终结符B所能推出的串归约成B，才能继续分析A右部的B后面部分。③ 归约项目?形如A→α·其中α∈V* ，即圆点在最右端的项目，称归约项目，它表明一个产生式的右部已分析完，句柄已形成可以归约。④ 接受项目?形如S′→S·，其中S∈VN ，S′→S为拓广文法的产生式，S′为左部的产生式只有一个，因而它是归约项目的特殊情况，对应状态称为接受状态，表明已分析成功。我们规定S′→·S 为初态。（3）LR(0)项目集规范族的构造?对于构成识别一个文法活前缀的DFA项目集(状态)的全体我们称之为这个文法的LR(0)项目集规范族。为此，在这里须引入LR(0)项目集的闭包函数CLOSURE和状态转换函数GO两个概念。 ① 闭包函数CLOSURE(I)的定义如下： a）I的项目均在CLOSURE(I)中。b）若A→α·Bβ属于CLOSURE(I)，则每一形如B→·γ的项目也属于CLO