编译原理－何炎祥-第七章.pptVIP

第七章 自下而上的LR(k)分析方法 LR(k)分析器是按从左至右方式扫描输入串，并按自下而上方式进行规范归约的分析程序。 一个LR(k)分析器主要由两部分组成：一个总控程序和一个分析表。一般说来，所有LR分析器的总控程序基本上是大同小异的，只是分析表各不相同。 本章主要介绍LR(0)、简单LR（SLR）、规范LR、向前LR（LALR）四种分析表的构造算法及相关知识。 7.1 LR(k)文法和LR(k)分析器 给定文法G，S是其开始符号。考虑该文法中一个终结符串w的一个规范推导S?w1?w2? … ?w 假定uAv?uxv是上述推导中的一个推导步。A?x是用于该推导步的产生式；uxv或是wi之一或是w本身；u和v∈(VN∪VT)﹡。 对每一个这样的推导和推导步，仅通过扫描ux和（至多）查看v中开始的k个符号就能唯一确定选用产生式A?x，我们就称G为LR(k)文法。 7.1 LR(k)文法和LR(k)分析器 LR分析器是一个确定的下推自动机 7.1 LR(k)文法和LR(k)分析器 LR(k)分析方法的主要思想： 1.严格地进行最左归约（识别句柄并归约它）。 2.将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的一个符号。 3.符号栈：存放已识别的部分。 4.状态栈：存放状态。 5.由一个总控程序来控制整个识别过程。 7.1 LR(k)文法和LR(k)分析器 LR分析器的分析表由分析动作表（ACTION表）和goto函数表(GOTO表)两部分组成，它们 都是用二维数组表示的。 ACTION表指明了分析程序采取的动作 移进：句柄尚未形成，将符号移进栈。 归约：句柄已经形成，用对应的产生式进行归约。 接收：表示整个分析工作完毕，输入串合法。 报错：出错处理。 GOTO[s,a]=后继状态（决定当前状态的下一状态） 7.2 LR(0)分析表的构造 7.2.1 规范句型的活前缀 一个符号串的前缀是指该串的任意首部，包括?。 活前缀（Viable Prefix）是指规范句型的一个前缀，它不包含该句型的句柄右边的任何符号。 7.2 LR(0)分析表的构造 7.2.2 LR(0)项目——用于指明已经识别出了哪些部分，还将识别哪些部分。文法G的LR(0)项目定义为：文法G的每个产生式右部的某个位置添加一个“·”。 A?·AB 希望看到从输入串中与AB对应的符号串。 A?A·B 已识别出由A对应的输入符号，并希望看到与B对应的输入串。 A?AB· 与AB对应的输入串已经识别出来，可以进行规约。 7.2 LR(0)分析表的构造 7.2.3 文法G的拓广文法 给定文法G，S是其开始符号，G的拓广文法是G?，其开始符号为S?，区别在于后者仅增加一个产生式S??S。 S??·S 初始项目 S??S· 接收项目 7.2 LR(0)分析表的构造 7.2.4 CLOSURE(I)函数——求与I相关的所有LR(0)项目 I中的每一项目都属于它 若A??·B?属于CLOSURE(I)且B??是文法中的一个产生式，则关于产生式B的任何形如B?·?的项目也属于它 重复上述步骤，直到它不再增大为止 7.2 LR(0)分析表的构造 7.2.5 goto(I, X)函数——求项目集中紧挨“·”后的后继项目集 goto(I, X)=CLOSURE ({所有形如[A??X·?]的项目? [ A??·X?]?I}) 先找出形如[ A??·X?]?I}的项目 然后将其变成A??X·? 再求CLOSURE (A??X·?) 7.2 LR(0)分析表的构造 7.2.6 LR(0)项目集规范族——在CLOSURE(I)和goto(I, X)作用下，获得的项目集的全体 令C={I0=CLOSURE({S??·S})} 对每个Ii?C和I中紧挨“·”后的项目，若goto(I, X)非空且不属于C，则将goto(I, X)之值加入C 重复2直至C不再增大 7.2 LR(0)分析表的构造 7.2.7 有效项目 一个项目[A?x·y]称为对某个活前缀ux是有效的(Valid)，当且仅当存在某个规范推导 S*?uAv?uxyv 其中，xy是规范句型uxyv的句柄，v是一个终结符号串。 7.2 LR(0)分析表的构造 7.2.8 举例（略） 7.2.9 LR(0)文法 如果文法G?的项目集规范族的每个项目集中不存在下述任何冲突项目： ① 移进项目和归约项目并存， ② 多个归约项目并存， 则称文法G?为LR(0)文法。 7.2 LR(0)分析表的构造 7.2.10 构造LR(0)分析