第四章 语法分析 南京大学计算机系 戴新宇 2019-3.

Presentation on theme: "第四章 语法分析 南京大学计算机系 戴新宇 2019-3."— Presentation transcript:

1 第四章 语法分析 南京大学计算机系 戴新宇 2019-3

2 概要 语法分析器 上下文无关文法 语法分析技术 自顶向下 自底向上 语法分析器生成工具

3 引言 程序设计语言源程序的构成 Standard C++ Grammar Java SE7 Grammar
文法：一种用于描述程序设计语言语法的表示方法，能够自然地描述程序设计语言构造的层次化语法结构。 文法给出了一个程序设计语言的精确易懂的语法规约 可以基于文法构造语法分析器，帮助确定源程序的语法结构 语法结构有助于把源程序翻译为正确的目标代码，以及检测导语法错误。 文法的扩展性 Standard C++ Grammar Java SE7 Grammar

4 语法分析器（What） 输入：词法分析器输出的词法单元序列 输出：语法树表示 语法分析器的类型： 通用型(CKY，Earley)
自顶向下：通常处理LL文法 自底向上：通常处理LR文法

5 语法分析器（Why） 语法分析器功能： 验证输入源程序的合法性，并输出良构程序的语法结构 对于病构的程序，能够报告语法错误，并进行错误回复
写入符号表，类型检查，语义分析，翻译生成中间代码等往往和语法分析过程交错完成，实践中往往和语法分析放入一个模块，图上用“前端的其余部分”表示上述活动。

6 文法 本书特指上下文无关文法 （Context Free Grammar, CFG） 程序设计语言中往往存在嵌套结构
上下文无关文法是一种能够很好描述程序设计语言的表示方法 stmt → if ( expr ) stmt else stmt expr → …… stmt → ……

7 CFG的定义 一个CFG由以下几个部分构成 终结符号 非终结符号 一个开始符号 一组产生式 组成串的基本符号，与“词法单元名字”同义
语法变量，表示特定串的集合 给出了语言的层次结构，这种层次结构是语法分析和翻译的关键 一个开始符号 某个特定的非终结符号，其表示的串集合是这个文法生成的语言 一组产生式 描述将终结符合和非终结符号组合成串的方法 产生式左部（头）是一个非终结符号 符号 “→” 一个由零个或多个终结符号与非终结符号组成的产生式右部（体）

8 用于描述算术表达式的文法定义 S -> NP VP VP -> V NP NP -> NAME
NP -> ART N NAME -> John V -> ate ART -> the N -> cat

9 符号表示约定 终结符号：a b + 3 id… 非终结符号: A B C…, S, stmt 文法符号: X Y …
终结符号串:u v w… 文法符号串:α β… 不同可选体: α1 α2 α3… 开始符号: S

10 推导 产生式又可称为重写规则（Rewriting rule） 从开始符号出发，每个重写步骤把一个非终结符号替换为它的某个产生式的体。
e.g. E E –(E) –(id) ， 称为从E到-(id)的推导。这个推导说明了–(id)是表达式E的一个实例，或者说由E产生。 推导的一般性定义： 假设一个产生式A → γ，αAβ αγβ ，符号 表示“通过一步推导出”。

11 推导（续） 推导序列α1 α2 … αn， 称为α1推导到αn。记作 α1 αn， 指经过零步或多步推导。 对于任意串 如果
表示经过一步或多步推导出 句型：如果从文法的开始符号S开始， ，则称α是G的一个句型。 句子，不包括非终结符号的句型。 语言：句子的集合{w|S w}，由文法G生成的语言被称为上下文无关语言L(G)。 文法的等价性：两个文法生成相同语言，则两文法等价

12 推导例子

13 推导中的问题 从推导的角度看，语法分析的任务是：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法。
推导中可能遇到的两个问题 每一步替换哪个非终结符号 若以这个非终结符号为头的产生式有多个，用哪个产生式的右部替换

14 非终结符号的替换顺序 通常使用两种方式进行推导 每个最左推导步骤可以写成 ， , 是应用的产生式 如果 经过最左推导得到 ，记作
最左推导：总是选择每个句型的最左非终结符号。记作 最右推导：总是选择最右边的非终结符号。记作 每个最左推导步骤可以写成 ， , 是应用的产生式 如果 经过最左推导得到 ，记作 最左句型 ：S是文法G的识别符号，如果 ，则 是G的最左句型 w是终结符号串

15 语法分析树 是推导的图形表示形式，树上看不出来推导的顺序 能够反映串的语法层次结构 语法分析树 内部节点：对应于一个非终结符号
子节点：对应于其父节点为头的产生式体 叶子节点：可以是终结符号或非终结符号，从左到右排列可以得到一个句型，称为这棵树的结果。

16 S -> NP VP VP -> V NP NP -> NAME NP -> ART N NAME -> John V -> ate ART -> the N -> cat S NP VP NAME V NP John ate ART N the cat

17 推导和语法树 对于推导中的每个句型 ，我们都可以构造出一个结果为 的语法树

18 推导与语法树例子

