写出文法G(E):E->i|E+E|E*E|(E)的最左推导和最右推导,画出对应的语法树并说明该文法是否具有二义性
时间: 2024-12-12 13:18:53 浏览: 3
表示依据文法进行的变换-第二章编译原理高级语言及其文法2
首先,让我们分析给出的文法 G(E),它描述的是一个简单的数学表达式的结构:
G(E): E -> i | E + E | E * E | (E)
- "i" 表示数字0(常量项)
- "+" 和 "*" 表示加法和乘法操作
- "()" 表示函数括号
**最左推导(Leftmost Derivation)**:
1. E -> i (初始)
2. E -> E + i 或 E * i 或 (E)
3. E -> (E) + i 或 (E) * i 或 ((E))
...
4. E -> (E1 + E2) 或 (E1 * E2) 或 ((E1))(递归)
**最右推导(Rightmost Derivation)**:
1. i -> E (结束)
2. E -> E + i 或 E * i 或 (E)
...
3. E -> E1 + E2 或 E1 * E2 或 (E1) (从左到右组合操作符和子表达式)
**语法树示例**:
对于表达式 "(i + (i * i))" 的最右推导,其语法树可以如下所示:
```
E
/ \
+ *
/ \ / \
i ( i i )
```
**是否存在二义性**:
由于这个文法中所有的非终结符都只出现在最右边的组合位置,比如 "E -> E + E"、"E -> E * E" 和 "E -> (E)",所以它是一个确定的无二义文法(确定性),不存在二义性。
阅读全文