LR0语法器讲解.docx

西 安 邮 电 大 学 （计算机学院） 课内实验报告 实验名称： LR(0)语法分析器 专业名称： 计算机科学与技术 班 级： 计科1304 学生姓名： 裴世宇 学号（8位）： 12） 指导教师： 陈燕 实验日期： 2016年05月15日 一、实验目的 . 1.巩固对语法分析的基本功能和原理的认识。 通过对语法分析表的自动生成加深语法分析表的认识。 3.理解并处理语法分析中的异常和错误。 二、实验环境 VC++6.0 Windows 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’INCLUDEPICTURE \d /compile/nandian/pic/n-7_image001.gif \* MERGEFORMATINET INCLUDEPICTURE \d /compile/nandian/pic/n-7_image003.gif \* MERGEFORMATINET αAωINCLUDEPICTURE \d /compile/nandian/pic/n-7_image004.gif \* MERGEFORMATINET INCLUDEPICTURE \d /compile/nandian/pic/n-7_image003_0000.gif \* MERGEFORMATINET αβω，若γINCLUDEPICTURE \d /compile/nandian/pic/n-7_image003_0001.gif \* MERGEFORMATINET 是αβ的前缀，则称γ是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)。 ② 若项目A→α· 属于Ik，则对任何终结符a 和#号置ACTION[k,a]和ACTION[k,#]为rj，j为在文法G′中某产生式A→α的序号。rj动作