19 词法分析和语法分析比较 阶段 输入 输出 描述体系 文法比正则表达式描述能力更强 正则表达式描述词法单元比较简洁
源程序符号串 词法单元序列 正则表达式 句法分析 语法树 上下文无关文法 文法比正则表达式描述能力更强 正则表达式描述词法单元比较简洁 基于正则表达式构造的词法分析器效率更高 正则表达式适合描述词法结构，文法适合描述嵌套结构

20 补充 文法的类别，Chomsky文法类 0型文法(短语结构文法)， α →β 1型文法(上下文相关文法)， αAβ → αγβ
3型文法(正则文法)，A →t, A →tB

21 上下文无关文法和正则表达式 CFG的表达能力更强 每个正则表达式都可以用一个上下文无关文法来描述，反之不成立
每个正则语言都是一个上下文无关语言，反之不成立 正则表达式(a|b)*abb 等价于文法 Ａ０→ａＡ０｜ｂＡ０｜ａＡ１ Ａ１→ｂＡ２ Ａ２→ｂＡ３ Ａ３→ε

22 为NFA构造等价文法

23 上下文无关文法和正则表达式 正则表达式 上下文无关文法 ✔ 上下文无关文法 正则表达式 ？ L={anbn|n>=1}
正则表达式 上下文无关文法 ✔ 上下文无关文法 正则表达式 ？ L={anbn|n>=1} 描述该语言的文法？ 可以用正则表达式描述该语言吗？

24 文法及其生成的语言 语言是由文法的开始符号出发，能够推导得到的所有句子的集合。 实质上回归到了原始的定义，证明采用数学归纳法
文法G: S → aS|a|b, L(G)={ai(a|b), i>=0} 文法G：S → aSb|ab L(G)={anbn, n>=1} 文法G：S → (S)S|ε L(G)={所有具有对称括号对的串} 如何验证文法G所确定的语言L 证明G生成的每个串都在L中 证明L中的每个串都能被G生成 实质上回归到了原始的定义，证明采用数学归纳法

25 文法的设计 在进行高效的语法分析之前，需要对文法做以下处理 消除二义性 消除左递归 提取左公因子
文法的二义性：文法可以为一个句子生成多颗不同的树 消除左递归 左递归：文法中一个非终结符号A使得对某个串α，存在一个推导 ，则称这个文法是左递归的。 提取左公因子

26 二义性文法 如果一个文法可以为一个句子生成多颗不同的语法分析树，则该文法为二义性文法。 通常情况下，我们需要无二义性的文法

27 消除文法的二义性 把二义性文法改写成无二义性文法

28 消除文法的二义性（续）

29 消除文法的二义性（续） 改写文法，基本思想: 在一个then和一个else之间出现的语句必须是“已匹配的”。也就是说then和else中间的语句不能以一个尚未匹配的then结尾。 解决方案：引入新的非终结符号，用来区分是否是成对的then/else。

30 消除文法的二义性示例2

31 消除左递归 左递归：文法中一个非终结符号A使得对某个串α，存在一个推导 ，则称这个文法是左递归的 如果存在A→ Aα,则称为立即左递归
自顶向下的语法分析技术不能处理左递归的文法 立即左递归消除： A→ β A’ A’ →αA’| ε A→ Aα|β

32 立即左递归消除示例

33 消除立即左递归步骤 首先对A产生式分组(所有αi不等于ε，βi不以A开头)： 然后将这些产生式替换为：

34 消除多步左递归 消除立即左递归的方法并不能消除因为两步或多步推导而产生的左递归 文法：S→Aa|b, A→Ac|Sd|ε
S => Aa => Sda 如何消除？

35 消除算法 算法原理： 输入：没有环Ai Ai和 A →ε 输出：一个等价的无左递归的文法 给非终结符号排序，A1,A2…,An
如果只有Ai -> Ajα (i<j)，则不会有左递归 如果发现Ai -> Ajα (i>j),代入Aj的当前产生式，若替换后有Ai的直接左递归，再消除 输入：没有环Ai Ai和 A →ε 输出：一个等价的无左递归的文法

36 消除算法（示例） S→Aa|b, A→Ac|Sd|ε 排序 S A i=1，没有处理
i=2, 替换A→Sd中的S，得到A→Ac|Aad|bd|ε 消除立即左递归

37 提取左公因子 在推导的时候，不知道该如何选择（自顶向下算法会详细描述） A→αβ1 | αβ2 A → αA’ A’→β1 | β2

38 提取左公因子算法 输入：文法G 输出：一个等价的提取了左公因子的文法
方法：对于每个非终结符号A，找出它的两个或多个可选项之间的最长公共前缀α，且α≠ε，那么将A所有的产生式 A→αβ1 | αβ2 | ... | αβn | γ 替换为 A→αA’ | γ A’→β1 | β2 |... | βn

39 提取左公因子

40 自顶向下分析技术 自顶向下分析可以被看作是为输入串构造语法分析树的问题。也可以看作一个寻找输入串的最左推导的过程。

41 id+id*id的自顶向下分析

42 自顶向下语法分析 一种通用的递归下降分析框架 由一组过程组成，每个非终结符号对应一个过程 程序的执行从开始符号对应的过程开始
每个过程的功能是：选择一个产生式体，扫描相应的句子。若遇到非终结符号，调用该符号对应的过程。

