第四章 语法分析 赵建华 南京大学计算机系 2010.3.

Presentation on theme: "第四章 语法分析 赵建华 南京大学计算机系 2010.3."— Presentation transcript:

1 第四章 语法分析 赵建华 南京大学计算机系 2010.3

2 程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无关文法或BNF表示法来描述 文法可给出精确易懂的语法规则
可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构，有助于进一步的语义处理/代码生成。 支持语言的演化和迭代。

3 语法分析器的作用 基本作用 从词法分析器获得词法单元的序列，确认该序列是否可以由语言的文法生成。 对于语法错误的程序，报告错误信息
对于语法正确的程序，生成语法分析树。 通常并不真的生产这棵语法分析树

4 语法分析器的分类 通用语法分析器 自顶向下语法分析器 自底向上语法分析器 后两种方法 可以对任意文法进行语法分析 效率很低，不适合用于编译器
从语法分析树的根部开始构造语法分析树 自底向上语法分析器 从语法分析树的叶子开始构造语法分析树 后两种方法 总是从左到右、逐个扫描词法单元。 只能处理特定类型的文法，但是这些文法足以用来描述程序设计语言。

5 上下文无关文法 定义：一个上下文无关文法包含四个部分 终结符号：组成串的基本符号（词法单元名字） 非终结符号：表示串的集合的语法变量。
给出了语言的层次结构。 在程序设计语言中通常对应于某个程序构造，比如stmt（语句） 开始符号：某个被指定的非终结符号。 它对应的串的集合就是文法的语言 产生式集合：描述将终结符号和非终结符号组成串的方法 产生式的形式：头/左部  体/右部 头部是一个非终结符号，右部是一个符号串； 例子：expression  expression + term

6 上下文无关文法的例子 简单算术表达式的文法： 终结符号：id + - * / ( )
非终结符号：expression, term, factor 开始符号：expression 产生式集合： expression  expression + term expression  expression – term expression  term term  term * factor term  term / factor term  factor factor  (expression) factor  id

7 文法书写的约定 终结符号 非终结符号 X,Y,Z文法符号（终结符号或非终结符号） 小写希腊字母表示文法符号串(α, β, γ)
靠前的小写字母(a,b,c)；运算符号(+ *)；标点符号；数位；黑体字符串(id, if, while) 非终结符号 靠前的大小字母(A,B,C)；字母S（通常是开始符号）；小写斜体字母；表示程序构造的大写字母 X,Y,Z文法符号（终结符号或非终结符号） 小写希腊字母表示文法符号串(α, β, γ) 靠后的小写字母表示终结符号串 具有相同头的产生式可以合并成A α1 | α2| … | αn的形式 通常第一个产生式的左部就是开始符号。

8 文法简单形式的例子 E  E + T | E – T | T T  T * F | T / F | F F  ( E ) | id
注意: | 是元符号（即文法描述方式中的符号，而不是文法符号） 这里(,)不是元符号；在有些地方会把( )看作元符号

9 推导（1） 推导： 例子 将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体。
从开始符号出发，不断进行上面的替换，就可以得到文法的不同句型 例子 文法: E  -E | E+E | E*E | (E) | id 推导序列：E => -E => -(E) => -(id)

10 推导（2） 推导的正式定义 经过零步或者多步推导出： 经过一步或者多步推导出： 如果Aγ是一个产生式，那么αAβ => αγβ
最左(右)推导：α(β)中不包含非终结符号 符号： 经过零步或者多步推导出： 对于任何串α α 如果α β且β=>γ，那么α γ 经过一步或者多步推导出： α β等价于α β且α不等于β

11 句型/句子/语言 句型（sentential form）： 句子（sentence） 语言 如果S=*=> α，那么α就是文法的句型
可能既包含非终结符号，又包含终结符号；可以是空串 句子（sentence） 文法的句子就是不包含非终结符号的句型 语言 文法G的语言就是G的句子的集合，记为L(G) w在L(G)中当且仅当w是G的句子，即S=*=>w

12 语法分析树 推导的图形表示形式 有时允许树的根不是开始符号（对应于某个短语）。 树的叶子组成的序列是根的文法符号的句型
根结点的标号时文法的开始符号 每个叶子结点的标号是非终结符号、终结符号或ε 每个内部节点的标号是非终结符号。 每个内部结点表示某个产生式的一次应用 内部结点的标号为产生式头，结点的子结点从左到右是产生式的体 有时允许树的根不是开始符号（对应于某个短语）。 树的叶子组成的序列是根的文法符号的句型 一棵分析树可对应多个推导序列，但是分析树和最左（右）推导序列之间具有一一对应关系

13 语法分析树的例子 文法： E  -E | E+E | E*E | (E) | id 句子：-(id+id)

14 从推导序列构造分析树 假设有推导序列： 算法： A=a1=>a2 => … => an
假设已经构造出ai-1=X1X2…Xk的分析树，且ai-1到a1的推导是将Xj替换为β，那么在当前分析树中找出第j个非ε结点，向这个结点增加构成β的子结点。如果β=ε，则增加一个标号为ε的子结点）

15 构造分析树的例子 推导序列： E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)

16 二义性（1） 二义性（ambiguous）：一个文法可以为某个句子生成多棵语法分析树，这个文法就是二义性的 例子：
E => E+E => id+E=>id+E*E => id+id*E=>id+id*id E => E*E => E+E*E=>id+E*E => id+id*E=> id+id*id

17 二义性（2） 程序设计语言的文法通常都应该是无二义性的 但有些二义性的情况可以方便文法或语法分析器的设计。
否则就会导致一个程序有多种“正确”的解释。 比如文法： E  -E | E+E | E*E | (E) | id 的句子a+b*c 但有些二义性的情况可以方便文法或语法分析器的设计。 但是需要消二义性规则来剔除不要的语法分析树 比如：先乘除后加减

18 证明文法生成的语言 证明文法G生成语言L可以帮助我们了解文法可以生成什么样的语言。 基本步骤： 证明L(G)L的方法之一：
一般使用数学归纳法 证明L(G)L的方法之一： 构造L’，使得L’Vt*=L；并证明S∈L’，且对于L’中的任意α，α=>β可推出β也在L中。 也可以按照推导序列长度进行数学归纳 证明LL(G)时，通常可按照符号串的长度来构造推导序列。

19 文法生成语言的例子（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。

20 文法生成语言的例子（2） LL(G)的证明： 归纳基础：如果括号对称的串的长度为0，显然它可以从S推导得到
注意：括号对称的串的长度必然是偶数。 归纳基础：如果括号对称的串的长度为0，显然它可以从S推导得到 归纳步骤：假设长度小于2n的括号对称的串都能够由S推导得到。假设w是括号对称且长度为2n的串 w必然以左括号开头，且w可以写成(x)y的形式，其中x也是括号对称的。因为x、y的长度都小于2n，根据归纳假设，x和y都可以从S推导得到。 因此S=>(S)S=*=>(x)y。

