【习题答案】第05章 自底向上的语法分析.pdf

《编译原理》课后练习参考答案 第05 章 自底向上的语法分析 课后练习参考答案 第05 章 自底向上的语法分析 1. S→aS|bS|a (1) 构造该文法的LR(0)项目集规范族。 (2) 构造识别该文法所产生的活前缀的DFA 。 (3) 构造其SLR 分析表，并判断该文法是否是SLR(1)文法。 【解】 构造LR(0)项目集规范族，有两种方法：一种是利用有限自动机来构造，另一种是利用函 数CLOSURE 和GO 来构造。本题采取第2 种方法，通过计算函数CLOSURE 和GO 得到 法的LR(0)项目集规范族，而GO 函数则把LR(0)项目集规范族连成一个识别该文法所产生的 活前缀的DFA 。 (1) 将文法G(S)拓广为G(S’) ： (0)S’→S (1)S→aS (2)S→bS (3)S→a 构造该文法的LR(0)项目集规范族： I0=CLOSURE({S →·S})={S’ →·S, S→·aS, S→·bS, S→·a} I =GO( I , a)=CLOSURE({S→a·S , S→a·})={S→a·S , S→a· , S→·aS, S→·bS, S→·a } 1 0 I =GO(I , b)=CLOSURE({S→b·S })={ S→b·S, S→·aS, S→·bS, S→·a } 2 0 I =GO(I , S)=CLOSURE({S’ →S·})={ S’ →S·} 3 0 GO(I , a)=CLOSURE({S→a·S , S→a·})=I 1 1 GO(I , b)=CLOSURE({S→b·S})=I 2 2 I =GO(I , S)=CLOSURE({S→aS·})={S→aS·} 4 1 GO(I , a)= CLOSURE({S→a·S , S→a·})=I 2 1 GO(I , b)= CLOSURE({S→b·S})=I 2 2 I =GO(I , S)=CLOSURE({S→bS·})={ S→bS·} 5 2 所以，项目集I ，I ，I ，I ，I 和I 构成了该文法的LR(0)项目集规范族。 0 1 2 3 4 5 共6 页，第1 页 《编译原理》课后练习参考答案 第05 章 自底向上的语法分析 (2) 我们用GO 函数把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA 如下 图所示。 (3) 构造其SLR 分析表。