推导与语法树

学习目标

通过本集的学习，你将能够：

• 理解最左推导和最右推导
• 学会构建语法树
• 认识歧义性问题

1. 推导

1.1 什么是推导？

推导是从开始符号出发，不断替换非终结符，直到得到终结符串的过程。

文法：
E → E + E | E * E | (E) | id

推导 id + id * id：
E ⇒ E + E
  ⇒ id + E
  ⇒ id + E * E
  ⇒ id + id * E
  ⇒ id + id * id

1.2 最左推导

每次替换最左边的非终结符：

最左推导：
E ⇒ E + E
  ⇒ id + E      (替换左边的E)
  ⇒ id + E * E  (替换左边的E)
  ⇒ id + id * E (替换左边的E)
  ⇒ id + id * id

1.3 最右推导

每次替换最右边的非终结符：

最右推导：
E ⇒ E + E
  ⇒ E + E * E  (替换右边的E)
  ⇒ E + E * id (替换右边的E)
  ⇒ E + id * id (替换右边的E)
  ⇒ id + id * id

2. 语法树

2.1 什么是语法树？

语法树用树形结构表示推导过程。

id + id * id 的语法树：

        E
       /|\
      / | \
     E  +  E
     |    /|\
     id  / | \
        E  *  E
        |     |
        id    id

2.2 语法树的特点

• 根节点是开始符号
• 内部节点是非终结符
• 叶节点是终结符
• 从左到右的叶节点就是句子

3. 歧义性

3.1 什么是歧义？

如果一个句子有两棵不同的语法树，这个文法就是歧义的。

id + id * id 的歧义：

树1（先乘后加）：
        E
       /|\
      / | \
     E  +  E
     |    /|\
     id  / | \
        E  *  E
        |     |
        id    id

树2（先加后乘）：
        E
       /|\
      / | \
     E  *  E
    /|\    |
   / | \   id
  E  +  E
  |     |
  id    id

3.2 消除歧义

通过引入优先级和结合性来消除歧义：

消除歧义后的文法：
E → E + T | T
T → T * F | F
F → (E) | id

这样 id + id * id 只有一棵语法树

4. 实用案例

4.1 案例1：构建语法树

句子：(id + id) * id

语法树：
        E
        |
        T
       /|\
      / | \
     T  *  F
     |     |
     F     id
     |
    ( E )
      /|\
     / | \
    E  +  T
    |     |
    T     F
    |     |
    F     id
    |
    id

4.2 案例2：识别歧义

文法：
S → if E then S | if E then S else S | other

句子：
if E1 then if E2 then S1 else S2

这是歧义的，可以有两种理解：
1. if E1 then (if E2 then S1 else S2)
2. (if E1 then if E2 then S1) else S2

5. 自测问题

1. 什么是最左推导？
2. 什么是语法树？
3. 什么是歧义文法？
4. 如何消除歧义？
5. 为什么需要消除歧义？

6. 下集预告

下一集我们将学习BNF表示法！

参考资料

• 《编译原理》（龙书）
• 《现代编译原理》（虎书）