21 上下文无关文法和正则表达式（1） 上下文无关文法比正则表达式的能力更强。即： 证明： 所有的正则语言都可以使用文法描述
但是一些用文法描述的语言不能用正则文法描述。 证明： 首先SaSb | ab 描述了语言{anbn|n>0}，但是这个语言无法用DFA识别。 假设有DFA识别此语言，且这个文法有K个状态。那么在识别ak+1…的输入串时，必然两次到达同一个状态。设自动机在第i个和第j个a时进入同一个状态，那么：因为DFA识别L，ajbj必然到达接受状态，因此aibj必然也到达接受状态。 直观地讲：有穷自动机不能数（大）数。

22 上下文无关文法和正则表达式（2） 证明（续） 其次证明：任何正则语言都可以表示为上下文无关文法的语言。
任何正则语言都必然有一个NFA。对于任意的NFA构造如下的上下文无关文法 对NFA的每个状态i，创建非终结符号Ai。 如果有i在输入a上到达j的转换，增加产生式AiaAj。 如果i在输入ε上到达j，那么增加产生式AiAj. 如果i是一个接受状态，增加产生式Aiε 如果i是开始状态，令Ai为所得文法的开始符号。

23 NFA构造文法的例子 A0aA0 | bA0 | aA1 A1bA2 A2bA3 A3 ε
考虑baabb的推导和接受过程可知：NFA接受一个句子的运行过程实际是文法推导出该句子的过程。

24 设计文法 文法能够描述程序设计语言的大部分语法 但不是全部，比如：标识符的先声明后使用无法用上下文无关文法描述。
因此：语法分析器接受的语言是程序设计语言的超集。必须通过语义分析来剔除一些符合文法、但不合法的程序。

25 二义性的消除(1) 一些二义性文法可以被改成等价的无二义性的文法 例子：
stmt  if expr then stmt | if expr then stmt else stmt |other if E1 then if E2 then S1 else S2的两棵语法树

26 二义性的消除(2) 为了保证“else和最近未匹配的then匹配”，我们要求在then分支的语句必须是匹配好的。
引入matched_stmt表示匹配好的语句，有如下文法： stmt  matched_stmt | open_stmt matched_stmt  if expr then matched_stmt else matched_stmt | other open_stmt  if expr then stmt | if expr then matched_stmt else open_stmt 二义性的消除方法没有规律可循。 通常并不是通过改变文法来消除二义性。

27 左递归的消除 左递归的定义： 立即左递归（规则左递归）
如果一个文法中有非终结符号A使得A=*=>Aα，那么这个文法就是左递归的。 立即左递归（规则左递归） 文法中存在一个形如AAα的产生式。 自顶向下的语法分析技术不能处理左递归的情况，因此需要消除左递归；但是自底向上的技术可以处理左递归。

28 立即左递归的消除 假设非终结符号A存在立即左递归的情形，假设以A为左部的规则有： 可以替换为
A Aα1 | Aα2 |…| Aαm | β1 | β2 |… | βn 可以替换为 Aβ1A’ | β2A’|… | βn A’ A’α1A’ | α2A’ |…| αmA’ | ε 由A生成的串总是以某个βi开头，然后跟上零个或者多个αi的重复。

29 通用的左递归消除方法 输入：没有环和ε产生式的文法G 输出：等价的无左递归的文法 步骤： 将文法的非终结符号任意排序为A1,A2,…,An
for 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后。（不能有环和ε产生式） 当外层循环结束时，所有的产生式都是如此。使用这些产生式当然不会产生左递归的情形。

30 通用左递归消除的例子 本例子中的ε产生式恰好没有影响算法的正确性 S  Aa | b AAc | Sd | ε 步骤1：排列为S，A
i=1时：内层循环不运行，S没有立即左递归； i=2时：j=1，处理规则ASd；替换得到 AAc | Aad | bd | ε 消除A的立即左递归 SAa | b AbdA’ | A’ A’cA’ | adA’ | ε 通用左递归消除的问题在于很难找到新文法和旧文法的推导之间的对应关系，因此很难依据新文法进行语义处理。 本例子中的ε产生式恰好没有影响算法的正确性

31 预测分析法简介 试图从开始符号推导出输入符号串； 以开始符号作为初始的当前句型 每次为最左边的非终结符号选择适当的产生式；
通过查看下一个输入符号来选择这个产生式。 有多个可能的产生式时预测分析法无能为力 比如文法：E +EE | -EE | id；输入为+ id - id id 当两个产生式具有相同的前缀时无法预测 文法：stmt  if expr then stmt else stmt | if expr then stmt 输入：if a then … 新文法：stmt  if expr then stmt elsePart elsePart  else stmt | ε 需要提取公因子

32 提取公因子的文法变换 算法： 输入：文法G 输出：等价的提取了左公因子的文法
方法：对于每个非终结符号A，找出它的两个或者多个可选产生式体之间的最长公共前缀。 A αβ1 | αβ 2 | … | αβ n | γ AαA’ | γ A’β1 | β 2 | … | β n 其中γ是不以α开头的产生式体

33 提取公因子的例子 文法： 对于S而言，最长的前缀是i E t S，因此： S  i E t S | i E t S e S | a
E  b 对于S而言，最长的前缀是i E t S，因此： S  i E t S S’| a S’e S | ε

34 非上下文无关语言的构造 抽象语言 L1={wcw | w在(a|b)*中} 这个语言不是上下文无关的语言
它抽象地表示了C或者Java中“标识符先声明后使用”的规则。 说明了这些语言不是上下文无关语言，不能使用上下文无关文法描述。 通常用上下文无关文法描述其基本结构，不能用文法描述的特性在语义分析阶段完成。原因是上下文文法具有高效的处理算法。

35 自顶向下的语法分析 为输入串构造语法分析树 基本步骤 关键问题是：确定对最左边的非终结符号应用哪个产生式
从分析树的根结点开始，按照先根次序，深度优先地创建各个结点 对应于最左推导。 基本步骤 确定对句型中最左边的非终结符号应用哪个产生式 然后对句型中的非终结符号和输入符号进行匹配 关键问题是：确定对最左边的非终结符号应用哪个产生式

36 自顶向下分析的例子 文法： 输入id + id * id 分析树序列见右面（图4-12） ETE’ E’+TE’ | ε TFT’
F(E) | id 输入id + id * id 分析树序列见右面（图4-12）

