第四部分第五七章语法分析

第四部分第五七章语法分析第一页，共一百九十八页，2022年，8月28日第四部分内容4.1自顶向下分析方法（第5章）4.2递归下降分析(递归子程序法)（第5章）4.3LL(1)分析方法（第5章）4.4自底向上分析方法（第6章）4.5算符优先分析法（第6章）4.6LR分析方法（第7章）第二页，共一百九十八页，2022年，8月28日一、语法分析是编译过程的核心部分语法分析的任务：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。语法分析程序的定义：执行语法分析任务的程序称为语法分析程序，也称为语法分析器，它是编译程序的主要部分之一。语法分析方法的分类：分成两大类。自顶向下分析和自底向上分析。第三页，共一百九十八页，2022年，8月28日二、语法分析的数学模型——下推自动机（1）下推机的逻辑结构PDA的读、写、状态转移动作决定于以下三个因素：当前所处状态读头所指符号下推栈栈顶符号一个输入串能为PDA所接受，仅当输入串读完，下推栈变空；或者输入串读完，控制器到达某些终态。有限状态控制器输入带输出带下推栈下推自动机逻辑结构第四页，共一百九十八页，2022年，8月28日（2）下推机的定义下推自动机是一个七元组M=(Q,Σ,H,δ,q0,z0,F)，其中：Q是控制器的有限状态集；Σ是输入字母表；H是下推栈内字母表；δ是Q×(Σ∪{ε})×H到Q×H*的有限子集映射；q0∈Q是控制器的初始状态；z0∈H是下推栈的栈初始符；F为Q的子集，是控制器的终态集。第五页，共一百九十八页，2022年，8月28日（3）说明映射函数δ描述PDA动作与状态的变化

δ(q,a,z)={(q1,γ1),(q2,γ2),…,(qn,γn)}

其中q,qi(1≤i≤n)∈Q,a∈Σ*,z∈H

含义：控制器当前状态为q，下推栈栈顶符号为z，输入符号为a(可为空)情况下，状态转换到序偶集(qi,γi),qi为下一状态，γi为代替z的栈顶符号串。映射函数δ不是单值映射，且下推机有两种接受状态：串读完进入终态和串读完栈空。例子：LL(1)语法分析器与PDA的对应关系 设CFGG=（VN，Σ，P，S），构造一个不确定的PDA M=（Q，Σ，H，δ，q0

，z0

，F），其中Q=F={q0}；H=VN∪

Σ；z0=S;δ映射关系的构造方法如下： 对于形如Aω

产生式，有δ(q,ε,A)=(q,ω)，

δ(q,a,a)=(q,ε)其中a∈Σ。第六页，共一百九十八页，2022年，8月28日4.1自顶向下分析方法4.1.1带回溯的自顶向下的分析方法4.1.2存在的问题及解决方法第七页，共一百九十八页，2022年，8月28日4.1.1带回溯的自顶向下的分析方法思路：对任一输入符号串，通过一切可能的办法，从树根结点(识别符号)出发，根据文法自上而下地为输入串建立一棵语法树；或者说，从识别符号开始，根据文法试图为输入串建立一个推导序列。特点：是自顶向下分析的一般方法，分析过程的本质是一种试探过程。第八页，共一百九十八页，2022年，8月28日以上文法没有左递归，且有以下两个特点：

(1)每个产生式的右部都由终结符号开始。