43 自顶向下分析技术 在递归下降的框架中：对于非终结符号A，选择哪一个产生式

44 递归下降分析过程示例 输入串w=cad 文法： S →cAd A →ab|a

45 递归下降过程示例(续) 可能需要回溯。或者说，可能需要重复扫描输入。 如果文法中存在左递归…… 回溯（盲目地试）显然是最愚蠢的办法
“在回到A时，我们必须把输入指针重新设置到位置2，即我们第一次尝试展开A时该指针指向的位置。这意味着A的过程必须将输入指针存放在一个局部变量中。” 如果文法中存在左递归…… 回溯（盲目地试）显然是最愚蠢的办法

46 预测分析技术 例1：文法G(S)： S→pA S→qB A→cAd A→a 输入串 W=pccadd 一种确定性的、无回溯的分析技术
在每一步选择正确的产生式 例1：文法G(S)： S→pA S→qB A→cAd A→a 输入串 W=pccadd

47 预测分析技术（续） 例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 输入W=ccap

48 预测分析技术（续） 通过在输入中向前看固定多个符号来选择正确的产生式 通常情况下，我们只需要向前看一个符号 给出两个与文法相关的两个函数
FIRST FOLLOW 基于上述两个函数，可以根据下一个输入符号来选择应用哪个产生式

49 FIRST(α) 定义：可从α推导得到的串的首符号的集合，其中α是任意的文法符号串。如果α ε，那么ε也在FIRST(α)中。
如果两个A产生式 A → α|β，其中First(α)和First(β)是不相交的集合。下一个输入符号是a，若a∈ First(α)，则选择A → α ，若a∈ First(β)，则选择A → β。

50 First(X)的计算 如果X是终结符号，那么FIRST(X)={X}
对于文法符号X的FIRST(X)，通过不断应用下列规则，直到没有新的终结符号或者ε可以加入到任何FIRST集合为止。 如果X是终结符号，那么FIRST(X)={X} 如果X是非终结符号，且有规则X → a…,那么将a添加到FIRST(X)中。如果X → ε，那么ε也在FIRST(X)中。 对于产生式X→ Y1Y2…Yn,把FIRST(Y1)中的非ε符号添加到FIRST(X)中。如果ε在FIRST(Y1)中，把FIRST(Y2)中的非ε符号添加到FIRST(X)中…；如果在FIRST(Yn)中，把ε添加到FIRST(X)中。

51 First(α)的计算（续） 对于文法符号串α=X1X2…Xn的First集合
向First(X1X2…Xn)加入First(X1)中所有的非ε符号。 如果ε在First(X1)中，再加入First(X2)中的所有非ε符号。如果ε在First(X1)和First(X2)中，再加入First(X3)中的所有非ε符号。依次类推。 如果对所有的i（1到n），ε都在First(Xi)中，则ε加入First(X1X2…Xn)中。

52 First的计算示例 First(F)=First(T)=First(E)={(,id} First(E’)={+, ε}
First(TE’)=First(T)={(,id} First(+TE’)={+} ……

53 文法G[S], 输入bcd S → AB|CD A →aD| ε C →cD B →bC D →d FOLLOW函数 对于非终结符号A，FOLLOW(A)定义为可能在某些句型中紧跟在A右边的终结符号的集合。S αAaβ，终结符号a∈Follow(A)。 如果A是某些句型的最右符号，那么$ ∈Follow(A)。 $是特殊的输入串“结束标记” FOLLOW函数的意义： 如果A → α，当α→ ε或α ε时，FOLLOW(A)可以帮助我们做出选择恰当的产生式 例如：if A → α, b属于FOLLOW(A)，如果α ε，则若当前输入符号是b，可以选择A → α，因为A最终到达了ε，而且后面跟着b。

54 FOLLOW计算 计算各个非终结符号A的FOLLOW(A)集合，不断应用下列规则，直到没有新的终结符号可以被加入到任意FOLLOW集合中。
将$放入FOLLOW(S)，S是开始符号。而$是输入串的结束标记。 如果存在产生式A → αBβ，那么First(β)中除ε之外的所有符号都在Follow(B)中。 如果存在一个产生式A → αB，或存在产生式A → αBβ且First(β)包含ε，那么Follow(A)中的所有符号都在Follow（B）中。

55 Follow的计算示例 文法 E::=TE’ E’::=+TE’| ε T::=FT’ T’::=*FT’| ε F::=(E)|i
FOLLOW(T)={+，)，$} FOLLOW(T’)={+，)，$} FOLLOW(F)=(*，+，)，$) ←FIRST( ) ) U {$} ← FOLLOW(E) ←FIRST(E’) U FOLLOW(E’) ← FOLLOW(T) ←FIRST(T’) U FOLLOW(T’)

56 LL(1)文法 满足上述条件的文法称为LL(1)文法，第一个L表示自左向右扫描，第二个L指产生最左推导，而1则表示向前看一个输入符号
如果对于文法G的任意两个不同的产生式A → α|β满足下列条件： First(α) ∩ First(β) = ∅ α ε和β ε不能同时成立 如果β ε，那么FIRST(α) ∩FOLLOW(A)=∅ 满足上述条件的文法称为LL(1)文法，第一个L表示自左向右扫描，第二个L指产生最左推导，而1则表示向前看一个输入符号 LL(1)文法可以利用不回溯的确定性的预测分析技术，因为只需要检查当前输入符号就可以为一个非终结符号选择正确的产生式