37 递归下降的语法分析 递归下降语法分析程序由一组过程组成 每个非终结符号对应于一个过程，该过程负责扫描非终结符号对应的结构
程序执行从开始符号对应的过程开始 当扫描整个输入串时宣布分析成功完成

38 递归下降分析技术的回溯 回溯需要来回扫描，低效 如果没有足够的信息来唯一地确定可能的产生式，那么分析过程就产生回溯。
前面的算法报告错误（第7行）并不意味着输入串不是句子，而可能是表示前面选错了产生式。 第一行上保存当前的扫描指针 在第七行上应该改成 回退到保存的指针；GOTO (1)并选择下一个产生式； 如果没有下一个产生式可选，报告错误。 回溯需要来回扫描，低效 如果嵌入了语义处理，则需要撤销已经完成的语义处理动作。 解决方法：设法通过一些信息确定唯一可能的产生式

39 递归下降分析中回溯的例子 文法：ScAd Aab | a 输入串：cad 步骤： 因此扫描结束，cad是句子。 调用函数S；
S选择唯一产生式ScAd 输入中的c和句型中的c匹配，继续调用A A首先选择产生式Aab，a和输入的a匹配，b和输入的d不匹配； 回溯并选择下一个产生式Aa；a和输入的a相匹配；对A的调用返回；到S的调用； ScAd中的d和下一个输入匹配； 对S的调用返回，已经读入所有输入符号； 因此扫描结束，cad是句子。

40 FIRST和FOLLOW（1） 在自顶向下的分析技术中，通常使用向前看几个符号来唯一地确定产生式（这里假定只看一个符号）
当前句型是xAβ，而输入是xa…。那么选择产生式Aα的必要条件是下列之一： α=*=>ε，且β以a开头；也就是说在某个句型中a跟在A之后； α=*=>a…； 如果按照这两个条件选择时能够保证唯一性，那么我们就可以避免回溯。 因此，我们定义FIRST和FOLLOW

41 FIRST和FOLLOW（2） FIRST(α)： FOLLOW(A)： 可以从α推导得到的串的首符号的集合；

42 FIRST的计算方法 计算FIRST(X)的方法 计算FIRST(X1X2…Xn)的方法 如果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)中，那么ε在FIRST(X)中。 如果X是非终结符号，且Xε是一个产生式，那么ε在FIRST(X)中 计算FIRST(X1X2…Xn)的方法 向集合中加入FIRST(X1)中所有非ε的符号； 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε的符号； … 如果ε在所有的FIRST(X1)中，将ε加入FIRST(X1X2…Xn)中。

43 FOLLOW的计算方法 算法 请注意各个步骤中将符号加入到FOLLOW集合中的理由。 将右端结束标记$放到FOLLOW(S)中
如果存在产生式AαBβ，那么FIRST(β)中所有非ε的符号都在FOLLOW(B)中。 如果存在一个产生式AαB，或者AαBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都加入到FOLLOW(B)中。 请注意各个步骤中将符号加入到FOLLOW集合中的理由。

44 FIRST/FOLLOW的例子（1） 文法： FIRST集合 由此可以推出各个产生式右部的FIRST集合。
ETE’ E’+TE’ | ε T  FT’ T’*FT’ | ε F(E) | id FIRST集合 FIRST(F) = {(, id}； FIRST(E) =FIRST(T) = {(,id} FIRST(E’) = {+, ε}; FIRST(T’)={*, ε} 由此可以推出各个产生式右部的FIRST集合。

45 FIRST/FOLLOW的例子（2） FOLLOW集合的计算过程 $在FOLLOW(E) 中（E是开始符号）
由规则F(E)可知，)也在FOLLOW(E)中 由规则ETE’ 可知FOLLOW(E’)也包含了$和)。 注意：因为E’只出现在E和E’的产生式的尾部，因此FOLLOW(E’)必然等于FOLLOW(E)。 由规则E’+TE’，FIRST(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：{+,*,),$}

46 LL(1)文法（1） 定义:对于文法的任意两个不同的产生式Aα|β 等价于：
不存在终结符号a使得α和β都可以推导出以a开头的串 α和β最多只有一个可以推导出空串 如果β可以推导出空串，那么α不能推导出以FOLLOW中任何终结符号开头的串； 等价于： FIRST(α)FIRST(β)=Φ;（条件一、二） 如果ε∈FIRST(β)，那么FIRST(α) FOLLOW(A)=Φ；反之亦然。（条件三） 考虑：对于一个LL(1)文法，我们期望从A推导出以终结符号a开头的符号串， 我们如何选择产生式？ 有多个选择吗？

47 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 else stmt 得到句型if (exp) stmt else stmt 然后发现要把句型中的第一个stmt展开，选择产生式stmt while (exp) stmt，得到句型if (exp) while (exp) stmt else stmt 。 然后再展开第一个stmt，得到if (exp) while (exp) a else stmt …

48 预测分析表构造算法 输入：文法G 输出：预测分析表M 方法： 对于文法G的每个产生式Aα 最后在所有的空白条目中填入error。
对于FIRST(α)中的每个终结符号a，将Aα加入到M[A,a]中； 如果ε在FIRST(α)，那么对于FOLLOW(A)中的每个符号b，将将Aα加入到M[A,b]中。 最后在所有的空白条目中填入error。

49 预测分析表的例子 文法： FIRST集： FOLLOW集： ETE’ E’+TE’ | ε T  FT’ T’*FT’ | ε
F(E) | id FIRST集： F：{(, id}； E,T：{(,id}； E’： {+, ε}; T’：{*, ε} FOLLOW集： E：{$,)} E’：{$,)} T,T’：{+, ), $} F：{+,*,),$} 这个例子恰巧使得每个产生式的右部的第一个符号的FIRST集合就等于产生式右部的FIRST集合。但是在一般情况下不总是这样的。

50 预测分析表冲突的例子 文法：SiEtSS’ | a S’eS | ε Eb 注意：LL(1)文法必然不是二义性的；而这个文法是二义性的
FIRST(eS)={e}，使得S’eS在M[S’,e]中； FOLLOW(S’)={$,e}使得S’ ε也在M[S’,e]中 注意：LL(1)文法必然不是二义性的；而这个文法是二义性的

51 LL(1)文法的递归下降分析 递归下降语法分析程序由一组过程组成 每个非终结符号对应于一个过程，该过程负责扫描非终结符号对应的结构
可以使用当前的输入符号来唯一地选择产生式 如果当前输入符号为a，那么选择M[A,a]中的产生式

