1、第07章 LR 分析第 7 章 LR 分析第1题 已知文法 AaAd|aAb|判断该文法是否是 SLR(1)文法，若是构造相应分析表，并对输入串 ab#给出分析过程。答案： 文法：AaAd|aAb|拓广文法为 G，增加产生式 SA 若产生式排序为：0 S A1 A aAd2 A aAb3 A 由产生式知：First (S ) = ,a First (A ) = ,a Follow(S ) = # Follow(A ) = d,b,#G的 LR(0)项目集族及识别活前缀的 DFA 如下图所示：在 I0 中：A .aAd 和 A .aAb 为移进项目，A .为归约项目，存在移进-归约冲突，因此所给
2、文法 不是 LR(0)文法。在 I0、I2 中：Follow(A) a= d，b，# a=所以在 I0、I2 中的移进-归约冲突可以由 Follow 集解决，所以 G 是 SLR(1)文法。 构造的 SLR(1)分析表如下：题目 1 的 SLR(1)分析表状态（State）ActionGotoadb#A0S2r3r3r311acc2S2r3r3r333S4S54r1r1r15r2r2r2题目 1 对输入串 ab#的分析过程状态栈（state stack）文法符号栈剩余输入串（input left）动作（action）0#ab#.Shift0 2#ab#.Reduce by :A 0 2 3#a
3、Ab#.Shift0 2 3 5#aAb#.Reduce by :A aAb0 1#A#.分析成功，说明输入串 ab 是文法的句子。第2题 若有定义二进制数的文法如下： SLL|LLLB|B B0|1(1) 试为该文法构造 LR 分析表，并说明属哪类 LR 分析表。 (2) 给出输入串 101.110 的分析过程。答案： 文法：SL.L|L LLB|B B0|1拓广文法为 G，增加产生式 SS 若产生式排序为：0 S S1 S L.L2 S L3 L LB4 L B5 B 06 B 1 由产生式知：First (S ) = 0,1 First (S ) = 0,1 First (L ) = 0
4、,1 First (B ) = 0,1 Follow(S ) = # Follow(S ) = # Follow(L ) = .,0,1,# Follow(B ) = .,0,1,#G的 LR(0)项目集族及识别活前缀的 DFA 如下图所示：在 I2 中：B .0 和 B .1 为移进项目，S L.为归约项目，存在移进-归约冲突，因此所给文法不 是 LR(0)文法。在 I2、I8 中：Follow(s) 0，1= # 0，1=所以在 I2 、I8 中的移进-归约冲突可以由 Follow 集解决，所以 G 是 SLR(1)文法。 构造的 SLR(1)分析表如下：题目 2 的 SLR(1)分析表状
5、态（State）ActionGoto 0 1 #S L B012345678S4 S5acc S6 S4 S5 r2 r4 r4 r4 r4 r5 r5 r5 r5 r6 r6 r6 r6S4 S5r3 r3 r3 r3S4 S5 r11 2 3.7.8 3.7题目 2 对输入串 101.110#的分析过程状态栈（state stack）文法符号栈剩余输入串（input left）动作（action）00 50 30 20 2 40 2 70 20 2 50 2 70 20 2 60 2 6 50 2 6 30 2 6 80 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40
6、2 6 8 70 1#1#B#L#L0#LB#L#L1#LB#L#L.#L.1#L.B#L.L#L.L1#L.LB#L.L#L.L0#L.LB#S101.110#.01.110#.01.110#.01.110#.1.110#.1.110#.1.110#.110#.110#.110#.110#.10#.10#.10#.0#.0#.0#.#.#.#.ShiftReduce by :B 1Reduce by :S LB ShiftReduce by :B 0Reduce by :S LB ShiftReduce by :B 1Reduce by :S LB ShiftShiftReduce by :
7、B 1Reduce by :S B ShiftReduce by :B 1Reduce by :S LB ShiftReduce by :B 0Reduce by :S L.L分析成功，说明输入串 101.110 是题目 2 文法的句子。第3题 考虑文法 S A S | bA S A | a(1)构造文法的 LR(0)项目集规范族及相应的 DFA。(2)如果把每一个 LR(0)项目看成一个状态，并从每一个形如 B X的状态出发画一 条标记为 X 的箭弧刀状态 B X，而且从每一个形如 B A的状态出发画标 记为的箭弧到所有形如 A 的状态。这样就得到了一个 NFA。说明这个 NFA 与(a)
8、中的 DFA 是等价的。(3)构造文法的 SLR 分析表。(4)对于输入串 bab，给出 SLR 分析器所作出的动作。 (5)构造文法的 LR(1)分析表和 LALR 分析表。答案： (1)令拓广文法 G为(0) S S (1)S A S (2)S b (3)A S A (4)A a其 LR(0)项目集规范族及识别该文法活前缀的 DFA 如下图所示： FOLLOW(S)=#,a,bFOLLOW(A)=a,bLR(0)项目：(2)显然，对所得的 NFA 求闭包，即得上面的 LR(0)项目集，即 DFA 中的状态。故此 NFA与(a)中 DFA 是等价的。(3)文法的 SLR 分析表如下：状态ac
9、tiongotoab#SA0S4S3121S4S3acc652S4S3723r2r2r24r4r45S4/ r3S3/r3726S4S3657S4 / r1S3 / r1r165因为 I5 中：FOLLOW（A）a，bI7 中：FOLLOW（S）a，b 所以，该文法不是 SLR（1）文法。或者：从分析表中可看出存在歧义，所以不是该文法 SLR（1）文法。 注意：不是 SLR(1)文法就不能构造 SLR(1)分析表，也不能作分析过程。(4)对于输入串 bab，SLR 分析器所作出的动作如下：步骤状态栈符号栈当前字符剩余字符串动作(1)0#bab#移进(2)03#bab#归约 Sb(3)01#Sa
10、b#移进(4)014#Sab#归约 Aa(5)015#SAb#归约 ASA(6)02#Ab#移进(7)023#Ab#归约 Sb(8)027#AS#归约 SAS(9)01#S#接受（在第 5 个动作产生歧义）(5)LR(1)项目集族为： I0 :S S, # S AS, #S b, #S SA, a / bA a, a / bI1 : S S,# A SA, a / bA a, a / bA SA, a / bS AS, a / bS b, a / bI2 : S AS, # S b, #S AS, #A SA, a / bA a, a / bI3 : S b, #I4 : A a, a / b
11、I5 : A SA, a / bS AS, a / b S AS, a / b S b, a/ bA SA, a / bA a, a / bI6 : A SA,a/bA SA, a / bA a, a / bS AS, a / bS b, a / bI7: S b, a / bI8 : S AS, #A SA, a / bA SA, a / bA a, a / bS AS, a / bS b, a / bI9 :S AS, # S AS, # S b, #S SA, a / bA a, a / bI10 :S AS, a/bA SA, a/bA S A, a/b A a, a / b S b,
12、 a/bS AS, a / bI11 :S AS, a/bS b, a/bS AS, a / bA S A, a/bA a, a / bI12 :S SA, a/b S AS, a/b S b, a/bS AS, a / bA S A, a/bA a, a / bI5 状态集中存在“归约移进”冲突，故无法构造 LR(1)分析表，因而也就无 法构造 LALR 分析表。注意：其实是可以构造的，这个题目出得不太严格。因为书上的定义是：根据这种文 法构造的 LR（1）分析表不含多重定义时，称 这样的分析表为 LR（1）分析表，能用 LR（1） 分析表的分析器称为 LR（1）分析器（规范的 LR 分析器
13、），能构造的 LR（1）分析表的文法 称为 LR（1）文法。教材习题：（1）列出这个文法的所有 LR(0)项目（2）按（1）列出的项目构造识别这个文法活前缀的 NFA，把这个 NFA 确定化为 DFA，说明 这个 DFA 的所有状态全体构成这个文法的 LR(0)规范族（3）这个文法是 SLR 的吗？若是，构造出它的 SLR 分析表（4）这个文法是 LALR 或 LR(1)的吗？答：（1）令拓广文法 G为0 S S1 S A S2 S b3 A S A4 A a其 LR(0)项目：(2) 识别这个文法活前缀的 NFA 如上图所示： 确定化为 DFA 如下图所示：（3）因为 I5 中：FOLLOW
14、（A）a，bI7 中：FOLLOW（S）a，b 所以，该文法不是 SLR（1）文法。（4）LR(1)项目集族为： I0 :S S, # S AS, #S b, #S SA, a / bA a, a / bI1 : S S,# A SA, a / bA a, a / bA SA, a / bS AS, a / bS b, a / bI2 : S AS, #S b, #S AS, #A SA, a / bA a, a / bI3 : S b, #I4 : A a, a / bI5 : A SA, a / bS AS, a / b S AS, a / b S b, a/ bA SA, a / bA
15、a, a / bI6 : A SA,a/bA SA, a / bA a, a / bS AS, a / bS b, a / bI7: S b, a / bI8 : S AS, #A SA, a / bA SA, a / bA a, a / bS AS, a / bS b, a / bI9 :S AS, # S AS, # S b, #S SA, a / bA a, a / bI10 :S AS, a/bA SA, a/bA S A, a/bA a, a / bS b, a/bS AS, a / bI11 :S AS, a/bS b, a/bS AS, a / bA S A, a/bA a, a
16、 / bI12 :S SA, a/b S AS, a/b S b, a/bS AS, a / bA S A, a/bA a, a / b因为 I5 状态集中存在“归约移进”冲突，所以不是 LR(1)文法，也不是 LALR 文法。第6题 文法 G=(U,T,S,a,b,c,d,e,P,S) 其中 P 为：SUTa|Tb TS|Sc|d UUS|e(1) 判断 G 是 LR(0)，SLR(1)，LALR(1)还是 LR(1)，说明理由。 (2) 构造相应的分析表。答案： 文法：SUTa|Tb TS|Sc|d UUS|e拓广文法为 G，增加产生式 SS 若产生式排序为：0 S S1 S UTa2 S
17、 Tb3 T S4 T Sc5 T d6 U US7 U e由产生式知：First (S ) = d,e First (S ) = d,e First (U ) = e First (T ) = d,eFollow(S ) = #Follow(S ) = a,b,c,d,e,# Follow(U ) = d,eFollow(T ) = a,bG的 LR(0)项目集族及识别活前缀的 DFA 如下图所示：在 I1 中：S S.为接受项目，T S. 为归约项目，T S.c 为移进项目，存在接受-归约和移进-归 约冲突，因此所给文法不是 LR(0)文法。在 I1 中：Follow(S) Follow(
18、T)= # a ，b= Follow(T) c= a ，b c=在 I8 中：Follow(U) Follow(T) c=d,e a ，b c=所以在 I1 中的接受-归约和移进-归约冲突与 I8 中的移进-归约和归约-归约冲突可以由 Follow 集解决，所以 G 是 SLR(1)文法。构造的 SLR(1)分析表如下：状态（State）ActionGotoabcde#SUT0S5S41231r3r3S6Acc2S5S48273S94r7r75r5r56r4r47S10S98r3r3S6r6r69r2r2r2r2r2r210r1r1r1r1r1r1第8题 证明文法： SA$ ABaBb|DbD
19、a BD是 LR(1)但不是 SLR(1)。(其中$相当于#)答案： 文法：ABaBb|DbDaBD拓广文法为 G，增加产生式 SA 若产生式排序为：0 SA1 A BaBb2 A DbDa3 B 4 D 由产生式知：First (S ) = a,bFirst (A ) = a,bFirst (B ) = First (D ) = Follow(S ) = # Follow(A ) = # Follow(B ) = a,b Follow(D ) = a,bG的 LR(1)项目集族及识别活前缀的 DFA 如下图所示：在 I0 中：B .,a 和 T .，b 为归约项目，但它们的搜索符不同，若当前
20、输入符为 a 时用产生式 B 归约，为 b 时用产生式 D 归约，所以该文法是 LR(1)文法。 若不看搜索符，在 I0 中项目 B .和 T .为归约-归约冲突，而Follow(B ) Follow(D ) = a,b a,b，冲突不能用 Follow 集解决，所以该文法 不是 SLR(1)文法。构造的 LR(1)分析表如下： 题目 4 的 LR(1)分析表StateActionGotoa . b . #A B D0123456789r3 r4.AccS4.S5 r3 r4. S8S9. r1 r21 2 3.67第 16题 给定文法：Sdo S or S|do S|S;S|act (1)
21、构造识别该文法活前缀的 DFA。(2) 该文法是 LR(0)吗?是 SLR(1)吗?说明理由。(3) 若对一些终结符的优先级以及算符的结合规则规定如下：a) or 优先性大于 do;b) ;服从左结合；c) ;优先性大于 do ；d) ;优先性大于 or ；请构造该文法的 LR 分析表,并说明 LR(0)项目集中是否存在冲突和冲突如何解决的。 答案：首先化简文法,用 d 代替 do;用 o 代替 or;用 a 代替 act;文法可写成： SdSoS|dS|S;S|a拓广文法为 G，增加产生式 SS 若产生式排序为：0 S S1 S dSoS2 S dS3 S S;S4 S a由产生式知：Fir
22、st (S ) = d,a First (S ) = d,a Follow(S ) = # Follow(S ) = o,;,#(1)识别该文法活前缀的 DFA 如下图。(2) 该文法不是 LR(0)也不是 SLR(1)因为：在 I5、I6、和 I8 中存在移进-归约冲突，因此所给文法不是 LR(0)文法。 又由于 Follow(S ) = o, ; ,#在 I6、和 I8 中：Follow(S ) ; =o, ; ,# ; =; 在 I5 中：Follow(S ) ; , o =o , ; ,# ; , o =; , o 所以该文法也不是 SLR(1) 文法。此外很容易证明所给文法是二义性的
23、， SSdSoSddSoSSSdSddSoS 因此该文法不可能满足 LR 文法。(3) 若对一些终结符的优先级以及算符的结合规则规定如下：a) or 优先性大于 do;b) ;服从左结合；c) ;优先性大于 do ；d) ;优先性大于 or ；则：在 I5 中：“or 和;优先性都大于 do”，所以遇输入符 o 和; 移进；遇#号归约。 在 I6 中：“; 号服从左结合”，所以遇输入符属于 Follow(S )的都应归约。在 I8 中：“; 号优先性大于 do ”， 所以遇输入符为;号 移进；遇 o 和#号归约。 此外，在 I1 中：接受和移进可以不看成冲突，因为接受只有遇#号。 由以上分析，所有存在的移进-归约冲突可用规定的终结符优先级以及算符的结合规则解决， 所构造的 LR 分析表如下：状态（State）ActionGotodo;a#S0S2S311S4Acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1r4r1附加题问题 1：试判别如下文法是否 LR(0)或 SLR(1)文法:a) 文法 GE: E E + T TT (E) id id E 其中 E,T 为非终结符,其余符号为终结符b) 文法 GS: S Ab ABcA aA aB b其中 S,A,B 为非终结符,其余符号为终结符答案：a) 增加产
