Part5语法分析 授课：胡静.

Presentation on theme: "Part5语法分析 授课：胡静."— Presentation transcript:

1 Part5语法分析 授课：胡静

2 自底向上的语法分析概述

3 目录 自底向上语法分析是一个更加强大的分析技术。 LR文法——比LL描述能力更强 移进-归约分析 构造程序的最右推导
几乎所有的程序设计语言都是左递归的 更加容易描述程序设计语言的语法。 移进-归约分析 LR文法的语法分析器 语法生成器的自动生成器 (e.g., yacc)

4 自顶向下vs自底向上 自底向上：只需要对当前的输入给出足够的语法树的部分就行

5 自底向上的语法分析 较常用的自底向上语法分析法 最易于实现的移动归约分析法 最一般的移动归约分析方法 移动－归约分析法 用栈实现移动归约分析
算符优先分析法 算符优先分析法定义、优先分析表的确定、优先函数的定义 使用算符优先关系进行分析 算符优先分析中的错误恢复 最一般的移动归约分析方法 LR分析法

6 自底向上语法分析概述 自底向上的语法分析方法，也称为移动归约分析法。
最易于实现的一种移动归约分析方法，叫做算符优先分析法， 而更一般的移动归约分析方法叫做LR分析法，LR分析法可以用作许多自动的语法分析器的生成器。 移动归约分析法为输入串构造分析数时是从叶结点（底端）开始，向根结点（顶端）前进。 我们可以把该过程看成是把输入串ω“归约”成文法开始符号的过程。 在每一步归约中，如果一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替该子串。 如果每一步都能恰当的选择子串，我们就可以得到最右推导的逆过程。

7 移进-归约分析 分析就是移进和归约动作的序列 移进：将当前扫描的token移动到堆栈中。
归约：将栈顶的符号串β 移除，用非终结符X代替，这对应着产生式A → β (pop β , push A)

8 短语、直接短语、句柄的定义： 文法G[S]，αβδ是文法G的一个句型，
S=>*αAδ且A=>+β则称β是句型αβδ相对于非终结符A的短语。若有A β则称β是句型αβδ相对于该规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。

9 用子树解释短语，直接短语，句柄: 短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。
直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。 句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。 例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。

10 E E 短语 T E+T E+T E + E+T*F T*F,E+T*F E+T*a3 a3,T*a3,E+T*a3 T * F T  E+F*a3 a3,F,F*a3,E+F*a3  E+a2*a3 a3,a2,a2*a3, E+a2*a3  T+a2 *a3 a3,a2,T, a2*a3, T+a2*a3 F a3 F  F+a2*a3 a3,a2,F, a2*a3, F+a2*a3 a1+a2 *a3 a1, a2, a3, a2 * a3 a1+ a2 *a3 a2 a1

11 移动归约分析法相关概念 规范归约 文法的最右推导为规范推导，自底向上分析是自顶向下最右推导的逆过程，叫规范归约 句柄
直观来看：一个符号串的“句柄”是和一个产生式右部匹配的子串，而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。 形式定义：右句型（最右推导可得到的句型）γ的句柄是一个产生式A→β以及γ的一个位置，在该位置可以找到串β，而且用A代替β可以得到γ的最右推导的前一个右句型 对于有二义性的文法而言，由于最右推导不一定，则句柄不一定唯一。只有当文法没有二义性时，每个右句型才只有一个句柄。 句柄剪裁 通过“剪裁句柄”可以得到最右推导的逆过程 在归约过程中用到的产生式序列的逆序就是输入串的最右推导

12 (1)S  aABe (2)A b (3)A Abc (4)B d
S＝>aABe＝>aAde＝>aAbcde＝>abbcde 步骤 符号栈 输入符号串 动作 1 $ abbcde$ 移动 2 $a bbcde$ 移动 3 $ab bcde$ 归约(2) 4 $aA bcde$ 移动 5 $aAb cde$ 移动 6 $aAbc de$ 归约（3） 7 $aA de$ 移动 8 $aAd e$ 归约(4) 9 $aAB e$ 移进 10 $aABe $ 归约(1) 11 $S $ 接受

13 移动归约分析中需要解决的问题 定位右句型中将要归约的子串（可归约串） 选择产生式对选定的串进行归约 移动归约分析过程中的冲突
在用堆栈实现时，这个子串总是在栈顶。语法分析器不需要深入到栈中去寻找句柄 选择产生式对选定的串进行归约 如果选定的子串是多个产生式的右部，要确定选择哪个产生式进行归约 移动归约分析过程中的冲突 根据栈中的内容和下一个输入符号不能决定是移动还是归约（移动-归约冲突） 不能决定按哪一个产生式进行归约（归约-归约冲突）

14 算符优先分析法

15 算符优先分析法 算符文法的定义： 算符优先文法的特点： 所有产生式的右部都不是ε或两个相邻的非终结符
设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(Operator Grammar)也称OG文法. 算符优先文法的特点： 一旦我们构造了算符优先语法分析器，就可以忽略原来的文法，栈中的非终结符仅仅作为与这些非终结符相关的属性的占位符 难以处理像减号这样有不同优先级的符号 由于分析的语言的文法和算符优先语法分析器本身的关系不是很紧密，所以不能肯定语法分析器接受的就是所期望的语言