(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。

举例（1）确定的自顶向下分析第九页，共一百九十八页，2022年，8月28日以上文法没有左递归，且有以下特点：

(1)产生式的右部不全是由终结符开始。

(2)如果两个产生式有相同的左部，其右部是由不同的终结符或非终结符开始。

(3)文法中无空产生式。

第十页，共一百九十八页，2022年，8月28日以上推导过程的特点：在第二步到第三步的推导中，即abAS=>abS时，因为当前输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但A可以推出空，所以d的匹配任务就只能依赖于A后面的符号，所以选用产生式“A空”进行推导，句型中紧跟A后面的符号为S，S产生式右部的开始符号中包含了d，所以可匹配。

第十一页，共一百九十八页，2022年，8月28日假定有文法G[S]：(1)S::=cAd(2)A::=ab|a 对输入串w=cad。要求自上而下地构造w的语法树。解决过程：（2）非确定的自顶向下分析第十二页，共一百九十八页，2022年，8月28日分析：通过上述解答过程可以看出：自顶向下地为输入符号串w建立语法树的过程实际上就是设法建立w的一个最左推导序列。比如对于上例中的输入串w可以通过如下的推导过程将其推导出来：

S=>cAd=>cad

由于对输入串是自左向右扫描的，因此用最左推导，只有用最左推导，才能保证按扫描顺序去匹配输入串。第十三页，共一百九十八页，2022年，8月28日问题：缺陷：不能处理左递归文法(教材P88图5.6、图5.7)。缺点：存在回溯，算法效率低。（另：更多例子参阅教材P91）第十四页，共一百九十八页，2022年，8月28日4.1.2存在的问题及解决方法一、左递归问题 ①直接左递归 ②间接左递归二、回溯问题 实现不带回溯的自顶向下分析的条件 ①文法非左递归 ②首符号集不相交第十五页，共一百九十八页，2022年，8月28日(一)左递归问题（P88）①直接左递归 自顶向下分析方法不能处理具有左递归性的文法的原因：例如∶规则U::=U…是一条左递归规则，为了实现用U…匹配输入串，又会遇到要用U去匹配。故又要启用上述规则的右部符号串U…来完成匹配工作。如此循环下去而无法终止。第十六页，共一百九十八页，2022年，8月28日方法：用第二章中介绍的重复和选择表示法(扩充的BNF表示)去改写左递归规则。例如：规则：E::=E+T|T 改写为： E::=T{+T} 规则： T::=T*F|T/F|F 改写为： T::=F{*F|/F}

改写后的文法消除了直接左递归，且改写前后的文法是等价的。第十七页，共一百九十八页，2022年，8月28日将直接左递归规则转换成使用重复表示法的等价规则的处理原则：1.规则1(提取因子)：当出现规则U::=xy|xw|…|xz时，用规则U::=x(y|w|…|z)代替。其中，圆括号是元符号。特例：对规则U::=x|xy，则转换为U::=x(y|ε)，其中ε是空符号。第十八页，共一百九十八页，2022年，8月28日2.规则2令U::=x|y|…|z|Uv是一组规则，它具有一个直接左递归右部且位于最后。该规则表明：语法类U的成员是由x或y或…或z其后随有零个或多个v组成的。因此，可以把这组规则等价变换成U::=(x|y|…|z){v}。第十九页，共一百九十八页，2022年，8月28日算法：使用规则1，通过提取因子将规则改写成满足以下要求的形式：相对于某个非终结符号，至多只有一个直接左递归的右部；使用规则2，将规则改写为不含直接左递规的扩充的BNF形式，以消除直接左递归。第二十页，共一百九十八页，2022年，8月28日例题：1.规则：E::=E+T|T（1）变形为：E::=T|E+T（2）由规则2，改写为：E::=T{+T}2.规则：T::=T*F|T/F|F（1）规则1，改写为：T::=F|T(*F|/F)（2）规则2，改写为：T::=F{(*F|/F)}（3）删去圆括号为：T::=F{*F|/F}第二十一页，共一百九十八页，2022年，8月28日②间接左递归要求：（1）文法没有回路(即没有形如A=>A的推导)（2）不存在形如：A::=ε的规则。则可以按下述算法消除文法的左递归性。第二十二页，共一百九十八页，2022年，8月28日消除左递归算法(1)：①把G的非终结符整理成某种顺序A1,A2,…,An。②fori:=1step1untilndobeginforj:=1step1untili-1do 把每个形如Ai::=Ajr的规则替换成 Ai::=δ1r│δ2r│…│δkr， 其中Aj::=δ1│δ2│…│δk是当前的全部Aj规则；消除Ai规则中的直接左递归end③化简由②所得的文法，删除所有多余规则。第二十三页，共一百九十八页，2022年，8月28日例题：有文法G[S]：S::=Qc|cQ::=Rb|b R::=Sa|a解：该文法有间接左递归。例如有S=>Qc=>Rbc=>Sabc + 即S=>Sabc（1）首先将非终结符号排列成：R，Q，S的顺序。（2）将R代入Q得：Q::=Sab|ab|b将Q代入S得：S::=Sabc|abc|bc|c消除S的直接左递归：S::=(abc|bc|c){abc}（3）处理后的文法为：S::=(abc|bc|c){abc}Q::=Sab|ab|b R::=Sa|a

化简后的文法为：S::=(abc|bc|c){abc}第二十四页，共一百九十八页，2022年，8月28日消除左递归算法(2)[1]设G是一上下文无关文法，Vn＝{X1,X2,…Xn}，对每个形如Xi∷＝γ1|γ2|…|γm的产生式，根据γ的开始符号作如下等价变换：（1）将“|”表示成“＋”，“∷＝”表示成“＝”（2）以非终结符号Xi引导的γi表示成：Xiαi（3）以终结符号引导的所有γi之“和”看成常数项，表示成：βi变形后的产生式为：Xi＝X1α1i+X2α2i+…+Xnαni+βi（如产生式不含有以Xi打头的候选式，则相应的系数α为φ）产生式集可表示为：

α11α12α1n

α21（X1，X2，…，Xn）＝（X1，X2，…，Xn）＋（β1，β2

，…βn）

αn1αnn

即：X=XA+B，且其通解为：X=BA*化简X=BA*

？[1]j蒋立源.编译原理[M].西北工业大学出版社.P91－94第二十五页，共一百九十八页，2022年，8月28日消除左递归算法(2)设：

z11z12z1nεφφz21φεA*=Z=I=zn1znnφ

ε则可得以下矩阵方程组：

X=BZZ=I+AZ解以上方程组并化简即可得到不含左递规的文法例题：S->Sa|Ab|aA->Sc第二十六页，共一百九十八页，2022年，8月28日第二十七页，共一百九十八页，2022年，8月28日(二)回溯问题（P91）（1）消除回溯的理由前面介绍的带回溯的自顶向下的分析方法实际上采用了一种穷尽一切可能的选择试探法（三种回溯情形举例：教材P91），回溯需要记住每一步分析的现场，浪费时间和空间，因此，效率低，代价高。要构造一个行之有效的自顶向下的语法分析程序，就必须消除回溯。（2）消除回溯的思路为了避免回溯，要求对文法的任何非终结符号，主要是对那些规则右部有多个选择(候选式)的非终结符号，当要用它去匹配输入串时，能够根据所面临的输入符号准确地选用一个候选式去执行匹配任务，并且工作的结果应是确定的。即若此选择匹配输入串成功，那么这种匹配一定正确无误；若此选择无法完成匹配任务，则任何其他的选择也肯定无法完成。第二十八页，共一百九十八页，2022年，8月28日（3）消除回溯的方法——预测与提左因子1、预测预测就是根据读入的符号选择满足一定条件的候选式：使其第一个符号与读头下的符号相同，或该候选式可推导出的第一个符号与读头下符号相同。所以，对文法有如下要求：令G是一个不含左递归的文法，对每条规则中的每个候选式α定义它的终结首符集

First(α)={a|α=*>a…,a∈VT}第二十九页，共一百九十八页，2022年，8月28日设A∈VN，且Aα|β，如当前用A去匹配输入串，且输入符号为a时，对A的候选式的选择可以分成以下四种情况(当A不能推出ε时)：(1)若a∈First(α),而a!∈First(β)，选Aα;(2)若a!∈First(α),而a∈First(β)，选Aβ;(3)若a!∈First(α),而a!∈First(β)，输入有错；(4)若a∈First(α),同时a∈First(β)，终结符首集两两相交，则需要改写文法。第三十页，共一百九十八页，2022年，8月28日2、改造文法方法：提取公共左因子（a）假定关于非终结符A的产生式是：

Aαβ1|αβ2|…|αβn

那么可改写成两条规则：

AαA’

A’β1|β2|…|βn

（b）一般情况，若有关A的产生式是：

Aαδ1|αδ2|βδ3|βδ4|β

则可写成：

AαA’|βA” A’δ1|δ2

A”δ3|δ4|ε

第三十一页，共一百九十八页，2022年，8月28日结论：

即当规则右部具有n个选择，从每一个选择出发，都可以推导出一个以上的终结符号串。为了避免回溯，就要保证当用非终结符号A去匹配输入串时，能够根据当前读入的符号准确地选用它的一个候选式执行任务。即对文法的要求是：对任意一个非终结符号，当对应的规则右部有多个选择时，由各个选择所推出的终结符号串的首符号集合要两两不相交。当文法不满足避免回溯的条件时，可以改写文法，对规则右部反复提取左因子。第三十二页，共一百九十八页，2022年，8月28日

例题：规则：U::=xV|xW，（1）改写为：U::=x(V|W)

（2）引入一个新的非终结符号Y，则规则变换成：

U::=xY Y::=V|W

改写后的文法中，非终结符号U的右部只有一个选择，而引入的新非终结符号Y具有两个选择V或W，且这两个选择所推出的终结符号串所组成的头符号集合不相交。第三十三页，共一百九十八页，2022年，8月28日总结： 为了实现不带回溯（确定）的自顶向下分析，对文法来说，需要满足下述两个条件：①文法是非左递归的。②对文法的任一非终结符号，若对应的规则右部有多个候选式时，那么，各选择所推出的终结符号串的头符号集合要两两不相交。第三十四页，共一百九十八页，2022年，8月28日4.2递归下降分析(递归子程序法)（一）基本思路

对文法中每个非终结符号U（分别代表一种语法成分）都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。第三十五页，共一百九十八页，2022年，8月28日（二）非终结符号的语法分析子程序的功能

用该非终结符号的规则的右部符号串去匹配输入串。分析过程：按文法规则自左向右地逐个处理每个文法符号，处理方法如下。(1)对规则中的终结符号直接与输入匹配；(2)非终结符号则调用该符号的分析子程序来完成匹配，即当编译程序根据文法和当前的输入符号预测到下一个语法成分为U时，即预测到待匹配的输入符号串可以和U推导出的符号串相匹配时，就确定U为子目标，并调用分析和识别U的子程序来完成该子目标的分析匹配工作。第三十六页，共一百九十八页，2022年，8月28日（三）特点

在分析和识别某个语法成份的过程中，有可能还要确立其它子目标并调用相应的分析子程序。只有在被调用的分析和识别某语法成分的子程序匹配输入串成功并正确返回后，该语法成分的分析才能继续进行，并最终完成分析任务。所以该分析方法具有明显的预测性特征，并在分析过程中向下确立多级子目标。所以，该方法也被称为面向预测和目标的分析方法（Predictiveparser）。第三十七页，共一百九十八页，2022年，8月28日（四）例题

Z::=（U）|aUb U::=dZ|Ud|eProcedureZ;ifCLASS=‘（‘thenbegin nextsym; U; ifCLASS=‘）’then nextsym else errorend;elseifCLASS=‘a’thenbegin nextsym; U; ifclass=‘b’then nextsym else errorend;elseerror;第三十八页，共一百九十八页，2022年，8月28日ProcedureU;//首先要消除左递归：U::=(dZ|e){d}ifCLASS=‘d’thenbegin nextsym; Z; whileCLASS=‘d’do nextsymend;elseifCLASS=‘e’thenbegin nexteym; whileCLASS=‘d’donextsymendelse error;第三十九页，共一百九十八页，2022年，8月28日4.3LL(1)分析方法基本思路：

相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推导。 其中第一个L表示从左向右扫描输入符号串，第二个L表示生成最左推导，括号中的“1”，则表示在分析过程中，每进行一步推导，只要向前查看一个输入符号，便能确定当前所应选用的产生式(规则)。第四十页，共一百九十八页，2022年，8月28日4.3.1LL(1)分析器的逻辑结构及工作过程（一）逻辑结构（1）LL分析器的数学模型设CFGG=（VN，Σ，P，S），构造PDA如下：M=（Q，Σ，H，δ，q0，z0，F），其中Q=F={q0}；H=VN∪Σ；z0=S；δ映射关系的构造方法如下：对于形如Aω

产生式，有δ(q,ε,A)=(q,ω)，对于a∈Σ，

δ(q,a,a)=(q,ε)。

第四十一页，共一百九十八页，2022年，8月28日（2）LL分析器的逻辑结构一个LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成，其中：“输入”即待分析的符号串。分析表M用一个矩阵(或二维数组)来表示，它概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符号、终结符号或#相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素M[A,a]指示分析器应采取的动作。其中A∈Vt∪Vn∪{#}，a∈Vt∪{#}第四十二页，共一百九十八页，2022年，8月28日（二）工作过程 第一步：分析开始时，首先将符号#及文法的开始符号S依次置于分析栈的底部，并把各指示器调整至起始位置，即初始格局为然后，反复执行第二步的操作。第四十三页，共一百九十八页，2022年，8月28日第二步：设在分析的某一步，分析栈及余留的输入符号串处于如下的格局：其中，X1，X2，…Xm为分析过程中所产生的文法符号，此时，可视栈顶符号Xm的不同情况，分别进行如下操作：第四十四页，共一百九十八页，2022年，8月28日若Xm∈VN，则以Xm及ai组成符号对(Xm,ai)查分析表M。设M[Xm,ai]为一产生式，譬如说Xm→UVW，此时将Xm从分析栈中退出，并将UVW按反序推入栈中(即用该产生式推导)，从而得到新的格局但若M[Xm,ai]=“ERROR”，则调用出错处理程序进行处理；第四十五页，共一百九十八页，2022年，8月28日若Xm=ai≠#，则表明栈顶符号已与当前正扫描的输入符号匹配，此时应将Xm(即ai)从栈中退出，并将输入符号指示器向前推进一个位置；若Xm=ai=#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。第四十六页，共一百九十八页，2022年，8月28日分析流程如下：第四十七页，共一百九十八页，2022年，8月28日举例：

原始文法：消除左递归：第四十八页，共一百九十八页，2022年，8月28日第四十九页，共一百九十八页，2022年，8月28日第五十页，共一百九十八页，2022年，8月28日4.3.2LL(1)分析表的构造方法

LL(1)分析算法对不同的LL(1)文法都相同。即总控部分相同，仅仅是分析表不同，而且总控程序十分简单，容易实现。所以，LL(1)分析方法的核心是构造LL（1）分析表。第五十一页，共一百九十八页，2022年，8月28日（一）定义符号串α的首符号集假定α是文法G的任一符号串，即α∈(VT∪VN)*，定义：

FIRST(α)={a|α=*>a…，a∈VT}特别是，若α=>ε，则规定：ε∈FIRST(α)，即FIRST(α)是从α可能推导出的所有开头终结符号或可能的ε。第五十二页，共一百九十八页，2022年，8月28日（二）定义非终结符的尾符号集假定S是文法的开始符号，对于G的任何非终结符A，定义：

FOLLOW(A)={a|S=*>…Aa…,a∈VT}特别是，若S=*>…A，则规定#∈FOLLOW(A)。即FOLLOW(A)是所有句型中能够紧接A之后的终结符或#。（三）定义SELECT集（教材P78）对文法的产生式X→α，如α≠*>ε，则SELECT(X→α)＝FIRST(α)如α=*>ε，则SELECT(X→α)＝

(FIRST(α)–{ε})∪FOLLOW(X)第五十三页，共一百九十八页，2022年，8月28日（四）构造First集的算法1．定义法若X∈VT，则FIRST(X)={X}。若X∈VN，对形如X→aα的产生式(a∈VT)，或形如X→ε的产生式，把a或ε加进FIRST(X)。设G中有形如X→Y1Y2…Yk的产生式，若Y1∈VN，则把FIRST(Y1)中的一切非ε的符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2…Yi-1均为非终结符，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi)中的一切非ε的符号加进FIRST(X)；若对一切1≤j≤k，均有ε∈FIRST(Yj)，则将ε加进FIRST(X)。第五十四页，共一百九十八页，2022年，8月28日２．关系图法（1）首先求出能推出ε的非终结符号第五十五页，共一百九十八页，2022年，8月28日（2）然后按照下面步骤求解第五十六页，共一百九十八页，2022年，8月28日 对于文法G的任一符号串α=X1X2…Xn可按如下的步骤构造相应的FIRST(α)。置FIRST(α)=φ；把FIRST(X1)中的一切非ε符号加进FIRST(α)；依次进行下述操作：若ε∈FIRST(X1)，将FIRST(X2)中的一切非ε的符号加进FIRST(α)；若ε属于FIRST(X1)及FIRST(X2)，将FIRST(X3)中一切非ε的符号加进FIRST(α)；以此类推。最后，若对于1≤i≤n，ε∈FIRST(Xi)，则将ε加进FIRST(α)。第五十七页，共一百九十八页，2022年，8月28日（五）构造Follow集的算法1．定义法对于文法的开始符号，令#∈FOLLOW(S)。若G中有形如A→αBβ的产生式，且β≠ε，则将FIRST(β)中的一切非ε符号加进FOLLOW(B)。(即FOLLOW不含ε)若G中有形如A→αB或A→αBβ的产生式，且ε∈FIRST(β)，则FOLLOW(A)中的全部元素均属于FOLLOW(B)。第五十八页，共一百九十八页，2022年，8月28日2．关系图法第五十九页，共一百九十八页，2022年，8月28日（六）构造分析表的算法分析表M是一个二维表，每一行对应一个文法符号，每一列对应一个终结符号，元素的赋值规则如下：（1）对规则A→α，FRIST（α）中的每一终结符a，置M[A,a]=“POP，PUSH（α’）”。其中α’为α的倒置。若ε∈FIRST（α），则对属于FOLLOW(A)的每一终结符号b或#，置M[A,b]=“A→ε”。（2）把M中所有M[a,a]置为“POP，NEXTSYM”。（3）把M中所有不能按以上规则定义的元素均置为“ERROR”（出错）。