57 预测分析技术 前提：无左递归 & LL(1)文法
将first和follow集合中的信息放入一个预测分析表M[A,a]，该预测表告诉我们当非终结符号为A，当前输入符号为a时，要选择哪条产生式。 预测分析表的构造 思想：若当前输入符号a在First(α)中，选择产生式A → α。若α ε，如果a在Follow(A)中，选择产生式A → α;或如果当前符号a是$，且$在Follow(A)中，则选择产生式A → α。

58 预测分析表构造 输入：文法G 输出：预测分析表M 方法：对于文法G的每个产生式A → α ，进行如下处理：
对于First(α)中的每个终结符号a，将A → α加入到M[A,a] 如果ε在First(α)中，那么对于Follow(A)中的每个终结符号b，将A → α加入到M[A,b]中 如果ε在First(α)中，且$在Follow(A)中，将A → α加入到M[A,$]中 完成上述操作后，若M[A,a]中没有产生式，填为error

59 预测分析表构造示例 文法： E::=TE’ E’::=+TE’| ε T::=FT’ T’::=*FT’| ε F::=(E)|i F T’
FIRST(TE ’)={ (， i} FIRST(＋TE ’)={＋} FIRST(FT’)={(，i} FIRST(*FT’)={*} FIRST((E))={(} FIRST(i)＝{i} FOLLOW(E)={) ， $} FOLLOW(E’)={) ， $} FOLLOW(T)={+，)，$} FOLLOW(T’)={+，)，$} FOLLOW(F)=(*，+，)，$) 预测分析表构造示例 文法： E::=TE’ E’::=+TE’| ε T::=FT’ T’::=*FT’| ε F::=(E)|i F T’ T E’ E $ ) ( * + i E::=TE’ E::=TE’ E’::=+TE’ E’::=ε E’::=ε T::=FT’ T::=FT’ T’::= ε T’::=*FT’ T’::= ε T’::= ε F::=i F::=(E)

60 预测分析表（续） 对于任何文法G，都可以构造预测分析表。但是对于LL(1)文法，预测表中每个条目都唯一地指定了一个产生式，或者标明error

61 二义性文法的预测分析表 对于某些文法，表中可能会有一些多重定义的条目，比如左递归或二义性文法。

62 非递归的预测分析技术 文法符号栈 输入缓冲区 控制程序
在任何时刻，栈顶符号X与当前输入符号a决定了控制程序所应执行的分析动作。四种可能的动作 如果X=a= $ ，则分析成功结束 如果X=a≠ $ ，则从栈中退去X，并把输入指针推进到指向下一个输入符号； 如果X是一个非终结符号，且分析表A的元素A[X][a]=“X::=X1X2…Xk”，则把栈顶的X替换为XkX2…X1 （反向下推入栈，使得X1在栈顶）。 除上述情况外的其它情况，调出出错程序。

63 表驱动的非递归的预测语法分析 输入：一个串w，文法G的预测分析表M。 输出：如果w在L(G)中，输出w的一个最左推导；否则报错。
方法：初始化输入缓冲区为w$, 栈顶是G的开始符号S，下面是$ 。

64 预测分析示例

65 语法错误的处理 错误难以避免 编译器需要具有处理错误的能力 程序中可能存在不同层次的错误
词法错误 语法错误 语义错误 逻辑错误 语法错误相同容易发现，语义和逻辑错误较难精确的检测到 语法分析器中错误处理程序的设计目标： 清晰准确地报告出现错误，并指出错误的位置 能从当前错误中恢复，以继续检测后面的错误 尽可能减少处理正确程序的开销

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

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

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

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

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

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

72 自底向上句法分析 概述 移进-规约技术 LR语法分析技术 简单LR技术 LR技术

73 自底向上句法分析概述 自底向上语法分析过程对应于为一个输入串构造语法分析树的过程。从叶子节点（底部）开始逐渐向上到达根节点（顶部）
Bottom-Up Parsing

74 自底向上句法分析概述 - 归约 Bottom-up parsing – 将一个串w归约为文法符号的过程
在每一步的归约中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号。一次归约实质上是一个推导的反向操作。 Bottom-up parsing – 将一个串w归约为文法符号的过程 – 反向构造一个推导的过程 问题： 何时进行归约 应用哪个产生式进行归约

75 自底向上句法分析概述 – 句柄剪枝 Bottom-Up Parsing – 归约过程 – 反向最右推导过程 – 句柄剪枝过程
句柄：和某个产生式体相匹配的子串，对它的归约代表了相应的最右推导的一个反向步骤。 句柄的形式定义：S αAw αβw，那么紧跟α的β可以一步归约到A。 w是所有的终结符号串。 注意： 归约前后都是最右句型 和某个产生式匹配的最左子串不一定是句柄 无二义性的文法，其每个右句型都有且只有一个句柄

76 句柄剪枝 最右句型 句柄 归约用产生式 id1*id2 id1 F→id F*id2 F T→F T*id2 id2 T*F T→T*F T
E→T

77 自底向上句法分析概述 – 句柄剪枝（续） 通过“句柄剪枝”可以得到一个反向的最右推导。从句子w开始，令w=γn, γn是未知最右推导的第n个最右句型。 以相反的顺序重构这个推导（实际上是重构归约序列），我们在γn中寻找句柄βn ，并将替换为相应产生式A → βn的头部，得到前一个最右句型γn -1。重复这个过程，直到S。 问题转变为：如何找到句柄？（搁置一下这个问题先）

78 移进归约语法分析框架 一种自底向上的分析形式 使用一个栈保存文法符号，一个输入缓冲区存放将要进行分析的剩余符号 初始栈： $ 初始输入 w$
对输入串的一次从左到右的扫描过程中，语法分析器将零个或多个输入符号移到栈的顶端，直到它可以对栈顶的一个文法符号串进行归约为止。它将归约为某个产生式的头。不断重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空。 分析成功时： 栈 $ S, 输入 $

79 移进归约语法分析框架（续） 移进归约分析器的四种可能动作 移入(Shift)： 将下一个输入符号移到栈顶
归约(Reduce)：被归约的符号串（句柄）的最右端必然是栈顶，语法分析器在栈中确定它的最左端，将句柄从栈中推出，将归约得到的非终结符号压入栈。 接受：分析结束并成功 报错：发现语法分析错误

80 移进归约语法分析框架（续） 可行性分析：句柄总是出现在栈的顶端，绝不会出现在栈的中间。
语法分析器进行一次归约以后，都必须接着移入零个或多个符号才能在栈顶找到下一个句柄。 不需要去栈中间去寻找句柄

81 移进归约冲突 移入-归约技术并不能处理所有上下文无关文法 某些上下文无关文法（比如二义性文法）：
移入/归约冲突：栈中的内容和接下来的k个输入符号，都不能确定进行移入还是归约操作。不能确定是否是句柄。 归约/归约冲突：存在多个可能的归约到不同非终结符号的归约。不能确定句柄归约到那个非终结符号。

82 移入/归约冲突

83 归约/归约冲突

84 冲突问题 让词法分析区分id和procid 用[]表示数组，用()表示函数 …… 但是并不能完全解决冲突问题
有一类文法可以解决句柄查找及归约唯一性的问题

85 Review of Bottom-up Parsing
从输入串出发构造一个反向最右推导序列（归约） 每一步是对句柄进行归约 -- 寻找句柄 一种移进-归约的分析框架 一个栈存放文法符号，一个输入缓冲区 移进 or 归约 总是能够在栈的顶端找到句柄 通过证明是可行的 有时候会有冲突，是移进还是归约？ 怎么归约？

86 LR语法分析技术 表格驱动，如果能够用某个方法为一个文法构造出移进-归约语法分析表，那么就称为LR文法
LR(k)分析：目前最流行的无回溯的移入-归约分析技术，并且高效 L：从左往右扫描输入 R: 反向构造一个最右推导序列 k:向前看k个符号（通常k<=1, 缺省为1）以帮助做出移入或归约的决定 LR语法分析技术很有吸引力 用于描述程序设计语言的上下文无关文法，通常均可以使用LR分析技术 对输入进行扫描时可以尽早检测到错误 能用该技术的文法类是使用预测方法或LL方法的文法类的真超集。（能处理更多的文法）

87 LR分析相关概念 移入-归约语法分析器如何知道何时该移入、何时该归约呢？
LR(0)项(item)：一个文法G的一个LR(0)项是G的一个产生式再加上一个位于它的体中某处的点。 项的意义：指明在语法分析过程中的给定点上，我们已经看到了一个产生式的哪些部分。或者说，如果我们想用这个产生式进行归约，还需要看到哪些文法符号。 项的集合（项集）对应于一个状态

88 LR(0)项集规范族 三个相关定义： 增广文法G’：在文法G上增加一个产生式S’ →S。 增广文法 项集闭包 GOTO函数

89 LR(0)项集规范族 -- 项集闭包 项集的闭包CLOSURE：如果I是文法G的一个项集，那么CLOSURE(I)就是根据下列两条规则从I构造得到的项集 将I中的各个项加入到CLOSURE(I)中 如果A → α·Bβ在CLOSURE(I)中，B→γ是一个产生式，并且项B→·γ不在CLOSURE(I)中，就将该项加入其中。不断应用这条规则，直到没有新项可以加入到CLOSURE(I)为止。 意义： A → α·Bβ，表示接下来希望看到由Bβ推导出的串，那首先要看到由B推导得到的子串，因此加上B的各个产生式对应的项。

90 项集闭包计算示例及算法 I={[E’→·E]}
CLOSURE(I)={[E’→·E], [E→ · E+T], [E → · T], [T → · T*F], [T → · F],[F → ·(E)],[F → · id]}

91 LR(0)项集规范族 – GOTO函数 GOTO函数：I是一个项集，X是一个文法符号，GOTO(I,X)定义: I中所有形如[A → α·Xβ]的项所对应的项[A → αX·β]的集合的闭包。 示例： I={[E’→E·],[E→ E·+T]} GOTO(I,+)={[E→ E+·T],[T→·T*F], [T→·F],[F→·(E)],[F→·id]}

92 LR(0)项集规范族的构造 为文法G构造LR(0)项集规范族C 步骤一：构造增广文法G’: S’ →S ……
步骤二：构造I0=CLOSURE(S’ →·S)，I0是C的初始项集 步骤三：对C中的每个项集Ii及每个文法符号Xj，将GOTO(Ii,Xj)加入到C中 重复步骤三，直到没有新的项集可以加入 Void items(G’){ C={CLOSURE({[S’ →·S]})}; repeat for(C中的每个项集I) for(每个文法符号X) if(GOTO(I,X)非空且不在C中) 将GOTO(I,X)加入C中 until在某一轮中没有新的项集被加入到C中； }

93 LR(0)项集规范族构造示例

94 LR(0)项集规范族 → LR(0)自动机 基于规范LR(0)项集族可以构造一个确定性的LR(0)自动机
GOTO函数则定义了LR(0)自动机中的状态转换。GOTO(I,X)描述了当输入为X时离开状态I的转换。

95 LR(0)自动机 通过构造LR(0)项集规范族可以得到LR(0)自动机
LR(0)自动机的开始状态是CLOSURE({[S’ →·S]})。状态j是指对应于项集Ij的状态 每个状态对应于一个文法符号， GOTO(Ii,X)=Ij，则到达j状态的转换一定对应于同一个文法符号X

96 利用LR(0)自动机进行移进归约语法分析 简单LR语法分析技术（SLR分析）的中心思想：
假设文法符号串γ使LR(0)自动机从开始状态0运行到某个状态j，LR(0)自动机按照如下方式决定移入或归约： 如果下一个输入符号为a，且j上有a的转换，就移入a 否则就归约，状态j中的项会告诉我们使用那个产生式进行归约

97 LR(0)运行语法分析示例 栈中只保留了状态，文法符号可以从相应的状态中获取

98 LR语法分析算法框架 一个输入、一个输出、一个栈、一个驱动程序和一个语法分析表 语法分析表包括ACTION和GOTO两个部分。
栈中存放状态序列s0…sm,sm在栈顶，在SLR中，这些状态就是LR(0)自动机中的状态

99 LR语法分析表 由语法分析动作函数ACTION和转换函数GOTO组成，帮助确定移入或归约动作及状态转换：
ACTION函数：状态i和终结符号a（或$）决定四种动作形式 移入j，j是一个状态。语法分析器采取的动作是把输入符号a移入栈中，实际上是移入状态j。因为j可以和a相关联。 归约A → β ，语法分析器的动作是把栈顶的β归约为产生式头A 接受 报错 GOTO函数 如果GOTO(Ii,X)=Ij，即GOTO把状态i和一个非终结符号A映射到状态j。

100 LR语法分析器的格局 在分析过程中的中间分析状态，称为格局 对应于句型 X1X2…Xmaiai+1…an
( So S Sm, ai ai an $ ) stack Rest of Input 对应于句型 X1X2…Xmaiai+1…an 因为栈中存放的是状态，因此需要从状态中复原出与其相关联的的文法符号。Xi是Si所关联的文法符号。 S0不代表任何文法符号。

101 LR语法分析程序行为 基于某个格局，语法分析器根据当前输入符号ai和栈顶的状态sm ，然后在分析动作表中查询条目ACTION[sm ，ai]，做完一个动作，分别进入以下格局： 如果ACTION[sm ，ai]=移入s，将状态s移入栈中，进入格局(sos1...sms, ai+1...an$)； 如果ACTION[sm，ai]=归约A→β，执行归约动作，进入格局(sos1...sm-rs, ai...an$)，r是β的长度，s=GOTO[sm-r ,A]； 如果ACTION[sm，ai]=接受，那么语法分析顺利结束； 如果ACTION[sm，ai]=报错，那么发现语法错误，并进行出错处理。

102 LR语法分析算法 输入：一个输入串w和一个LR语法分析表 输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的归约步骤，否则报错。
栈中初始状态：S0， 输入缓冲区：w$

103 LR分析示例 si表示移入并将状态i压入栈 rj表示按照编号为j的产生式进行归约 Acc表示接受 空白表示报错

104 SLR分析表构造 以LR(0)项和LR(0)自动机为基础，基于文法G的规范项集族C和GOTO函数就可以构造出SLR的语法分析表。

105 SLR分析表构造算法 4) 规则2)和3)没有定义的所有条目设置为“报错” 输入：一个增广文法G’
输出：G’的SLR语法分析表函数ACTION和GOTO 方法： 1）构造G’ LR(0)项集规范族C={I0, I1,… In,} 2）对于状态i中的项： [A → α·aβ]且GOTO[Ii ,a]=Ij, 那么ACTION[i,a]=移入j。这里的a是终结符号 [A → α·]，那么对于FOLLOW(A)中的所有a， ACTION[i,a]=归约A → α [S’ →S·], 那么ACTION[i,$]=接受 3）状态i对于非终结符号A的转换规则：如果GOTO[Ii ,A]=Ij，那么GOTO[i ,A]=j 4) 规则2)和3)没有定义的所有条目设置为“报错”

