内容发布更新时间 : 2024/5/24 14:02:00星期一 下面是文章的全部内容请认真阅读。

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