简化表示：可以省略分析表中所有终结符号对应的行。第六十页，共一百九十八页，2022年，8月28日定义：一个文法G，若它的分析表M不含多重定义元素，则称它是一个LL(1)文法。一个LL(1)文法是无二义的，它所定义的语言恰好就是它的分析表M所能识别的全部句子。可以证明，一个文法G是LL(1)文法，当且仅当对于G的每一个非终结符A的任何两条不同规则A::=α|β，下面的条件成立：（1）FIRST(α)∩FIRST(β)=φ，即由α和β推导不出以同一终结符a为首字符的符号串；且不应该都能推出空字符ε。（2）假若β=*>ε，则FIRST(α)∩FOLLOW(A)=φ；即若β=*>ε，则α所能推出的串的首符号不应在FOLLOW(A)中。教材P78:（即SELECT(A::=α)与SELECT(A::=β)不相交，且两者不能同时推出ε）第六十一页，共一百九十八页，2022年，8月28日主要结论：任何LL(1)文法都是无二义性的。若一文法中含有左递归的非终结符号，则它必然是非LL(1)文法。存在一种算法，它能判定任一文法是否为LL(1)文法。存在一种算法，它能判定任意两个LL(1)文法是否产生相同的语言。不存在这样的算法，它能判定任意上下文无关语言能否由LL(1)文法产生。非LL(1)语言是存在的。第六十二页，共一百九十八页，2022年，8月28日一、非LL（1）文法的改造