106 SLR（1） 根据上一算法构造的语法分析表，若表中各位置没有多个条目，则称为文法G的SLR(1)分析表。使用该分析表的分析器，称为G的SLR(1)语法分析器。G称为SLR(1)文法 若表中某位置存在多个条目（多个可选的动作，冲突），则该文法是非SLR(1)文法

107 构造示例

108 构造示例

109 LR(0)自动机进行语法分析的基本原理 语法分析的栈中内容一定是某个最右句型的前缀。但是不会跨过句柄。
可行前缀：可以出现在一个移入-归约语法分析器的栈中的最右句型前缀。 LR(0)自动机能够识别可行前缀。 如果存在一个推导过程S αAw αβ1β2w，项A→β1·β2是可行前缀αβ1的有效项。 有效项的意义：语法分析栈中发现αβ1时，如果β2≠ε，表示句柄还没有全部移入到栈，因此选择移入。如果β2 =ε，那么β1就是句柄，可以归约到A。同一个可行前缀可能会有不同的有效项，要求做不同的事情，这样的冲突需要向前看输入符号来解决。后面会有更一般的解决方案。 LR语法分析理论的核心思想：如果我们在某个文法的LR(0)自动机中从初始状态开始沿着标号为某个可行前缀的路径到达一个状态，那么该状态对应的项集就是的有效项集。

