Pushdown Automation 下推自动机﹙PDA﹚是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。 技术原理编辑 下推自动机可以形象的理解为，把有限状态自动机扩展使之可以存取一个栈。每一个下推自动机都接受一个形式语言。下推自动机存在确定与非确定两种形式，两者并不等价。﹙对有限状态自动机两者是等价的﹚被非确定下推自动机接受的语言是上下文无关语言。 基本特征编辑 如果把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。 下推自动机 M 是如下的一个七元组 ( Q, Σ, Γ, δ, q0, Z0, F ) ，其中：

• Q 是一个有穷状态集合；
• Σ 是一个字母表，称为输入字母表。
• Γ 是一个字母表，称为栈字母表。
• q0 属于 Q ，是初始状态。
• Z0 属于 Γ ，是一个特殊的栈符号，称为栈起始符号。
• F 包含于 Q ，是终结状态集合。
• δ : Q×(Σ∪{ε})×Γ -> Q×Γ* 是 M 的动作函数。[1] 半环方法编辑 在给出下推自动机的定义之前先做如下的约定:Q, Γ同上面一致 , Q , Γ, Γ中的元素分别表示为 :q , Z ,π,其中 Γ的克林闭包 Γ =Γ0∪ Γ∪ Γ2∪ Γ3∪ … ,这里 Γ0 ={ε}, π同字符表中的字的概念类似叫作栈符号下推转换矩阵[ 2] :一个矩阵 M ∈(P(∑ ∪ ε)Q×Q)JΓ×Γ如果对所有的 π1 , π2 ∈ Γ,有 ,Mπ1=Zπ4,π2=π3π4 =MZ ,π3 　Z ∈ Γ, π4 ∈ Γ0则称该矩阵为下推转换矩阵.对任意 Z , 非零矩阵块 MZ ,π表示栈顶符号 Z 出栈, 栈符号表上的字 π入栈.(由于下推自动机也是无穷语言的一种有穷描述机制 ,故描述它动作的下推转换矩阵也必是有限个非零块矩阵组成 ,也就是说下推转换矩阵必是行列有限的 .)J 表示矩阵是行列有限矩阵 .由下推转换矩阵的定义可知下推转换矩阵是一个分块矩阵,它的每一个分块 Mπ1,π2, π1 , π2 ∈Γ是一个 P(∑ ∪ε)Q×Q矩阵 .进一步直观地来理解下推转换矩阵:假设下推栈包含 Zπ,三元组(q , a , Z)其中 a∈ ∑ ∪ ε, 它表示自动机在状态 q , 栈顶符号为 Z , 读入字符为 a ,与上面自动机的动作一样 :状态 q 变为 q1 ,栈顶符号 Z 弹出 ,并将 π1 中的符号从右到左依次压入栈 ,然后将读头向右移动一个字符而指向字符串的下一个字符,记为状态(q1 , π1).下推转换矩阵表示为 : a ∈ (MZπ′,π1π′)q, q1 () 特别地下推转换矩阵的定义要确保与 π′无关()这一条件的满足 .称((q , Zπ′),(q1 , π1 π′))是用 a 标记的边 .边的标记也就是字母表上的字母 .状态(q , π)到(q′, π′)的一条路是 c ,它是边的有序序列 :((q0 , π0),(q1 , π1))((q1 , π1),(q2 , π2)), …,((qk-1 , πk-1)(qk , πk)), k ≥0 且(q0 , π0)=(q, π), (qk , πk)=(q′, π′),记为 c ∶(q , π)※(q′, π′),并称 k 为路c 的长度, 记为 c .如果 at 是边((qt-1 , πt-1),(qt , πt))的标记,1 ≤t ≤k ,则称 a1a2 …ak 为路c 的标记 ,记为‖c‖ , 也就是 ‖c ‖ =a1 a2 …ak .路的标记也就是字母表中的字.对于每个状态(qt , πt),((qt , πt),(qt , πt))的路称作空路 ,记为 λt ,并有 λt =0 , ‖λt ‖ =ε若c ∶(q1 , π1)※(q2 ,π2), d ∶(q2 , π2)※(q3 , π3)是路 ,则它们的合成(也就是字母表的乘法)定义为 cd ∶(q1 , π1)※(q3 , π3), 且有cd = c + d , ‖cd ‖ =‖c ‖ ‖d ‖ .从而在上面的基础上给出下推自动机在半环中的定义 .下推自动机 :A=(Q , ∑ , Γ, M , q0 , Z0 ,F)其中, M 是下推转换矩阵, 其他符号同上面下推自动机的定义相同 .下推自动机 A=(Q, ∑ , Γ, M , q0 , Z0 ,F)的行为‖A‖ ∈ P(∑)定义为 :‖A‖ = ∪qf∈F ∑∞k=0 c∶(q ∑ i0,Z0)※(qf,ε),|c|=k‖c ‖ ,如果 w ∈ ‖A‖ ,则称 w 被‖A‖接收或者产生.下面将给出下推转移矩阵和下推自动机行为之间的关系:(M)kπ1,π2 q1, q2 是所有长度为 k 的路c ∶(q1 ,π1)※(q2 , π2)的标记 ,即 (M)kπ1,π2q1, q2 =c(q ∑ 1,π1)※(q2,π2),|c|=k‖c ‖ .对 k 实施数学归纳法证明 :这里要用到半环同构即任意的 M′∈ 〈P(∑)(Q×Γ)×(Q×Γ)J , +, · , 0 , E′〉, 必有 M′(q1, π1),(q2,π2) =(Mπ1, π2 )q1, q2, 其中M ∈〈P(∑)(Q×Γ)×(Q×Γ)J , +, · , 0 , E′〉.当 k =0 时 ,(M0π1, π2 )q1, q2 =M′0(q1,π1),(q2, π2) =E′(q1,π1),(q2, π2=δ(q1, π1),(q2π2)ε, 同时 c∶(π ∑ 1, q1)※(π2, q2),|c|=0‖c‖ =δ(q1, π1),(q2,π2)ε,所以 k =0 结论成立.假设对 k -1 ,k ≥1 结论成立, 则(M)kπ1,π2q1, q2 =M′k(q1,π1),(q2,π2)=(M′k-1 M′)(q1,π1),(q2,π2)=(q,π)∑∈Q×ΓM′k-1(q1,π1 ),(q,π)M′(q, π),(q2, π2) =(q,π)∑∈Q×Γ c ∑ 1∶(q1,π1)※(q,π),|c|=k-1‖c1 ‖c ∑ 2:(q,π)※(q2,π2),|c|=1‖c2 ‖ =(q,π)∑∈Q×Γ* c ∑ 1∶(q1,π1)※(π, q),|c|=k-1c ∑ 2∶(q, π)※(q2, π2),|c|=1‖c1c2 ‖ =c∶(q,π)※(∑q′,π′),|c|=k‖c ‖下推转换矩阵和移动函数的等价性 :任意 w ∈((M)kπ0,πk)q0, qk, 存在即时描述序列(q0 , a0 w0 , π0),(q1 , a2 ,w1 , π1), … ,(qk ,ε, πk),其中当 i ≤j 时, wj 是 w i 的后缀, 且 w =a0a1 …ak-1 .读完字 w 后, 自动机 A从状态(q0 , π0)转移到(qk , πk),即从 q0 转变为 qk ,同时下推栈的符号串由 π0 替换为 πk .这个序列用移动函数来描述为: δ(q0 , a0 , π0)※(q1 , π1), δ(q1 , a1 ,π1)※(q2 , π2), …, δ(qk-1 , ak-1 , πk-1)※(qk ,πk).[1] 查询研究编辑 基于下推自动机的 XML 数据流递归查询研究 可扩展标记语言(XML)由于其易用性和强大的复杂数据描述能力，已逐渐成为因特网上数据交换的标准。很多流行的数据库引擎已经开始通过增加对于这种新数据类型以及相关操作的支持来满足新的需求。XML数据流上的应用是XML研究的一个很重要的方面，在新的基于Web的应用场景下，有研究已经提出，有效地处理XML数据流[1-3]上的XPath、XQuery查询将会成为下一代信息系统的特点。可扩展标记语言(XML)由于其易用性和强大的复杂数据描述能力，已逐渐成为因特网上数据交换的标准。很多流行的数据库引擎已经开始通过增加对于这种新数据类型以及相关操作的支持来满足新的需求。XML数据流上的应用是XML研究的一个很重要的方面，在新的基于Web的应用场景下，有研究已经提出，有效地处理XML数据流[1-3]上的XPath、XQuery查询将会成为下一代信息系统的特点。出现了存在递归结构的 XML 数据流，如果当包含和谓词的XPath对它进行递归查询，将会发生多重匹配从而产生大量的匹配模式，需要花费大量的时间和空间管理这些匹配模式，这样会严重影响到查询处理的性能。面对这种情况，提出一种基于下推自动机技术的处理方法，能有效地实现XML数据流的递归查询。 1.1 XML 数据流递归查询 定义 1 XML 数据流对应的文档树结构中，从根到叶子的路径上，相同名字的元素结点重复出现，我们称作递归的XML 数据流[6]，在数据流中，所有从根到叶子的路径当中，相同名字的元素结点重复出现次数的数目称作元素结点的递归深度，符号为 R。 定义 2 在查询 XML 数据流时，相互嵌套的不同深度的XML 元素可能会匹配 XPath 查询表达式的同一个置步，这种现象称为多重匹配。 2 基于 PDA 的递归查询 N0N1 … Nn/O 作为查询表达式最通用的表示方式，Ni表示XPath 的置步，O 表示查询结果的输出形式。由于 XPath 由许多置步组成，查询目的是通过这些置步来定位 XML 文档片段。置步处理模块作为整个查询模型的基本组成部分，它是由 XPath 每个置步转化而来，该模块实质是一个状态集，这些状态包括主干路径匹配状态和谓词匹配状态，并且有模块运行的开始状态，状态之间用箭头连接在一起，箭头上标示了跳转条件，如果置步中存在谓词，主干路径匹配状态中有属性为TRUE 的状态，表明主干路径匹配和谓词检验成功；另外主干路径匹配状态中有属性为 FALSE 的状态，表明主干路径匹配成功和谓词检验不成功；如果置步中不存在谓词，则主干路径匹配状态中只有属性为 TRUE 的状态，表明主干路径匹配和谓词检验成功，这样与谓词存在的情况有良好的衔接。图 3是置步/person[name.text() = lee]转化成处理模块的一个实例，S0 是整个模块处理的开始状态，其中S0、S1 和S3 是主干路径匹配状态，其它状态是谓词匹配状态。标示的箭头，表示只有 Person 元素的开始事件才能通过箭头到达所指状态，</person>标示的箭头，表示只有 Person 元素的结束事件才能通过箭头到达所指状态，模块中其它标示的箭头尽管名称不同，但含义类似。查询过程中，当前活跃状态为 S2 时，将会出现 3 种情况：①Person 元素下无 Name 元素文本值，则状态直接从 S2 跳到 S1，状态 S1 属性为 False，谓词检验不成功；②Person 元素下有 Name 元素，但 Name 元素的文本值不符合要求，则状态从S2—>S4—>S1；主干路径匹配成功和谓词检验不成功；③Person 元素下有 Name 元素，并且 Name 元素的文本值符合要求，则状态从 S2—>S5—>S3，状态 S3 属性为 TRUE，主干路径匹配成功和谓词检验成功。 3 性能测试与分析 为了验证本文提出的算法性能和相对于以前工作的性能提升，本文用 Java 语言实现了基于 PDA 的递归查询算法，并进行了性能测试，并且和之前工作基于 LazyDFA 算法做了比较。实验平台为：操作系统为 Windows XP，CPU 为双核处理器，内存 1024M 实验数据，采用了 IBM 的 XML Generator[9]生成不同递归层次结构的 XML 数据集。XML 数据流处理对时间和内存的耗用量有严格的要求，对于XML数据流的递归查询，数据流的递归深度是影响这两个方面的主要因素，算法采用了整数移位运算的方式，它便于对匹配模式的保存和检验，同时谓词匹配位检验和缓存操作，有利于快速处理潜在的缓存结果。通过从运行时间和内存使用量上来对两个算法进行比较，从图 5、图 6 的实验结果显示，针对不同复杂程度的XML数据流，基于 PDA 算法的性能要优于 LazyDFA 算法

它对文法的限制最少，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析。 分析法介绍编辑 1965年，D.Knuth首先提出了LR(K)文法及LR(K)分析技术。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 LR分析是当前最一般的分析方法。这是因为它对文法的限制最少，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析，而且在分析的效率上也不比诸如不带回溯的自顶向下分析、一般的“移进归约”以及算符优先等分析方法逊色。此外，LR分析器在工作过程中，还能准确及时地发现输入符号串的语法错误。凡此种种，就使LR分析方法在国际上受到了广泛的重视。 对于LR(K)文法的理论研究业已证明：① 每一LR(K)文法都是无二义性文法；② 一个由LR(K)文法所产生的语言也可由某一LR(1)文法产生。同时，由于通常的程序设计语言一般均能由LR(1)文法来产生。因此，对程序设计语言的编译来说，我们可仅考虑k≤1，即LR(0)和LR(1)的情况。 下面，我们首先介绍LR分析器的逻辑结构及工作原理，接着再依次介绍LR(0)，SLR(1)，LR(1)及LALR(1)等四种LR分析器的构造方法。其中，LR(0)分析器的分析能力最低，但它是构造其余三种LR分析器的基础。SLR是“简单LR”分析的缩写，它是为了解决构造LR(0)分析器所出现的问题而形成的一种方法，其分析能力自然要比LR(0)分析器稍强一些。 LR(1)分析器的分析能力是四种LR分析器中的最强者，但对规模较大的文法来说，在具体构造分析器时，由于所需的工作量及要求的存储空间都很庞大，将会遇到很大的困难。为此，采用所谓向前LR分析器即LALR(1)分析器将是一种恰当的选择。LALR(1)分析器的能力介于SLR(1)和LR(1)之间，但其分析表的规模比LR(1)分析表要小得多。至于工作量的问题，则可通过开发和使用LR分析器的自动生成工具来解决。目前十分流行的语法分析器自动生成工具YACC和OCCS正是为自动生成LALR(1)分析器而研制的。 结构及原理编辑 在逻辑上，一个LR分析器有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR分析器在总控程序的控制下自左至右扫视输入串的各个符号，并根据当前分析栈中所存放之文法符号的状况及正注视的输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止所移进或归约出的全部文法符号，即记录了从分析开始到目前为止的整个历程。 因此，为了方便，对于分析过程的每一步，我们可将分析栈中所存放的全部文法符号用一种“状态”来刻画，且将此状态名置于分析栈的栈顶所示。分析刚开始时，栈中仅有一个句子的左界符#，此时分析器处于初始状态S0，它不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着即将扫视的输入符号应当是可作为句子首符号的那些符号。类似地，状态S1刻画了分析栈中已有符号#X1的情况，…，栈顶状态Sm则刻画了分析栈中已存在符号串#X1X2…Xm的情况，等等。此外，根据分析栈的栈顶状态，还可对当前可能遇到的输入符号进行预测。例如，对于前面所述的文法G[E]，设分析栈中已移进和归约出的符号串为#E+T时的栈顶状态为Si，则Si不仅表征了迄今扫描过的输入串部分已被归约成#E+T，而且由Si还可以作这样的预测： 若输入符号串无语法错误，则当前可遇到的输入符号仅能是+,,)或#。 显然，在栈顶状态为上述Si的情况下，若当前所扫视到的符号为，则应将移进栈中；当所扫视到的符号为+,)或#时，则应将E+T归约为E；若所扫视到的符号不是上述四种符号之一，则应按语法错误处理。由此可见，知道了栈顶状态Sm和正扫视到的输入符号ai，就知道了当前所需的全部有用信息，从而也就可惟一地确定当前LR分析器所应采取的动作。所以，在具体实现时，并不需要将文法符号记入分析栈中。 LR分析器的核心是一张分析表，它由两个子表组成： 其一是分析动作表；另一个为状态转移表。其中： S1,S2,…,Sn为分析器的各个状态；a1,a2,…,al为文法的全部终结符号和句子界符；X1,X2,…,Xp为文法字汇表中的全部文法符号。分析动作表中的每一个元素ACTION[Sm,ai]指明，当栈顶状态为Sm且正扫视的输入符号为ai时要完成的分析动作。状态转移表中的元素GOTO[Sm,Xi]则指明，当向分析栈中移进一个输入符号或按某一产生式进行归约之后所要转移到的下一状态。 LR分析器的工作在总控程序的控制下进行，其过程如下 (为书写方便，我们将分析栈按顺时针旋转90度)： 1?分析开始时，首先将初始状态S0及句子左界符#推入分析栈。 2?设在分析的某一步，分析栈和余留输入符号串处于如下格局： S0S1S2…S↓m[]#X1X2…Xma↓iai+1…an# 则用当前栈顶的状态Sm及正扫视的输入符号ai组成符号对(Sm,ai)去查分析动作表，并根据分析表元素ACTION[Sm,ai]的指示采取相应的分析动作，每一分析表元素所指示的仅能是下列四种动作之一： (1) 若ACTION[Sm,ai]=“移进”，则表明句柄尚未在栈顶部形成，正期待继续移进输入符号以形成句柄，故将当前的输入符号ai推入栈中，即 S0 S1 S2 … S↓m[]# X1 X2 … Xm aia↓i+1ai+2…an# 然后，以符号对(Sm,ai)查状态转移表，设相应的表元素GOTO[Sm,ai]=Sm+1，再将此新的状态Sm+1 (即要转移到的下一状态)推入栈中，则有如下格局： S0 S1 S2 … Sm S↓m+1[]# X1 X2 … Xm aia↓i+1ai+2…an# (2) 若ACTION[Sm,ai]=rj，其中rj意指按文法的第j个产生式A→Xm-r+1Xm-r+2…Xm进行归约。这表明栈顶部的符号串Xm-r+1Xm-r+2…Xm已是当前句型 (对非终结符号A)的句柄。按第j个产生式进行归约，也就是将分析栈从顶向下的r个符号 (因为该产生式右部符号串的长度为r)退出，然后再将文法符号A推入栈中，此时分析栈的格局为 S0 S1 S2 … S↓m-r[]# X1 X2 … Xm-r Aa↓iai+1…an# 然后再以(Sm-r,A)查状态转移表，设GOTO[Sm-r,A]=SK，将此新状态推入栈中，则有如下的格局： S0S1S2…Sm-rS↓K[]#X1X2…Xm-rAa↓iai+1…an# 必须注意的是，当完成归约动作之后，输入串指示器不向前推进，它仍然指向动作前的位置。 (3) 若ACTION[Sm,ai]=“接受”则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。 (4) 若ACTION[Sm,ai]=ERROR，则表明当前的输入串中有语法错误，此时应调用出错处理程序进行处理。 3?重复步骤2的工作，直到在分析的某一步，栈顶出现“接受状态”为止。此时，分析栈的最终格局应为 S0S↓z[]#Z#↓ 其中，Z为文法的开始符号，Sz则为使ACTION[Sz,#]=“接受”的惟一状态 (即接受状态)。 上述所列的三个步骤，实质上是对LR分析器总控程序的一个非形式化的描述，它对任何不同的LR分析表都是适用的。顺便提及，LR分析器的输出是在用某个产生式进行归约之后，通过执行相应的语义子程序来实现的，我们将在第5章再讨论这一问题。 分析表构造编辑 顾名思义，LR(0)分析就是LR(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。 为了给出构造LR分析表的算法，我们首先需要引入一些非常重要的概念和术语。 活前缀 (viable prefix) 由例4?6对输入串“a,b,a”的分析过程容易看出，如果所分析的输入串没有语法错误，则在分析的每一步，若将分析栈中已移进和归约出的全部文法符号与余留的输入符号串拼接起来，就形成了所给文法的一个规范句型。换言之，也就是在分析的每一步，如输入串已被扫视的部分无语法错误，则当前分析栈中的全部文法符号应当是某一规范句型的前缀。而且还不难看出，此种规范句型的前缀决不会含有句柄右边的任何符号，这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。以后，我们将把规范句型具有上述性质 (即不含句柄之右的任何符号)的前缀称为它的活前缀。例如，对于文法G[L]的规范句型“E,b,a” (见表412分析过程第5步)，其句柄为“b”，栈中的符号串为“E，b”，此句型的活前缀为ε，“E”，“E，”，“E,b”等。 由此可见，一个LR分析器的工作过程，实质上也就是一个逐步产生 (或识别)所给文法的规范句型之活前缀的过程。同时，在分析的每一步，分析栈中的全部文法符号 (如果输入串无语法错误)应是当前规范句型的活前缀，并且与此时的栈顶状态相关联。因此，我们自然会想到，如果能构造一个识别所给文法的所有活前缀的有限自动机，那么就能很方便地构造出相应的LR分析表来。稍后我们将讨论这一问题。 LR项目 上面我们已经说过，在一个规范句型的活前缀中决不含有句柄右边的任何符号。因此，活前缀与句柄的关系不外下述三种情况： (1) 其中已含有句柄的全部符号 (句柄的最右符号即为活前缀的最右符号)； (2) 其中只含句柄的一部分符号 (句柄开头的若干符号与活前缀最右的若干个符号一致)； (3) 其中全然不含有句柄的任何符号。 第一种情况表明，此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应是用此产生式进行归约。第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现于栈顶，正期待着从余留输入串中看到能由β2推出的符号串。而第三种情况则意味着期望从余留输入串中能看到由某一产生式A→α的右部，即α所推出的符号串。为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。例如，对于上述三种情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别，对形如A→ε的产生式，相应的LR(0)项目为A→·。显然，不同的LR(0)项目反映了分析过程中栈顶的不同情况。下面我们就会看到，文法的全部LR(0)项目，将是构造识别其全部活前缀的有限自动机的基础。 识别活前缀 DFA 在作出文法的全部LR(0)项目之后，现在用它们来构造识别全部活前缀的DFA。这种DFA的每一个状态由若干个LK(0)项目所组成的集合 (称为项目集)来表示。下面以例4?7所给出的文法为例来说明构造此种DFA的方法。 首先，我们用I0表示这个DFA的初态，它预示着分析过程的开始，并且期待着将给定的输入符号串逐步归约为文法的开始符号S′。或者反过来说，我们所期待的是，从使用产生式S′→S开始，能够逐步推导出所给的输入符号串。因此，我们应将项目S′→·S列入状态I0中。换言之，也就是我们期待着将要扫视的输入串正好就是能由S推出的任何终结符号串。然而，由于不能从输入串中直接读出非终结符号S，因此我们也应当把项目S→·A以及S→·B列入到I0中。由于A和B同样是非终结符号，所以又应当将A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由于最后列入I0的项目中，圆点之后都是终结符号，故I0已经“封闭”，构造项目集I0宣告结束。这样，表示初态的项目集I0由如下的项目组成： I0: S′→·SS→·AA→·aAb S→·BB→·aBbB→·d A→·c 我们将项目S′→·S称为项目集I0的基本项目。上述从项目S′→·S出发构造项目集I0的过程，可用一个对其基本项目集{S′→·S}的闭包运算，即CLOSURE({S′→·S})来表示。一般地，设I为一项目集，则构造I的闭包CLOSURE(I)的算法如下： (1) I中每一项目都属于CLOSURE(I)； (2) 若形如A→α·Xβ的项目属于CLOSURE(I)，且X为非终结符号，则文法中任何X产生式的一切圆点在最左边的项目X→·γ也都属于CLOSURE(I)； (3) 重复上述过程，直至不再有新的项目加入CLOSURE(I)为止。 有了初态I0之后，我们来说明如何确定从I0可能转移到的下一个状态。设X为一个文法符号 (终结符号或非终结符号)，若I0中有圆点位于X左边的项目A→α·Xβ (其中α可以为ε)，则当分析器从输入串识别出 (即移进或归约出)文法符号X后，分析器将进入它的下一个状态。设此状态为Ii，显然Ii中必含有全部形如A→αX·β的项目，我们将这样的项目称为A→α·Xβ的后继项目。对于每一文法符号X，如果存在这样的后继项目，则可能不止一个，设其组成的集合为J,J中的每个项目也就是项目集Ii的基本项目。因此，按照与上面构造项目集I0相类似的讨论，我们就有 Ii=CLOSURE(J) 为了指明Ii是“I0关于文法符号X的后继状态”这一事实，我们可定义一个状态转移函数 GO(I,X)=CLOSURE(J) 其中，I为当前状态，X为文法符号，J为I中所有形如A→α·Xβ的项目的后继项目所组成的集合，而CLOSURE(J)就是项目集I (即状态I)关于X的后继项目集 (即后继状态)。例如，对于上例，我们有： I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·} I2=GO(I0,A)=CLOSURE({S→A·})={S→A·} I3=GO(I0,B)=CLOSURE({S→B·})={S→B·} I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})= {A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d} I5=GO(I0,c)=CLOSURE({A→c·})={A→c·} I6=GO(I0,d)=CLOSURE({B→d·})={B→d·} 请注意，由于I0中无圆点在b之前的项目，故GO(I0,b)无定义。这样，我们求出了I0的全部后继项目集I1,I2,I3,I4,I5,I6。容易看出，由于I1,I2,I3,I5,I6诸项目集中的项目均无后继项目，因此它们都没有后继状态。对于项目集I4，我们再仿此求出它的后继状态，这些后继状态是： I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b} I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b} 此外，由于 GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6 故它们均不产生新的项目集。最后，再求出I7,I9的后继项目集。它们分别是 I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·} I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·} 由于I8和I10已无后继项目集，所以至此我们已求出所给文法G[S]的全部项目集I0~I10，通常，我们将这些项目集的全体称为文法G[S]的LR(0)项目集规范族，并记为 C={I0,I1,I2,I3,…,I10} 于是，我们所要构造的识别文法G[S]全部活前缀的DFA为 M=(C,V,GO,I0,C) 其中： M的状态集也就是文法的LR(0)项目集规范族C={I0,I1,…,I10}； M的字母表也就是文法的字汇表V={S′，S，A，B，a,b,c,d}； M的映像也就是如上定义的状态转换函数GO； M的终态集也是C，这表明M的每一状态都是它的终态。 对于上述文法G[S]，如上构造的识别其全部活前缀的DFA的状态转换图如图416所示。 由于状态转换图416中的每一个状态都是终态，因此在上述DFA工作的过程中，从初态I0出发，沿着有向边所指示的方向前进，可以使DFA在所经历的任何状态上中止它的工作。当DFA到达某一状态时，我们把从初态I0出发，到达该状态所经过的全部有向边上的标记符号依次连接起来，就得到了DFA在到达该状态时，所识别出的某规范句型的一个活前缀。例如：当上述DFA处于初态I0时，它所识别的活前缀为ε；当M处于状态I3时，它所识别的活前缀为B；当M处于I4时，它所识别的活前缀为aa；而达到I9时，它所识别的活前缀为aaB等等。需要注意的是，对那些只含有归约项目的项目集，即M的I1,I2,I3,I5,I6,I8和I10，当M到达这些状态时，表明活前缀中已含有相应句柄的全部符号 (即句柄已在栈顶形成)，因此，我们将这些状态称为句柄识别状态。特别是当M处于状态I1时，M所识别的活前缀为S，这意味着已将所给的输入串归约为S，如果再按产生式S′→S归约一步，就得到了拓广文法G′的开始符号S′。因此，我们将状态I1称为“接受状态”，它预示着对输入串的分析已成功地完成。 对于一个给定文法G的拓广文法G′，当识别它的全部活前缀的DFA作出之后，我们就可据此构造相应的LR(0)分析表了。然而，应当首先注意的是，用前述方法所构造的每一个LR(0)项目集，实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，我们自然会提出这样的要求，即每一项目集中的诸项目应当是相容的。所谓相容，是指在一个项目集中，不出现这样的情况： (1) 移进项目和归约项目并存； (2) 多个归约项目并存。 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含冲突项目，则称G为LR(0)文法。显然，只有当一个文法是LR(0)文法时，才能构造出不含冲突动作的LR(0)分析表来。 从前面的讨论和分析，我们将不难得出构造LR(0)分析表的算法。为方便起见，我们用整数0，1，2，…表示状态I0,I1,…，而且如表411那样，也将GOTO子表中有关终结符号的各列并入ACTION子表相应的各列中去，此外，算法中形如sj和rj等记号的含义同前，此算法如下： (1) 对于每个项目集Ii中形如A→α·Xβ的项目，若GO(Ii,X)=Ij，且X为一终结符号a时，置ACTION[i,a]=sj。但若X为非终结符号时，则仅置GOTO[i,X]=j。 (2) 若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对文法的任何终结符号或句子的右界符# (将它们统一地记为a)，置ACTION[i,a]=rj。 (3) 若接受项目S′→S·属于Ii，则置ACTION[i,#]=acc。 (4) 在分析表中，凡不能按上述规则填入信息的元素，均置为“出错”。 SLR构造编辑 在前面讨论LR(0)分析表的构造算法时，我们曾经指出，仅当一个文法G是LR(0)文法时，才能对它构造出无冲突动作的LR(0)分析表。然而，对于通常的程序设计语言来说，它们一般都不能用LR(0)文法来描述。例如，考虑如下“简单分程序”的文法G[B′]： 0? B′→B3? D→d 1? B→bD;Se4? S→s;S 2? D→D;d5? S→s 相应识别其全部活前缀的DFA及LR(0)分析表如图417及表414所示。由于在项目集I8中，既含有移进项目[S→s·;S]，又含有归约项目[S→s·]，因而反映到分析表中就出现了具有多重定义的元素ACTION[8,′；′]={s10,r5}，前者指明当输入符号为“；”时应将它移进栈中，而后者则要求按第5个产生式S→s进行归约。于是就出现了有“移进归约”冲突的分析动作。又如，对于通常用来描述简单表达式的文法G[E]，当构造它的项目集规范族时，也会出现类似的情况。这就表明，这两个文法都不是LR(0)文法。然而，尽管如此，对大多数程序设计语言来说，这种具有冲突项目的项目集，在整个项目集规范族中所占的比例毕竟是很小的。因此，如果我们能设法解决出现在一个项目集中的“移进归约”或“归约归约”冲突，那么，只要对前述构造LR(0)分析表的算法稍加修改，它仍能适用于我们现在讨论的情况。 表414G[B′]的LR(0)分析表 b[]d[]；[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[]r3[]r3[]r3[]r3[]r3[]r35[][]s7[][]s8[10]66[6]s97[]r2[]r2[]r2[]r2[]r2[]r28[]r5[]r5[]r5,s10[]r5[]r5[]r59[]r1[]r1[]r1[]r1[]r1[]r110[5]s8[10]1111[]r4[]r4[]r4[]r4[]r4[]r4 仔细分析上述构造LR(0)分析表的算法容易看出，使分析表中出现多重定义分析动作的原因在于其中的规则(2)，即对于每一项目集Ii中的归约项目A→α·，不管当前的输入符号是什么，都把ACTION子表相应于Ii那一行 (即第i行)的各个元素指定为rj，其中j是产生式A→α的编号。因此，如果该项目集Ii中同时还含有形如B→α·bβ或C→α·的项目，则在分析表的第i行中，必然会出现多重定义的元素。 由此可见，对于含有冲突的项目集 Ii={B→α·bβ，A→α·，C→α·} 在构造分析表时，如果能根据不同的向前符号a，将Ii中各项目所对应的分析动作加以区分，那么就有可能使冲突得到解决。为此，对于文法中的非终结符号U，我们定义集合 FOLLOW(U)={a|S′#?…Ua…, a∈VT∪{#}} 即FOLLOW(U)是由所有含U的句型中，直接跟在U后的终结符号或#组成的集合。现对上述项目集Ii，考察FOLLOW(A)，FOLLOW(C)及{b}，若它们两两不相交，则可采用下面的方法，对Ii中各个项目所对应的分析动作加以区分。 对任何输入符号a： (1) 当a=b时，置ACTION[i,b]=“移进”； (2) 当a∈FOLLOW(A)时，置ACTION[i,a]={按产生式A→α归约}； (3) 当a∈FOLLOW(C)时，置ACTION[i,a]={按产生式C→α归约}； (4) 当a不属于上述三种情况之一时，置ACTION[i,a]=“ERROR”。 一般地，若一个项目集I含有多个移进项目和归约项目，例如 I={A1→α·a1β1, A2→α·a2β2，…，Am→α·amβm, B1→α·, B2→α·, …, Bn→α·} 则当集合{a1,a2,…,am}，FOLLOW(B1),FOLLOW(B2)，…,FOLLOW(Bn)两两不相交时，可类似地根据不同的向前符号，对状态为i时的冲突动作进行区分。 上述用来解决分析动作冲突的方法称为SLR(1)规则。此规则是由F?DeRemer于1971年提出的。 有了SLR(1)规则之后，只须对前述构造LR(0)分析表的算法中的规则(2)作如下的修改：“(2)′若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对于任何属于FOLLOW(A)的输入符号a，置ACTION[i,a]=rj”，且其余的规则仍保持不变，就得到了构造SLR(1)分析表的算法。 对于给定的文法G，若按上述算法构造的分析表不含多重定义的元素，则称文法G为SLR(1)文法。例如，对于上面的文法G[B′]，它的项目集 I8={S→s·; S,S→s·} 含有冲突的项目，但由于FOLLOW(S)={e}≠{;}，故冲突可用SLR(1)规则解决，与上述项目相应的分析动作分别是： ACTION[8,;]=s10ACTION[8,e]=r5 此外，再注意到FOLLOW(B′)=FOLLOW(B)={#}和FOLLOW(D)={;}，则按上述算法为G[B′]所构造的SLR(1)分析表b[]d[];[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[4]r35[3]s7[][]s8[10]66[6]s97[4]r28[4]s10[][]r59[7]r110[5]s8[10]1111[6]r4 LR构造编辑 前面所介绍的SLR(1)分析法是一种较实用的方法。其优点是状态数目少，造表算法简单，大多数程序设计语言基本上都可用SLR(1)文法来描述。然而，也的确存在这样的文法，其项目集的“移进归约”冲突不可能通过SLR(1)规则得到解决。试看下面的例子。 例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中，P由如下的产生式组成： 0? S′→S4?B→C 1?S→CbBA5?B→Db 2?A→Aab6?C→a 3?A→ab7?D→a 识别此文法的全部活前缀的DFA见图418。其中项目集I10={S→CbBA·,A→A·ab}存在“移进归约”冲突，但因FOLLOW(S)={#}，故上述冲突可通过SLR(1)规则得到解决。然而，在项目集I8={C→a·,D→a·}中，由于FOLLOW(C)={a,b}，FOLLOW(D)={b}，即FOLLOW(C)∩FOLLOW(D)≠?，故用SLR(1)规则解决上述“归约归约”冲突无效。而且还可验证，对于任何K>0，上述文法也是非SLR(k)的，故不能通过任何SLR(k)规则使项目集I8中的“归约归约”冲突得到解决 [2]。因此，我们需要更强的LR分析法，即LR(1)分析方法来解决这一问题。 对SLR(1)规则稍作分析即可发现，它对某些文法失效的原因，在于当所给的文法出现冲突的分析动作时，SLR(1)规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW(A)，以确定是否应按产生式A→α进行归约，而没有考察符号串α所在规范句型的“环境”，即没有考察α在规范句型中的“上下文”，这就具有一定的片面性。因为一旦α出现在分析栈的顶部 (设分析栈当前所存放的符号串为#δα)，且当前的输入符号a也属于FOLLOW(A)，就贸然将α归约为A，此时分析栈中的符号串将变成#δA，但若文法中并不存在以δAa为前缀的规范句型，那么，这种归约无效。例如，对于上述文法中的规范句型Cbabab，当分析达到格局 I0I2I4I8[]#Cbabab(4?50) 时，如果仅根据当前输入符号b∈FOLLOW(C)，就将栈顶符号a按产生式C→a归约为C，则有如下的格局： I0I2I4I6[]#CbCbab 但在该文法中，根本不存在以CbCb为前缀的规范句型，因此在执行下一动作将b移进之前，分析器将报告“出错”。由此可见，在分析过程中，当试图用某一产生式A→α归约栈顶符号串α时，不仅应查看栈中符号串δα，还应向前扫视一输入符号a (我们将a称为向前搜索符号)，只有当δAa的确构成文法某一规范句型的前缀时，才能用此产生式进行归约。为了指明上述事实，应当在原来的每一LR(0)项目[A→α·β]中放置一个向前搜索符号a，使之成为[A→α·β,a]的形式，我们将此种项目称为一个LR(1)项目。同时，为了使分析的每一步都能在栈中得到一个规范句型的活前缀，还应要求每一个LR(1)项目对相应的活前缀都是有效的 (其定义在下面给出)。此外，为了克服分析动作的冲突，在必要时，我们还可将某些项目集进行分解，以便使每一个状态都能确切地指明： 当α已出现在栈顶，且面临哪些输入符号时，才能按产生式A→α将α归约为A。 所谓一个LR(1)项目[A→α·β，a]对活前缀γ=δα有效，是指存在规范推导 S?δAy?δαβyy∈VT 且满足下列条件： (1) 当y≠ε时，a是y的首符号； (2) 当y=ε时，a=#。 例如，对于例4?8所给文法，因有 S?CbBA?CbBab?CbDbab 其中，δ=Cb,α=D,β=b,y=ab,A=B，故LR(1)项目[B→D·b,a]对活前缀γ=CbD有效。又因 S?CbDbab?Cbabab 其中，δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)项目[D→a·,b]对活前缀γ=Cba有效。由此也可看出，当分析器所处的格局为式(4?50)时，应当将栈顶符号a归为D，而不应将它归约为C。 与LR(0)文法的情况相类似，识别文法全部活前缀的DFA的每一个状态也是用一个LR(1)项目集来表示，而每一个项目集又是由若干个对相应活前缀有效的LR(1)项目组成。为了构造LR(1)项目集族，我们同样需要用到两个函数，即CLOSURE(I)及GO(I，X)。 对每一LR(1)项目集I，相应的CLOSURE(I)的定义如下： (1) I中的任何LR(1)项目都属于CLOSURE(I)。 (2) 设项目[A→α·Bβ，a]∈CLOSURE(I)，并假设它对活前缀γ=δα有效，则对文法中所有形如B→η的产生式和每一个b∈FIRST(βa)，形如[B→·η,b]的全部项目也都对γ有效，故若[B→·η,b]原不在CLOSURE(I)中，则应将其放入。事实上，因为[A→α·Bβ，a]对γ=δα有效，则由定义我们有： s?δAy?δαBβyy∈VT 且a∈FIRST(y)∪{#}，故可将上面的推导写成 S?δAy?δαBβaωω∈VT∪{#} 现设文法已经过化简，故不论β是否为ε，从βaω总能推出终结符号串，于是可假定 βaω?bω′ 又因a≠ε，有FIRST(βaω)=FIRST(βa)，从而就得到推导 S?δαBbω′ 由此可见，一切形如[B→·η,b]的项目也对活前缀γ=δα有效。 (3) 重复步骤(2)直到没有新的项目加入为止。 至于函数GO(I，X)，其中I为一LR(1)项目集，X为某一文法符号，与LR(0)文法类似，我们也将它定义为： GO(I,X)=CLOSURE(J) 其中J是由这样的一些LR(1)项目组成： 对I中所有圆点在X左边形如[A→α·Xβ,a]的项目，其后继项目[A→αX·β,a]∈J。注意，每一LR(1)项目与其后继项目有相同的向前搜索符号。 有了上述CLOSURE(I)和GO(I，X)的定义之后，采用与LR(0)类似的方法，可构造出所给文法G的LR(1)项目集族C及状态转换图。例如，对于上述文法，其LR(1)项目集及状态转换图如图419所示。 对于给定的文法G，当相应的LR(1)项目集族C及GO函数构造出来之后，便可按如下的算法构造它的LR(1)分析表： (1) 对于每个项目集Ii中形如[A→α·Xβ,b]的项目，若GO(Ii,X)=Ij，且当X为一终结符号a时，置ACTION[i,a]=sj。但若X为一非终结符号时，则置GOTO[i,X]=j。 (2) 若归约项目[A→α·,a]∈Ii，A→α为文法的第j个产生式，则置ACTION[i,a]=rj。 (3) 若项目[S′→S·,#]∈Ii，则置ACTION[i,#]=acc。 (4) 在分析表中，凡不能照上述规则填入信息的元素，均置为“出错”。 对于一个文法G来说，若按上述算法所构造的分析表不含有多重定义的元素，则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。例如，上述文法的LR(1)分析表见表416，所以它是一个LR(1)文法。 LALR构造编辑 上述每个LR(1)项目均由两部分组成： 第一部分是一个LR(0)项目，称为LR(1)项目的核；第二部分则是一个向前搜索符号集。对于移进项目而言，搜索符号对分析表的构造无影响；但对归约项目而言，则仅在当前输入符号属于该搜索符号集时，才能用相应的产生式进行归约。LR(1)分析表的这种机理，较圆满地解决了SLR(1)分析所难以解决的某些“移进归约”或“归约归约”冲突，从而使LR(1)的分析能力比SLR(1)分析有明显的提高。然而，LR(1)分析的主要缺点在于，对同一个文法而言，LR(1)分析表的规模将远远大于相应的SLR(1)或LR(0)分析表。例如，为一个C语言构造LR(0)分析表，一般大约设置300个状态即可，而构造LR(1)分析表则需上千个状态，即后者将导致时间和内存空间开销的急剧上升。因此，就有必要寻求一种其分析表的规模与SLR(1)相当，但其分析能力又不比LR(1)相差太大的LR分析方法，这就是下面我们要介绍的LALR(1)分析技术。 下面，我们首先对造成LR(1)项目集族规模大幅度上升的原因进行分析，然后再设法从中找出构造高效LR分析表 (即LALR(1)分析表)的方法。为此，试看下面的例子。 再考察文法G[E]： 0?S→E4?T→F 1?E→E+T5?F→(E) 2?E→T6?F→ID 3?T→TF 利用上面所给算法，为G[E]构造的LR(1)项目集族和识别活前缀的DFA如图420(a)，(b)所示 (请注意，由于图幅较大，这里将其划分为(a)，(b)两部分)。对比这两幅图我们立即就会发现，除其中的状态0和状态3之外，对于(a)中的每一状态 (LR(1)项目集)，在(b)中都有一个状态 (LR(1)项目集)与其相似。例如，比较状态7和16：在这两个项目集中，除搜索符号集不同外，各个LR(1)项目的核都彼此相同 (即产生式相同，且产生式中圆点的位置也相同)，我们把具有这种特点的两个LR(1)项目集称为同心集。所以，在图420(a)和(b)中，7/16，5/12，10/17，4/13，8/18，2/14，11/19，6/20，1/15和9/21都是同心集。显然，在LR(0)分析器中，每个“心”仅对应一个LR(0)项目集；但在LR(1)分析器中，由于向前搜索符号的不同，同一个“心”将会派生出多个同心集。这就是对同一文法而言，LR(1)项目集族远大于LR(0)项目集规范族的原因。 7E→E+·T[]#+T→·TF T→·F F→·(E) F→·ID〖〗#+ #+* #+* #+[][]16E→E+·T[]+)T→·TF T→·F F→·(E) F→·ID〖〗+)* +)* +)* +)* 为解决上述问题，F?DeRemer提出了LALR(1)分析法。这种方法的基本思想是将LR(1)项目集族中的同心项目集加以合并，以削减项目集的个数。所谓合并同心集，实际上也就是将其中的每个LR(1)项目的向前搜索符集对应地合并在一起。例如，对于文法G[E]的同心项目集4和13，设合并后的新项目集为4/13，则有 4E→T· T→T·F〖〗#+ #+[][]13E→T· T→T·F〖〗+) +)[][]4/13E→T· T→T·F〖〗#+) #+) 由于同心集的合并，对原来识别活前缀的DFA也须作相应的修改。 对于LALR(1)项目集族，我们须着重指出如下几点： (1) 合并同心集也就是将同心集中每个LR(1)项目的两个组成部分 (核及向前搜索符号集)分别、对应地合并在一起。设I1,I2,…,Im为同心项目集，J是合并之后的新的项目集，显然J与Ii同心；再设X∈V∪{#}，则GO(I1,X),GO(I2,X)，…，GO(Im,X)也必然同心，若把这m个同心项目集合并后的新项目集记为K，则有GOTO(J，X)=K。可见前面定义的GOTO函数在这里仍然适用。 (2) 尽管原来各LR(1)项目集均不存在冲突，但合并同心集后就有可能出现冲突。换言之，即LR(1)文法未必总是LALR(1)文法。不过，由此引入的冲突只能是“归约归约”冲突，而决不会是“移进归约”冲突。事实上，设原LR(1)项目集族中有如下两个项目集 Ik： [A→α·，W1] [B→β·aγ,b]Ij: [A→α·,W2] [B→β·aγ，c] 并设Ik与Ij均无冲突，故有 W1∩{a}=?W2∩{a}=? 从而 (W1∪W2)∩{a}=? 现将Ik与Ij合并，有 Ik/j: [A→α·,W1∪W2] [B→β·aγ，{b}∪{c}] 若此时Ik/j有“移进归约”冲突，则必有 (W1∪W2)∩{a}≠? 这就与Ik与Ij无冲突的假设相矛盾。因此，合并同心集不会引入新的“移进归约”冲突。 (3) 对同一个语法上正确的输入符号串而言，不论用LALR(1)分析表还是用LR(1)分析表进行分析，所经历的移进、归约序列总是相同的 (仅状态名可能不同)。然而，当输入符号串有错时，LALR分析器可能会比LR(1)分析器多进行几步归约才能报错，但决不会比LR分析器多移进输入符号。也就是说，LALR分析器虽然可能延迟了发现出错的时间，但对错误的准确定位不产生影响。 (4) LALR(1)项目集族总是与同一文法的SLR(1)项目集族有同样个数的项目集。但是构造LALR项目集族的开销比SLR大。实现LALR分析对文法的要求比LR(1)严、比SLR(1)宽，但开销远小于LR(1)。权衡利弊的结果，LALR堪称为当前实现自底向上语法分析，特别是构造分析器自动生成工具的最为适用的技术。 综上所述，可给出构造LALR(1)分析表的算法如下。 1? 对已给的拓广文法G′，构造相应的LR(1)项目集族C={I0,I1,…,In}。 2? 对于C，将各LR(1)项目集按同心关系进行分组，并将同组的同心集加以合并，设所得的新项目集族为C′={J0,J1,…,Jm}，其中含有项目[S′→·S,#]的项目集对应于初态。 3? 若C′中的项目集含有冲突项目，则G′不是LALR(1)文法。否则，可按如下法则构造LALR(1)分析表： (1) 用构造LR(1)分析表类似的方法构造ACTION表； (2) 对于某个X∈VN，若有GO(Jk,X)=Jt，则置GOTO(k,X)=t。 上述通过构造LR(1)项目集族和合并同心集来构造LALR分析表的方式仅有理论意义而无实用价值。因为构造完整的LR(1)项目集族的时间和空间开销都很大，故应首先设法予以解决。 迄今已有多种高效构造LALR分析表的算法，其共同的特点都是不从直接构造完整的LR(1)项目集入手，而是通过构造LR(0)项目集并添加相应的向前搜索符号来形成LALR(1)项目集 (请注意，对同一个文法而言，LALR(1)项目集与同心的LR(0)项目集一一对应)。例如，OCCS/YACC构造LALR(1)项目集所采用的策略是，每当创建一新的项目集时，就检查目前是否已存在与之同心的项目集，若有这样的项目集，则只需将向前搜索符号加入其中，而不再建立新的项目集。一种更为有效的方法甚至无需构造完整的LALR(1)项目集，而仅通过各个项目集中的“核心项目”便能构造相应的LALR(1)分析表。这里所说的核心项目是指形如[S′→·S，#]的项目 (其中，S′→S是拓广文法的第1个产生式)，或者是形如[A→α·Xβ,a]的项目 (其中，α≠ε，即圆点不出现在产生式右部的最左位置)，亦即那些用于构造本项目集闭包的“基本项目”。例如，对于文法G[E]，各项目集的核心项目如图422所示。 下面，我们对利用项目集的核心项目构造LALR分析表的原理进行说明。 ACTION 构造ACTION表的关键在于确定“归约”和“移进”两种动作。 (1) 归约动作的确定 由核心项目的定义可知，任何归约项目都必然会出现在某个项目集的核心项目之中，现设项目集I的核心为K，若[A→α·,a]∈K (其中α≠ε，搜索符号如何配置下面再介绍)，我们立即可以确定： 在当前状态下所面临的输入符号为a时，应按产生式A→α进行归约，即有 ACTION[I,a]=rj 若α=ε，则当且仅当 [B→γ·Cδ， b]∈KC?[]rAη 且a∈FIRST(ηδb)时，才能确定面临输入符号a时用产生式A→ε进行归约。由于对任何C∈VN，满足C?[]rAη的所有非终结符号A预先能完全确定，故项目集I所引发的归约动作，仅由其核心K即能完全确定。 (2) 移进动作的确定 若 [A→α·Xβ,b]∈KX?[]raη(a∈VT) 且上述推导的最后一步未使用ε产生式，则可确定： 状态I面临输入符号a时的动作为“移进”。其中，终结符号a可通过预先计算FIRST(X)加以确定。 GOTO 对于任何项目[B→γ·Xδ,b]∈K，相应的项目[B→γX·δ,b]显然必属于某个项目集J=GO(I，X)的核心L。另外，若 [B→γ·Cδ,b]∈KC?[]rAη 且A→Xβ是文法中的一个产生式，则对于任何 a∈FIRST(ηδb)[A→X·β,a]∈L 由于对每一对非终结符号(C，A)，是否存在关系C?[]rAη，可采用类似于计算FIRST集的方法预先求出，故仅从I的核心同样可构造出GOTO表。 配置 上面的讨论，是在假定每个核心项目都已配置了搜索符号的情况下进行的。现在，再回头讨论： 如何为每个LR(0)项目集的核心项目配置搜索符号，使之成为LALR项目集的核心项目。为此，我们首先考察搜索符号从项目集I传播到项目集GO(I，X)的规律。 再设项目集I的核心为K，若有 [B→γ·Cδ,b]∈KC?[]rAη 且A→Xβ是文法中的一个产生式，则根据上面的讨论有 [A→X·β,a]∈La∈FIRST(ηδb) 其中L是项目集J的核心，且J=GO(I,X)。现分如下两种情况讨论搜索符号a和b间的关系。 (1) 当ηδ?ε时，显然也有[A→X·β,b]∈L。此时，我们就说项目[A→X·β,b]中的搜索符号b是从项目[B→γ·Cδ,b]中传递过来的 (propagate)。 (2) 当ηδ不能推导出ε时，a仅取决于η或δ，而与b无关，此时我们就说搜索符号a是自生的 (spotaneous)。 无论a是传递的还是自生的，它总能根据项目[B→γ·Cδ,b]中的有关信息，通过上述计算获得，这便是搜索符号从项目集I传播到项目集J的规律。 其次，在同一项目集中，核心项目中的搜索符号向非核心项目传播的规律与上述规律极为相似。事实上，设[B→γ·Cδ,b]∈K，而C→α是文法中的一个产生式，则[C→·α，c]是I的一个非核心项目。其中，搜索符c∈FIRST(δb)，且按如下方法确定： 若δ不能推出ε，则c是自生的；否则，c=b，即c是从上面的项目传递下来的。 类似地，也可讨论搜索符号在非核心项目间的传播规律。例如，对于文法G[E]，从核心项目[S→·E，#]开始，向前搜索符号在I0中的传递和自生的情况如图423所示。 设K是LR(0)项目集I的核心，X是某个文法符号，则对GO(I，X)的核心中的每一项目A→αX·β，通过程序47描述的操作 (请注意，这里使用了一个虚拟搜索符号lookahead)，可由I中的项目确定其全部自生的搜索符号，并能确定K中的哪些项目将其搜索符号传递给GO(I，X)中的项目A→αX·β。 程序47确定自生搜索符号和传递搜索符号的项目 for (K中的每个项目B→γ·δ) { J′=CLOSURE ([B→γ·δ,lookahead]); /计算GO函数之值 */ for (J′中的每一项目[A→α·Xβ,a]) { if(a!=lookahead) 确定GO(I，X)核心项目[A→αX·β,a] 之搜索符号a是自生的 if(a==lookahead) 确定GO(I，X)核心项目[A→αX·β，a]之搜索符号a是从K中项目 B→γ·δ传递过来的； } } 最后，我们再考虑如何给每个LR(0)项目集的核心中的各个项目都配置一个搜索符号集，以获得各个LALR(1)项目集的核心。完成此项任务的大致过程如下。 (1) 为拓广文法G′构造全部LR(0)项目集的核心。 (2) 首先从初始项目集I0惟一的核心项目S′→·S (其搜索符号显然为#)开始，对每个LR(0)项目集的核心和每个文法符号X，利用上面的算法，确定GO(I，X)各核心项目的自生搜索符号集，并确定从I的哪些项目将搜索符号传递到GO(I，X)的核心项目。 (3) 按某种便于操作的结构，建立一张核心项目表，此项目表记录了每个项目集的各个核心项目及其相应的搜索符号集。开始时，这些搜索符号集仅是由第(2)步所确定的自生搜索符号集 (若该核心项目无自生向前搜索符号则为空)。 (4) 传递每个核心项目中的自生搜索符号，直到无法再进行传递为止。即反复扫视各项目集的每个核心项目，每当访问一个核心项目i时，便根据第(2)步所获的信息，将i当前要传递的搜索符号添加到承接它的那个核心项目之中，直至没有新的搜索符号要传递为止。 对一个给定的文法G而言，当它的各个LALR(1)项目集的核心构造出来之后，就能根据上面所描述的原理，为G构造相应的LALR(1)分析表。不过，尽管上述构造LALR分析表的方法效率较高，但对于常见的程序设计语言，企图用手工的方式来建立LALR分析表仍几乎是不可能的。所幸的是，目前已有一些自动生成LALR分析表的工具可资使用(如YACC)。 还应当指出，在构造LR语法分析器时，尚有若干技术问题需予以考虑，如二义性文法的处理，避免按单产生式的归约，等等。前者我们将在第5章介绍语法分析器自动生成工具时再进行讨论；至于后者，由于需涉及一些语义处理及其信息传递的细节，故就不再讨论了。 在结束本章时，我们还要给出如下的结论，这些结论的证明读者可参阅有关的文献(1，2，8，15)。 (1) 任何LR(K)，LL(K)及简单优先文法类都是无二义性的；对于算符优先文法，如果不考虑归约所得非终结符号的名字，也可认为是无二义性的。 (2) 任何二义性的文法都不可能是LR(1)(或LL(1))文法，但可借助于其它因素，如算符的优先级和结合规则以及某些语义解释等等，来构造无冲突的分析表。 (3) 每个SLR(K)文法都是LR( 各类文法之间的关系 各类文法之间的关系 K)文法，但却存在这样的LR(1)文法，它对任何K而言均不是SLR(K)文法。

说明：

rpc服框架，提供多语言的编译功能，并提供多种服务器工作模式；用户通过Thrift的IDL（接口定义语言）来描述接口函数及数据类型，然后通过Thrift的编译环境生成各种语言类型的接口文件，用户可以根据自己的需要采用不同的语言开发客户端代码和服务器端代码。

mac 上可以用 brew install thrift 进行安装 $thrift -version Thrift version 0.11.0 但是我们需要 0.9.2