52 非递归的预测分析（1） 在自顶向下分析的过程中，我们总是 匹配掉句型中左边的所有终结符号；
对于最左边的非终结符号，我们选择适当的产生式展开。 匹配成功的终结符号不会再被考虑，因此我们只需要记住句型的余下部分，以及尚未匹配的输入终结符号串。 由于展开的动作总是发生在余下部分的左端，我们可以用栈来存放这些符号。

53 非递归的预测分析（2） 分析时的处理过程： 因此对所有文法的预测分析都可以共用同样的驱动程序。 初始化时，栈中仅包含开始符号；
如果栈顶元素是终结符号，那么进行匹配 如果栈顶元素是非终结符号 使用预测分析表来选择适当的产生式； 在栈顶用产生式右部替换产生式左部； 因此对所有文法的预测分析都可以共用同样的驱动程序。

54 分析表驱动的预测分析器 性质1：如果栈中的符号序列为α，而w是已经被读入的部分输入，w’是尚未处理的输入；那么
S推导出wα 我们试图从α推导出余下的输入终结符号串w’ 预测分析程序使用M[X,a]来扩展X，将此产生式的右部按倒序压入栈中 请注意：这样的操作使得分析过程中性质1得到保持。

55 预测分析算法 输入：串w，预测分析表M 输出：如果w是句子，输出w的最左推导；否则报错 方法：
初始化：输入缓冲区中为w $；栈中包含S$；ip指向w的第一个符号； 令X=栈顶符号，ip指向符号a if(X==a) 出栈，ip向前移动；/*和终结符号的匹配*/ else if (X是终结符号) error()；/*失配*/ else if (M[X,a]是报错条目) error();/*无适当的产生式*/ else if (M[X,a]=XY1Y2…Yk) { 输出产生式XY1Y2…Yk；弹出栈顶符号X； 将Yk,Yk-1,…,Y1压入栈中； } 不断执行第二步；直到要么报错，要么栈中为空

56 分析表驱动预测分析的例子 注意：已经匹配部分加上栈中符号必然是一个最左句型 文法4.28，输入：id+id*id;

57 预测分析中的错误恢复 错误恢复 两类错误恢复方法： 当预测分析器报错时，表示输入的串不是句子。
对于使用者而言，希望预测分析器能够进行恢复，并继续语法分析过程，以便在一次分析中找到更多的语法错误。 有可能恢复得并不成功，之后找到的语法错误有可能是假的。 进行错误恢复时可用的信息：栈里面的符号，待分析的符号 两类错误恢复方法： 恐慌模式 短语层次的恢复

58 恐慌模式 基本思想 语法分析器忽略输入中的一些符号，直到出现由设计者选定的某个同步词法单元； 解释：
语法分析过程总是试图在输入的前缀中找到和某个非终结符号对应的串；出现错误表明现在已经不可能找到这个非终结符号（程序结构）的串。 如果编程错误仅仅局限于这个程序结构，那么我们可以考虑跳过这个程序结构，假装已经找到了这个结构；然后继续进行语法分析处理。 同步词法单元就是这个程序结构结束的标志。

59 同步词法单元的确定 非终结符号A的同步集合的启发式规则 哪些符号需要确定同步集合需要根据特定的应用而定。
FOLLOW(A)的所有非终结符号A的同步集合中 这些符号的出现可能表示之前的那些符号是错误的A的串； 将高层次的非终结符号对应串的开始符号加入到较低层次的非终结符号的同步集合 比如语句的开始符号，if，while等可以作为表达式的同步集合； FIRST(A)中的符号加入到非终结符号A的同步集合。 碰到这些符号时，可能意味着前面的符号是多余的符号 如果A可以推导出空串，那么把此产生式当作默认值。 在匹配时出现错误，可以直接弹出相应的符号； 哪些符号需要确定同步集合需要根据特定的应用而定。

60 恐慌模式的例子（1） 对文法4.28的表达式进行语法分析时，可以直接使用FIRST、FOLLOW作为同步集合。
我们为E、T和F设定同步集合； 空条目表示忽略输入符号；synch条目表示忽略到同步集合，然后弹出非终结符号； 终结符号不匹配时，弹出栈中终结符号；

61 恐慌模式的例子（2） 错误输入： id * + id

62 短语层次的恢复 在预测语法分析表的空白条目中插入错误处理例程的函数指针； 例程可以改变、插入或删除输入中的符号；发出适当的错误消息；

63 自底向上的语法分析 为一个输入串构造语法分析树的过程； 从叶子（输入串中的终结符号，将位于分析树的底端）开始，向上到达根结点；
在实际的语法分析过程中并不会真的构造出相应的分析树，但是分析树概念可以方便理解； 重要的自底向上语法分析的通用框架 移入-归约； LR：最大的可以构造出移入-归约语法分析器的语法类

64 分析过程示例

65 归约 自底向上语法分析过程看成从串w“归约”为文法开始符号的过程； 归约步骤： 问题：
一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号； 问题： 何时归约（归约哪些符号串）？ 归约到哪个非终结符号？

66 归约的例子 id * id的归约过程 对于句型T*id，有两个子串和某产生式右部匹配 id * id ，F*id，F*id，T*F，T，E
T是ET的右部； id是Fid的右部； 为什么选择将id归约为F，而不是将T归约为E？ 原因：T归约为E之后，E*id不再是句型； 问题：如何确定这一点？

67 句柄剪枝 对输入从左到右扫描，并进行自底向上语法分析，实际上可以反向构造出一个最右推导； 句柄： 在一个最右句型中，句柄右边只有终结符号
最右句型中和某个产生式体匹配的子串，对它的归约代表了该最右句型的最右推导的最后一步； 正式定义：如果S αAw αβw；那么紧跟α之后的Aβ的一个句柄； 在一个最右句型中，句柄右边只有终结符号 如果文法是无二义性的，那么每个句型都有且只有一个句柄。

68 句柄的例子 输入：id *id

69 移入-归约分析技术 使用一个栈来保存归约/扫描移入的文法符号； 栈中符号（从底向上）和待扫描的符号组成了一个最右句型；
开始时刻：栈中只包含$，而输入为w$； 成功结束时刻：栈中$S，而输入$； 在分析过程中，不断地移入符号，并在识别到句型时进行归约； 句柄被识别时总是出现在栈的顶部；

70 主要分析动作 移入：将下一个输入符号移动到栈顶； 归约：将句柄归约为相应的非终结符号; 接受：宣布分析过程成功完成；
句柄总是在栈顶。 具体操作时弹出句柄，压入被归约到的非终结符号。 接受：宣布分析过程成功完成； 报错：发现语法错误，调用错误恢复子程序；

71 归约分析过程的例子

