根据两个集合的信息构造分析表(算法3.7)2.预测分析器方法 3.4.5.3LL(1)文法 M[A,a]的作用：指导产生式产生句子（指导推导） 问题：是否为任意文法构造的分析表M[A,a]中都最多有一个 条目？ 例3.23 二义文法文法的预测分析表： 文法： SiCtSSa SeSε 预测分析表：FIRST与FOLLOW集合： FIRST(C) 3.4.5.3LL(1)文法（续1） 定义3.12 文法G被称为是LL(1)文法，当且仅当为它构造的预测 分析表中不含多重定义的条目。由此分析表所组成的分析器被 称为LL(1)分析器，它所分析的语言被称为LL(1)语言。第一个L 代表从左到右扫描输入序列，第二个L表示产生最左推导，1表 示在确定分析器的每一步动作时向前看一个终结符。 判定LL(1)文法的方法：a.构造分析表；b.无需构造分析表。 推论3.2 G是LL(1)的，当且仅当G的任何两个产生式Aαβ 满足:

　　ε,则α不能导出以FOLLOW(A)中终结符开始的任何串。 3.4.5.3LL(1)文法（续2） 若条件1不满足，即存在终结符a，α和β同时推导出以a开始的串，则根据算法3.7步骤2，M[A，a]中有多重定义 若条件2不满足，即α和β均可推出ε串，则根据算法3.2步骤3，任何属于FOLLOW（A）的终结符b(包括#)，M[A，b] 中有多重定义Aα和Aβ 若条件3不满足，即存在终结符b，它既在FOLLOW(A)中，又在FIRST(α)中，则算法3.2步骤2把条目Aα加入到M[A， b]中，而步骤3又把条目Aβ加入到M[A，b]中，即M[A，b] 中有多重定义Aα和Aβ 根据推论3.2，有左递归和左因子的文法不是LL(1)文法。为什么？（考虑算术表达式文法），二义文法呢？ 推论3.2 G是LL(1)的，当且仅当G的任何两个产生式Aαβ满足: 3.4.5.3LL(1)文法（续3） 推论3.2 G是LL(1)的，当且仅当G的任何两个产生式Aαβ满足: (G3.4)F(E)-Fid 文法(G3.4)不是LL(1)的，因为不满足条件1。 事实上：任何直接左递归必有公共左因子。（为什么？） 文法(G3.4)是LL(1)的，因为三个条件均满足。 具体判断请同学们自己做。 3.4.5.3LL(1)文法（续4） LL(1)文法的弱点： 适应范围有限，往往写不出有些语言的LL(1)文法。因此，实际编译器中使用更多的是一类LL(1)文法的线自下而上语法分析 自上而下分析的方法是产生语言的自然过程。 但是对于分析语言来讲，自下而上分析的方法更 自然，因为语法分析处理的对象一开始都是终结符组 成的串，而不是文法的开始符号。 同时，自下而上分析中最一般的方法，LR方法的 能力比自上而下分析的LL方法要强，从而使得LR分析 成为最为实用的语法分析方法。 两种主要的自下而上分析方法： 算符优先分析（不讨论） LR分析 3.5.1自下而上分析的基本方法 思路：从句子ω开始，从左到右扫描ω，反复用产生式的左部 替换产生式的右部、谋求对ω的匹配，最终得到文法的开始符 号，或者发现一个错误。 3.5.1.1 规范归约与“剪句柄” 定义3.13 设αβδ是文法G的一个句型， 称β是句型αβδ相对于A的短语，特别的，若 称β是句型αβδ相对于产生式Aβ的直接短语。 一个句型的最左直接短语被称为句柄。 直观上，句型是一个完整结构，短语是句型中的某部分(针对某非终结符)。S是一个句型而不是一个短语(树根不是短语)。 短语形成的两个要素：1．从S可以推导出A，即S= 3.5.1.1规范归约与“剪句柄”（续1） 例3.25 文法、分析树与短语 文法：EE+TT Fid句型：id1+id2*id3， 分析树： 短语： id1+id2*id3 (E1) id2*id3 (T1) id1 (E2, T2, F1) id2 (T3, F3) id3 (F2) 直接短语： id1 (F1) id2 (F3) id3 (F2) 句柄：id1 (F1) 直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）； 句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。 特征： 问题：id1+id2是句型 id1+id2*id3的短语吗？ 答案：不是。 为什么？ 没有一个E的子树，它的全部叶子是 id1+id2；或者 找不到某个E，使得 id2id3 103.5.1.1 规范归约与“剪句柄”（续2） 定义3.14 α是文法G的句子且满足下述条件，则称序列α 将句柄替换为相应产生式左部非终结符得到的。 提醒：最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。 例3.26 文法(1) SaABe 对句子：abbcde的最左归约：问题：如何直观地看出句柄并进行归约？ 11“剪句柄”： 3.5.1.1 规范归约与“剪句柄”（续3） 文法(1) SaABe 句子：abbcde假设已经有了句子的分析树，则： 确定如何选择正确的产生式进行归约。移进-归约：用一个栈“记住”将要归约句柄的前缀，句柄未 形成前移进，形成后归约。 12 3.5.1.2 移进-归约分析器工作模式 移进-归约分析器的工作模式： 与预测分析对比： 驱动器 输入记号流 输出top ip 预测分析器模型预测分析表 驱动器 输入记号流 输出top ip 移进-归约 分析表 预测分析器： 1.分析方法：格局与格局变换 2.分析表 LL（文法、语言、分析器）移进-归约分析器： SLR分析表的构造13 3.5.1.2 移进-归约分析器工作模式（续1） 驱动器 输入记号流 输出top ip 移进-归约 分析表 工作方法：放幻灯，每个幻灯片是一个格局。 格局：（#栈，当前剩余输入#，改变格局的动作） 改变格局的动作： 报错(error)：发现语法错误，调用错误恢复例程。对照预测分析： 最左推导（展开非终结符）14 3.5.1.2 移进-归约分析器工作模式（续2） 例3.27 用移进-归约方法分析abbcde： abbcde

　　1后，分析器的构造趋于复杂，一般情况下并不构造k

　　1的LR(k)分析器。 我们仅构造SLR(1)分析器。LR分析器是一类分析器 21 3.5.2.2 构造SLR(1)分析器 思路：首先构造一个可以识别文法G中所有活前缀的DFA，然 后根据DFA和简单的向前看信息构造SLR分析表。 活前缀与LR（0）项目集族定义3.16 出现在移进-归约分析器栈中的右句型的前缀，被称 为文法G的活前缀（viable prefix）。 （#0E1-6-5id*id# s4） 这意味着：在移进-归约分析中，只要保证已扫描过的输入序 列可以归约为一个活前缀，则分析到目前为止没有错误。 构造SLR分析器的关键：为文法G构造一个识别它的所有活前缀 的DFA。 步骤：NFADFA 问题：识别活前缀的NFA是什么？ 活前缀的两个要素： 1．右句型的前缀； 2．已在分析栈中 即：活前缀＋若干剩余输入（不在栈中）＝

　　右句型。 22 3.5.2.2 构造SLR(1)分析器（续1） 回顾产生式与产生式(EE+T和TT*F)的状态转换图： 它们是FA，而且是NFA。因为从状态1经+既到达状态2也到达状态4（为什么？）； 在产生式的右部加入一个点“.”，用它在右部的位置表示一个NFA的状态。 定义3.17 一个LR(0)项目（简称项目）是这样一个产生式，在 它右部的某个位置有一个点“.”。对于Aε，它仅有一个项 233.5.2.2 构造SLR(1)分析器（续2） 对于文法G： EE-TT F-Fid它的全部LR(0)项目： E.E-T EE.-T EE-.T EE-T. F.idFid. 项目Aα.β显示了分析过程中看到(移进)了产生式的多少。 β不为空的项目称为可移进项目， β为空的项目称为可归约项目。 项目如何识别活前缀： TT.*F是识别活前缀αT的状态。产生式TT*F是识别活前缀αT*F的NFA。 即：每个产生式是一个识别活前缀的NFA；每个项 目是NFA的一个状态； 于是：所有产生式构成 文法G识别活前缀的NFA 集合，将其确定化即得 到识别活前缀的DFA。 24 3.5.2.2 构造SLR(1)分析器（续3） 拓广文法与识别活前缀的DFAa．拓广文法G 目的是使最终构造的DFA状态集中具有唯一初态和唯一终态。文法G： EE-TT F-Fid的拓广文法： b．NFA（项目）DFA（项目集）词法分析器－“子集法” smove（I，a）：所有从I经字符a能直接到达的状态全体。类似的两个过程： goto(I，x)：所有从I经文法符号x能直接到达的项目全体。25 3.5.2.2 构造SLR(1)分析器（续4） 定义3.18 项目集I的闭包closure(I)是这样一个项目集 若Aα.Bβ属于closure(I)，则所有形如B.γ的项目属于closure(I)； 定义3.19对所有属于项目集I、且形如[Aα.Xβ]的项目， 令XNT，则goto(I，X)是所有形如[AαX.β]的项目。 设J=goto(I，X)，K=closure(J)，则K中项目Aα.β分为两类： J=goto(I，X)：α非空，因为至少有一个X。 .在产生式右部最左边；可由某个J计算而来（K-J=closure(J)-J）。 定义3.20 项目[S.S]和所有“.”不在产生式右部最左边的项目 称为核心项目(kernel items)，其它“.”在产生式右部最左边的 项目(不包括[S.S])称为非核心项目（nonkernel items）。 核心项目：J=goto(I，X)加S.S（作为项目集的代表）非核心项目：K-J=closure(J)-J（特点：可由某J计算得到） 26 3.5.2.2 构造SLR(1)分析器（续5） 算法3.9 计算文法G的、基于LR(0)项目的、识别活前缀的DFA 输入：拓广文法G 输出：DFA=(C, Dtran) C是状态集，Dtran是状态转移方法： whileC中还有未标记状态I 考察所有未标记状态loop 标记I; 考察所有xloop end loop; end loop; J:=closure(goto(I,x))非空--有下一状态 记录下一状态转移end 加入J到C且未标记；end 273.5.2.2 构造SLR(1)分析器（续6） 构造DFA： EE.-TI1 I9EE-.T F.idI6 F.idI0 Fid.I4 id F.idI7 F.idI5 idid 初态：I0终态：I1 下一页 文法G：EE-TT F-Fid项目(NFA状态) 项目集(DFA状态) 项目集族(DFA状态全体) 28 3.5.2.2 构造SLR(1)分析器（续6） F.idI0 F.idFid. EE-.T F.idI1 I2 I3 I4 I5 idid I6I7 I9 I10 I8构造DFA： 初态：I0终态：I1 29 如何识别活前缀3.5.2.2 构造SLR(1)分析器（续7） 定义3.21 若存在最右推导S= 项目[Aβ1.β2]对活前缀αβ1有效。 在当前活前缀的情况下，该项目可指导下一步分析动作(αAω=

　　αβ1β2ω)。 30 一个项目可能对若干个活前缀有效（例1）项目Aβ1.β2对所有从初态出发可以到达此项目的路 径上的标记均有效（一个路径标记是一个活前缀）。 若干个项目可能对同一个活前缀有效（例2）项目集中的所有项目对同一活前缀均有效。 综合可知： 同一项目集中的所有项目，对此项目集的所有活前缀均有效。 即，项目集中的每个项目均有同等权利指导下一步动作。 有效项目的意义1.到目前为止分析是正确的； 2.指导下一步的分析： Aβ1.β2（可移进项）：移进β2中第一个终结符 Bβ.（可归约项）：按产生式Bβ归约 活前缀与项目的关系： 31 项目集中的冲突和解决冲突的简单方法：SLR(1)当一个项目集中同时存在： Aα.和B