110 可行前缀示例 可行前缀E+T＊对应的有效项： T → T＊·F F → ·(E) F → ·id

111 分析表冲突 状态2，输入符号为=时，选择移入还是归约…… 没有参考更多的上下文信息 为什么归约出错？Follow集合？

112 更强大的LR语法分析器 规范LR方法。充分利用向前看符号。这种方法是用了一个更大的项集，称为LR(1)项集 向前看LR，又称LALR

113 LR(1)项 FOLLOW集提供的可归约条件过松 每个状态能否明确指出哪些输入符号可以跟在句柄α后面，从而使句柄α可能被归约为A。
在SLR中，如果项集Ii中包含项[A → α·]，且当前符号a在FOLLOW(A)中，那么就可以按照A→α进行归约。 有时，在任何最右句型中a都不可能跟在βA之后，这时输入为a不能按照A → α进行归约。如上面的示例二。 FOLLOW集提供的可归约条件过松 每个状态能否明确指出哪些输入符号可以跟在句柄α后面，从而使句柄α可能被归约为A。

114 LR(1)项 (续) 形式如[A → α·β,a]，其中A → αβ是一条产生式，a是一个终结符号或者$符
a是向前看符号，长度为1。其意义是若栈顶状态中存在LR(1)项[A → α·,a] ，在输入符号为a时才会进行归约 a的集合总是FOLLOW(A)的子集 β≠ε时， a没有任何作用 a指出能够进行归约的准确判断 向前看符号与确定归约有关