72 为什么句柄总是在栈顶？（1） 为什么每次归约得到的新句型的句柄仍不在栈顶？ 考虑最右推导的两个连续步骤的两种情况
A被替换为βBy，然后产生式体中的最右非终结符号B被替换为γ。（归约之后句柄为βBy） A首先被展开，产生式体中只包含终结符号；下一个最右非终结符号B位于y左侧。 y是终结符号串

73 移入-归约分析中的冲突 对于有些不能使用移入-归约分析的文法，不管用什么样的移入-归约分析器都会到达这样的格局
即使知道了栈中所有内容、以及下面k个输入符号，人们仍然无法知道是否该进行归约，或者不知道按照什么产生式进行归约； 形式化地表达：设栈中符号串是αβ，接下来的k个符号是x，产生移动/归约冲突的原因是存在y和y’使得aβxy是最右句型且β是句柄，而aβxy’也是最右句型，但是句柄还在右边。

74 归约/归约冲突的例子 输入为id ( id , id ) 冲突时的格局： 栈：…id ( id 输入：, id ) …
某个语言中，多维数组的表示方法。

75 LR语法分析技术 LR(k)的语法分析概念 当k的数量增大时，相应的语法分析器的规模急剧增大； L表示最左扫描，R表示反向构造出最右推导；

76 LR语法分析器的优点 由表格驱动；虽然手工构造表格工作量大，但表格可以自动生成；
最通用的无回溯移入-归约分析技术，且和其它技术一样高效； 可以尽早检测到错误。 能分析的文法集合是LL(k)文法的超集

77 LR(0)项 文法的一个产生式加上在其产生式体中某处的一个点。 直观含义： A.XYZ，AX.YZ，AXY.Z，AXYZ.
注意：Aε只对应一个项A. 直观含义： 项A α.β表示已经扫描/归约到了α，并期望接下来的输入中经过扫描/归约得到β。然后把αβ归约到A。 如果β为空，表示我们可以把α归约为A。 项也可以用一对整数表示。(i,j)表示第i条规则，点位于右部第j个位置

78 项和最右推导的关系 构造以项为状态的NFA 这个NFA接受的语言是最右句型的包含其句柄，但是不包含句柄右边符号的前缀 开始状态S’.S；
转换： Aα.Bβ到B. γ有一个ε转换， 从Aα.Xβ到AαX.β有一个X转换。 接受状态：Aα.，即点在最后的项 这个NFA接受的语言是最右句型的包含其句柄，但是不包含句柄右边符号的前缀

79 NFA运行和句柄的关系 文法 最右句型E+T*F+id+id 句柄为T*F 分析树见右图 沿着分析树的左边缘遍历可以和NFA的运行类比
E’E EE+T | T TT*F | F Fid 最右句型E+T*F+id+id 句柄为T*F 分析树见右图 句柄的确定只和每一层最左边的推导有关系；和右边的推导无关 沿着分析树的左边缘遍历可以和NFA的运行类比 上层到下一层的推导即NFA中的ε边； 同一层中从左向右即NFA的非ε边 如果能够走到某个分支的最右边，就找到了句柄 E’ E E T E T id id E T T * F

80 规范LR(0)项集族的构造 增广文法： 规范LR(0)项集族即LR(0)自动机的状态集合；
G的增广文法G’是在G中增加新开始符号S’，并加入产生式S’S而得到的。 显然G’和G接受相同的语言，且按照S’S进行归约实际上就表示已经将输入符号串归约成为开始符号。 规范LR(0)项集族即LR(0)自动机的状态集合； LR(0)自动机实际上是前面的NFA对应的DFA。 构造过程中用到的子函数 CLOSURE(I)：I的项集闭包 对应于DFA化算法的 ε-CLOSURE GOTO(I,X)：I的X后继 对应于DFA化算法的MOVE(I,X)。

81 CLOSURE(I)的构造算法（1） 算法： 第二步的分析含义： 注意和 ε-CLOSURE的对应关系
首先将I中的各个项加入到CLOSURE(I)中； 如果Aα.Bβ在CLOSURE(I)中，那么对B的任意产生式Bγ，将B.γ加到CLOSURE(I)中； 不断重复第二步，直到收敛。 第二步的分析含义： 项Aα.Bβ表示期望在接下来的输入中归约到B。 显然，要归约到B，首先要扫描归约到B的某个产生式的右部； 因此对每个产生式Bγ，加入B.γ； 表示它期望能够扫描归约到γ。 注意和 ε-CLOSURE的对应关系

82 构造算法的伪代码描述

83 闭包构造的例子 增广文法： 项集{[E’.E]}的闭包 E’E EE+T | T ET*F | F F(E) | id
[E.E+T]，[E.T]在闭包中； [T.T*F]，[T.F]在闭包中； [F.(E)]，[F.id]在闭包中；

84 LR(0)项集中的内核项和非内核项 在算法中，在加入某个项B.γ时，所有以B为左部的产生式所对应的（点在最左边的）项都会被加入
内核项：初始项S’.S、以及所有点不在最左边的项 非内核项：除了S’.S之外、点在最左边的项； 实现算法时可以考虑只保存相应的非终结符号；甚至可以只保存内核项，而在要使用非内核项时调用CLOSURE函数重新计算。

85 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]； CLOSURE({[EE+.T]}) = {[EE+.T]，[T.T*F], [T.F]，[F.(E)]，[F.id]}。

86 求LR(0)项集规范族的算法 从初始项集开始，不断计算各种可能的后继，直到生成所有的项集。 建议和NFA的子集构造算法类比

87 项集规范族和GOTO函数的例子

88 LR(0)自动机的构造 构造方法： 规范LR(0)项集族中的项集可以作为LR(0)自动机的状态，
GOTO(I,X)=J，则从I到J有一个标号为X的转换； 初始状态为CLOSURE({S’.S})对应的项集； 接受状态：包含形如A α.的项集对应的状态。

89 LR(0)自动机的作用（1） 假设文法符号串γ使LR(0)自动机从开始状态运行到状态（项集）j 如果j中有一个形如Aα.的项。那么
在γ之后添加一些终结符号可以得到一个最右句型， α是γ的后缀，且Aα是这个句型的句柄 表示可能找到了当前最右句型的句柄 如果j中存在一个项Bα.Xβ。那么 在γ之后添加Xβ，然后再添加一个终结符号串可得到一个最右句型， 在这个句型中BαXβ是句柄 此时表示还没有找到句柄，需要移入

90 LR(0)自动机的作用（2） LR(0)自动机的使用 移入-归约时，LR(0)自动机被用于识别句型
如果路径到达接受状态，表明栈上端的某个符号串可能是句柄。 不需要每次用归约/移入得到的串来运行LR(0)自动机 路径被放到栈中；且文法符号可以省略，因为由LR(0)状态可以确定相应文法符号 在移入后，根据原来的栈顶状态即可知道新的状态； 在归约时，根据归约产生式的右部长度弹出相应状态，仍然可以根据此时的栈顶状态计算得到新状态。

