《编译原理与技术》练习题 9
练习 5
5.1 设文法G5.10[E]为 E → E+T | E-T | T T → T*F | T/F | F F → F↑P | P P → (E) | i
求以下句型的短语、直接短语、素短语、句柄和最左素短语： （1）E-T/F+i （2）E+F/T-P↑i （3）T*(T-i)+P （4）(i+i)/i-i
5.2 根据下列优先关系矩阵计算其优先函数，并说明优先函数是否存在。
5.3 对于文法G5.11[S] S → (R) | a | b R → T T → S; T | S
（1）计算G5.11 [S]的FIRSTTV和LASTTV；
（2）构造G5.11 [S]的优先关系表，并说明G5.11 [S]是否为算符优先文法； （3）计算G5.11 [S]的优先函数。
5.4 对于文法G5.12 [S] S → S;G | G G → G(T) | H H → a | (S) T → T+S | S
《编译原理与技术》练习题 10
（1）构造G5.12 [S]的算符优先关系表，并判断G5.12 [S]是否为算符优先文法； （2）给出句型a(T+S);H;S的短语、直接短语、句柄、素短语和最左素短语； （3）分别给出(a+a)和a;(a+a)的分析过程，并说明它们是否为G5.12 [S]的句子； （4）给出（3）中输入串的最右推导，分别说明它们是否为G5.12 [S]的句子； （5）从（3）和（4）说明算符优先分析的优缺点。
5.5 对于文法G5.13[P] P → LAd | cd L → c A→ aP | P | a
请证明它不存在优先函数。 5.6 给定文法G5.14 [S] S →AS | b A → SA | a
（1）构造它的LR(0)的项集；
（2）构造识别该文法所有活前缀的DFA；
（3）这个文法是SLR(1)吗？若是，构造出它的SLR(1)分析表。
5.7 给定文法G5.15[S] S →AS | ? A → aA | b
（1）构造它的LR(1)文法；
（2）构造识别该文法所有活前缀的DFA； （3）构造出它的SR(1)分析表； （4）给出字符串abab$的分析过程。 5.8 若有定义二进制数的文法G5.16[D] D → L . L | L L → LB | B B → 0 | 1
（1） 通过构造该文法的无冲突的分析表来说明它是哪类LR文法; （2） 给出输入串101.010的分析过程。 5.9 给定文法G5.17[S]
《编译原理与技术》练习题 11
S → L = R| R L → *R | id R → L
（1）构造它的LR(0)的项集； （2）构造它的LR(0)项集规范族； （3）构造识别该文法所有活前缀的DFA；
（4）该文法是SLR(1)、LR(1)以及LALAR(1)？构造相应的分析表。 5.10 对于文法G5.18[S] S → A A → Ab | bBa B → aAc | aAb | a
（1）证明它是SLR(1)文法，但不是LR(0)文法； （2）证明所有SLR(1)文法都是LR(1)文法。 5.11 证明文法G5.19[M] M → N
N → Qa | bQc | dc | bda Q → D
是LALR(1)文法，但不是SLR(1)文法。 5.12 证明文法G5.20[S] S → aAa | aBb | bAb | bBa A → c B → c
是LR(1)文法，但不是LALR(1)文法。 5.13 对于文法G5.21[S] S → AaAb | BbBa A → ? B → ?
（1）证明它是LL(1)文法，但不是SLR(1)文法； （2）证明所有LL(1)文法都是LR(1)文法。
5.14 对于下列各个文法，判断它是哪类最简单的LR文法，并构造相应的分析表。
《编译原理与技术》练习题 12
（1） （2）
A → AA + | AA* | a S → AB
A → aBa | ? B → bAb | ? （3）
S → D; B | B
D → d | ? B → B; a | a| ? （4）
S → D; B | B
D → d | ? B → B; a | a| ? （5）
S → (SR | a
R → . SR | ) （6）
S → UTa | Tb
T → S | Sc | d U → US | e
5.15 命题演算的文法G5.22[B]
B → B and B | B or B | not B | (B) | true | false | b 是二义性文法。
（1）为句子b and b or true构造两个不同的最右推导，以此说明该文法是二义的。 （2）为它写一个等价的非二义性文法。
（3）给出无二义性规则，构造出LR(0)分析表，并给出句子b and b or true的分析过程。