（四种改造情形举例：教材P85）,ε第六十三页，共一百九十八页，2022年，8月28日二、非LL（1）文法第六十四页，共一百九十八页，2022年，8月28日4.4自底向上分析方法（一）基本思路

自底向上的分析方法，也称为“移进—归约”法，这种方法的一般过程是：设置一个寄存符号的先进后出栈，称为符号栈，用来记录分析的历史和指示分析的下一步动作。第六十五页，共一百九十八页，2022年，8月28日（二）分析过程

在分析进行时，把输入符号一个个地按扫描顺序移进栈里，当栈顶符号串形成一个句柄(为某条规则的右部)时，就进行一次归约，把栈顶构成句柄的那个符号串用相应规则左部的非终结符号来代替。接着再检查在栈顶是否又出现了新的句柄，若出现新的句柄，就再进行归约；若没有形成新的句柄，则再从输入符号串移进新的符号，……，如此继续直到整个输入符号串处理完毕。最终如栈底为识别符号，则所分析的输入符号串为合法的句子，报告成功；否则，是不合法的符号串，报告错误。第六十六页，共一百九十八页，2022年，8月28日例1：有文法G[S]： (1)S::=aAcBe (2)A::=b (3)A::=Ab (4)B::=d分析符号串abbcde第六十七页，共一百九十八页，2022年，8月28日步骤栈内输入串输出带动作0#abbcde#1#abbcde#移进2#abbcde#移进3#aAbcde#2归约4#aAbcde#移进5#aAcde#2,3归约6#aAcde#移进7#aAcde#移进8#aAcBe#2,3,4归约9#aAcBe#移进10#S#2,3,4,1归约11识别成功abbcde的移进－归约过程：第六十八页，共一百九十八页，2022年，8月28日abbcde语法树的构造过程：第六十九页，共一百九十八页，2022年，8月28日（三）关键问题在自底向上分析中，如何寻找或确定一个句型的句柄，是构造一个自左向右扫描、自底向上分析方法必须要解决的一个关键问题。 下面介绍较为常用的两种方法： （1）算符优先分析方法 （2）LR分析法第七十页，共一百九十八页，2022年，8月28日4.5算符优先分析法4.5.1方法概述4.5.2直观算符优先分析法4.5.3算符优先分析法的进一步讨论第七十一页，共一百九十八页，2022年，8月28日4.5.1方法概述思路：

