China-pub.com 第5章自底向上的分析 165 下载 发生)： stmtcall-stmt assign-stm cal-stut→identifier assign-sml→ar:=exp var-var exp identifier exp var number 这个文法模块语句既可是调用无参数的过程也可以是对变量的表达式的赋值。请注意，赋值和 过程调用都是以一个标识符开头。只有到看到语句的结尾或记号：=时，分析才会决定该语句 是一个赋值还是一个调用。将这种情形简化成以下的文法，在其中刷去了变量的替换选择，并 将语句选项简化为无需改变基本的情况： S→idV:=E +主d E-VIn 为了显示这个文法在SLR(1)分析中是如何引起一个分析冲突，请考虑项目集合的DF的开始 状态： S-.S S-.id S-V=F V-.id 这个状态在id上有一个到状态 S-id. V-id. 的转换。现在有Follow(S={S和Follow()={:=,$(由于有规则V一V:=E所以有：=，又由 于E可以是厂，所以有$)。因此，SL(1)分析算法要求在这个状态中有一个在输入符号$下的利用 规则S一id和规则V一id实现的归约（这是一个归约-归约冲突）。这个分析冲突实际上是一个由 SLR(I)方法的缺点所引起的“假目”问题。实标上当输入为$时，用V→1d实现的归约永远也不 应该在这个状态中，这是由于只有到看到记号：=和被移进后，变量才会出现在语句的末端。 在下面的两节中，读者将会看到如何利用更强大的分析方法来解决这个分析问题。 5.3.4SLRk)文法 同其他分析算法一样，SLR()分析算法可被扩展为SLR()分析，其中的分析动作是基于 k≥1个先行的符号之上。利用上一章定义的集合First,和Follow,,Slr()分析程序使用以下两个 规则： 1)若状态s包含了格式A一a郑(X是一个记号)，且w E First(郑)是输入串中之后的k个 记号，那么该动作就是将当前输入记号移进到栈中，而且被压入到栈中的新状态是包含了项目 A一XB的状态。 2)若状态s包含了完整项目A一a.,且w∈Follow,(4)是输入串中之后的k个记号，则动作 用规则4→α归约。 当k>1时，SLR()分析比SLR(1)分析更强大，但由于分析表的大小将按k的指数倍增长
发生）： stmt → call-stmt | a s s i g n - s t m t call-stmt → i d e n t i f i e r assign-stmt →var : = e x p var → var [ exp ] | i d e n t i f i e r exp → var | n u m b e r 这个文法模块语句既可是调用无参数的过程也可以是对变量的表达式的赋值。请注意，赋值和 过程调用都是以一个标识符开头。只有到看到语句的结尾或记号 : = 时，分析才会决定该语句 是一个赋值还是一个调用。将这种情形简化成以下的文法，在其中删去了变量的替换选择，并 将语句选项简化为无需改变基本的情况： S→ i d | V : = E V→ i d E→ V | n 为了显示这个文法在 SLR(1) 分析中是如何引起一个分析冲突，请考虑项目集合的 D FA的开始 状态： S¢→.S S→.i d S→.V : = E V→.i d 这个状态在i d 上有一个到状态 S→i d. V→i d. 的转换。现在有Follow (S) = {$}和Follow (V) = { : =, $ }(由于有规则V→V : = E所以有: =，又由 于E可以是V，所以有$ )。因此，S L R ( 1 )分析算法要求在这个状态中有一个在输入符号$下的利用 规则S→i d 和规则V→i d 实现的归约(这是一个归约-归约冲突)。这个分析冲突实际上是一个由 S L R ( 1 )方法的缺点所引起的“假冒”问题。实际上当输入为$时，用V→i d 实现的归约永远也不 应该在这个状态中，这是由于只有到看到记号: =和被移进后，变量才会出现在语句的末端。 在下面的两节中，读者将会看到如何利用更强大的分析方法来解决这个分析问题。 5.3.4 SLR(k)文法 同其他分析算法一样， S L R ( 1 )分析算法可被扩展为 S L R (k)分析，其中的分析动作是基于 k≥1个先行的符号之上。利用上一章定义的集合 F i r s tk 和F o l l o wk，S l r (k)分析程序使用以下两个 规则： 1) 若状态s 包含了格式A→a.Xb（X是一个记号)，且Xw Î F i r s tk (Xb)是输入串中之后的k 个 记号，那么该动作就是将当前输入记号移进到栈中，而且被压入到栈中的新状态是包含了项目 A→aX .b的状态。 2) 若状态s 包含了完整项目A→a.，且w Î F o l l o wk (A)是输入串中之后的k 个记号，则动作 用规则A→a归约。 当k > 1时，S L R (k)分析比S L R ( 1 )分析更强大，但由于分析表的大小将按 k的指数倍增长， 第 5章 自底向上的分析 1 6 5 下载
166翁译原理及实践 China-pub.com 下载 所以它又要复杂许多。非SLR(1)的典型语言构造可利用LRLA(I)分析程序处理得更好一些，它 可使用标准的消除二义性的规则，或将文法重写。虽然例5.13的简单非SLR(1)文法确实也可出 现在SLR(2)中，但对于为任意值的k而言，它所来自的程序设计语言问题却不是SLR()。 5.4一般的LR(1)和LALR(1)分析 本节将研究LR(I)分析的最一般格式，有时它称作LR(1)规范(canonical))分析。这种方法解 决了上一节最后所提到的$L(1)分析中出现的问题，但它却复杂得多。实际上在绝大多数情况 下，通常地，一般的LR(1)分析太复杂以至于不能在大多数情况下的分析程序的构造中使用。 幸运的是， 一般的LR(I)分析的一个修正一一称作LRLA(I)(即“先行”LR分析)在保留了LR( 分析的大多数优点之外还保留了SLR(1)方法的有效性。LALR(I)方法已成为诸如用于诸如Yacc 这样的分析程序生成器所选用的方法，本节稍后将会研究到它。但为了理解这个方法，首先应 学习普通方法。 5.4.1LR(1)项的有穷自动机 SLR(1)中的困难在于它在LR(O)项的DFA的构造之后提供先行，而构造却又忽略了先行 一般的LR(I)方法的功能在于它使用了一个从开始时就将先行构建在它的构造中的新DFA。这 个DFA使用了LR(O)项的扩展的项目。由于它们包括了每个项目中的一个先行记号，所以就称 作LR()项(LR(I)item)。说得更准确一些就是：LR(I)项应是由LR(O)项和一个先行记号组成 的对。利用中括号将LR(1)项写作 A-a.B a 其中A一a.B是一个LR(0)项，而a则是一个记号（先行）。 为了完成一般LR(1)分析所用的自动机的定义，我们需要首先定义LR(1)项之间的转换。它 们与LR(O)转换相类似，但它们还知道先行。同LR(O)项一样，它们包括了-转换，此外还需建 立一个DFA,它的状态是项目为e-闭包的集合。LR(O)自动机和LR(I)自动机的主要差别在于ε 转换的定义。我们首先给出较简单的情况下（非ε转换）的定义，它们与LR(O)的情况基本一致。 定义：LR(I)转换（第1部分）的定义(definition of LR(I)tra nsitions(part1).假设有 LR(1)项目[4一α，a,其中X是任意符号（终结符或非终结符），那么X就有一个到项 目[A+Xy.al的转换。 请注意在这种情形下，两个项目中都出现了相同的先行α，所以这些转换并不会引起新的 先行的出现。只有g-转换才“创建”新的先行，如下所示 定义：LR(I)转换（第2部分）的定义(definition of LR()transitions(part2)。假设有 LR(1)项目[A*a.By.a1,其中B是一个非终结符，那么对于每个产生式B*B和在Fist (@)中的每个记号b都有到项目[B一B,b]的e-转换。 请诗者留章，这些。转换是如句跟踪在其中结构B需要被识别的上下文。实际上项目[A a.,ad说明了在分析的这一点上可能要识别B,但这只有是当这个B后跟有一个从串Ya派生出 的串时，且这样的串须以一个在Fist(ya)中的记号开始才可能。由于串y跟随在位于产生式A一 aBy中的B之后，所以若a是被构造在Follow()中，那么有First(Ya)CFollow(B),且在项目[B
所以它又要复杂许多。非S L R ( 1 )的典型语言构造可利用L R L A ( 1 )分析程序处理得更好一些，它 可使用标准的消除二义性的规则，或将文法重写。虽然例 5 . 1 3的简单非S L R ( 1 )文法确实也可出 现在S L R ( 2 )中，但对于为任意值的k 而言，它所来自的程序设计语言问题却不是 S L R (k)。 5.4 一般的L R ( 1 )和L A L R ( 1 )分析 本节将研究L R ( 1 )分析的最一般格式，有时它称作 L R ( 1 )规范( c a n o n i c a l )分析。这种方法解 决了上一节最后所提到的S L R ( 1 )分析中出现的问题，但它却复杂得多。实际上在绝大多数情况 下，通常地，一般的 L R ( 1 )分析太复杂以至于不能在大多数情况下的分析程序的构造中使用。 幸运的是，一般的L R ( 1 )分析的一个修正——称作L R L A ( 1 ) (即“先行”L R分析)在保留了L R ( 1 ) 分析的大多数优点之外还保留了 S L R ( 1 )方法的有效性。L A L R ( 1 )方法已成为诸如用于诸如Ya c c 这样的分析程序生成器所选用的方法，本节稍后将会研究到它。但为了理解这个方法，首先应 学习普通方法。 5.4.1 LR(1)项的有穷自动机 S L R ( 1 )中的困难在于它在 L R ( 0 )项的D FA的构造之后提供先行，而构造却又忽略了先行。 一般的L R ( 1 )方法的功能在于它使用了一个从开始时就将先行构建在它的构造中的新 D FA。这 个D FA使用了L R ( 0 )项的扩展的项目。由于它们包括了每个项目中的一个先行记号，所以就称 作L R(1)项(LR(1) item)。说得更准确一些就是： L R ( 1 )项应是由L R ( 0 )项和一个先行记号组成 的对。利用中括号将L R ( 1 )项写作 [A→a.b a] 其中A→a.b是一个L R ( 0 )项，而a 则是一个记号(先行)。 为了完成一般L R ( 1 )分析所用的自动机的定义，我们需要首先定义 L R ( 1 )项之间的转换。它 们与L R ( 0 )转换相类似，但它们还知道先行。同L R ( 0 )项一样，它们包括了 - 转换，此外还需建 立一个D FA，它的状态是项目为 - 闭包的集合。L R ( 0 )自动机和L R ( 1 )自动机的主要差别在于 - 转换的定义。我们首先给出较简单的情况下 (非 -转换)的定义，它们与L R ( 0 )的情况基本一致。 定义：L R ( 1 )转换(第1部分)的定义(definition of LR(1) transitions (part 1))。假设有 L R ( 1 )项目[A→a.Xg, a]，其中X是任意符号(终结符或非终结符)，那么X就有一个到项 目[A→aX.g, a]的转换。 请注意在这种情形下，两个项目中都出现了相同的先行 a，所以这些转换并不会引起新的 先行的出现。只有 - 转换才“创建”新的先行，如下所示。 定义：L R ( 1 )转换(第2部分)的定义(definition of LR(1) transitions (part 2))。假设有 L R ( 1 )项目[A→a.Bg,a]，其中B是一个非终结符，那么对于每个产生式 B→b和在F i r s t (ga) 中的每个记号b都有到项目[B→.b,b] 的 - 转换。 请读者留意，这些 - 转换是如何跟踪在其中结构 B需要被识别的上下文。实际上项目 [A→ a.Bg,a]说明了在分析的这一点上可能要识别 B，但这只有是当这个B后跟有一个从串ga 派生出 的串时，且这样的串须以一个在First (ga)中的记号开始才可能。由于串g 跟随在位于产生式A→ aBg 中的B之后，所以若a是被构造在Follow (A)中，那么有First (ga) Follow (B)，且在项目[B 1 6 6 编译原理及实践 下载