第四章 语法分析程序设计语言构造的描述程序设计语言构造的语法可使用上下文无关文法或BNF表示法来描述文法可给出精确易懂的语法规则可以自动构
造出某些类型的文法的语法分析器文法指出了语言的结构，有助于进一步的语义处理/代码生成。支持语言的演化和迭代。语法分析器的作用基本作
用从词法分析器获得词法单元的序列，确认该序列是否可以由语言的文法生成。对于语法错误的程序，报告错误信息对于语法正确的程序，生成语法
分析树。通常并不真的生产这棵语法分析树语法分析器的分类通用语法分析器可以对任意文法进行语法分析效率很低，不适合用于编译器自顶向下语
法分析器从语法分析树的根部开始构造语法分析树自底向上语法分析器从语法分析树的叶子开始构造语法分析树后两种方法总是从左到右、逐个扫描
词法单元。只能处理特定类型的文法，但是这些文法足以用来描述程序设计语言。上下文无关文法定义：一个上下文无关文法包含四个部分终结符号
：组成串的基本符号（词法单元名字）非终结符号：表示串的集合的语法变量。给出了语言的层次结构。在程序设计语言中通常对应于某个程序构造
，比如stmt（语句）开始符号：某个被指定的非终结符号。它对应的串的集合就是文法的语言产生式集合：描述将终结符号和非终结符号组成串
的方法产生式的形式：头/左部 ? 体/右部头部是一个非终结符号，右部是一个符号串；例子：expression ? expre
ssion + term上下文无关文法的例子简单算术表达式的文法：终结符号：id + - / ( )非终结符号：express
ion, term, factor开始符号：expression产生式集合： expression ? expression +
term expression ? expression – term expression ? term term ? term
factor term ? term / factor term ? factor factor ? (expression
) factor ? id文法书写的约定终结符号靠前的小写字母(a,b,c)；运算符号(+ )；标点符号；数位；黑体字符串(id
, if, while)非终结符号靠前的大小字母(A,B,C)；字母S（通常是开始符号）；小写斜体字母；表示程序构造的大写字母X,
Y,Z文法符号（终结符号或非终结符号）小写希腊字母表示文法符号串(α, β, γ)靠后的小写字母表示终结符号串具有相同头的产生式可
以合并成A? α1 | α2| … | αn的形式通常第一个产生式的左部就是开始符号。文法简单形式的例子E ? E + T | E
– T | TT ? T F | T / F | FF ? ( E ) | id注意:| 是元符号（即文法描述方式中的符号，
而不是文法符号）这里(,)不是元符号；在有些地方会把( )看作元符号推导（1）推导：将待处理的串中的某个非终结符号替换为这个非终结
符号的某个产生式的体。从开始符号出发，不断进行上面的替换，就可以得到文法的不同句型例子文法: E ? -E | E+E | EE
| (E) | id推导序列：E => -E => -(E) => -(id)推导（2）推导的正式定义如果A?γ是一个产生式，那
么αAβ => αγβ最左(右)推导：α(β)中不包含非终结符号符号：经过零步或者多步推导出：对于任何串α α如果α
β且β=>γ，那么α γ经过一步或者多步推导出：α β等价于α β且α不等于β句型/句子/语言句型（
sentential form）：如果S==> α，那么α就是文法的句型可能既包含非终结符号，又包含终结符号；可以是空串句子（s
entence）文法的句子就是不包含非终结符号的句型语言文法G的语言就是G的句子的集合，记为L(G)w在L(G)中当且仅当w是G的
句子，即S==>w语法分析树推导的图形表示形式根结点的标号时文法的开始符号每个叶子结点的标号是非终结符号、终结符号或ε每个内部节
点的标号是非终结符号。每个内部结点表示某个产生式的一次应用内部结点的标号为产生式头，结点的子结点从左到右是产生式的体有时允许树的根
不是开始符号（对应于某个短语）。树的叶子组成的序列是根的文法符号的句型一棵分析树可对应多个推导序列，但是分析树和最左（右）推导序列
之间具有一一对应关系语法分析树的例子文法： E ? -E | E+E | EE | (E) | id句子：-(id+id)从推导
序列构造分析树假设有推导序列：A=a1=>a2 => … => an算法：初始化：a1的分析树是标号为A的单个结点假设已经构造出a
i-1=X1X2…Xk的分析树，且ai-1到a1的推导是将Xj替换为β，那么在当前分析树中找出第j个非ε结点，向这个结点增加构成β
的子结点。如果β=ε，则增加一个标号为ε的子结点）构造分析树的例子推导序列：E => -E => -(E) => -(E+E) =
> -(id+E) => -(id+id)二义性（1）二义性（ambiguous）：一个文法可以为某个句子生成多棵语法分析树，这个
文法就是二义性的例子：E => E+E => id+E=>id+EE => id+idE=>id+ididE => EE
=> E+EE=>id+EE => id+idE=> id+idid二义性（2）程序设计语言的文法通常都应该是无二义性的否
则就会导致一个程序有多种“正确”的解释。比如文法： E ? -E | E+E | EE | (E) | id 的句子a+bc但
有些二义性的情况可以方便文法或语法分析器的设计。但是需要消二义性规则来剔除不要的语法分析树比如：先乘除后加减证明文法生成的语言证明
文法G生成语言L可以帮助我们了解文法可以生成什么样的语言。基本步骤：首先证明L(G)?L然后证明L?L(G)一般使用数学归纳法证明
L(G)?L的方法之一：构造L’，使得L’?Vt=L；并证明S∈L’，且对于L’中的任意α，α=>β可推出β也在L中。也可以按照
推导序列长度进行数学归纳证明L?L(G)时，通常可按照符号串的长度来构造推导序列。文法生成语言的例子（1）文法：S?(S)S |
ε语言：所有具有对称括号对的串L(G)?L的证明：令L’={删除S后括号对称的串}，显然有L’?Vt=L且S ∈L’任意的删除S
后括号对称的串α，不管使用S?ε还是(S)S 推导出串β，删除β中的S后得到的串仍然是括号对称的。有上面两点可知：G的所有句型都属
于L’，且L’中的终结符号串就是L。可知L(G)?L。文法生成语言的例子（2）L?L(G)的证明：注意：括号对称的串的长度必然是偶
数。归纳基础：如果括号对称的串的长度为0，显然它可以从S推导得到归纳步骤：假设长度小于2n的括号对称的串都能够由S推导得到。假设w
是括号对称且长度为2n的串w必然以左括号开头，且w可以写成(x)y的形式，其中x也是括号对称的。因为x、y的长度都小于2n，根据归
纳假设，x和y都可以从S推导得到。因此S=>(S)S==>(x)y。上下文无关文法和正则表达式（1）上下文无关文法比正则表达式的
能力更强。即：所有的正则语言都可以使用文法描述但是一些用文法描述的语言不能用正则文法描述。证明：首先S?aSb | ab 描述了语
言{anbn|n>0}，但是这个语言无法用DFA识别。假设有DFA识别此语言，且这个文法有K个状态。那么在识别ak+1…的输入串时
，必然两次到达同一个状态。设自动机在第i个和第j个a时进入同一个状态，那么：因为DFA识别L，ajbj必然到达接受状态，因此aib
j必然也到达接受状态。直观地讲：有穷自动机不能数（大）数。上下文无关文法和正则表达式（2）证明（续）其次证明：任何正则语言都可以表
示为上下文无关文法的语言。任何正则语言都必然有一个NFA。对于任意的NFA构造如下的上下文无关文法对NFA的每个状态i，创建非终结
符号Ai。如果有i在输入a上到达j的转换，增加产生式Ai?aAj。如果i在输入ε上到达j，那么增加产生式Ai?Aj.如果i是一个接
受状态，增加产生式Ai?ε如果i是开始状态，令Ai为所得文法的开始符号。NFA构造文法的例子A0?aA0 | bA0 | aA1
A1?bA2A2?bA3A3? ε考虑baabb的推导和接受过程可知：NFA接受一个句子的运行过程实际是文法推导出该句子的过程。设
计文法文法能够描述程序设计语言的大部分语法但不是全部，比如：标识符的先声明后使用无法用上下文无关文法描述。因此：语法分析器接受的语
言是程序设计语言的超集。必须通过语义分析来剔除一些符合文法、但不合法的程序。二义性的消除(1)一些二义性文法可以被改成等价的无二义
性的文法例子：stmt ? if expr then stmt | if expr then stmt else stmt
|otherif E1 then if E2 then S1 else S2的两棵语法树二义性的消除(2)为了保证“else和
最近未匹配的then匹配”，我们要求在then分支的语句必须是匹配好的。引入matched_stmt表示匹配好的语句，有如下文法：
stmt ? matched_stmt | open_stmtmatched_stmt ? if expr then ma
tched_stmt else matched_stmt | otheropen_stmt ? if expr
then stmt | if expr then matched_stmt else open_stmt二义性的消除方法没有
规律可循。通常并不是通过改变文法来消除二义性。左递归的消除左递归的定义：如果一个文法中有非终结符号A使得A==>Aα，那么这个文
法就是左递归的。立即左递归（规则左递归）文法中存在一个形如A?Aα的产生式。自顶向下的语法分析技术不能处理左递归的情况，因此需要消
除左递归；但是自底向上的技术可以处理左递归。立即左递归的消除假设非终结符号A存在立即左递归的情形，假设以A为左部的规则有：A? A
α1 | Aα2 |…| Aαm | β1 | β2 |… | βn 可以替换为 A?β1A’ | β2A’|… | β
n A’ A’?α1A’ | α2A’ |…| αmA’ | ε由A生成的串总是以某个βi开头，然后跟上零个或者多个αi的重复。通
用的左递归消除方法输入：没有环和ε产生式的文法G输出：等价的无左递归的文法步骤：将文法的非终结符号任意排序为A1,A2,…,Anf
or i=1 to n do { for j = 1 to i-1 do {将形如Ai? Ajγ的产生式替换为Ai?δ1γ| δ2
γ | … |δnγ， 其中Aj? δ1| δ2|…| δm}是以Aj为左部的所有产生式； } 消除Ai的立即左递归；}内层循环
的每一次迭代保证了Ai的产生式的右部首符号都比Aj更加靠后。当内层循环结束时，Ai的产生式的右部首符号不先于Ai。消除立即左递归就
保证了Ai的产生式的右部首符号必然比Ai后。（不能有环和ε产生式）当外层循环结束时，所有的产生式都是如此。使用这些产生式当然不会产
生左递归的情形。通用左递归消除的例子S ? Aa | b A?Ac | Sd | ε步骤1：排列为S，Ai=1时：内层循环不运行
，S没有立即左递归；i=2时：j=1，处理规则A?Sd；替换得到A?Ac | Aad | bd | ε消除A的立即左递归S?Aa
| bA?bdA’ | A’A’?cA’ | adA’ | ε通用左递归消除的问题在于很难找到新文法和旧文法的推导之间的对应关系，
因此很难依据新文法进行语义处理。本例子中的ε产生式恰好没有影响算法的正确性预测分析法简介试图从开始符号推导出输入符号串；以开始符号
作为初始的当前句型每次为最左边的非终结符号选择适当的产生式；通过查看下一个输入符号来选择这个产生式。有多个可能的产生式时预测分析法
无能为力比如文法：E? +EE | -EE | id；输入为+ id - id id当两个产生式具有相同的前缀时无法预测文法：st
mt ? if expr then stmt else stmt | if expr then stmt输入：if a then
…新文法：stmt ? if expr then stmt elsePart elsePart ? else stmt |
ε需要提取公因子提取公因子的文法变换算法：输入：文法G输出：等价的提取了左公因子的文法方法：对于每个非终结符号A，找出它的两个或
者多个可选产生式体之间的最长公共前缀。A? αβ1 | αβ 2 | … | αβ n | γA?αA’ | γ A’?β1
| β 2 | … | β n 其中γ是不以α开头的产生式体提取公因子的例子文法：S ? i E t S | i E t S e
S | aE ? b对于S而言，最长的前缀是i E t S，因此：S ? i E t S S’| aS’?e S | εE ? b
非上下文无关语言的构造抽象语言 L1={wcw | w在(a|b)中}这个语言不是上下文无关的语言它抽象地表示了C或者Java中
“标识符先声明后使用”的规则。说明了这些语言不是上下文无关语言，不能使用上下文无关文法描述。通常用上下文无关文法描述其基本结构，不
能用文法描述的特性在语义分析阶段完成。原因是上下文文法具有高效的处理算法。自顶向下的语法分析为输入串构造语法分析树从分析树的根结点
开始，按照先根次序，深度优先地创建各个结点对应于最左推导。基本步骤确定对句型中最左边的非终结符号应用哪个产生式然后对句型中的非终结
符号和输入符号进行匹配关键问题是：确定对最左边的非终结符号应用哪个产生式自顶向下分析的例子文法：E?TE’ E’?+TE’ |
εT?FT’ T’?FT’| ε F?(E) | id输入id + id id分析树序列见右面（图4-12）递
归下降的语法分析递归下降语法分析程序由一组过程组成每个非终结符号对应于一个过程，该过程负责扫描非终结符号对应的结构程序执行从开始符
号对应的过程开始当扫描整个输入串时宣布分析成功完成递归下降分析技术的回溯如果没有足够的信息来唯一地确定可能的产生式，那么分析过程就
产生回溯。前面的算法报告错误（第7行）并不意味着输入串不是句子，而可能是表示前面选错了产生式。第一行上保存当前的扫描指针在第七行上
应该改成回退到保存的指针；GOTO (1)并选择下一个产生式；如果没有下一个产生式可选，报告错误。回溯需要来回扫描，低效如果嵌入
了语义处理，则需要撤销已经完成的语义处理动作。解决方法：设法通过一些信息确定唯一可能的产生式递归下降分析中回溯的例子文法：S?cA
d A?ab | a输入串：cad步骤：调用函数S；S选择唯一产生式S?cAd输入中的c和句型中的c匹配，继续调用AA首先选择产
生式A?ab，a和输入的a匹配，b和输入的d不匹配；回溯并选择下一个产生式A?a；a和输入的a相匹配；对A的调用返回；到S的调用；
S?cAd中的d和下一个输入匹配；对S的调用返回，已经读入所有输入符号；因此扫描结束，cad是句子。FIRST和FOLLOW（1）
在自顶向下的分析技术中，通常使用向前看几个符号来唯一地确定产生式（这里假定只看一个符号）当前句型是xAβ，而输入是xa…。那么选择
产生式A?α的必要条件是下列之一：α==>ε，且β以a开头；也就是说在某个句型中a跟在A之后；α==>a…；如果按照这两个条件
选择时能够保证唯一性，那么我们就可以避免回溯。因此，我们定义FIRST和FOLLOWFIRST和FOLLOW（2）FIRST(α)
：可以从α推导得到的串的首符号的集合；如果α==>ε，那么ε也在FIRST(α)中；FOLLOW(A)：可能在某些句型中紧跟在A
右边的终结符号的集合。FIRST的计算方法计算FIRST(X)的方法如果X是终结符号，那么FIRS(X)=X如果X是非终结符号，且
X?Y1Y2…Yk是产生式，如果a在FIRST(Yi)中，且ε在FIRST(Y1), FIRST(Y2),…, FIRST(Yi-
1)中，那么a也在FIRST(X)中。如果ε在FIRST(Y1), FIRST(Y2),…, FIRST(Yk)中，那么ε在FIR
ST(X)中。如果X是非终结符号，且X?ε是一个产生式，那么ε在FIRST(X)中计算FIRST(X1X2…Xn)的方法向集合中加
入FIRST(X1)中所有非ε的符号；如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε的符号；…如果ε在所有的F
IRST(X1)中，将ε加入FIRST(X1X2…Xn)中。FOLLOW的计算方法算法将右端结束标记$放到FOLLOW(S)中按照
下面的两个规则不断迭代，直到所有的FOLLOW集合都不再增长为止。如果存在产生式A?αBβ，那么FIRST(β)中所有非ε的符号都
在FOLLOW(B)中。如果存在一个产生式A?αB，或者A?αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都加
入到FOLLOW(B)中。请注意各个步骤中将符号加入到FOLLOW集合中的理由。FIRST/FOLLOW的例子（1）文法：E?TE
’ E’?+TE’ | εT ? FT’ T’?FT’ | ε F?(E) | idFIRST集合FIRST(F) = {(,
id}； FIRST(E) =FIRST(T) = {(,id}FIRST(E’) = {+, ε}; FIRST(T’)={
, ε}由此可以推出各个产生式右部的FIRST集合。FIRST/FOLLOW的例子（2）FOLLOW集合的计算过程$在FOLLO
W(E) 中（E是开始符号）由规则F?(E)可知，)也在FOLLOW(E)中由规则E?TE’ 可知FOLLOW(E’)也包含了$和
)。注意：因为E’只出现在E和E’的产生式的尾部，因此FOLLOW(E’)必然等于FOLLOW(E)。由规则E’?+TE’，FIR
ST(E’) 中的+在FOLLOW(T)中；且FIRST(E’) 包含ε，因此FOLLOW(E’)中的$和)也在FOLLOW(T)
中。因为T’只出现在T’和T的产生式的末尾，可以FOLLOW(T’)=FOLLOW(T)；由规则T?FT’且T’可以推导出ε，因此
可知FOLLOW(F)包含FOLLOW(T)；同时FIRST(T’)也在FOLLOW(F)中。因此 E：{$,)} E’：{$
,)} T,T’：{+, ), $} F：{+,,),$}LL(1)文法（1）定义:对于文法的任意两个不同的产生式A?α|β
不存在终结符号a使得α和β都可以推导出以a开头的串α和β最多只有一个可以推导出空串如果β可以推导出空串，那么α不能推导出以FOLL
OW中任何终结符号开头的串；等价于：FIRST(α)?FIRST(β)=Φ;（条件一、二）如果ε∈FIRST(β)，那么FIRST
(α) ?FOLLOW(A)=Φ；反之亦然。（条件三）考虑：对于一个LL(1)文法，我们期望从A推导出以终结符号a开头的符号串，我
们如何选择产生式？有多个选择吗？LL(1)文法（2）对于LL(1)文法，可以在自顶向下分析过程中，根据当前输入符号来确定使用的产生
式。例如：产生式：stmt ? if (exp) stmt else stmt | while (exp) stmt
| a输入：if (exp) while (exp) a else a首先选择产生式stmt ? if (exp) stmt e
lse stmt 得到句型if (exp) stmt else stmt 然后发现要把句型中的第一个stmt展开，选择产生式stm
t ?while (exp) stmt，得到句型if (exp) while (exp) stmt else stmt 。然后再展
开第一个stmt，得到if (exp) while (exp) a else stmt …预测分析表构造算法输入：文法G输出：预测
分析表M方法：对于文法G的每个产生式A?α对于FIRST(α)中的每个终结符号a，将A?α加入到M[A,a]中；如果ε在FIRST
(α)，那么对于FOLLOW(A)中的每个符号b，将将A?α加入到M[A,b]中。最后在所有的空白条目中填入error。预测分析表
的例子文法：E?TE’ E’?+TE’ | εT ? FT’ T’?FT’ | ε F?(E) | idFIRST集：F：
{(, id}； E,T：{(,id}； E’： {+, ε}; T’：{, ε}FOLLOW集：E：{$,)} E’：{$,
)} T,T’：{+, ), $} F：{+,,),$}这个例子恰巧使得每个产生式的右部的第一个符号的FIRST集合就等于产生式
右部的FIRST集合。但是在一般情况下不总是这样的。预测分析表冲突的例子文法：S?iEtSS’ | a S’?eS | ε E
?bFIRST(eS)={e}，使得S’?eS在M[S’,e]中；FOLLOW(S’)={$,e}使得S’? ε也在M[S’,e]
中注意：LL(1)文法必然不是二义性的；而这个文法是二义性的LL(1)文法的递归下降分析递归下降语法分析程序由一组过程组成每个非终
结符号对应于一个过程，该过程负责扫描非终结符号对应的结构可以使用当前的输入符号来唯一地选择产生式如果当前输入符号为a，那么选择M[
A,a]中的产生式非递归的预测分析（1）在自顶向下分析的过程中，我们总是匹配掉句型中左边的所有终结符号；对于最左边的非终结符号，我
们选择适当的产生式展开。匹配成功的终结符号不会再被考虑，因此我们只需要记住句型的余下部分，以及尚未匹配的输入终结符号串。由于展开的
动作总是发生在余下部分的左端，我们可以用栈来存放这些符号。非递归的预测分析（2）分析时的处理过程：初始化时，栈中仅包含开始符号；如
果栈顶元素是终结符号，那么进行匹配如果栈顶元素是非终结符号使用预测分析表来选择适当的产生式；在栈顶用产生式右部替换产生式左部；因此
对所有文法的预测分析都可以共用同样的驱动程序。分析表驱动的预测分析器性质1：如果栈中的符号序列为α，而w是已经被读入的部分输入，w
’是尚未处理的输入；那么S推导出wα我们试图从α推导出余下的输入终结符号串w’预测分析程序使用M[X,a]来扩展X，将此产生式的右
部按倒序压入栈中请注意：这样的操作使得分析过程中性质1得到保持。预测分析算法输入：串w，预测分析表M输出：如果w是句子，输出w的最
左推导；否则报错方法：初始化：输入缓冲区中为w $；栈中包含S$；ip指向w的第一个符号；令X=栈顶符号，ip指向符号aif(X=
=a) 出栈，ip向前移动；/和终结符号的匹配/else if (X是终结符号) error()；/失配/else i
f (M[X,a]是报错条目) error();/无适当的产生式/else if (M[X,a]=X?Y1Y2…Yk) {
输出产生式X?Y1Y2…Yk；弹出栈顶符号X； 将Yk,Yk-1,…,Y1压入栈中；}不断执行第二步；直到要么报错，要么栈中为
空分析表驱动预测分析的例子文法4.28，输入：id+idid;注意：已经匹配部分加上栈中符号必然是一个最左句型预测分析中的错误恢
复错误恢复当预测分析器报错时，表示输入的串不是句子。对于使用者而言，希望预测分析器能够进行恢复，并继续语法分析过程，以便在一次分析
中找到更多的语法错误。有可能恢复得并不成功，之后找到的语法错误有可能是假的。进行错误恢复时可用的信息：栈里面的符号，待分析的符号两
类错误恢复方法：恐慌模式短语层次的恢复恐慌模式基本思想语法分析器忽略输入中的一些符号，直到出现由设计者选定的某个同步词法单元；解释
：语法分析过程总是试图在输入的前缀中找到和某个非终结符号对应的串；出现错误表明现在已经不可能找到这个非终结符号（程序结构）的串。如
果编程错误仅仅局限于这个程序结构，那么我们可以考虑跳过这个程序结构，假装已经找到了这个结构；然后继续进行语法分析处理。同步词法单元
就是这个程序结构结束的标志。同步词法单元的确定非终结符号A的同步集合的启发式规则FOLLOW(A)的所有非终结符号A的同步集合中这
些符号的出现可能表示之前的那些符号是错误的A的串；将高层次的非终结符号对应串的开始符号加入到较低层次的非终结符号的同步集合比如语句
的开始符号，if，while等可以作为表达式的同步集合；FIRST(A)中的符号加入到非终结符号A的同步集合。碰到这些符号时，可能
意味着前面的符号是多余的符号如果A可以推导出空串，那么把此产生式当作默认值。在匹配时出现错误，可以直接弹出相应的符号；哪些符号需要
确定同步集合需要根据特定的应用而定。恐慌模式的例子（1）对文法4.28的表达式进行语法分析时，可以直接使用FIRST、FOLLOW
作为同步集合。我们为E、T和F设定同步集合；空条目表示忽略输入符号；synch条目表示忽略到同步集合，然后弹出非终结符号；终结符号
不匹配时，弹出栈中终结符号；恐慌模式的例子（2）错误输入： id + id短语层次的恢复在预测语法分析表的空白条目中插入错误
处理例程的函数指针；例程可以改变、插入或删除输入中的符号；发出适当的错误消息；自底向上的语法分析为一个输入串构造语法分析树的过程；
从叶子（输入串中的终结符号，将位于分析树的底端）开始，向上到达根结点；在实际的语法分析过程中并不会真的构造出相应的分析树，但是分析
树概念可以方便理解；重要的自底向上语法分析的通用框架移入-归约；LR：最大的可以构造出移入-归约语法分析器的语法类分析过程示例归约
自底向上语法分析过程看成从串w“归约”为文法开始符号的过程；归约步骤：一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结
符号；问题：何时归约（归约哪些符号串）？归约到哪个非终结符号？归约的例子id id的归约过程id id ，Fid，Fi
d，TF，T，E对于句型Tid，有两个子串和某产生式右部匹配T是E?T的右部；id是F?id的右部；为什么选择将id归约为F，
而不是将T归约为E？原因：T归约为E之后，Eid不再是句型；问题：如何确定这一点？句柄剪枝对输入从左到右扫描，并进行自底向上语法
分析，实际上可以反向构造出一个最右推导；句柄：最右句型中和某个产生式体匹配的子串，对它的归约代表了该最右句型的最右推导的最后一步；
正式定义：如果S αAw αβw；那么紧跟α之后的A?β的一个句柄；在一个最右句型中，句柄右边只有终结符号如
果文法是无二义性的，那么每个句型都有且只有一个句柄。句柄的例子输入：id id移入-归约分析技术使用一个栈来保存归约/扫描移入的
文法符号；栈中符号（从底向上）和待扫描的符号组成了一个最右句型；开始时刻：栈中只包含$，而输入为w$；成功结束时刻：栈中$S，而输
入$；在分析过程中，不断地移入符号，并在识别到句型时进行归约；句柄被识别时总是出现在栈的顶部；主要分析动作移入：将下一个输入符号移
动到栈顶；归约：将句柄归约为相应的非终结符号;句柄总是在栈顶。具体操作时弹出句柄，压入被归约到的非终结符号。接受：宣布分析过程成功
完成；报错：发现语法错误，调用错误恢复子程序；归约分析过程的例子为什么句柄总是在栈顶？（1）为什么每次归约得到的新句型的句柄仍不在
栈顶？考虑最右推导的两个连续步骤的两种情况A被替换为βBy，然后产生式体中的最右非终结符号B被替换为γ。（归约之后句柄为βBy）A
首先被展开，产生式体中只包含终结符号；下一个最右非终结符号B位于y左侧。移入-归约分析中的冲突对于有些不能使用移入-归约分析的文法
，不管用什么样的移入-归约分析器都会到达这样的格局即使知道了栈中所有内容、以及下面k个输入符号，人们仍然无法知道是否该进行归约，或
者不知道按照什么产生式进行归约；形式化地表达：设栈中符号串是αβ，接下来的k个符号是x，产生移动/归约冲突的原因是存在y和y’使得
aβxy是最右句型且β是句柄，而aβxy’也是最右句型，但是句柄还在右边。归约/归约冲突的例子输入为id ( id , id )冲
突时的格局：栈：…id ( id输入：, id ) …某个语言中，多维数组的表示方法。LR语法分析技术LR(k)的语法分析概念L表
示最左扫描，R表示反向构造出最右推导；k表示最多向前看k个符号；当k的数量增大时，相应的语法分析器的规模急剧增大；K=2时，程序设
计语言的语法分析器的规模通常非常庞大；当k=0、1时已经可以解决很多语法分析问题，因此具有实践意义。因此，我们只考虑k<=1的情况
。LR语法分析器的优点由表格驱动；虽然手工构造表格工作量大，但表格可以自动生成；对于几乎所有的程序设计语言，只要写出上下文无关文法
，就能够构造出识别该构造的LR语法分析器。最通用的无回溯移入-归约分析技术，且和其它技术一样高效；可以尽早检测到错误。能分析的文法
集合是LL(k)文法的超集LR(0)项文法的一个产生式加上在其产生式体中某处的一个点。A?.XYZ，A?X.YZ，A?XY.Z，A
?XYZ.注意：A?ε只对应一个项A?.直观含义：项A? α.β表示已经扫描/归约到了α，并期望接下来的输入中经过扫描/归约得到β
。然后把αβ归约到A。如果β为空，表示我们可以把α归约为A。项也可以用一对整数表示。(i,j)表示第i条规则，点位于右部第j个位置
项和最右推导的关系构造以项为状态的NFA开始状态S’?.S；转换：A?α.Bβ到B?. γ有一个ε转换，从A?α.Xβ到A?αX.
β有一个X转换。接受状态：A?α.，即点在最后的项这个NFA接受的语言是最右句型的包含其句柄，但是不包含句柄右边符号的前缀NFA运
行和句柄的关系文法E’?E E?E+T | T T?TF | F F?id最右句型E+TF+id+id句柄为TF分
析树见右图句柄的确定只和每一层最左边的推导有关系；和右边的推导无关沿着分析树的左边缘遍历可以和NFA的运行类比上层到下一层的推导即
NFA中的ε边；同一层中从左向右即NFA的非ε边如果能够走到某个分支的最右边，就找到了句柄E’EE +
TE + TT FE + Tid
id规范LR(0)项集族的构造增广文法：G的增广文法G’是在G中增加新开始符号S’，并加入产生式S’?S而得到的。显然G
’和G接受相同的语言，且按照S’?S进行归约实际上就表示已经将输入符号串归约成为开始符号。规范LR(0)项集族即LR(0)自动机的
状态集合；LR(0)自动机实际上是前面的NFA对应的DFA。构造过程中用到的子函数CLOSURE(I)：I的项集闭包对应于DFA化
算法的 ε-CLOSUREGOTO(I,X)：I的X后继对应于DFA化算法的MOVE(I,X)。CLOSURE(I)的构造算法（1
）算法：首先将I中的各个项加入到CLOSURE(I)中；如果A?α.Bβ在CLOSURE(I)中，那么对B的任意产生式B?γ，将B
?.γ加到CLOSURE(I)中；不断重复第二步，直到收敛。第二步的分析含义：项A?α.Bβ表示期望在接下来的输入中归约到B。显然
，要归约到B，首先要扫描归约到B的某个产生式的右部；因此对每个产生式B?γ，加入B?.γ；表示它期望能够扫描归约到γ。注意和 ε-
CLOSURE的对应关系构造算法的伪代码描述闭包构造的例子增广文法：E’?E E?E+T | T E?TF | F F?(E
) | id项集{[E’?.E]}的闭包[E’?.E]在闭包中；[E?.E+T]，[E?.T]在闭包中；[T?.TF]，[T?.
F]在闭包中；[F?.(E)]，[F?.id]在闭包中；LR(0)项集中的内核项和非内核项在算法中，在加入某个项B?.γ时，所有以
B为左部的产生式所对应的（点在最左边的）项都会被加入内核项：初始项S’?.S、以及所有点不在最左边的项非内核项：除了S’?.S之外
、点在最左边的项；实现算法时可以考虑只保存相应的非终结符号；甚至可以只保存内核项，而在要使用非内核项时调用CLOSURE函数重新计
算。GOTO函数GOTO(I,X)：项集{[A?αX.β] | [A?α.Xβ] ∈I} 的闭包根据项的历史-期望的含义，GOTO
(I,X)表示读取输入中的X或者归约到一个X之后的情况。GOTO(I,X)定义了LR(0)自动机中状态I在X之上的转换。例如：I=
{[E’?E.],[E?E.+T]}；GOTO(I,+)计算如下：I中只有一个项的点后面跟着+，对应的项为[E?E+.T]；CLO
SURE({[E?E+.T]}) = {[E?E+.T]，[T?.TF], [T?.F]，[F?.(E)]，[F?.id]}。求
LR(0)项集规范族的算法从初始项集开始，不断计算各种可能的后继，直到生成所有的项集。建议和NFA的子集构造算法类比项集规范族和G
OTO函数的例子LR(0)自动机的构造构造方法：规范LR(0)项集族中的项集可以作为LR(0)自动机的状态，GOTO(I,X)=J
，则从I到J有一个标号为X的转换；初始状态为CLOSURE({S’?.S})对应的项集；接受状态：包含形如A? α.的项集对应的状
态。LR(0)自动机的作用（1）假设文法符号串γ使LR(0)自动机从开始状态运行到状态（项集）j如果j中有一个形如A?α.的项。那
么在γ之后添加一些终结符号可以得到一个最右句型，α是γ的后缀，且A?α是这个句型的句柄表示可能找到了当前最右句型的句柄如果j中存在
一个项B?α.Xβ。那么在γ之后添加Xβ，然后再添加一个终结符号串可得到一个最右句型，在这个句型中B?αXβ是句柄此时表示还没有找
到句柄，需要移入LR(0)自动机的作用（2）LR(0)自动机的使用移入-归约时，LR(0)自动机被用于识别句型已经归约/移入得到的
文法符号序列对应于LR(0)自动机的一条路径；如果路径到达接受状态，表明栈上端的某个符号串可能是句柄。不需要每次用归约/移入得到的
串来运行LR(0)自动机路径被放到栈中；且文法符号可以省略，因为由LR(0)状态可以确定相应文法符号在移入后，根据原来的栈顶状态即
可知道新的状态；在归约时，根据归约产生式的右部长度弹出相应状态，仍然可以根据此时的栈顶状态计算得到新状态。LR(0)的作用演示：分
析idid根据LR(0)自动机状态和符号的对应关系，可以得到符号栏中的符号串。LR语法分析器的结构所有的分析器都使用相同的驱动程
序分析表随文法以及LR分析技术的不同而不同。栈中存放的是状态序列；可以由状态序列求出符号序列分析程序根据栈顶状态、当前输入，通过分
析表确定语法分析动作。LR语法分析表的结构两个部分：动作ACTION，转换GOTOACTION有两个参数：状态i、终结符号a移入j
：j是一个状态。把j压入栈；归约A?β：把栈顶的β归约为A。接受：接受输入、完成分析。报错：在输入中发现语法错误。状态集上的GOT
O函数如果GOTO[Ii,A]=Ij，那么GOTO[i,A] = j。LR语法分析器的格局LR与法分析器的格局包含了栈中内容和余下
输入 (s0s1…sm, aiai+1…an$)第一个分量是栈中的内容（右侧是栈顶）第二个分量是余下输入LR语法分析器的每一个
状态都对应一个文法符号（s0除外）。如果进入状态s的边的标号为X，那么s就对应于X。回忆LR(0)的构造方法可知，进入一个状态的边
的标号相同令Xi为si对应的符号，那么X1X2…Xm aiai+1…an对应于一个最右句型LR语法分析器的行为对于格局(s0s1…
sm, aiai+1…an$)，LR语法分析器查询条目ACTION[sm,ai]确定相应动作：移入s：执行移入动作，将s（对应a）
移入栈中，新格局(s0s1…sms，ai+1…an$)归约A?β，将栈顶的β归约为A，压入状态s： (s0s1…sm-rs，a
iai+1…an$)， 其中r是β的长度，s=GOTO[sm-r,A]；接受：语法分析过程完成报错：发现语法错误，调用错误恢复例程
。LR语法分析算法输入：文法G的LR语法分析表，输入串w输出：如果w在L(G)中，输出最左归约步骤（反过来就是最右推导），否则输出
错误指示。算法如下：LR分析表的例子文法： (1)E?E+T (2)E?T (3)T?TF (4)T?F (5)F?
(E) (6)F?idLR分析过程的例子输入：idid+idSLR语法分析表的构造SLR语法分析表以LR(0)自动机为基础：增
广文法G’的SLR语法分析表构造算法：构造G’的LR(0)项集规范族{I0,I1,…,In}。状态i对应于项集Ii，相关的ACTI
ON表/GOTO表条目如下：[A?α.aβ]在Ii中，且GOTO(Ii,a)=Ij,那么A[i,a]=sj。[A?α.]在Ii中，
那么对FOLLOW(A)中所有a，A[i,a]=按A?α归约如果[S’?S.]在Ii中，那么将ACTION[i,$]设置为“接受”
如果GOTO(Ii,A)=Ij,那么GOTO表中，GOTO[i,A]=j。空白的条目设置为error。如果SLR分析表中没有冲突，
这个文法就是SLR的。SLR的基本思想是：要把归约成为A，后面必须是FOLLOW(A)中的终结符号；否则只能移入SLR分析表构造的
例子项集I0: E’?.E E?.E+T E?.T T?.TF T?.F F?.(E) F?.idACTION[0,(] =
s4, ACTION[0,id]=S5GOTO[0,E]=1 GOTO[0,T]=2 GOTO[0,F] = 3项集I1：E
’?E. E?E.+TACTION[1,$] = 接受；ACTION[1,+] = s6项集I2：E?T. T?T.FACTIO
N[2,]=s7 ACTION[2,$/+/)]=归约E?T非SLR(1)文法的例子S?L=R | RL?R | idR?L对
于I2，第一个项使ACTION[2,=]=s6,第二个项使ACTION[2,=]=归约R?L.SLR的原理：可行前缀（1）LR(0
)自动机刻画了可能出现在语法分析栈中的文法符号串。直接把项当作状态，可以构造得到一个NFA。然后确定化得到DFA就是LR(0)自动
机可行前缀：可以出现在移入-归约语法分析器栈中的右句型前缀。定义：某个右句型的前缀，且没有越过该句型的句柄的右端。有效项：如果存在
S到αAw==>αβ1β2w，那么我们说项A?β1 . β2么对αβ1有效。SLR的原理：可行前缀（2）如果我们知道A?β1 .
β2对αβ1有效，当β2不等于空，表示句柄尚未出现在栈中，应该移入或者等待归约；如果β2等于空，表示句柄出现在栈中，应该归约。如果
某个时刻存在两个有效项要求执行不同的动作，那么就应该设法解决冲突。冲突实际上表示可行前缀可能是两个最右句型的前缀，第一个包含了句柄
，而另一个尚未包含句型E+T+id E+TidSLR解决冲突的思想：假如要按照A?β进行归约，那么得到的新句型中A后面
跟随下一个输入符号。因此只有当下一个输入在FOLLOW(A)中时才可以归约。也可能都认为包含句柄，但是规则不一样SLR的原理：可行
前缀（3）如果在文法G的LR(0)自动机中，从初始状态出发，沿着标号为γ的路径到达一个状态，那么这个状态对应的项集就是γ的有效项集
。回顾确定分析动作的方法，就可以知道我们实际上是按照有效项来确定的。为了避免冲突，归约时要求下一个输入符号在FOLLOW(A)中。
活前缀/有效项的例子可行前缀E+T对应的LR(0)项T?T.F F?.(E)F?.id对应的最右推导E’?E?E+T?E+T
FE’?E?E+T?E+TF?E+T(E)E’?E?E+T?E+TF?E+TidSLR语法分析器的弱点（1）SLR技术解决
冲突的方法：项集中包含[A?α.]时，按照A?α进行归约的条件是下一个输入符号a可以在某个句型中跟在A之后。如果对于a还有其它的移
入/归约操作，则出现冲突。假设此时栈中的符号串为βα，如果βAa不可能是某个最右句型的前缀，那么即使a在某个句型中跟在A之后，仍然
不应该按照A?α归约。进行归约的条件更加严格可以降低冲突的可能性SLR语法分析器的弱点（2）[A?α.]出现在项集中的条件：首先[
A?. α]出现在某个项集中，然后逐步读入/归约到α中的符号，点不断后移，到达末端。而[A?. α]出现的条件是B?β.Aγ出现在
项中期望首先按照A?α归约，然后将B?β.Aγ中的点后移到A之后。显然，在按照A?α归约时要求下一个输入符号是γ的第一个符号。但是
从LR(0)项集中不能确定这个信息。更强大的LR语法分析器规范LR方法（或直接称LR方法）添加项[A?. α]时，把期望的向前看符
号也加入项中。这个做法可以充分利用向前看符号，但是状态很多。向前看LR（LALR方法）基于LR(0)项集族。但是每个LR(0)项都
带有向前看符号。分析能力强于SLR方法，且分析表和SLR分析表一样大。LALR已经可以处理大部分的程序设计语言。LR(1)项LR(
1)项中包含更多信息来消除一些归约动作。实际的做法相当于“分裂”一些LR(0)状态，精确地指明何时应该归约。LR(1)项的形式 [
A?α.β,a]a称为向前看符号，可以是终结符号或者$a表示如果将来要按照A?αβ进行归约，归约时的下一个输入符号必须是a。当β非
空时，移入动作不考虑a，a传递到下一状态。LR(1)项和可行前缀[A?α.β,a]对于一个可行前缀γ有效的条件是存在一个推导S
δAw δαβw，其中γ=δα，且a是w的第一个符号，或者w为空且a=$。如果[A?α.Bβ,a]对于可行前缀γ有
效，那么[B?.θ,b]对于γ有效的条件是什么？S δAw δαBβw δαBxw δαθxw显
然：b应该是xw的第一个符号，或xw为空且b=$。如果x为空，则b=a。如果[A?α.Xβ,a]对于可行前缀γ有效， [A?αX.
β,a]对γX有效。可行前缀和LR(1)有效项的例子文法：S?BB B?aB | b最右推导：S aaBab a
aaBab。对应于前面的定义：δ=aa，A=B w=ab，α=a β=Bγ=δα = aaa因此：[B?a.B,a]对于aaa是有
效的；构造LR(1)项集项集族的构造和LR(0)项集族的构造类似，但是CLOSURE和GOTO有所不同：在CLOSURE中，当由项
[A?α.Bβ,a]生成新项[B?.θ,b]时，b必须在FIRST(βa)中。注意：对应LR(1)项集族中的任意项[A?α.Bβ,
a]，总是保证a在FOLLOW(A)中初始项集满足这个条件每次求CLOSURE项集时，新产生的项也满足这个条件。LR(1)项集的C
LOSURE算法注意添加[B?.γ,b]时，b的取值范围。即点后面跟着终结符号的项LR(1)项集的GOTO算法和LR(0)项集的G
OTO算法基本相同即点后面跟文法符号X的项LR(1)项集族的主构造算法和LR(0)项集族的构造算法相同LR(1)项集族的例子增广文
法S’?S S?CC C?cC | dI0=CLOSURE{[S’?.S,$]} [S’?.S,$]，[S?.CC,$]，[
C?.cC,c/d]，[C?.d,c/d]GOTO(I0,S)={[S’?S.,$]}GOTO(I0,C)=CLOSURE{[S?
C.C,$]}= {[S?C.C,$],[C?.cC,$]，[C?.d,$]}GOTO(I0,c) ={[C?c.C,c/d]
, [C?.cC,c/d]，[C?.d,c/d]}GOTO(I0,d) ={[C?d.,c/d]}如果它是当前状态，下一个输入符号
必须是c或者d才可以归约…LR(1)项集的GOTO图不计向前看符号，I3，I6相同I8，I9相同I4，I7相同如果构造LR(0)项
集族，只有6个项集。LR语法分析表的构造步骤：构造得到LR(1)项集族C’={I0,I1,…,In}。状态i对应于项集Ii。其分析
动作如下：[A?α.aβ,b]在项集中，且GOTO(Ii,a)= Ij，那么ACTION[i,a]=“移入j”[A?α.,a]在项
集中， ACTION[i,a]=“按照A?α归约”[S’?S.,$]在项集中， ACTION[i,$]=“接受”。GOTO表：GO
TO[i,A]=j，如果GOTO(Ii,A)= Ij。没有填写的条目为报错。如果条目有冲突，则不是LR(1)的。初始状态对应于[S
’?S.,$]所在的项集。LR(1)语法分析表的例子(3,6)，(4,7)，(8,9)分别可以看作是由原来的一个LR(0)状态拆分
而来的。文法： S’?S S?CC C?cC | d构造LALR语法分析表LR(1)语法分析表的状态数量很大SLR(1)语法分析表
的分析能力较弱LALR(1)是实践中常用的方法状态数量和SLR(1)的状态数量相同能够方便地处理大部分常见的程序设计语言的构造LR
(1)语法分析表的合并状态4和7仅在向前看符号上有所不同。[C?d. c/d] vs [C?d., $]状态4：下一个符号
如果为c或d则归约；为$在报错。状态7：分析动作正好反过来。如果我们将4和7中的项合并得47，那么在所有情况都归约新的语法分析过程
会在原来报错时进行归约；但是最终总会报错。对与这个文法，合并4和7不会引起任何冲突，但是有些文法会有冲突。对任意文法，如果SLR(
1)分析表无冲突，合并后的分析表也无冲突。文法： S’?S S?CC C?cC | dLALR分析技术的基本思想寻找具有相同核心的
LR(1)项集，并把它们合并成为一个项集项集的核心就是项的第一分量的集合；I4和I7的核心都是{[C?d.]}，I3和I6的核心{
C?c.C C?.cC C?.d}一个LR(1)项集的核心是一个LR(0)项集；GOTO(I,X)的核心只由I的核心决定，因
此被合并项集的GOTO目标也可以合并。这表示合并之后，我们仍然可以建立GOTO关系。合并引起的冲突原来无冲突的LR(1)分析表在合
并之后得到LALR(1)分析表；新的表中可能存在冲突。合并不会导致移入/归约冲突假设合并之后在a上存在移入/归约冲突，即存在项[B
?β.aγ,?]和[A?α.,a]。因为被合并的项集具有相同的核心，因此被合并的所有项集中都包括[B?β.aγ,?]。而[A?α.
,a]必然在某个项集中。这个项集必然已经存在冲突！合并会引起归约/归约冲突，即不能确定按照哪个产生式进行归约。合并引起归约/归约冲
突的例子文法：S’?S S?aAd | bBd | aBe | bAe A?c B?c语言{acd，ace
，bcd，bce}可行前缀ac的有效项集{[A?c.,d],[B?c.,e]}可行前缀bc的有效项集{[A?c.,e],[B?c.
,d]}合并之后的项集为{[A?c.,d/e],[B?c.,d/e]}。这个项集包含了归约/归约冲突。应该把c归约成为A还是B？基
本的LALR分析表构造算法步骤：构造得到LR(1)项集族C={I0,I1,…,In}。对于LR(1)中的每个核心，找出所有具有这个
核心的项集，并把这些项集替换为它们的并集令C’={J0,J1,…,Jn}为得到的LR(1)项集族按照LR分析表的构造方法得到ACT
ION表。（如果存在冲突，则这个文法不是LALR的）GOTO表的构造：设J是一个或者多个LR(1)项集（包括I1）的并集，令K是所
有和GOTO(I1,X)具有相同核心的项集的并集，那么GOTO(J,X)=K。得到的分析表称为LALR语法分析表。LALR分析表的
例子（1）文法：S’?S S?CC C?cC | d文法的LR(1)项集族中有三对可以合并的项集：I3和I6 (I36)：[C
?c.C, c/d/$] [C?.cC,c/d/$] [C?.d,c/d/$]I4和I7 (I47)：C?d., c/d/$I8
和I9 (I89)：C?cC., c/d/$GOTO(I36,C)就是原来的GOTO(I3,C)（即I8）所在的并集I89。…LA
LR分析表的例子（2）合并后得到的LALR分析表LALR分析表的例子（3）处理语法正确的输入时，LALR语法分析器和LR语法分析器
的动作序列完全相同。栈中的状态名字不同，但是状态序列之间有对应关系：如果LR分析器压入状态I，那么LALR分析器压入I对应的合并项
集。比如：当前面的LR分析器压入状态I3时，LALR分析器压入状态I36。当处理错误的输入时，LALR可能多执行一些归约动作，但是
不会多移入一个符号。LALR分析表的高效构造算法LALR的项集可以看作是在LR(0)项集上添加了适当的向前看符号。基本方法只使用内
核项来表示LR(0)或LR(1)项集。只使用[S’?.S]或[S’?.S,$]，以及点不在最左端的项。使用传播和自发生成的过程来生
成向前看符号，得到LALR(1)内核项。使用CLOSURE函数，求出内核的闭包。然后得到LALR分析表。LALR项中的向前看符号L
ALR项集中的项[A?α.β,a]必然是具有相同核心的LR项集中的一个项。LALR项集J中包含项[B?γ.δ,b]的条件：存在相应
的LR项集J’使得下列条件之一成立LR项集I’中包含项[A?α.β,a]且J’=GOTO(I’,X)，且[B?γ.δ,b]在GOT
O(CLOSURE({[A?α.β,a]}),X)中。b是“自发生成的”，不管a是什么，[B?γ.δ,b]一定在J中。LR项集I’
中包含项[A?α.β,b]且J’=GOTO(I’,X)，且[B?γ.δ,b]在GOTO(CLOSURE({[A?α.β,b]}),
X)中。b是从前一个状态传播过来的，即[A?α.β,b]在I’中则[B?γ.δ,b]在J中；若[A?α.β,c]在I’中则[B?γ
.δ,b]在J中。存在LR项集I’包含某个项，也就是存在LALR项集I包含该项传播关系只取决于项的核心部分，和具体的向前看符号无关
要么传播所有的向前看符号，要么都不传播。确定自发生成/传播关系基本思想：引入一个特殊向前看符号#作为“指示剂”，察看这个符号可以如
何传播。令[A?α.β]为项集I中的一个项，对每个文法符号X计算J=GOTO(CLOSURE({[A?α.β,#]}),X)。检查
J中的每个内核项，检查它的向前看符号集合。如果项[B?γ.δ,#]在J中就表示#从I中的A?α.β传播到了[B?γ.δ,#]。其它
的向前看符号都是自发生成的。确定向前看符号的算法输入：LR(0)项集I的内核K以及一个文法符号输出：向前看符号的传播/自发生成。L
ALR项集族中向前看符号的计算基本思想：以LR(0)项集为基础；自发生成的符号首先被加入到相应的LALR项集中；然后不停地传播向前
看符号，直到收敛。具体算法构造G的LR(0)项集族的内核将确定自发生成/传播关系的算法应用于每个LR(0)项集的内核和每个文法符号
X，确定自发生成和传播的向前看符号。初始化：给出每个项集和每个内核项的自发生成的向前看符号；迭代：不断扫描所有项集的内核项，将项I
的向前看符号加入到传播目标项的向前看符号集合中。直到各个向前看符号集合不变为止。构造LALR项集的例子（1）文法：S’?S S?
L=R S?RL?R L?id R?LLR(0)项集内核： 构造LALR项集的例子（2）对于I0的内核，CLOSURE(
{[S’?S,#]}):S’?.S,# S?.L=R,# S?.R,#L?.R,#/= L?id,#/= R?L,#对各文法
符号计算GOTO，可知I0中的S’?.S将向前看符号传播到I1: S’?S. I2: S?L.=R I3: S?R.I4: L?
.R I5: L?id. I2: R?L.构造LALR项集的例子（3）得到的传播关系：构造LALR项集的例子（4）计算向前看符
号传播的迭代过程：二义性文法的使用二义性文法都不是LR的。某些二义性文法是有用的可以简洁地描述某些结构；隔离某些语法结构，对其进行
特殊处理。对于某些二义性文法可以通过消除二义性规则来保证每个句子只有一棵语法分析树。且可以在LR分析器中实现这个规则。优先级/结合
性消除冲突二义性文法：E?E+E | EE | (E) | id等价于：E?E+T | T T?TF | F F?(E
)|id二义性文法的优点：容易修改算符的优先级和结合性。简洁：如果有多个优先级，那么无二义性文法讲引入太多的非终结符号高效：不需要
处理E?T这样的归约。二义性表达式文法的LR(0)项集E?E+E | EE | (E) | idI7、I8中有冲突，且不可能通过向前看符号解决！冲突的原因以及解决当栈顶状态为7时，表明栈中状态序列对应的文法符号序列为…E+E；下一个输入符号不等于+、，则归约归约之后早晚会报错；如果下一个符号为+或，移入还是归约？…E+E （…E+E+）时，是否先求和？如果的优先级大于+，且+是左结合的下一个符号为+时，我们应该将E+E归约为E下一个符号为时，我们应该移入，期待引入下一个符号。解决冲突之后的SLR(1)分析表对于状态7，+时归约时移入对于状态8执行归约这个表和等价的无二义性文法的分析表类似悬空else的二义性文法： S’?S S?iSeS | iS | aLR(0)项集中I4包含冲突，它出现在栈顶时，栈中符号为iS如果下一个符号为e，因栈中的i尚未匹配，因此应该移入e。否则，如果下一个符号属于FOLLOW(S)，就归约。LR语法分析中的错误恢复（1）LR语法分析器查询GOTO表时不会有语法错误。查询ACTION表时可能发现报错条目假设栈中的符号串为α，当前输入符号为a；报错表示不可能存在终结符号串x使得αax是一个最右句型。恐慌模式的错误恢复策略从栈顶向下扫描，找到状态s，s有一个对应于非终结符号A的GOTO目标；（s之上的状态被丢弃）在输入中读入并丢弃一些符号，直到找到一个可以合法跟在A之后的符号a（不丢弃a）；将GOTO(s,A)压栈；继续进行正常的语法分析。基本思想：假定当前正在试图归约到A且碰到了语法错误。因此设法扫描完包含语法错误的A的子串，假装找到了A的一个实例。LR语法分析中的错误恢复（2）短语层次的恢复检查LR分析表中的每个报错条目，根据语言的特性来确定程序员最可能犯了什么错误，然后构造适当的恢复程序。语法分析器生成工具YACCYACC的使用方法如下：YACC源程序的结构声明分为两节：第一节放置C声明，第二节是对词法单元的声明。翻译规则：指明产生式及相关的语义动作辅助性C语言例程被直接拷贝到生成的C语言源程序中，可以在语义动作中调用。其中必须包括yylex()。这个函数返回词法单元，可以由LEX生成声明%%翻译规则%%辅助性C语言程序翻译规则的格式<产生式头> : <产生式体>1 {<语义动作>1} | <产生式体>2 {<语义动作>2} … … … … | <产生式体>n {<语义动作>n} ;第一个产生式的头被看作开始符号；语义动作是C语句序列；$$表示和产生式头相关的属性值，$i表示产生式体中第i个文法符号（注意，保护终结符号）的属性值。在按照某个产生式归约时，执行相应的语义动作。通常根据$i来计算$$的值。在YACC源程序中，可以通过定义YYSTYPE来定义$$，$i的类型。YACC源程序的例子YACC中的冲突处理缺省的处理方法对于归约/归约冲突，选择列在前面的产生式对于归约/移入冲突，总是移入（悬空-else的解决）运行选项-v可以在文件y.output中描述冲突及其解决方法；可以通过一些命令来确定终结符号的优先级/结合性，解决移入/归约冲突。结合性：%left %right %nonassoc产生式的优先级它的最右终结符号的优先级。或者加标记%prec<终结符号>，指明产生式的优先级移入符号a/按照A?α归约：比较a和A?α的优先级，根据结合性，选择不同的操作。YACC的错误恢复使用错误产生式的方式来完成语法错误恢复错误产生式A?error α例如：stmt ? error ;首先定义哪些“主要”非终结符号有错误恢复动作；比如：表达式，语句，块，函数定义等非终结符号当语法分析器碰到错误时不断弹出栈中状态，直到栈顶状态包含A?.error α;分析器将error移入栈中。如果α为空，分析器直接执行归约，并调用相关的语义动作；否则向前跳过一些符号，找到可以归约为α的串为止。 |
|