115 LR(1)项 (续) 从可行前缀和有效项的角度看：
LR(1)项[A → α·β,a]对于一个可行前缀δα有效的条件是存在一个推导S δAw δαβw，其中a∈First(w)。当w为ε，a=$

116 LR(1)项集构造 过程类似于LR(0)项集构造 多了一个向前看符号分量的计算 CLOSURE GOTO

117 LR(1)项集闭包CLOSURE CLOSURE(I)=I U {[B → .γ，b] | [A → α·Bβ,a] ∈CLOSURE(I)，b∈First(βa)，且B →γ为文法规则}

118 LR(1)项集GOTO函数

119 LR(1)项集规范族构造算法

120 LR(1)项集规范组构造示例

121 规范LR(1)语法分析表 4) 规则2)和3)没有定义的所有条目设置为“报错” 输入：一个增广文法G’
输出：G’的规范LR语法分析表函数ACTION和GOTO 方法： 1）构造G’ LR(0)项集规范族C={I0, I1,… In} 2）对于状态i中的项： [A → α·aβ，b]且GOTO[Ii ,a]=Ij, 那么ACTION[i,a]=移入j [A → α·，a]，且A ≠ S’ ， ACTION[i,a]=归约A → α [S’ →S·, $], 那么ACTION[i,$]=接受 3）状态i对于非终结符号A的转换规则：如果GOTO[Ii ,A]=Ij，那么GOTO[i ,A]=j 4) 规则2)和3)没有定义的所有条目设置为“报错”

122 语法分析表示例

123 LR(1)文法 通过上述算法构造的LR(1)语法分析表中若不存在冲突条目，则给定的文法称为LR(1)文法。

124 LR(1)语法分析器状态再观察 在(3,6) (4,7) (8,9)中，项的第一个分量是一样的，实质上它们来自于同样的LR(0)状态

125 LALR分析 LR(1)语法分析器的状态过多 但LR(1)的分析能力强于SLR(1) LALR分析 状态和SLR一样多