算符优先分析法是仿照算术式的四则运算过程而设计的一种语法分析方法。该方法首先要规定运算符之间的优先关系和结合性质，然后利用这种关系，通过比较相邻运算符的优先顺序来确定句型的“句柄”和进行归约。特点：

简单直观，最适用于表达式分析，宜于手工实现。第七十二页，共一百九十八页，2022年，8月28日例：有文法G[E]： E::=E+E|E-E|E*E|E/E|(E)|i试分析句子i+i-i*(i+i)根据运算符优先顺序和结合原则的规定对句子i+i-i*(i+i)进行归约，归约过程为：①#i+i-i*(i+i)# ②#E+i-i*(i+i)# ③#E+E-i*(i+i)#④#E-i*(i+i)# ⑤#E-E*(i+i)# ⑥#E-E*(E+i)#⑦#E-E*(E+E)# ⑧#E-E*(E)# ⑨#E-E*E#⑩#E-E# (11)#E#该归约过程是唯一的。第七十三页，共一百九十八页，2022年，8月28日在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子，解决了前面提到的问题，即：（1）可以只根据相邻运算符的优先关系，就能方便地并且唯一地确定归约的“句柄”；（2）同时还可以发现：该方法可以用来分析二义性文法所产生的语言。 上述文法是二义性的，但用算符优先法分析其句子时，其归约过程是唯一的。我们所规定的运算符之间的优先顺序和左结合的原则，就是避免二义性的充分条件。第七十四页，共一百九十八页，2022年，8月28日4.5.2直观算符优先分析法（1）算符优先分析的关键在于定义任何两个可能相邻的终结符a和b之间的优先关系 要求对于任何两个可能相继出现的终结符a和b具有形式：“…ab…”或“…aQb…”，Q∈VN，定义a，b之间有3种关系：(1)a＜b a的优先级低于b(2)a≈b a的优先级等于b(3)a＞b a的优先级高于b如果a和b在任何情况下不可能相继出现，则a，b之间不可比，即无关系；要与算术中的‘<’或‘>’区分，a＞b并不意味着b＜a，比如栈内的‘＋’大于栈外‘－’，同时栈内‘－’也大于栈外‘＋’。第七十五页，共一百九十八页，2022年，8月28日优先关系矩阵示例内外+*↑

i()#+＞＜＜＜＜＞＞*＞＞＜＜＜＞＞↑

＞＞＜＜＜＞＞i＞＞＞＞＞(＜＜＜＜＜≈)＞＞＞＞＞#＜＜＜＜＜≈第七十六页，共一百九十八页，2022年，8月28日（2）直观算符优先分析法的基本步骤使用两个工作栈OPTR（寄存运算符）和OPND（存放“操作数”和“运算结果”）；开始，将OPTR栈底置为‘#’，输入串尾设置右界符‘#’，OPND初始为空；令θ代表OPTR现行栈顶符号，a存放新输入的符号；则分析算法的基本步骤如下：第七十七页，共一百九十八页，2022年，8月28日(1)把下一个输入符号读至a中；(2)若a为运算数i，则把它压入OPND，转(1)；(3)若θ＞a，则调用θ的处理程序，处理子表达式E(1)θE(2)，同时，把θ从OPTR栈顶弹出，然后重新进入(3)；(4)若θ≈a，则按优先关系表有两种可能： ①θ=‘（’，a=‘）’，此时弹出OPTR顶的 ‘（’，放弃a中的‘）’，然后转(1)； ②θ=a=‘#’，结束；(5)若θ＜a，把a移进OPTR栈，转（1）;(6)θ与a不存在优先关系，则输入串有错。第七十八页，共一百九十八页，2022年，8月28日4.5.3算符优先分析法的进一步讨论(一)算符优先文法定义1：设有一文法G，如果G中没有形如U::=…VW…的规则，其中V和W是非终结符号，那么，就称G为算符文法（OG文法）第七十九页，共一百九十八页，2022年，8月28日定义2 设G是一OG文法，并令a和b是任意两个终结符号，U、V、W是非终结符号。终结符号的优先关系定义如下：（1）a

≈b，当且仅当文法中有形如U::=…ab…或U::=…aVb…的规则；(a、b同时归约)（2）a＜b，当且仅当文法中有形如U::=…aW…的规则，其中W=+>b…或W=+>Vb…；（b归约在前）（3）a＞b，当且仅当文法中有形如U::=…Wb…的规则，其中W=+>…a或W=+>…aV。（a归约在前）第八十页，共一百九十八页，2022年，8月28日三种优先关系和归约的先后顺序的图形解释（参见教材P108）第八十一页，共一百九十八页，2022年，8月28日定义3

设有一OG文法，如果在任意两个终结符号之间，在＜、＞和≈中至多只有一种关系成立，那么，这样的OG文法称为算符优先文法(OPG文法)。第八十二页，共一百九十八页，2022年，8月28日(二)构造优先关系矩阵定义1

非终结符号U的FIRSTVT集合

FIRSTVT(U)={a|U=*>a…或U=*>Va…}定义2

非终结符号U的LASTVT集合

LASTVT(U)={a|U=*>…a或U=*>…aV}第八十三页，共一百九十八页，2022年，8月28日

（1）构造FIRSTVT算法（LASTVT的构造算法与此类似）ProcedureInsert(U,b);ifnotF[U,b]then Begin F[U,b]:=TRUE;Push(U,b);//把(U,b)下推进STACK End第八十四页，共一百九十八页，2022年，8月28日主程序{F为2维数组，如b∈FIRSTVT(U)，则F[U,b]:=TRUE}

BEGINFor每个非终结符号U和终结符号bdo F[U,b]:=FALSE；{初始化为0}For每个形如U::=b…或U::=Vb…的规则 doInsert(U,b)WhileSTACK非空do Begin Pop(V,b){记STACK栈顶为(V,b)，弹出} For每条形如U::=V…的规则do Insert(U,b) EndofWhile;END第八十五页，共一百九十八页，2022年，8月28日例子：给定如下表达式文法G[E]:(0)E’→#E#，(1)E→E+T,(2)E→T,(3)T→T*F,(4)T→F,(5)F→P↑F|P,(6)P→(E),(7)P→i非终结符号的FIRSTVTLASTVT如右：第八十六页，共一百九十八页，2022年，8月28日（2）用图形法求FIRSTVT的算法（教材P105）图形法求解结果如右图所示：第八十七页，共一百九十八页，2022年，8月28日（3）构造优先关系表算法