91 LR(0)的作用演示：分析id*id 根据LR(0)自动机状态和符号的对应关系，可以得到符号栏中的符号串。

92 LR语法分析器的结构 所有的分析器都使用相同的驱动程序 分析表随文法以及LR分析技术的不同而不同。
栈中存放的是状态序列；可以由状态序列求出符号序列 分析程序根据栈顶状态、当前输入，通过分析表确定语法分析动作。

93 LR语法分析表的结构 两个部分：动作ACTION，转换GOTO ACTION有两个参数：状态i、终结符号a 状态集上的GOTO函数
移入j：j是一个状态。把j压入栈； 归约Aβ：把栈顶的β归约为A。 接受：接受输入、完成分析。 报错：在输入中发现语法错误。 状态集上的GOTO函数 如果GOTO[Ii,A]=Ij，那么GOTO[i,A] = j。

94 LR语法分析器的格局 LR与法分析器的格局包含了栈中内容和余下输入 (s0s1…sm, aiai+1…an$)
第一个分量是栈中的内容（右侧是栈顶） 第二个分量是余下输入 LR语法分析器的每一个状态都对应一个文法符号（s0除外）。 如果进入状态s的边的标号为X，那么s就对应于X。 回忆LR(0)的构造方法可知，进入一个状态的边的标号相同 令Xi为si对应的符号，那么 X1X2…Xm aiai+1…an对应于一个最右句型

95 LR语法分析器的行为 对于格局(s0s1…sm, aiai+1…an$)，LR语法分析器查询条目ACTION[sm,ai]确定相应动作：
移入s：执行移入动作，将s（对应a）移入栈中，新格局(s0s1…sms，ai+1…an$) 归约Aβ，将栈顶的β归约为A，压入状态s： (s0s1…sm-rs，aiai+1…an$)， 其中r是β的长度，s=GOTO[sm-r,A]； 接受：语法分析过程完成 报错：发现语法错误，调用错误恢复例程。

96 LR语法分析算法 输入：文法G的LR语法分析表，输入串w
输出：如果w在L(G)中，输出最左归约步骤（反过来就是最右推导），否则输出错误指示。 算法如下：

97 LR分析表的例子 文法： (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E) (6)Fid

98 LR分析过程的例子 输入：id*id+id

99 SLR语法分析表的构造 SLR语法分析表以LR(0)自动机为基础： 增广文法G’的SLR语法分析表构造算法：
构造G’的LR(0)项集规范族{I0,I1,…,In}。 状态i对应于项集Ii，相关的ACTION表/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)中的终结符号；否则只能移入

100 SLR分析表构造的例子 项集I0: E’.E E.E+T E.T T.T*F T.F F.(E) F.id
ACTION[0,(] = s4, ACTION[0,id]=S5 GOTO[0,E]=1 GOTO[0,T]=2 GOTO[0,F] = 3 项集I1：E’E. EE.+T ACTION[1,$] = 接受；ACTION[1,+] = s6 项集I2：ET. TT.*F ACTION[2,*]=s7 ACTION[2,$/+/)]=归约ET

101 非SLR(1)文法的例子 SL=R | R L*R | id RL 对于I2， 第一个项使ACTION[2,=]=s6,
第二个项使ACTION[2,=]=归约RL.

102 SLR的原理：可行前缀（1） LR(0)自动机刻画了可能出现在语法分析栈中的文法符号串。 可行前缀： 有效项：
直接把项当作状态，可以构造得到一个NFA。 然后确定化得到DFA就是LR(0)自动机 可行前缀： 可以出现在移入-归约语法分析器栈中的右句型前缀。 定义：某个右句型的前缀，且没有越过该句型的句柄的右端。 有效项： 如果存在S到αAw==>αβ1β2w，那么我们说项Aβ1 . β2么对αβ1有效。

103 SLR的原理：可行前缀（2） 如果我们知道Aβ1 . β2对αβ1有效，
当β2不等于空，表示句柄尚未出现在栈中，应该移入或者等待归约； 如果β2等于空，表示句柄出现在栈中，应该归约。 如果某个时刻存在两个有效项要求执行不同的动作，那么就应该设法解决冲突。 冲突实际上表示可行前缀可能是两个最右句型的前缀，第一个包含了句柄，而另一个尚未包含句型 E+T+id E+T*id SLR解决冲突的思想：假如要按照Aβ进行归约，那么得到的新句型中A后面跟随下一个输入符号。因此只有当下一个输入在FOLLOW(A)中时才可以归约。 也可能都认为包含句柄，但是规则不一样

104 SLR的原理：可行前缀（3） 如果在文法G的LR(0)自动机中，从初始状态出发，沿着标号为γ的路径到达一个状态，那么这个状态对应的项集就是γ的有效项集。 回顾确定分析动作的方法，就可以知道我们实际上是按照有效项来确定的。 为了避免冲突，归约时要求下一个输入符号在FOLLOW(A)中。

105 活前缀/有效项的例子 可行前缀E+T* 对应的LR(0)项 对应的最右推导 TT*.F F.(E) F.id
E’EE+TE+T*F E’EE+TE+T*FE+T*(E) E’EE+TE+T*FE+T*id

106 SLR语法分析器的弱点（1） SLR技术解决冲突的方法：
项集中包含[Aα.]时，按照Aα进行归约的条件是下一个输入符号a可以在某个句型中跟在A之后。 如果对于a还有其它的移入/归约操作，则出现冲突。 假设此时栈中的符号串为βα， 如果βAa不可能是某个最右句型的前缀，那么即使a在某个句型中跟在A之后，仍然不应该按照Aα归约。 进行归约的条件更加严格可以降低冲突的可能性

107 SLR语法分析器的弱点（2） [Aα.]出现在项集中的条件：
而[A. α]出现的条件是Bβ.Aγ出现在项中 期望首先按照Aα归约，然后将Bβ.Aγ中的点后移到A之后。 显然，在按照Aα归约时要求下一个输入符号是γ的第一个符号。 但是从LR(0)项集中不能确定这个信息。

108 更强大的LR语法分析器 规范LR方法（或直接称LR方法）添加项[A. α]时，把期望的向前看符号也加入项中。 向前看LR（LALR方法）
这个做法可以充分利用向前看符号，但是状态很多。 向前看LR（LALR方法） 基于LR(0)项集族。但是每个LR(0)项都带有向前看符号。 分析能力强于SLR方法，且分析表和SLR分析表一样大。 LALR已经可以处理大部分的程序设计语言。

