VC++环境下的LR语法分析器实现.pdf

2010年第9卷第1期(忌第141期) VC++环境下的LR语法分析器实现 崔 蕊 (南阳师范学院计算机与信息技术学院，河南南阳473061) 摘要：本文讨论了LR(O)语法分析器的工作原理和过程，以具体实例说明语法定义、造表和总控程序的实现过 程。 关键词：编译原JE；自下而上语法分析；LR分析法 Abstract：Thisdiscussthe and ofLRParsermainl．declarethe paper operationprincipleprocedure phrasing defines、constructtheformand methodofcontrol implement procedure． fromthe Parser downward；LR Keywords：Compilingprinciple；Syntacticanalysis top 中图分类号：TP314 文献标识码：A 一、引言 止。此过程就是模拟规范推导的逆过程。 编译程序能够将软件语言书写的各种程序处理成可 四、LR(0)分析表的构造 在计算机上执行的程序，是重要的系统软件。在编译系统 整个分析过程中，关键部分是分析表的构造，本文主 中，语法分析阶段是整个编译过程中继词法分析后的第 要讨论LR(0)分析表的构造，即在分析过程中不需要向右 二个阶段。语法分析的任务是在词法分析识别出单词符 查看输入符号。 号串的基础上，分析并判定程序的语法结构是否符合语 (一)拓广文法。由于最后的归约状态必须归约为开 法规则。按照建立语法分析树的方法，语法分析分为两 始符号，因此为了归约的唯一性，开始符号的产生式必须 类：自上而下分析和自下而上分析。本文讨论的LR分析 智能有一个候选式，因此对于开始符号有两个或以上候 法属于自下而上的方法。 选式的情况(例如本例)，需要对文法进行拓广，加入一条 二、语法规则的表示 产生式S-E，且把S作为开始符号。 语法规则是由上下文无关文法进行定义的。例如一 (二)计算LR项目集族。由于LR分析法是模拟规范 个语言可用一系列的产生式定义： 归约，因此每次归约后的符号串都应称为一个规范句型， 那么，已扫描过的字符串就是规范句型的一个前缀，且不 程序一begin语句串end语句串一语句 ；语句串等等，为了方便问题描述，把实际含义用含句柄之后的任何符号，称之为活前缀。造表的基本思想 符号进行抽象，本文讨论的例子就是抽象后的符号表示 就是构造一个识别所有活前缀的有限自动机，再转换成 的，且LR(0)法进行语法分析要求文法是非二义性的。本分析表。此有限自动机的状态就是每一个产生式后面加 A一eAIdB一cBId 文的文法如下：E一aAIbB 一个圆点后形成的项目。识别文法活前缀的DFA的项目 三、LR分析法的基本思想 集的全体称为LR项目集规范族。计算方法为： 本文所讨论的LR(0)分析法是从句子出发，从左到右 1、从S_哆开始符号产生式开始，求产生式的 扫描符号串，根据当前分析栈中的符号串(通常以状态表 示)和向右顺序查看输人串的k个(≥0)符号，根据LR分 属于CLOSURE(I)；②如A一d·B 析表，可唯一地确定分析器的动作是移进还是归约以及 用哪个产生式对旬柄进行归约，直至归约为初始符号为 作者简介：崔蕊