For每条规则U::=x1x2…xnDOFori:=1TOn-1DO BEGIN IFxi和xi+1均为终结符号THEN 置xi

≈xi+1； IFxi为终结符号而xi+1为非终结符THEN 置xi

≈xi+2； IFxi为终结符号而xi+1为非终结符THEN ForFIRSTVT(xi+1)中的每个bDO置xi

＜b； IFxi为非终结符号而xi+1为终结符THEN ForLASTVT(xi)中的每个aDO置a

＞

xi+1； End第八十八页，共一百九十八页，2022年，8月28日例：设文法G[S]的产生式为：

SaAcBe AAb|b BdFIRSTVT(S)={a}FIRSTVT(A)={b}FIRSTVT(B)={d}LASTVT(S)={e}LASTVT(A)={b}LASTVT(B)={d}abcdea＜≈b＞＞c＜≈d＞e第八十九页，共一百九十八页，2022年，8月28日(三)算符优先分析算法设计定义4

文法句型的素短语是满足以下条件的一个短语，它至少包含一个终结符号，并且除它自身之外，不再包含其他素短语。第九十页，共一百九十八页，2022年，8月28日定理1 一个OPG句型的最左素短语是满足下列条件的最左子串Njaj…NiaiNi+1

aj-1

＜aj aj

≈aj+1,aj+1

≈aj+2,…,ai-2

≈ai-1,

ai-1

≈ai

ai

＞ai+1出现在aj左端或ai右端的非终结符号一定属于这个素短语。举例：P116图6.6、图6.7第九十一页，共一百九十八页，2022年，8月28日例子：

P110与规范归约的比较：第九十二页，共一百九十八页，2022年，8月28日继续往前扫描寻找素短语尾找到素短语尾往栈底搜索找素短语头找到素短语头S为分析栈，k为栈顶指针。第九十三页，共一百九十八页，2022年，8月28日注意：

(1)在查找所应归约的最左素短语的过程中，没有用到非终结符号，因此，在符号栈中放不放相应的非终结符号，对分析过程中寻找最左素短语没有影响。

(2)与归约为某个非终结符号相对应，语义程序分配一个工作单元来存放该子表达式的运算结果。所以，对语义处理程序来说，也不需要知道真正的非终结符号的名字。第九十四页，共一百九十八页，2022年，8月28日算符优先函数及其构造方法为什么要构造优先函数？

对具有n个终结符号（包括句子界符＃）的算符优先文法，其优先关系矩阵需要n2的存储空间。是否可能将空间消耗控制在n的线性复杂度范围内。第九十五页，共一百九十八页，2022年，8月28日算符优先函数及其构造方法

把每一个终结符θ与一对整数f(θ)、g(θ)联系在一起，其中f(θ)为终结符θ在栈内时的优先数，g(θ)为终结符θ在栈外的优先数。 （1）f(θ)与g(θ)的值应满足如下关系若θ1＜θ2

则f(θ1)<g(θ2)若θ1≈θ2

则f(θ1)=g(θ2)若θ1＞θ2

则f(θ1)>g(θ2)2个优先函数所需空间为2n第九十六页，共一百九十八页，2022年，8月28日（2）优先表与优先函数的关系1)优先函数并不等价于优先表，在优先表中没有关系的终结符对存在优先函数。2)有些优先表不存在对应的优先函数f和g。3)如果存在一对优先函数，则存在无穷多对优先函数。根据不同的算法从优先表转换推演出优先函数时也可能得到不同的结果。第九十七页，共一百九十八页，2022年，8月28日（3）从优先表转换为优先函数的算法算法一：逐次加1法1)对所有终结符a(包括#)，令f(a)=g(a)=c2)对所有终结符： 若a＞b且f(a)≤g(b)，则f(a):=g(b)+1

若a＜b且f(a)≥g(b)，则g(b):=f(a)+1

若a≈b且f(a)≠g(b)，则f(a)=g(b)=max(f(a)，g(b))3)重复步骤(2)直至f(a)，g(b)不再改变为止。如果f(a)或g(b)的任一值≥2n+c而步骤(2)还没结束，表示优先函数不存在。第九十八页，共一百九十八页，2022年，8月28日例：由G(E)文法的优先表构造优先函数的过程/P118IO+*↑

i()#+＞＜＜＜＜＞＞*＞＞＜＜＜＞＞↑

＞＞＜＜＜＞＞i＞＞＞＞＞(＜＜＜＜＜≈)＞＞＞＞＞#＜＜＜＜＜≈第1步：f(+)与g(+)、g(*)、…g(#)比较，按算法调整对应的f、g值；第2步：f(*)与g(+)、g(*)、…g(#)比较，按算法调整对应的f、g值；…第n步：f(#)与g(+)、g(*)、…g(#)比较，按算法调整对应的f、g值；第九十九页，共一百九十八页，2022年，8月28日以上优先函数的计算迭代三次收敛。不难看出对优先函数每个元素的值都增加同一个常数，优先关系不变，所以同一个文法的优先关系矩阵对应的优先函数可以不唯一。

但是也有一些优先关系矩阵中的优先关系是唯一的，却不存在优先函数。例如下面的优先关系矩阵：第一百页，共一百九十八页，2022年，8月28日构造算法二：Bell有向图方法1)对每个终结符a（包括#），令其对应两个节点fa和ga，画一张以所有fa和ga为节点的有向图，如果a＞b或a≈b，就从fa画一弧指向gb，若a＜b或a≈b，则从gb画一弧指向fa；2)令f(a)等于节点fa可达的节点数(包括自身)，令g(a)等于节点ga可达的节点数(包括自身)；3)检查构造出来的f(a)和g(a)，若与优先表符合则优先函数存在，否则不存在。第一百零一页，共一百九十八页，2022年，8月28日Bell有向图举例：i*+#fg67654322第一百零二页，共一百九十八页，2022年，8月28日4.6LR分析方法4.6.1概述4.6.2LR(0)分析器4.6.3SLR(1)分析器4.6.4规范LR(1)分析器4.6.5规范LALR(1)分析器4.6.6语法分析程序的自动生成工具—YACC第一百零三页，共一百九十八页，2022年，8月28日基本思路：