16 算符优先关系的定义 a的优先级低于b a的优先级等于b a的优先级高于b 算符的优先关系是有序的
a < b：文法中有形如A→…aB...的产生式而B+b…或B+Cb… a的优先级等于b a = b：文法中有形如A→…ab…或者A→…aBb…的产生式 a的优先级高于b a > b：文法中有形如A…Bb…的产生式,而B+…a或B+…aC 算符的优先关系是有序的 如果a > b，不能推出b < a 如果a > b，有可能b > a 如果a > b， b > c，不一定a > c

17 算符优先关系定义（续1） a < b，则存在语法子树如下 其中，δ为ε或者C， a和b不在同一个句柄中，b先被归约 A … a B …
P δ b … 其中，δ为ε或者C， a和b不在同一个句柄中，b先被归约

18 算符优先关系定义（续2） a = b，则存在语法子树如下 A … a δ b … 其中，δ为ε或者B， a和b在同一个句柄中，同时被归约，

19 算符优先关系定义（续3） a > b，则存在语法子树如下 其中，δ为ε或者C， a和b不在同一个句柄中，a先被归约 A … B b …
P … a δ 其中，δ为ε或者C， a和b不在同一个句柄中，a先被归约

20 最左素短语 一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1， aj-1<aj
aj=aj+1,…, ai-1=ai ai>ai+1

21 使用算符优先关系 算符优先关系主要用于界定右句型的句柄 非终结符的处理 <标记句柄的左端；=出现在句柄的内部；>标记句柄的右端。
发现句柄的过程： 从左端开始扫描串，直到遇到第一个>为止。 向左扫描，跳过所有的=，直到遇到一个<为止。 句柄包括从上一步遇到的<右部到第一个>左部之间的所有符号，包括介于期间或者两边的非终结符 非终结符的处理 因为非终结符不能影响语法分析，所以不需要区分它们，于是只用一个占位符来代替它们

22 算符优先分析算法 算法的主体思想 算法描述 用栈存储已经看到的输入符号，用优先关系指导移动归约语法分析器的动作
如果栈顶的终结符和下一个输入符之间的优先关系是<或=，则语法分析器移动，表示还没有发现句柄的右端 如果是>关系，就调用归约 算法描述 输入：输入字符串ω和优先关系表 输出：如果ω是语法产生的一个句子，则输出其用来归约的产生式；如果有错误，则转入错误处理

23 规范归约和算符优先归约 句型#i+i#的规范归约过程
E’ => #E# => #E+T# => #E+F# => #E+P# => #E+i# => #T+i# => #F+i# => #P+i# => #i+i# 步骤 符号栈 剩余输入串 句柄 归约用产生式 1 # i+i# 2 #i +i# i Pi 3 #P +i# P FP 4 #F i# F TF 5 #T i# T ET 6 #E +i# 7 #E i# 8 #E+i # i Pi 9 #E+P # P FP 10 #E+F # F TF 11 #E+T # E+T EE+T 12 #E # 接受

24 规范归约和算符优先归约 句型#i+i#的算符优先归约过程 步骤 栈 优先关系 当前符号 剩余符号串 动作 1 # < i +i# 移进
步骤 栈 优先关系 当前符号 剩余符号串 动作 1 # < i i# 移进 2 #i > i# 归约 3 #P < i# 移进 3 #P+ < i # 移进 4 #P+i > # 归约 4 #P+P > # 归约 4 #E = # 接受

25 算符优先分析法优缺点 由于算符优先分析并未对文法的非终结符定义优先关系，所以就无法发现由单个非终结符组成的“可归约串”。
也就是说，在算符优先归约过程中，我们无法用那些右部仅含一个非终结符的产生式（称为单非产生式，如P→Q）进行归约。这样，算符优先分析比规范归约要快很多。这既是算符优先分析的优点，也是它的缺点。 忽略非终结符在归约过程中的作用，存在某种危险性，可能导致把本来不成句子的输入串误认为是句子。

26 优先函数 优先函数的计算方法 优先函数的问题 优先关系表的存储方式 1.f(a) < g(b)，如果a < b
使得优先关系表中的空白项是模糊的 使得错误的发现被推迟 优先关系表的存储方式 矩阵表示：准确直观；需要大量内存空间(n+1)2 优先函数：需要内存空间小2(n+1)；不利于出错处理

27 优先函数的构造算法 输入：算符优先表 输出：表示输入矩阵的优先函数或指出它不存在 方法：
为每个终结符（包括#）创建fa和ga。并以其作为结点，画出2n个结点 如果a > b或者a = b，则画一条从fa到gb的箭弧 如果a < b或者a = b，则画一条从gb到fa的箭弧 如果构造的图中有环路，则不存在优先函数；如果没有环路，则将f(a)设为从fa开始的最长路径的长度；g(a)为从ga开始的最长路径的长度。 检查是否一致！

28 实例说明 fi gi g* f* f+ g+ g# f# 检查是否一致！ i * + $ < > = i * + $ f g 4
5 3 2 1 f+ g+ g# f# 检查是否一致！

29 算符优先分析中的错误恢复 算符优先分析器能发现的语法错误 归约时的错误处理
如果栈顶的终结符和当前输入之间没有优先关系（如果用优先函数存储，这个错误不能发现） 如果发现句柄，但句柄不是任何产生式的右部 归约时的错误处理 给出相应的具有描述性的出错信息 试图通过插入、删除来获得句柄

