LR0语法分析器-.doc

西安邮电大学(计算机学院课内实验报告实验名称:LR(0语法分析器专业名称:计算机科学与技术班级:计科1304学生姓名:裴世宇学号(8位:04131132(12指导教师:陈燕实验日期:2016年05月15日一、。。。二、实验环境VC++、实验内容大多数用上下文无关文法描述的程序语言都可用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→β的右部所推出的符号串。(1ACTON表和GOTO表的构建每一项ACTION[s,a]所规定的动作不外是下述四种可能之一:①移进把Sj=GOTO[Si,a]移入到状态栈,把a移入到文法符号栈。其中i,j表示状态号。②归约当在栈顶形成句柄为β时,则用β归约为相应的非终结符A,即文法中有A→β的产生式,若β的长度为r(即|β|=r,则从状态栈和文法符号栈中自栈顶向下去掉r个符号,即栈指针SP减去r。并把A移入文法符号栈内,Sj=GOTO[Si,A]移进状态栈,其中Si为修改指针后的栈顶状态。③当归约到文法符号栈中只剩文法的开始符号S时,并且输入符号串已结束即当前输入符是'#',则为分析成功。④报错当遇到状态栈顶为某一状态下出现不该遇到的文法符号时,则报错,说明输入串不是该文法能接受的句子。①若项目A→α·aβ属于Ik且转换函数GO(Ik,a=Ij,当a为终结符时则置ACTION[k,a]为Sj,其动作含意为将终结符a移进符号栈,状态j进入状态栈,(相当状态k时遇a转向状态j。②若项目A→α·属于Ik,则对任何终结符a和'#'号置ACTION[k,a]和ACTION[k,#]为"rj",j为在文法G′中某产生式A→α的序号。rj动作的含义是把当前文法符号栈顶的符号串α归约为A,并状态栈指针从栈顶向下移动|α|的长度,文法符号栈从栈顶弹出|α|个符号,非终结符A变为当前面临的符号。③若GO(Ik,A=Ij,则置GOTO[k,A]为"j",其中A为非终结符,表示当前状态为"k"时,遇文法符号A时状态应转向j,因此A移入文法符号栈,j移入状态栈。④若项目S′→S·属于Ik,则置ACTION[k,#]为"acc",表示接受。⑤凡不能用上述方法填入的分析表的元素,均应填上"报错标志"。为了表的清晰我们仅用空白表示错误标志。(2LR(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′为左部的产生式只有一个,因而它是归