109 LR(1)项 LR(1)项中包含更多信息来消除一些归约动作。 实际的做法相当于“分裂”一些LR(0)状态，精确地指明何时应该归约。
LR(1)项的形式 [Aα.β,a] a称为向前看符号，可以是终结符号或者$ a表示如果将来要按照Aαβ进行归约，归约时的下一个输入符号必须是a。 当β非空时，移入动作不考虑a，a传递到下一状态。

110 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有效。

111 可行前缀和LR(1)有效项的例子 文法：SBB BaB | b 最右推导：S aaBab aaaBab。 对应于前面的定义：
δ=aa，A=B w=ab，α=a β=B γ=δα = aaa 因此：[Ba.B,a]对于aaa是有效的；

112 构造LR(1)项集 项集族的构造和LR(0)项集族的构造类似，但是CLOSURE和GOTO有所不同：
在CLOSURE中，当由项[Aα.Bβ,a]生成新项[B.θ,b]时，b必须在FIRST(βa)中。 注意：对应LR(1)项集族中的任意项[Aα.Bβ,a]，总是保证a在FOLLOW(A)中 初始项集满足这个条件 每次求CLOSURE项集时，新产生的项也满足这个条件。

113 LR(1)项集的CLOSURE算法 注意添加[B.γ,b]时，b的取值范围。 即点后面跟着终结符号的项

114 LR(1)项集的GOTO算法 和LR(0)项集的GOTO算法基本相同 即点后面跟文法符号X的项

115 LR(1)项集族的主构造算法 和LR(0)项集族的构造算法相同

116 LR(1)项集族的例子 增广文法 S’S SCC CcC | d I0=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才可以归约 …

117 LR(1)项集的GOTO图 不计向前看符号， I3，I6相同 I8，I9相同 I4，I7相同 如果构造LR(0)项集族，只有6个项集。

118 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表：GOTO[i,A]=j，如果GOTO(Ii,A)= Ij。 没有填写的条目为报错。如果条目有冲突，则不是LR(1)的。 初始状态对应于[S’S.,$]所在的项集。 移入时不考虑向前看符号

119 LR(1)语法分析表的例子 (3,6)，(4,7)，(8,9)分别可以看作是由原来的一个LR(0)状态拆分而来的。 文法： S’S
SCC CcC | d

120 构造LALR语法分析表 LR(1)语法分析表的状态数量很大 SLR(1)语法分析表的分析能力较弱 LALR(1)是实践中常用的方法
能够方便地处理大部分常见的程序设计语言的构造

121 LR(1)语法分析表的合并 状态4和7仅在向前看符号上有所不同。 状态4：下一个符号如果为c或d则归约；为$在报错。
[Cd. c/d] vs [Cd., $] 状态4：下一个符号如果为c或d则归约；为$在报错。 状态7：分析动作正好反过来。 如果我们将4和7中的项合并得47，那么在所有情况都归约 新的语法分析过程会在原来报错时进行归约；但是最终总会报错。 对与这个文法，合并4和7不会引起任何冲突，但是有些文法会有冲突。 对任意文法，如果SLR(1)分析表无冲突，合并后的分析表也无冲突。 文法： S’S SCC CcC | d

122 LALR分析技术的基本思想 寻找具有相同核心的LR(1)项集，并把它们合并成为一个项集 一个LR(1)项集的核心是一个LR(0)项集；
项集的核心就是项的第一分量的集合； I4和I7的核心都是{[Cd.]}， I3和I6的核心{Cc.C C.cC C.d} 一个LR(1)项集的核心是一个LR(0)项集； GOTO(I,X)的核心只由I的核心决定，因此被合并项集的GOTO目标也可以合并。 这表示合并之后，我们仍然可以建立GOTO关系。

123 合并引起的冲突 原来无冲突的LR(1)分析表在合并之后得到LALR(1)分析表；新的表中可能存在冲突。 合并不会导致移入/归约冲突
假设合并之后在a上存在移入/归约冲突，即存在项[Bβ.aγ,?]和[Aα.,a]。 因为被合并的项集具有相同的核心，因此被合并的所有项集中都包括[Bβ.aγ,?]。 而[Aα.,a]必然在某个项集中。 这个项集必然已经存在冲突！ 合并会引起归约/归约冲突，即不能确定按照哪个产生式进行归约。

124 合并引起归约/归约冲突的例子 文法：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？

125 基本的LALR分析表构造算法 步骤： 得到的分析表称为LALR语法分析表。 构造得到LR(1)项集族C={I0,I1,…,In}。
令C’={J0,J1,…,Jn}为得到的LR(1)项集族 按照LR分析表的构造方法得到ACTION表。（如果存在冲突，则这个文法不是LALR的） GOTO表的构造：设J是一个或者多个LR(1)项集（包括I1）的并集，令K是所有和GOTO(I1,X)具有相同核心的项集的并集，那么GOTO(J,X)=K。 得到的分析表称为LALR语法分析表。

