第6章lr分析程序及其自动构造

第6章lr分析程序及其自动构造内容摘要：

 [S]=   [A]=a+[A]  [B]=aAc 令 ={[S’]， [S]， [A]， [B]， a，A,c} 则方程两边都是 上的正规式 而 [A]=a+[A] 即为 [A]=a | [A] 由正规式所表示的正规集  得： [A]=a G[S]: (0) S’S (1) S a A c B e (2)A b (3) A Ab (4)B d 定义 (产生式的 LR(0)左文 ) LR(0)LC(A)={|  =且 S’A , Vt*} 有推论： LR(0)LC(A )=LC(A).{} 则有 : LR(0)LC(S’S)=S LR(0)(LC(SaAcBe)=aAcBe LR(0)LC(Ab)=ab LR(0)LC(AAb)=aAb LR(0)LC(Bd)=aAcd ( =VnVt)上的正规式 R * R x 5 ④ ⑧ 9 ① 2 14 3 0 6 7 10 11 12 16 15 ⒀ 17 18 ⒆ S a a a a A A A b c c b d e B      DFA x 2 3 5 7 8 9 6 4 1 A b a S b c B e d 构造 LR(0)项目集规范族  LR(0)项目集规范族 (构成识别一个文法的活前缀的DFA的状态的全体 )。  LR（ 0） 项目或配置 （ item or configuration） .  在右端某一位置有圆点的 G的产生式 A xyz A.xyz A A Axyz. 如： S→aAd S→ .aAd S→a .Ad S→aA .d S→aAd . 活前缀与句柄的关系：  G[S]:  若 S = α Aω =α β ω r是 αβ的前缀，则  称 r是 G的一个活前缀  ，表明产生式 A→ β 的 右部 β 已出现在栈顶  A→ β 1β 2的右部子串 β 1已出现在栈顶，期待从输入串中看到 β 2推出的 符号  3. 活前缀不含有句柄的任何符号，此时期望 A→ β 的右部所推出的符号串 R * R 活前缀 ,与句柄 ,与 LR(0)项目  为刻划这种分析过程中的文法 G的每一个产生式的右部符号已有多大一部分被识别 （ 出现在栈顶 ） 的情况 ， 分别用标有圆点的产生式来指示位置。 A→ β ． 刻划产生式 A→ β 的 右部 β 已出现在栈顶 A→ β 1． β 2 刻划 A→ β 1β 2的右部子串 β 1已出现在栈顶 ，期待从输入串中看到 β 2推出的 符号 A→ ． β 刻划没有句柄的任何符号 在栈顶 ， 此时期望 A→ β的右部所推出的符号串  对于 A→ ε 的 LR(0)项目只有 A→ ． 构造识别活前缀的 DFA  LR（ 0） 项目集的闭包Ｃ LOSURE, GO 函数 ， function CLOSURE (I)。 /* I 是项目集 */ { J:= I。 repeat for J 中的每个项目 A  .B  和产生式 B  ， 若 B . 不在 J中 do 将 B . 加到 J中 until 再没有项目加到 J中 return J }。 GO (I,x)=== CLOSURE(J)。 其中 ， I:项目集 ， x: 文法符号 ， J={任何形如 A x.  的项目 |A .x  I} LR（ 0） 项目集的闭包Ｃ LOSURE 若当前处于 A – X•YZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y – u | w . 那么 Y – •u和 Y – •w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况 .  A – X•YZ  Y – •u  Y – •w 这三个项目对应移进归约分析的同一个状态 ,这三个项目构成一个 配置集 , 对应每个配置集，分析表将有一个状态 . LR(0)项目集规范族  计算 LR（ 0） 项目集规范族  C={I0 ， I1 , ... In }  Procedure itemsets(G’)。  Begin C := { CLOSURE ({S’.S})}  Repeat  For C 中每一项目集 I和每一文法符号 x  Do if GO(I,x) 非空且不属于 C  Then 把 GO(I,x) 放入 C中  Until C 不再增大  End。  例：文法 G:  （ 0） S`→E (1) E→aA (2) E→bB  (3) A→cA (4) A→d (5) B→cB  (7) B→d  LR(0) 项目集规范族（ 识别 G的活前缀的 DFA)： I0: S`→ ． E I1: S`→E ． I2: E→a ． A  E→ ． aA A→.cA  E→ ． bB A→ ． d   I3: E→b ． B I4: A→c .A I5: B→ ． cB A→ ． cA B→c ． B B→ ． d A → .d B→ ． cB B→ ． d I6: I7: I8: E→aA ． E→bB ． A→cA ． I9: B→cB ． I10: A→d ． I11: B→cB ． LR(0)分析表的构造  假定 C={I0, I1,…… ， In}， 令每个项目集 Ik的下标 k 为分析器的一个状态 ， 因此 ， G` 的 LR(0)分析表含有状态 0， 1， …… ， n。 令那个含有项目 S`→ ． S的 Ik的下标 k为初态。 ACTION和 GOTO可按如下方法构造： 187。 若项目 A→ α ． aβ 属于 Ik且 GO (Ik, a)= Ij, a为终结符 ， 则置 ACTION[k, a]为 “ 把状态 j和符号 a移进栈 ” ， 简记为“ sj”。 187。 若项目 A→ α ． 属于 Ik, 那么 ， 对任何终结符 a, 置ACTION[k, a]为 “ 用产生式 A→ α 进行规约 ” ， 简记为“ rj”。 其中 ， 假定 A→ α 为文法 G`的第 j个产生式； 187。 若项目 S`→S ． 属于 Ik, 则置 ACTION[k, ]为 “ 接受 ” ， 简记为 “ acc”。 187。 若 GO (Ik, A)= Ij, A为非终结符 ， 则置 GOTO(k, A)=j。 187。 分析表中凡不能用规则 1至 4填入信息的空白格均置上 “ 出错标志 ”。  按上述算法构造的含有 ACTION和 GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法 G的一张 LR(0)表。 具有 LR(0)表的文法 G称为一个 LR（ 0） 文法。  LR(0)文法是无二义的。 ACTION GOTO a c b d E A B 0 S2 S3 1 1 acc 2 S4 S10。