七LR分析1.ppt

§7.4 LR(1)分析 三、LR(1)分析方法 1. LR(1)项目集族的构造 以[S′→?S,#]属于初始项目集，把#号作为向前有哪些信誉好的足球投注网站符，表示活前缀为γ(若γ是有关S产生式的某一右部)要归约成S时，必须面临输入符为#号才行。因此对初始项目[S′→?S,# ]求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。 主要思想 §7.4 LR(1)分析 三、LR(1)分析方法 1. LR(1)项目集族的构造 构造LR(1)项目集的闭包函数 步骤 I 的任何项目都属于CLOSURE(I) 若有项目[A→α?Bβ,a ]属于CLOSURE(I)， B→γ是文法中的产生式，β∈V*，b∈FIRST(βa)， 则[B→?γ,b]也属于CLOSURE(I)中。 c) 重复b)直到CLOSURE(I)不再增大为止。 举 例 若文法G′为： (0) S′→S (1) S→BB (2) B→aB(3) B→b I0: S’??S, # S??BB, # B??aB, a/b B??b, a/b 构造LR(1)项目集的初态I0 I 的任何项目都属于CLOSURE(I) 若有项目[A→α?Bβ,a ]属于CLOSURE(I)， B→γ是文法中的产生式，β∈V*，b∈FIRST(βa)， 则[B→?γ,b]也属于CLOSURE(I)中。 c) 重复b)直到CLOSURE(I)不再增大为止。 §7.4 LR(1)分析 三、LR(1)分析方法 1. LR(1)项目集族的构造 转换函数的构造 步骤 LR(1)转换函数的构造与LR(0)的相似，GO(I,X)＝CLOSURE(J)　　其中I是LR(1)的项目集，X是文法符号：　　J={任何形如[A→αX?β,a]的项目 | [A→α?Xβ,a]∈I} 举 例 若文法G′为： (0) S′→S (2) B→aB　　 (1) S→BB (3) B→b I0: S’??S, # S??BB, # B??aB, a/b B??b, a/b S I1:S’?S?, # B I2:S?B?B, # B??aB, # B??b, # b I4:B?b?, a/b a I3:B?a?B, a/b B??aB, a/b B??b, a/b 构造LR(1)项目集初态I0的转换函数 举 例 若文法G′为： (0) S′→S (2) B→aB　　 (1) S→BB (3) B→b 构造LR(1)分析表 I0: S’??S, # S??BB, # B??aB, a/b B??b, a/b S I1:S’?S?, # B I2:S?B?B, # B??aB, # B??b, # b I4:B?b?, a/b a I3:B?a?B, a/b B??aB, a/b B??b, a/b b B I5:S?BB?, # a I6:B?a?B, # B??aB, # B??b, # b I7:B? b?, # b a B I8:B? aB?, a/b a B I9:B? aB?, # ①LR(1)项目集族和转换函数 §7.4 LR(1)分析 三、LR(1)分析方法 2. LR(1)分析表的构造 构造步骤 (2)若项目A→α?属于Ik，则对任何终结符a 和‘#’号 置ACTION[k,a]和ACTION[k,#]为“rj”，j为在 文法G′中某产生式A→α的序号。 LR(1)分析表 (2)若项目A→α?属于Ik，则对任何终结符 a∈Follow(A) ，置ACTION[k,a] 为“rj”，j为在文 法G′中某产生式A→α的序号。 (2) 若项目[A→α?,a]属于Ik，则对任意终结符a置 ACTION[k,a]= rj 。 SLR(1) LR(1) LR(0) 举 例 若文法G′为： (0) S′→S (2) B→aB　　 (1) S→BB (3) B→b 构造LR(1)分析表 ②构造LR(1)分析表 状 态 ACTION GOTO a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 s4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2 a I0: S’??S, # S??BB, # B??aB, a/b B??b, a/b S I1:S’?S?, #