126 LALR分析表的例子（1） 文法的LR(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。 …

127 LALR分析表的例子（2） 合并后得到的LALR分析表

128 LALR分析表的例子（3） 处理语法正确的输入时，LALR语法分析器和LR语法分析器的动作序列完全相同。
栈中的状态名字不同，但是状态序列之间有对应关系：如果LR分析器压入状态I，那么LALR分析器压入I对应的合并项集。 比如：当前面的LR分析器压入状态I3时，LALR分析器压入状态I36。 当处理错误的输入时，LALR可能多执行一些归约动作，但是不会多移入一个符号。

129 LALR分析表的高效构造算法 LALR的项集可以看作是在LR(0)项集上添加了适当的向前看符号。 基本方法
只使用内核项来表示LR(0)或LR(1)项集。只使用[S’.S]或[S’.S,$]，以及点不在最左端的项。 使用传播和自发生成的过程来生成向前看符号，得到LALR(1)内核项。 使用CLOSURE函数，求出内核的闭包。然后得到LALR分析表。

130 LALR项中的向前看符号 LALR项集中的项[Aα.β,a]必然是具有相同核心的LR项集中的一个项。
LALR项集J中包含项[Bγ.δ,b]的条件：存在相应的LR项集J’使得下列条件之一成立 LR项集I’中包含项[Aα.β,a]且J’=GOTO(I’,X)，且[Bγ.δ,b]在GOTO(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中。

131 存在LR项集I’包含某个项，也就是存在LALR项集I包含该项 传播关系只取决于项的核心部分，和具体的向前看符号无关
要么传播所有的向前看符号，要么都不传播。

132 确定自发生成/传播关系 基本思想： 引入一个特殊向前看符号#作为“指示剂”，察看这个符号可以如何传播。 令[Aα.β]为项集I中的一个项，对每个文法符号X计算J=GOTO(CLOSURE({[Aα.β,#]}),X)。 检查J中的每个内核项，检查它的向前看符号集合。如果项[Bγ.δ,#]在J中就表示#从I中的Aα.β传播到了[Bγ.δ,#]。 其它的向前看符号都是自发生成的。

133 确定向前看符号的算法 输入：LR(0)项集I的内核K以及一个文法符号 输出：向前看符号的传播/自发生成。

134 LALR项集族中向前看符号的计算 基本思想： 以LR(0)项集为基础； 自发生成的符号首先被加入到相应的LALR项集中；
然后不停地传播向前看符号，直到收敛。

135 具体算法 构造G的LR(0)项集族的内核 将确定自发生成/传播关系的算法应用于每个LR(0)项集的内核和每个文法符号X，确定自发生成和传播的向前看符号。 初始化：给出每个项集和每个内核项的自发生成的向前看符号； 迭代：不断扫描所有项集的内核项，将项I的向前看符号加入到传播目标项的向前看符号集合中。 直到各个向前看符号集合不变为止。

136 构造LALR项集的例子（1） 文法： S’S SL=R SR L*R Lid RL LR(0)项集内核：

137 构造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.

138 构造LALR项集的例子（3） 得到的传播关系：

139 构造LALR项集的例子（4） 计算向前看符号传播的迭代过程：

140 二义性文法的使用 二义性文法都不是LR的。 某些二义性文法是有用的 对于某些二义性文法 可以简洁地描述某些结构；
隔离某些语法结构，对其进行特殊处理。 对于某些二义性文法 可以通过消除二义性规则来保证每个句子只有一棵语法分析树。 且可以在LR分析器中实现这个规则。

141 优先级/结合性消除冲突 二义性文法：EE+E | E*E | (E) | id
等价于：EE+T | T TT*F | F F(E)|id 二义性文法的优点： 容易修改算符的优先级和结合性。 简洁：如果有多个优先级，那么无二义性文法讲引入太多的非终结符号 高效：不需要处理ET这样的归约。

142 二义性表达式文法的LR(0)项集 EE+E | E*E | (E) | id I7、I8中有冲突，且不可能通过向前看符号解决！

143 冲突的原因以及解决 当栈顶状态为7时，表明 如果*的优先级大于+，且+是左结合的 栈中状态序列对应的文法符号序列为…E+E；
下一个输入符号不等于+、*，则归约 归约之后早晚会报错； 如果下一个符号为+或*，移入还是归约？ …E+E* （…E+E+）时，是否先求和？ 如果*的优先级大于+，且+是左结合的 下一个符号为+时，我们应该将E+E归约为E 下一个符号为*时，我们应该移入*，期待引入下一个符号。

144 解决冲突之后的SLR(1)分析表 对于状态7， +时归约 *时移入 对于状态8 执行归约 这个表和等价的无二义性文法的分析表类似

145 悬空else的二义性 文法： LR(0)项集中I4包含冲突，它出现在栈顶时，栈中符号为iS
S’S SiSeS | iS | a LR(0)项集中I4包含冲突，它出现在栈顶时，栈中符号为iS 如果下一个符号为e，因栈中的i尚未匹配，因此应该移入e。 否则，如果下一个符号属于FOLLOW(S)，就归约。

146 LR语法分析中的错误恢复（1） LR语法分析器查询GOTO表时不会有语法错误。 查询ACTION表时可能发现报错条目 恐慌模式的错误恢复策略
假设栈中的符号串为α，当前输入符号为a；报错表示不可能存在终结符号串x使得αax是一个最右句型。 恐慌模式的错误恢复策略 从栈顶向下扫描，找到状态s，s有一个对应于非终结符号A的GOTO目标；（s之上的状态被丢弃） 在输入中读入并丢弃一些符号，直到找到一个可以合法跟在A之后的符号a（不丢弃a）； 将GOTO(s,A)压栈；继续进行正常的语法分析。 基本思想：假定当前正在试图归约到A且碰到了语法错误。因此设法扫描完包含语法错误的A的子串，假装找到了A的一个实例。

147 LR语法分析中的错误恢复（2） 短语层次的恢复

148 语法分析器生成工具YACC YACC的使用方法如下：

149 YACC源程序的结构 声明 翻译规则： 辅助性C语言例程 声明 %% 翻译规则 辅助性C语言程序
指明产生式及相关的语义动作 辅助性C语言例程 被直接拷贝到生成的C语言源程序中， 可以在语义动作中调用。 其中必须包括yylex()。这个函数返回词法单元，可以由LEX生成 声明 %% 翻译规则 辅助性C语言程序

150 翻译规则的格式 <产生式头> : <产生式体>1 {<语义动作>1}
<产生式头> : <产生式体>1 {<语义动作>1} | <产生式体>2 {<语义动作>2} … … … … | <产生式体>n {<语义动作>n} ; 第一个产生式的头被看作开始符号； 语义动作是C语句序列； $$表示和产生式头相关的属性值，$i表示产生式体中第i个文法符号（注意，保护终结符号）的属性值。 在按照某个产生式归约时，执行相应的语义动作。通常根据$i来计算$$的值。 在YACC源程序中，可以通过定义YYSTYPE来定义$$，$i的类型。

151 YACC源程序的例子

152 YACC中的冲突处理 缺省的处理方法 运行选项-v可以在文件y.output中描述冲突及其解决方法；
对于归约/归约冲突，选择列在前面的产生式 对于归约/移入冲突，总是移入（悬空-else的解决） 运行选项-v可以在文件y.output中描述冲突及其解决方法； 可以通过一些命令来确定终结符号的优先级/结合性，解决移入/归约冲突。 结合性：%left %right %nonassoc 产生式的优先级 它的最右终结符号的优先级。 或者加标记%prec<终结符号>，指明产生式的优先级 移入符号a/按照Aα归约：比较a和Aα的优先级，根据结合性，选择不同的操作。

153 YACC的错误恢复 使用错误产生式的方式来完成语法错误恢复 首先定义哪些“主要”非终结符号有错误恢复动作； 当语法分析器碰到错误时
错误产生式Aerror α 例如：stmt  error ; 首先定义哪些“主要”非终结符号有错误恢复动作； 比如：表达式，语句，块，函数定义等非终结符号 当语法分析器碰到错误时 不断弹出栈中状态，直到栈顶状态包含A.error α; 分析器将error移入栈中。 如果α为空，分析器直接执行归约，并调用相关的语义动作；否则向前跳过一些符号，找到可以归约为α的串为止。