126 项集合并 将LR(1)项集中具有相同核心的项集合并为一个项集 项集核心是指LR(1)项集中第一个分量的集合
被合并项集的GOTO目标显然也可以被合并 I3={[C→c·C, c/d],[C→·cC, c/d],[C→·d, c/d]} I6={[C→c·C, $],[C→·cC, $],[C→·d, $]} 合并后： I36= {[C→c·C, c/d/$],[C→·cC, c/d/$],[C→·d, c/d]/$} GOTO(I3,C)和GOTO(I6,C)显然也可以合并……

127 合并可能产生的冲突 合并引起的冲突是指：本来的LR(1)项集没有冲突，而合并具有相同核心的项集后有冲突。 不可能引入归约-移入型冲突。 假定合并后有移入_归约冲突，就是说：有项[A→α·, a]和项[B→β·aγ, b]。显然，原来的项集中都有[B→β·aγ, ?]。而[A→α·, a]必然也在某个原来的项集中。这样，合并前的LR(1)项集已经存在移入-归约冲突。 但是可能引起归约_归约冲突。

128 归约-归约冲突 语言{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]} 当输入为d或e时，用哪个归约？ 从引起新的冲突可以看出：LALR的分析能力比规范LR弱一些

129 LALR语法分析表构造方法 最朴素的方法 高效的方法

130 LALR语法分析表构造方法 – 朴素的方法 基本思想： 输入：一个增广文法G’ 输出：文法G’的LALR语法分析表 方法：
得到的分析表成为LALR语法分析表。构造得到LR(1)项集族C={I0,I1,…,In}。 对于LR(1)项集中的每个核心，找出所有具有这个核心的项集，并把这些项集替换为它们的并集 令C’={J0,J1,…,Jn}是得到的LR(1)项集族。按照LR(1)分析表的构造方法得到ACTION表。（注意检查若存在冲突，则这个文法不是LALR的） GOTO表的构造：若J是一个或者多个LR(1)项集的并集，即J=I1∪I2 ∪ … ∪ IK，令K是所有和GOTO(I1,X)具有相同核心的项集的并集，那么GOTO(J,X)=K。

131 LALR分析表构造示例

132 LALR分析器和LR分析器 若构造出的LALR分析表中没有冲突，则可以用LALR分析表进行语法分析。 如果是正确的输入串 如果是错误的输入串

133 LALR技术本质 对LR(1)项集规范族中所谓的同心项集进行合并，从而使得分析表既保持了LR(1)项中向前看符号的信息，又使状态数减少到与SLR分析表的一样多。

134 二义性文法的自底向上分析 二义性文法都不是LR的 二义性文法却有其存在的必要 对于某些二义性文法
可以通过消除二义性规则来保证每个句子只有一棵语法分析树 且可以在LR分析器中实现这个规则

135 优先级/结合性消除冲突 二义性文法的优点： 容易修改算符的优先级和结合性。 简洁：较少的非终结文法符号 高效：不需要处理ET这样的归约。

136 二义性表达式文法的LR(0)项集 I7，I8中有冲突，在输入+或*时，不能确定是归约还是移入。且不可能通过向前看符号解决

137 基于优先级解决冲突 如果*的优先级大于+，且+是左结合的 下一个符号为+时，我们应该将E+E归约为E
下一个符号为*时，我们应该移入*，期待移入下一个符号。

138 解决冲突之后的SLR(1)分析表 对于状态7，输入 +时归约 *时移入 对于状态8 执行归约

139 悬空else的二义性 栈中内容if expr then stmt, 是输入else，还是归约？ 答案是移入

140 文法比较

141 语法错误的处理 错误难以避免 编译器需要具有处理错误的能力 程序中可能存在不同层次的错误
词法错误 语法错误 语义错误 逻辑错误 语法错误相同容易发现，语义和逻辑错误较难精确的检测到 语法分析器中错误处理程序的设计目标： 清晰准确地报告出现错误，并指出错误的位置 能从当前错误中恢复，以继续检测后面的错误 尽可能减少处理正确程序的开销

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

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

144 语法分析器生成工具YACC YACC的使用方法如下： C语言写的LALR语法分析器

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

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

147 YACC源程序的例子

148 YACC对于二义性文法的处理 缺省的处理方法 运行选项-v可以在文件y.output中看到冲突的描述及其解决方法；
对于归约/归约冲突，选择前面的产生式 对于归约/移入冲突，总是移入（悬空-else的解决） 运行选项-v可以在文件y.output中看到冲突的描述及其解决方法； 可以通过一些命令来确定终结符号的优先级/结合性，解决移入/归约冲突。 结合性：%left %right %nonassoc 终结符号的优先级通过它们在声明部分的出现顺序而定。 产生式的优先级设定为它的最右终结符号的优先级。也可以加标记%prec<终结符号>，指明产生式的优先级等同于该终结符号 移入符号a/按照Aα归约：当Aα的优先级高于a，或者两者优先级相同但产生式是左结合时，选择归约，否则移入。

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

150 1. 文法：S→ L=R|R L→ *R|id R→ L 1）. 请分别构造该文法的LR(0)和LR（1）项集规范族及自动机 2). 构造SLR语法分析表和LR（1）分析表 3). 基于分析表，写出串id=id和*id=id的移进规约的分析过程。 2. 请将语言{ xm y zm+1 a | m ≥ 1 }用上下文无关文法描述。