2. 考虑文法 G[S]: S → (T) | | a T → | S
消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归： S→(T) | | a T→′ T′→′| ε 提取公共左因子： S→(T) | ′ S′→ | ε T→′ T′→′| ε
3. 试为表达式 ()*((10)+8) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * +
4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： (A 5 / 81 { (A ≥ 1) 1; (A ≤ D) 2; }。 解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)： 100 (j<,102) 101 (,113) 102 (j<,104) 103 (,113) 104 (,1,106) 105 (,108) 106 (+, C, 1, C) 107 (,112) 108 (j≤,110) 109 (,112) 110 (+, A, 2, A) 111 (,108) 6 / 81 112 (,100) 113 5. 已知文法 G[S] 为 S → ，试证明文法 G[S] 为二义文法。 证明： 由文法G[S]：S→，对句子对应的两棵语法树为： 因此，文法G[S]为二义文法。 五.计算题（10分） 已知文法 > ε 7 / 81 判断该文法是否是 (1) 文法，若是构造相应分析表，并对输入串 给出分析过程。 解：增加一个非终结符后，产生原文法的增广文法有： S'->A >ε 下 面 构 造 它 的 (0) 项 目 集 规 范 族 为 ： 从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是(0)文法。对于I0来说有：(A)∩{a}={}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是(1) 8 / 81