LR(K)分析器从左到右扫描所给定的输入串，并以相反的方向构造该输入串的最右推导(Right-mostDerive即规范推导)。LR(K)分析器根据分析栈的内容以及向前查看输入串中K个符号来决定分析动作。特点：（1）分析器对源程序中错误的诊断灵敏；（2）分析器对文法适应性强，文法分析能力强；（3）分析器结构复杂，K越大，相应的分析器愈复杂。当K＝0时，表示在确定分析动作时不需向前查看符号，LR（0）分析器是LR分析器中最简单的一种。LR（0）分析器分析能力弱，实用性差，一般仅作为构造更复杂的LR分析器的基础。第一百零四页，共一百九十八页，2022年，8月28日LR分析器的逻辑结构和工作原理

LR分析器的数学模型是下推自动机。该下推机具有一个输入机构，一个分析栈和一个有穷的控制系统。一般来说，其控制系统是一个具有多状态的有穷状态机。 总控程序输入带输出带下推栈下推自动机逻辑结构动作表状态转移表4.6.1概述第一百零五页，共一百九十八页，2022年，8月28日1、下推自动机的定义

M=〈θ，∑，Τ，R，q0，Z0

，F〉

θ：有穷状态集

Τ

：堆栈字母表 ∑：输入字母表

R：转换关系

(θ×(∑∪{ε})×Τ)→(θ×Τ*) q0

：初态

Z0

：初始堆栈，符号Z0∈Τ F：为θ的子集，是控制器的终态集第一百零六页，共一百九十八页，2022年，8月28日2、有穷自动机状态的分类有穷状态集Θ中的状态分成3类①读状态，当读一个终结符或非终结符时，发生由一个状态到另一状态的状态转移。②归约状态，识别出当前句型的活前缀的句柄部分。处于归约状态时，检测出来的句柄将归约为一个非终结符号。③识别状态，输入串被分析器成功识别。第一百零七页，共一百九十八页，2022年，8月28日3、LR(0)分析栈的结构

LR(0)分析器的分析栈是一个符号对偶栈。对偶的第一个元素是文法符号。对偶的第二个元素是分析器扫描一个文法符号时所进入的状态。XmXm-1………X1#SmSm-1………S1S0文法符号状态

第一百零八页，共一百九十八页，2022年，8月28日4、LR(0)分析过程

LR(0)分析器由总控程序和分析表两部分组成。分析开始时，栈内的初始状态为S0，即与分析器有关的有穷控制的开动状态。（1）当分析器处于读状态时，它将当前扫描到的符号压入堆栈，并执行由所读符号所指示的状态转移，并将该后继状态也压入栈内；（2）当分析器处于归约状态时，将对偶栈中与句柄对应的部分弹出进行归约，然后执行读操作，读入归约后的符号并压入堆栈。如果归约到的符号为识别符号，则分析器接受所给定的符号串并停机；否则，归约生成的左部符号和当前栈顶状态将确定下一个状态转移。第一百零九页，共一百九十八页，2022年，8月28日一、初始情况二、一般过程分析栈输入带对应“句型”S0#a1a2…an#

a1a2…an分析栈输入带对应“句型”S0S1…Sm

#

X1…Xmaiai＋1…an#

X1…Xmaiai＋1…an第一百一十页，共一百九十八页，2022年，8月28日（1）Ifaction[sm,ai]=si(shiftsi)then分析格局变为（2）Ifaction[sm,ai]=ri(Reducei)then表示用第i个产生式A→Xm-(k-1)…Xm进行归约，分析格局变为分析栈输入带S0S1…Sm－k

#X1…Xm－kAaiai＋1…an#

分析栈输入带S0S1…SmSi#X1…Xmaiai＋1…an#

第一百一十一页，共一百九十八页，2022年，8月28日然后查goto表，Ifgoto[sm-k,A]=si

then

格局变为（3）Ifaction[sm,ai]=accthen

分析成功分析栈输入带S0S1…Sm－kSi#X1…Xm－kAaiai＋1…an#

第一百一十二页，共一百九十八页，2022年，8月28日5、举例（P124）文法G[S]：S→aAcBeA→bA→AbB→d第一百一十三页，共一百九十八页，2022年，8月28日注意：分析中只需要状态栈信息1）因为分析器的有穷控制是确定的，所以文法符号可不必压入栈内。2）当到达一归约状态时，与该状态对应的句柄是确定的。第一百一十四页，共一百九十八页，2022年，8月28日4.6.2LR(0)分析器

LR(0)分析器是最简单的分析器，无需向前查看输入符号即可确定分析器的动作（如下面的分析表，栈顶状态为0、2、3、5、7时采取移进操作，状态4、6、8、9时采取归约操作，不需要查看输入符号）。LR(0)分析器是构造其它更为复杂的分析的基础。第一百一十五页，共一百九十八页，2022年，8月28日

LR分析器为一个输入串构造一个最左归约序列，即逆向构造最右（规范）推导。最右推导序列的特征分析：考虑文法G，其开始符号为S，对于输入串x，其规范推导序列为：

S≠>α1≠>α2…≠>αm-1≠αm=x在推导序列中的每一步都具有形式

ψBt=>ψβ

t式中αi=ψBt，B→β是所使用的产生式，t∈Vt*。第一百一十六页，共一百九十八页，2022年，8月28日定义：规范句型的活前缀对于规范句型ψβt，β表示句柄，如果ψβ=u1u2…ur，那么称符号串u1u2…ui(其中1≤i≤r)是句型ψβt的活前缀。其中包含了完整句柄的活前缀称为可归前缀，其它称为子前缀（P125）。注意：由定义可知所有活前缀都不包括句柄右边的任何符号(即t中的任何符号)。第一百一十七页，共一百九十八页，2022年，8月28日要建立输入串的最左归约序列，分析器的一个基本的功能就是要能检测当前规范句型的句柄，即能够识别出每一步规范推导ψBt=>ψβ

t中的ψβ（即规范句型的所有活前缀）。例子：文法G[S’]:（P126）[0]S’→S[1]S→aAcBe[2]A→b[3]A→Ab[4]B→d分析符号串abbcde第一百一十八页，共一百九十八页，2022年，8月28日a 活前缀为：aab[规则2归约] 可归前缀：ab，句柄为：baAb[规则3归约] 可归前缀：aAb