30 一个加入了出错处理的优先矩阵 id ( ) $ E3 > < = E4 E2 E1 E1：缺少整个表达式 把id插入输入字符串中
输出诊断信息 Missing operand E2：表达式以右括号开始 从输入中删除 ) Unbalanced right parenthesis E3：id/)后面跟id/( 把+插入输入字符串 Missing operator E4：表达式以左括号结束 从栈中弹出( Missing right parenthesis id ( ) $ E3 > < = E4 E2 E1

31 LR分析法

32 LR语法分析器概述 LR(k)语法分析器适用于一大类上下文无关文法的语法分析。K省略时，假设k是1。 构造LR分析表的三种方法
简单LR方法（SLR），最容易实现，功能最弱 规范LR方法，功能最强，代价最高 向前看的LR方法（LALR），其功能和代价介于前两者之间

33 LR语法分析器的优缺点 LR分析富有吸引力的原因有以下几点：

34 (1)S  aABe (2)A b (3)A Abc (4)B d
S＝>aABe＝>aAde＝>aAbcde＝>abbcde 步骤 符号栈 输入符号串 动作 1 $ abbcde$ 移动 2 $a bbcde$ 移动 3 $ab bcde$ 归约(2) 4 $aA bcde$ 移动 5 $aAb cde$ 移动 6 $aAbc de$ 归约（3） 7 $aA de$ 移动 8 $aAd e$ 归约(4) 9 $aAB e$ 移进 10 $aABe $ 归约(1) 11 $S $ 接受

35 LR语法分析算法 LR分析的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。 当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。

36 LR语法分析器的结构 一个LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。

37 LR语法分析器的结构——栈 我们将把“历史”和“展望”材料综合的抽象成某些“状态”，存放在栈里。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。

38 LR语法分析器的结构——分析表 ACTION[s ,a]规定了当前状态s面临输入符号a时应采取什么动作。
GOTO[s, X]规定了状态s面对文法符号X（终结符或非终结符）时下一个状态是什么。 显然GOTO[s, X]定义了一个以文法符号为字母表 DFA。

39 LR语法分析器的结构——ACTION表 每一项ACTION[s,a]所规定的动作不外是下述四种可能之一。
移进：把(s,a)的下一个状态s’=GOTO[s,a]和输入符号a推进栈，下一个输入符号变成现行输入符号 归约：指用某一个产生式A→β进行归约。假若β的长度为r，归约的动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r, A）的下一个状态s’=GOTO[Sm-r, A]和文法符号A推进栈。 接受：宣布分析成功，停止分析器的工作。 报错：发现源程序含有错误，调用出错处理程序。

40 LR语法分析器分析过程举例 文法G： (1)E  E+T (2)E  T (3)T  T*F (4)T  F (5)F  (E)
状态 ACTION GOTO i + * （ ） # E T F S5 S4 1 2 3 S6 acc r2 S7 r4 4 8 5 r6 6 9 7 10 S11 r1 r3 11 r5 文法G： (1)E  E+T (2)E  T (3)T  T*F (4)T  F (5)F  (E) (6)F  i

41 对上述例子的分析 LR语法分析器不需要扫描整个栈就可以知道什么时候句柄出现在栈顶。栈顶的状态符号包含了所需要的一切信息。
请注意一个非常重要的事实：如果仅由栈的内容和现实的输入符号就可以识别一个句柄，那么就可以用一个有限自动机自底向上扫描栈的内容和检查现行输入符号来确定呈现于栈顶的句柄是什么（当栈顶呈现一个句柄时）。 实际上，LR分析表的goto函数就是这样一个有限自动机，只是它不需要每次移动都读栈。

42 LR文法与LL文法的区别 LL文法要求每个非终结符的所有候选首字符均不相同，因为预测程序认为，一旦看到首符之后就看准了该用哪一个产生式进行推导。 但LR分析程序只有在看到整个右部所推导的东西之后才认为是看准了归约方向。因此，LR方法比LL方法更加一般化。

43 LR(0)项目集族和LR(0)分析表的构造 相关概念： 前缀：字的前缀是指该字的任意首部。
字abc的前缀有ε、a、ab、abc。 活前缀：指规范句型的一个前缀，这种前缀不含句柄之后任何符号。之所以称为活前缀，是因为在右边添加一些符号之首，就可以使它称为一个规范句型。 在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X0 X1 …Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型。 只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。

44 LR(0)项目的定义 对于一个文法G，我们首先要构造一个NFA，它能识别G的所有活前缀。这个NFA的每一个状态是下面定义的一个“项目”。
文法G的每一个产生式的右部添加一个圆点称为G的一个LR(0)项目（简称项目）。例如产生式A→XYZ对应有四个项目： A→•XYZ A→X•YZ A→XY•Z A→XYZ• 产生式A→ε只对应一个项目A→•。

45 LR(0)项目的说明 直观上说，一个项目指明了在分析过程的某时刻我们看到产生式多大部分。
例如， A→•XYZ这个项目意味着，我们希望能从后面输入串中看到可以从XYZ推出的符号串。 A→X•YZ这个项目意味着，我们已经从输入串中看到能从X推出的符号串，我们希望能进一步看到可以从YZ推出的符号串。 将每个项目看成NFA的一个状态，我们就可以构造这样一个NFA，用来识别文法所有的活前缀。

46 LR(0)项目间的转换规则 如果状态i和j来自同一个产生式，而且状态j的圆点只落后于状态i的原点一个位置，
如状态i为X→X1 …Xi-1 •Xi…Xn， 状态j为X→X1 …Xi •Xi+1…Xn， 那么就从状态i画一条标志为Xi的弧到状态j。 假若状态i的圆点之后的那个符号为非终结符， 如i为X→α•Aβ，A为非终结符， 就从状态i画ε弧到所有A→•γ状态。 NFA的接受状态就是那些圆点出现在最右边的项目。

47 LR(0)项目分类 归约项目 接受项目 移进项目 待约项目 凡圆点在最右的项目，如A→α•称为一个“归约项目”
对文法的开始符号S’的归约项目，如S’→α•称为“接受”项目。 移进项目 形如A→α•aβ的项目，其中a为终结符，称为“移进”项目。 待约项目 形如A→α•Bβ的项目，其中B为非终结符，称为“待约”项目。

48 识别LR(0)活前缀的NFA举例 文法G： S’  E E  aA | bB A  cA | d B  cB | d 文法的项目有：
11. E  •bB 12. E  b•B 13. E  bB• 1. S’  •E 2. S’  E• 3. E  •aA 4. E  a•A 5. E  aA• 14. B  •cB 15. B  c•B 16. B  cB• 6. A  •cA 7. A  c•A 8. A  cA• 17. B  •d 18. B  d• 9. A  •d 10. A  d•

49 识别LR(0)活前缀的NFA举例（续） 初态 句柄识别态 句子识别态 S’  •E [1] E  aA• [5] A  cA• [8]
A  d• [10] E  bB• [13] B  cB• [16] B  d• [18] 句子识别态 S’  E• [2] 1. S’  •E 2. S’  E• 3. E  •aA 4. E  a•A 5. E  aA• 6. A  •cA 7. A  c•A 8. A  cA• 9. A  •d 10. A  d• 11. E  •bB 12. E  b•B 13. E  bB• 14. B  •cB 15. B  c•B 16. B  cB• 17. B  •d 18. B  d•

50 ε 6. A  •cA 7. A  c•A 8. A  cA• ε ε ε 9. A  •d 3. E  •aA
1. S’  •E 2. S’  E• 18. B  d• ε d b B 11. E  •bB 12. E  b•B 13. E  bB• 17. B  •d ε ε ε c B 14. B  •cB 15. B  c•B 16. B  cB• ε

51 8. A  cA• 4. A  c•A A  •cA A  •d 10. A  d• 2. E  a•A A  •cA
0. S’  •E E  •aA E  •bB E 1. S’  E• B 3. E  b•B B  •cB B  •d 7. E  bB• b d c d 11. B  d• 5. B  c•B B  •cB B  •d B 9. B  cB• c

52 LR(0)项目集规范族的构造 用ε-CLOSURE(闭包)的办法来构造一个文法G的LR(0)项目集规范族。 准备工作：
假定文法G是一个以S为开始符号的文法，我们构造一个文法G’，它包含整个G，但它引进了一个不出现在G中的非终结符S’，并加进一个新产生式S’→S，而这个S’是G’的开始符号。那么我们称G’是G的拓广文法。 这样，便会有一个仅含项目S’→S•的状态，这就是唯一的“接受”状态。

53 LR(0)项目集规范族的构造 假定I是文法G’的任一项目集，定义和构造I的闭包CLOSURE(I)的办法是：
若A→α•Bβ属于CLOSURE(I)，那么，对任何关于B的产生式B→γ，项目B→•γ也属于CLOSURE(I)； 重复执行上述两步骤直至CLOSURE(I)不再增大为止。 函数GO(I,X)是一个状态转换函数。 第一个变元I是一个项目集， 第二个变元X是一个文法符号。 函数值GO(I,X)定义为GO(I,X)=CLOSURE(J)， 其中J={任何形如A→αX•β的项目 | A→α•Xβ属于I}

54 LR(0)项目集规范族举例 初始状态I0的项目集规范族： I1、I2、I3和分别是GO(I0,E)、 GO(I0,a)和GO(I0,b)
S’  •E E  •aA E  •bB I1、I2、I3和分别是GO(I0,E)、 GO(I0,a)和GO(I0,b) I1是CLOSURE(S’E•)={S’E•} I2是CLOSURE(Ea•A)={Ea•A, A•cA, A•d} I3是CLOSURE(Eb•B)={Eb•B, B•cB, B•d} 文法G： (0) S’  E (1) E  aA (2) E  bB (3) A  cA (4) A  d (5) B  cB (6) B  d

55 8. A  cA• 4. A  c•A A  •cA A  •d 10. A  d• 2. E  a•A A  •cA
0. S’  •E E  •aA E  •bB E 1. S’  E• B 3. E  b•B B  •cB B  •d 7. E  bB• b d c d 11. B  d• 5. B  c•B B  •cB B  •d B 9. B  cB• c

56 LR(0)项目集规范族的讨论 有效项目 LR(0)项目集可能出现的冲突
我们说项目A→β1•β2对活前缀αβ1是有效的，其条件是存在规范推导S’=>*αAω=>αβ1β2ω。 LR(0)项目集可能出现的冲突 同一项目可能对好几个活前缀都是有效的（当一个项目出现在好几个不同的集合中便是这种情况）。 若归约项目A→β1•对活前缀αβ1是有效的，则它告诉我们应该把符号串β1归于为A。即把活前缀αβ1变成αA。 若移进项目A→β1•β2对活前缀αβ1是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应该是移进。 但是，可能存在这样的情形，对同一活前缀，存在若干项目对它都是有效的，而且告诉我们应该做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许能够解决，但有些冲突却是无法解决的。

57 LR(0)分析表的构造 假如一个文法G的拓广文法G’的活前缀识别自动机的每个状态（项目集）不存在下述情况：
既含移进项目又含归约项目。 含多个归约项目。 则称G是一个LR(0)文法。换言之，LR(0)文法规范族的每个项目集不包含任何冲突项目。

58 LR(0)分析表的构造 假定项目集规范族C={I0,I1,…,In}。令每一个项目集Ik的下标k作为分析器的状态。分析表的ACTION子表和GOTO子表可按如下方法构造 令那个包含项目S’→•S的集合Ik的下标k为分析器的初态。 若项目A→α•aβ属于Ik且GO(Ik , a)= Ij,a为终结符，置ACTION[k,a]为“把(j,a)移进栈”，简记为“sj”。 若项目A→α•属于Ik，对任何终结符a(或结束符#)，置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”（假定产生式A→α是文法G’的第j个产生式）。 若项目S’→S•属于Ik，则置ACTION[k,#]为“接受”，简记为“acc”。 若GO(Ik , A)= Ij，A为非终结符，则置GOTO[k,A]=j。 分析表中凡不能用规则1至4填入信息的空白格均填上“报错标志”。

59 8. A  cA• 4. A  c•A A  •cA A  •d 10. A  d• 2. E  a•A A  •cA
0. S’  •E E  •aA E  •bB E 1. S’  E• B 3. E  b•B B  •cB B  •d 7. E  bB• b d c d 11. B  d• 5. B  c•B B  •cB B  •d B 9. B  cB• c

60 SLR分析表的构造

61 SLR语法分析概述 LR(0)文法的活前缀识别自动机的每一个状态（项目集）都不含冲突的项目。
本节我们要研究一种有点简单“展望”材料的LR分析法，即SLR文法。 SLR文法构造分析表的主要思想是：许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。

62 LR(0)文法的局限性 假定一个LR(0)规范族中含有如下的一个项目集（状态）I：I={X→α•bβ, A→α•, B→α•}
第一个项目是移进项目，第二、三个项目是归约项目。这三个项目告诉我们应该做的动作各不相同，互相冲突： 第一个项目告诉我们应该把下一个符号b移进； 第二个项目告诉我们应该把栈顶的α归约为A； 第三个项目告诉我们应该把栈顶的α归约为B。

63 SLR基本算法 解决冲突的方法是分析所有含A和B的句型，考察集合FOLLOW(A)和FOLLOW(B)，如果这两个集合不相交，而且也不包含b，那么当状态I面临输入符号a时，我们可以使用如下策略： 若a=b，则移进。 若a∈FOLLOW(A)，则用产生式A→α进行归约； 若a∈FOLLOW(B)，则用产生式B→α进行归约； 此外，报错

64 SLR基本算法 假定LR(0)规范族的一个项目集I中含有m个移进项目 同时含有n个归约项目
A1→α•a1β1，A2→α•a2β2，…，Am→α•amβm； 同时含有n个归约项目 B1→α•，B2→α•，…，B3→α•， 如果集合{ a1,…, am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交（包括不得有两个FOLLOW集合有#），则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中的哪个集合而活的解决： 若a是某个ai，i=1,2,…,m，则移进。 若a∈FOLLOW(Bi)，i=1,2,…,m，则用产生式Bi→α进行归约； 此外，报错 这种冲突的解决方法叫做SLR(1)解决办法。

65 SLR语法分析表的构造算法 首先把G拓广为G’，对G’构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO。函数ACTION和GOTO可按如下方法构造： 若项目A→α•bβ属于Ik，GO(Ik,a)= Ij,a为终结符，置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”； 若项目A→α•属于Ik，那么，对任何非终结符a，a∈FOLLOW(A)，置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”；其中，假定A→α为文法G’的第j个产生式 若项目S’→S•属于Ik，则置ACTION[k,#]为可“接受”，简记为“acc”； 若GO(Ik, A)= Ij，A为非终结符，则置GOTO[k, A]=j； 分析表中凡不能用规则1至4填入信息的空白格均填上“出错标志”。 语法分析器的初始状态是包含S’ →•S的项目集合的状态

66 SLR分析举例 文法G： (0) S’  E (1) E  E+T
I0:S’  •E E  •E+T E  •T T  •T*F T  •F F  •(E) F  •i 文法G： (0) S’  E (1) E  E+T (2) E  T (3) T  T*F (4) T  F (5) F  (E) (6) F  i I5:F  i• I6:E  E+•T T  •T*F T  •F F  •(E) F  •i FOLLOW(S’) {#} FOLLOW(E) {#, ), +} I1:S’  E• E  E•+T I7:T  T*•F F  •(E) F  •i I2:E  T• T  T•*F I8:F  (E•) E  E•+T I3:T  F• I9:E  E+T• T  T•*F I4:F  (•E) E  •E+T E  •T T  •T*F T  •F F  •(E) F  •i I10:T  T*F• I11:F  (E)•

67 SLR分析举例 状态 ACTION GOTO i + * ( ) # E T F s5 s4 1 2 3 s6 acc r2 s7 r4 4
s5 s4 1 2 3 s6 acc r2 s7 r4 4 8 5 r6 6 9 7 10 s11 r1 r3 11 r5 I1:S’  E• E  E•+T I2:E  T• T  T•*F I9:E  E+T• T  T•*F FOLLOW(S’) {#} FOLLOW(E) {#, ), +}

68 构造规范LR语法分析表

69 SLR文法中可能出现的冲突 文法G’： (0) S’  S (1) S  L=R (2) S  R
I0:S’  •S S  •L=R S  •R L  •*R L  •i R  •L 文法G’： (0) S’  S (1) S  L=R (2) S  R (3) L  *R (4) L  i (5) R  L I5:L  i• I6:S  L=•R R  •L L  •*R L  •i I1:S’  S• I2:S  L•=R R  L• I7:L  *R• I3:S  R• I4:L  *•R R  •L L  •*R L  •i I8:R  L• I9:S  L=R•

70 SLR语法分析的局限性 所有的SLR语法必须满足如下条件
I = {X → • b , A → • , B → • } 若有：FOLLOW(A) ∩FOLLOW(B) = Ø FOLLOW(A) ∩{b} = Ø FOLLOW(B) ∩{b} = Ø 状态I面临某输入符号a 1) 若a=b，则移进 2) 若aFOLLOW(A), 则用产生式 A → 进行归约 3) 若aFOLLOW(B), 则用产生式 B → 进行归约 4) 此外，报错

71 构造规范LR语法分析表 针对SLR语法分析的局限性，我们给出如下解决方案：
重新定义项目，使之包含一个终结符作为第二个分量，可以把更多的信息并入状态中。 项目的一般形式也就变成了[A→α•β, a1a2…ak] ，其中A→α•βLR(0)项目，每一个a都是终结符或者#。——LR(k) 项目中的a1a2…ak称为它的向前搜索符串（或展望串） 搜索符对β是非空的产生式没有什么影响 这样的a的集合是FOLLOW(A)的子集，有可能是真子集 归约项目[A→α•, a1a2…ak]意味着：当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2…ak时，才可以把栈顶的α归约为A。我们只对k≤1的情形感兴趣 ——LR(1)

72 LR(1)对活前缀有效的定义 形式的，LR(1)的项目[A→α·β, a]对活前缀γ有效，如果存在推导S=>*δAω=>δαβω，其中： γ=δα a是ω的第一个符号，或者ω是空串，a是#。 对于Closure运算的新定义 考虑对对活前缀γ有效的项目集中的项目[A→α·Bβ,a]必定存在一个最右推导S=>*δAax=>δαBβax，其中γ=δα。 假设βax能推导出终结符串by，那么对每一个形如B→η的产生式，存在推导S=>*γBby =>γηby ，于是[B→·η, b]对γ有效 可以说，b是FIRST(βax)中的任何终结符，根据FIRST的定义， FIRST(βax)= FIRST(βa)。

73 规范LR语法分析表的构造 步骤 构造拓广文法G’的LR(1)项目集规范族C={I0,I1,…,In}
从Ii构造语法分析器的状态i，状态i的分析动作如下： 如果[A→α·aβ, b]在Ii中，且goto(Ii,a)= Ij，则置action[i,a]为sj ，即“移动j进栈”，这里要求a必须是终结符 如果[A→α·, a]在Ii中，且A≠$’，则置action[i,a]为rj ，即按照rj归约，其中j是产生式A→α的序号 如果[S’→S·, $]在Ii中，则置action[i,$]为acc，表示接受 如果上述出现冲突，那么该文法不是LR(1)文法 状态i的转移按照下面的方法确定：如果goto(Ii,A)= Ij,那么goto[i,a]=j 其余表项设为出错 初始状态是包含[S’→·S, #]的项目集构造出的状态。

74 LR(1)分析表构造举例 文法G： (0) S’  S (1) S  CC (2) C  cC (3) C  d
I0:S’  •S, # S  •CC, # C  •cC, c/d C  •d, c/d I1:S’  S•, # I2:S  C•C, # C  •cC, # C  •d, # I3:C  c•C, c/d C  •cC, c/d C  •d, c/d I6:C  c•C, # C  •cC, # C  •d, # I4:C  d•, c/d I7:C  d•, # I8:C  cC•, c/d I5:S  CC•, # I9:C  cC•, #

75 构造LALR(1)语法分析表 LR(1)项目的特点 LALR(1)项目集 合并同心集需要注意的问题 一部分和SLR(1)项目相同，称为“心”
另一部分为向前搜索符集合。 LALR(1)项目集 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。 合并同心集需要注意的问题 同心集合并后心仍相同，只是超前搜索符集合为各同心集超前搜索符的和集；合并同心集后转换函数自动合并 LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突 合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的

76 同心集合并后的问题分析 就语法分析器的大小而言，SLR表和LALR表对同一文法具有同样多的状态。
我们称两个LR(1)项目集具有相同的心，如果除去搜索符之后，这两个集合是相同的。由于GO(I,X)的心仅仅依赖于I的心，因此，LR(1)项目集合并后的转换函数GO可通过GO(I,X)自身的合并得到。 假定一个LR(1)文法，其LR(1)项目集不存在冲突，但是如果把同心集合并之后就有可能导致冲突。这种冲突不会是“移进-归约”冲突。

77 LALR冲突分析 文法G： (0) S’  S (1) S  aAd | bBd | aBe | bAe
(2) A  c (3) B  c I0:S’  •S, # S  •aAd, # S  •bBd, # S  •aBe, # S  •bAe, # I1:S’  S•, # I2:S  a•Ad, # S  a•Be, # A  •c, d B  •c, e I4:A  c•, d B  c•, e I3:S  b•Bd, # S  b•Ae, # B  •c, d A  •c, e I5:B  c•, d A  c•, e

78 LALR分析与LR分析比较 文法G： (0) S’  S (1) S  CC (2) C  cC (3) C  d 状态
ACTION GOTO c d # S C s3 s4 1 2 acc s6 s7 5 3 8 4 r3 r1 6 9 7 r2 状态 ACTION GOTO c d # S C s36 s47 1 2 acc 5 36 89 47 r3 r1 r2

79 LALR分析与LR分析法比较 LR(1)分析输入串cd# LALR(1)分析输入串cd# 推迟发现错误的时间，但错误出现的位置仍是准确的
步骤 符号栈 输入符号串 动作 状态栈 ACTION GOTO 1） # cd# 移进 S3 2） #c d# 归约 S4 3） #cd # 出错 步骤 符号栈 输入符号串 动作 状态栈 ACTION GOTO 1） # cd# 移进 S3,6 2） #c d# 归约 (3,6) S4,7 3） #cd # 归约 (3,6)(4,7) r (8,9) 4） #cC # 归约 (3,6)(8,9) r 5） #C # 出错

80 LALR算法分析 LALR分析表的一个算法是：首先构造LR(1)项目集族，如果不存在冲突，就把同心集合并在一起。若合并后的集族不存在归约-归约冲突，就按照这个集族构造分析表。 这个算法虽然简单明确，但是实现起来很费时间和空间。

81 LALR直接构造的算法 我们所讨论的各种项目集都是以一定项目为核心的闭包。如果我们用核代替闭包，则不论那一种项目集都将大大的缩小它所需要的存储空间。 任何项目集的核是由此集中所有那些圆点不再最左端的项目组成的。唯一例外的是初态项目集的核含有（而且只含有）项目[S’→•S, #]。

82 使用核有效的构造出分析表 首先，看一看如何从核构造出ACTION表。令Ｉ是一个项目集，Ｋ是它的核。
如果ACTION[I,a]为“用A→α归约”。 那么若α≠ε，则项目A→α•必属于I的核。 若a=ε，意味着在K中必有某个项目[B→β•Cγ, b]，其中C=>R*Aδ，且a∈FIRST(δγb)。但是对于任何C，满足C=>*Aδ的所有非终结符A是可以预先计算出来的。 其次，如果ACTION[I, a]为“移进”，则意味着K中有某个项目[A→α•Bρ, b]，其中B=>R*aω，每个B满足B=>*aω的所有终结符a也是预先可以计算出来的。

83 使用核有效的构造出分析表 现在我们来看如何通过核构造GOTO表。假若GO(I, X)=J，I的核为K，J的核为L。
显然，若[A→α•Xρ, a]∈K，则[A→αX•ρ, a]∈J。 类似地，如果有某个[B→β•Cγ, b]∈K，且C=>R*Aδ和a∈FIRST(δγb)，而A→Xρ是一个产生式，则[A→X•ρ, a]∈J。

84 搜索符是如何传播的 假定B→β•Cγ属于LR(0)集I的核K，C=>R*Aδ（可能C=A而δ=ε），而且A→Xρ是一个产生式，那么显然A→X•ρ属于GO(I, X)的核。 如果考虑的项目集I是LR(1)项目集，假定[B→β•Cγ, b]属于LR(1)集I的核K，那么GO(I,X)核中[A→X•ρ, a]的a的产生有两个途径， 由C=>R*Aδ，若a∈FIRST(δγ)，则这个a和b不相干。在这种情况下，我们说GO(I, X)核中的A→X•ρ的搜索符a是自生的。 若δγ=>*ε，则这个a就是b。在这种情况下，我们说I的核K中的B→β•Cγ把它自己的搜索符b传播给GO(I, X)核中的A→X•ρ

85 LR(1)分析表构造举例 文法G： (0) S’  S (1) S  CC (2) C  cC (3) C  d
I0:S’  •S, # S  •CC, # C  •cC, c/d C  •d, c/d I1:S’  S•, # I2:S  C•C, # C  •cC, # C  •d, # I3:C  c•C, c/d C  •cC, c/d C  •d, c/d I6:C  c•C, # C  •cC, # C  •d, # I4:C  d•, c/d I7:C  d•, # I8:C  cC•, c/d I5:S  CC•, # I9:C  cC•, #

86 自生搜索符的计算算法 PROCEDURE SPONSOR(I,X); /*I是一个LR(0)集，X是一个文法符号。
实际上我们并不需要项目集I而只需要它的核K*/ FOR I的核中的每个项目B→γ•δ DO BEGIN J:= CLOSURE({[B→γ•δ, ※]}); /*采用对LR(1)项目集的求闭包法*/ IF[A→α•Xρ, a] ∈J但a不等于※ THEN GO(I,X)核中的[A→αX•ρ, a]的搜索符a是自生的 IF[A→α•Xρ, ※] ∈J THEN GO(I,X)核中的A→αX•ρ,的搜索符※是从K中的 B→γ•δ传播过来 END

87 手工生成核的算法 构造G的LR(0)项目集的核。
对每个LR(0)项目集的核和每个文法符号，应用算法SPONSOR，确定出哪些搜索符对于GO(I,X)中的核项目是自生的，并确定出从哪些I中的项目出发搜索符可以传播到在GO(I,X)中的核项目中去。 对于每个项目集记的每个核项目，初始化一个表，使之给出与之相关联的各个搜索符。开始时，与每个项目相联系的搜索符仅是哪些在(2)中确定的自生搜索符。 反复遍历所有集合中的核项目。当我们访问一个项目i时，利用(2)中所建立的信息来查看i能将它的搜索符传播到哪些核项目当中。把i的当前搜索符集合附加到已经与i相关联的各个项目中去。即附加到i已将其搜索符传播到达的那些项目中去。继续遍历核项目，直到没有新的搜索符被传播为止。

88 LALR分析表构造的例子 文法G’： (0) S’  S (1) S  L=R (2) S  R
I0:S’  •S S  •L=R S  •R L  •*R L  •i R  •L 文法G’： (0) S’  S (1) S  L=R (2) S  R (3) L  *R (4) L  i (5) R  L I5:L  i• I6:S  L=•R R  •L L  •*R L  •i I1:S’  S• I2:S  L•=R R  L• I7:L  *R• I3:S  R• I4:L  *•R R  •L L  •*R L  •i I8:R  L• I9:S  L=R•

89 I0:S’  •S S  •L=R S  •R L  •*R L  •i R  •L I5:L  i•
从 到 I0:S’  •S I1:S’  S• I2:S  L•=R I2:R  L• I3:S  R• I4:L  *•R I5:L  i• I6:S  L=•R I7:L  *R• I8:R  L• I9:S  L=R• I0:S’  •S S  •L=R S  •R L  •*R L  •i R  •L I5:L  i• I6:S  L=•R R  •L L  •*R L  •i I1:S’  S• I2:S  L•=R R  L• I7:L  *R• I3:S  R• I4:L  *•R R  •L L  •*R L  •i I8:R  L• I9:S  L=R•

90 从 到 I0:S’  •S I1:S’  S• I2:S  L•=R I2:R  L• I3:S  R• I4:L  *•R I5:L  i• I6:S  L=•R I7:L  *R• I8:R  L• I9:S  L=R• 项目 搜索符 初始 第1遍 第2遍 第3遍 I0:S’  •S # I1:S’  S• I2:S  L•=R I2:R  L• I3:S  R• I4:L  *•R = =/# I5:L  i• I6:S  L=•R I7:L  *R• I8:R  L• I9:S  L=R•

91 LR语法分析表的压缩 action表中经常有许多行是相同的。如果我们对每个状态建立一个指向一维数组的指针，则相同表项的指针指向同一个位置。
为每个状态的动作创建一个列表可进一步提高空间的利用效率。列表由（终结符，动作）对组成。 频繁发生的动作放在列表的尾部，并可用符号“any”代替一个终结符，这意味着如果当前输入符号在列表中没有发现，则不管输入是什么都要执行这个动作。 goto表，列表序对的格式为（current_state, next_state）含义为：Goto[current_state]=next_state 我们注意到goto表中的错误表项从来没有被考虑过，因而，我们可以用最常用的非错误表项替换这些错误表项，使该常用表项称为默认值，并把当前状态换成any。

92 对于0、4、6、7： 对于3(5/10/11)： 对于1： 对于8： 对于2： 对于9： 对于T的goto表： 对于F的goto表：
状态 ACTION GOTO i + * ( ) # E T F s5 s4 1 2 3 s6 acc r2 s7 r4 4 8 5 r6 6 9 7 10 s11 r1 r3 11 r5 对于0、4、6、7： 符号 动作 id s5 ( s4 any error 对于3(5/10/11)： 符号 动作 any r4 对于1： 符号 动作 + s6 # acc any error 对于8： 符号 动作 + s6 ) s11 any error 对于2： 符号 动作 * s7 any r2 对于9： 符号 动作 * s7 any r1 对于T的goto表： current_state nest_state any 对于F的goto表： current_state nest_state any 对于E的goto表： current_state nest_state any

93 二义性文法在LR分析中的应用 二义性文法不属于LR文法（定理） 算术表达式的二义性文法 对应的非二义性文法为
E→E+E | E*E | (E) | id 对应的非二义性文法为 E→E+T | T T→T*F | F F→(E) | id I7:E  E+E• E  E•+E E  E•*E I8:E  E*E• E  E•+E E  E•*E

94 二义性文法在LR分析中的应用 悬空else的二义性 条件语句 stmt→if expr then stmt else stmt
| other 重写文法如下 S’ →S S →iSeS | iS | a

95 二义性文法在LR分析中的应用 悬空else的二义性构造LR(0)项目集后，发现冲突： I4：S→iS·eS S→iS·
程序设计语言中的规则，else要和最近的if…then…结构配对，因此当栈顶是iS，而输入是e的时候，要移进。

96 二义性文法在LR分析中的应用 特例产生式引起的二义性 数学公式编排预处理器EQN中使用了特例产生式 E→E sub E sup E
E→E sup E E→{E} （复合表达式） E→c

97 二义性文法在LR分析中的应用 构造LR(0)项目集后，发现冲突： 一部分冲突如果定义了优先级和结合顺序，可以解决
定义sub和sup具有相同的优先级 定义其结合顺序是右结合的 一些归约-归约冲突不好解决： E→E sub E sup E· E→E sup E ·

98 LR语法分析中的错误恢复 在LR分析过程中，当我们处在这样一种状态下，即输入符号既不能移入栈顶，栈内元素又不能归约时，就意味着发现语法错误。
处理的方法分为两类： 第一类多半是用插入、删除或修改的办法。如果不能使用这种办法，则采用第二类办法， 第二类办法包括在检查到某一不合适的短语时，采用局部化的方法进行处理。类似前面讲过的同步符号

99 LR分析 LR(1)分析 LALR(1)分析 SLR(1)分析 LR(0)分析

100

101 自顶向下语法分析 非递归的预测语法分析 自底向上语法分析 提取左因子 消除左递归 FIRST、FOLLOW 算符优先分析法 LR语法分析
SLR(1) LR(1) LALR(1) 二义性文法在LR分析中的应用

102 Thanks for your time! Questions & Answers