，句柄为：AbaAc 活前缀为：aAcaAcd[规则4归约] 可归前缀：aAcd

，句柄为：daAcBe[规则1归约]可归前缀：aAcBe

，句柄为：aAcBe

以上规范归约对应的最右推导如下：S≠>

aAcBe.→aAcb.e→aA.cde→aAb.cde→aA.bcde→ab.bcde→.abbcde

↑↑↑↑↑↑↑第一百一十九页，共一百九十八页，2022年，8月28日识别活前缀的NFA第一百二十页，共一百九十八页，2022年，8月28日化简NFA引入共同的初态结点X，用ε弧联结得到图7.3。化简后得到图7.4第一百二十一页，共一百九十八页，2022年，8月28日例子文法G：

E→T|E+T|E－T T→i|(E)引入一个新的开始符号S，得到拓广文法G’：

S→E# E→T|E+T|E－T T→i|(E)其中符号#为文法G所产生的终结符号串的右界符。考察句型：E-(i+i)#，建立其规范推导如下：S→E-T＃→E-(E)＃→E-(E+T)＃→E-(E+i)＃→E-(T+i)＃→E-(

i＋i)＃根据定义：E、E-、E-(、E-(i均为该句型的活前缀，E-(

i为可归前缀。拓展文法的目的：使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。i为句柄第一百二十二页，共一百九十八页，2022年，8月28日活前缀及可归前缀的一般计算方法（P128）定义规范句型中非终结符号A的左串集合为LC（A）推论：如文法中有产生式B→γAδ，则有第一百二十三页，共一百九十八页，2022年，8月28日根据以上推论和文法列出前缀集合方程[0]S’→S[1]S→aAcBe[2]A→b[3]A→Ab[4]B→d第一百二十四页，共一百九十八页，2022年，8月28日求解前缀集合方程第一百二十五页，共一百九十八页，2022年，8月28日一、LR(0)项目LR(0)项目定义文法G的一个项目是一个在右部符号串中标有一圆点的产生式，其形式为：A→α1·α2其中A→α1α2为G的一个产生式。对空产生式A→ε，其LR(0)项目只有一个为A→．项目的意义在于它可以表示分析的进程，圆点是项目中标识分析进度的一种记号，圆点前面的部分是已经分析过的内容，后面的部分表示下面将要分析的内容，显然圆点后面的部分带有明显的预期特征。根据项目的特点，可以将LR（0）项目划分成三种类型：（1）A→α1·aα2

其中a∈Vt

称为移进项目；（2）A→α1·Xα2

其中X∈Vn

称为待约项目；（3）A→α·

称为归约项目；举例：一般情况下，一个产生式可以有几个项目。例如，产生式E→E－T有下面四个项目：

E→·E－T E→E．－T E→E－．T E→E－T．第一百二十六页，共一百九十八页，2022年，8月28日二、有效性

LR分析器的有穷控制机构的任务是识别规范句型的句柄。因此，只有包含在规范句型中的LR（0）项目才是合法有效的。一个项目A→α1·α2对于某个规范句型ψα1·α2t的活前缀ψα1是有效的，当且仅当存在某个最右推导。

S≠>ψAt≠>ψα1·α2t其中t是终结符号串。第一百二十七页，共一百九十八页，2022年，8月28日举例：一般来说，活前缀与有效项目是多对多关系。例如，具有如下产生式的LR(0)文法 S→E# E→T|E+T|E－T T→i|(E)项目E→E－．T，T→．i和T→．(E)对活前缀E－全都是有效的，即一个活前缀对应多个有效项目。如最右推导： S=>E#=>E－．T#证明项目E→E－．T对E－是有效的。第一百二十八页，共一百九十八页，2022年，8月28日最右推导： S=>E#=>E－T#=>E－．i#证明项目T→．i对E－也是有效的。最右推导： S=>E#=>E－T#=>E－．(E)#证明项目T→．(E)对E－是有效的。请举出一个有效项目对应多个活前缀的例子？第一百二十九页，共一百九十八页，2022年，8月28日三、LR(0)分析器实现思路

LR分析器的基本功能是识别当前句型的句柄，LR（0）项目刻画了当前句型的句柄被分析的程度（句柄完全在分析栈外；句柄的一部分已经进入分析栈；句柄全部进入分析栈），通过建立LR（0）项目集与分析器的每个状态之间的联系，构造LR（0）分析器的有穷控制机构。第一百三十页，共一百九十八页，2022年，8月28日识别活前缀的有限自动机构造方法（方法1：直接法P131）（1）求出文法的所有LR(0)项目（2）按照一定规则构造NFA1.确定状态结点每一个LR(0)项目都是结点，且为活前缀识别状态，圆点在最右的项目为句柄识别状态。

2.生成转移弧线第一百三十一页，共一百九十八页，2022年，8月28日（3）将NFA确定化得到DFA

例子：P131（图7.7－7.8）第一百三十二页，共一百九十八页，2022年，8月28日四、LR(0)项目集规范族的构造（识别活前缀的有限自动机构造方法2）首先，将项目S→.α将作为有穷状态控制的开始状态，其中S为文法的开始符号。项目S→.α反映了此时分析器还没有识别任何(非空)活前缀。然后、需要对项目集中的该初始项目进行闭包(closure)运算。为了获得一个项目A→α1·Xα2的闭包(X为非终结符号)，应该将形式为X→.λ的项目添加到该项目集中。第一百三十三页，共一百九十八页，2022年，8月28日一）闭包(closure)运算定义设I为一项目集，定义CLOSURE(I)如下：（1）I中的每一个项目都属于CLOSURE(I)。（2）如项目A→α1·Xα2属于CLOSURE(I)，且X为非终结符号，则将形式为X→.λ的项目添加到CLOSURE(I)中。（3）重复（1）和（2），直到CLOSURE(I)封闭为止。二）后继项目定义令项目A→α.Xβ是对应某个状态U的项目集中的一个项目，则称项目A→αX.β为其后继项目，其中X为文法字汇表中的任一符号。三）状态转移 当扫描一输入符号或者分析器处于归约状态时，则在LR分析器的有穷控制中将发生状态转移。在分析器的构造过程中，读操作是建立新状态的一种手段。因为项目A→α.Xβ的后继项目A→αX.β将与机器中另一状态V相联系。所以，读操作对所扫描的符号X将定义由状态U到状态V的状态转移。第一百三十四页，共一百九十八页，2022年，8月28日举例：具有如下产生式的LR(0)文法 S→E# E→T|