3.3语法分析-分析树与二义性

前端

• 源程序–<词法分析器–记号–语法分析–抽象语法树–语义分析器>–中间表示

语法分析器的任务

• 记号流和语言的语法规则–>语法分析器–>语法树

推导与分析树

S -> N V N  (名词 动词 名词)
N -> s      // 羊
   | t      // 老虎
   | g      // 草
   | w      // 水
V -> e      // 吃
   | d      // 喝
           

• 在推导的过程中有多条路可以走，不同的路可能导致不同的结果
• 如果选错路径就要回溯重新走另一条路径，如果走完所有路径都还没有匹配到那就报错，如果中间有匹配到，就算语法正确

分析树

• 推导可以表达成树状结构
  • 和推导所用的顺序无关（最左、最右、其他）
• 特点：
  • 树中的每个内部节点代表非终结符
  • 每个叶节点代表终结符
  • 每一步推导代表如何从双亲节点生成它的直接孩子节点

表达式的例子

E -> num
   | id
   | E + E
   | E * E
           

• 推导：3+4*5
  • 左推导

E -> E + E
  ->  + E
  ->  + E * E
  ->  +  * E
  ->  +  * 
           

• 右推导

E -> E * E
  -> E + E * E
  ->  + E * E
  ->  +  * E
  ->  +  * 
           

• 根据左右推导的结果可以看出，同样的文法推导出来的结果有所不同，其中涉及优先级问题

二义性文法

• 给定文法G，如果存在句子S,它有两棵不同的分析树，那么称G是二义性文法
• 从编译器角度，二义性文法存在问题：
  • 同一个程序会有不同的含义
  • 因此程序运行的结果不是唯一的
• 解决方案：文法的重写

表达式文法的重写

E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id
           

• 推导：3+4*5

E -> E + T
  -> T + T
  -> F + T
  ->  + T
  ->  + T * F
  ->  + F * F
  ->  +  * F
  ->  +  * 
           

• 推导：3+4+5

E -> E + T
  -> E + T + T
  -> T + T + T
  -> F + T + T
  ->  + T + T
  ->  + F + T
  ->  +  + T
  ->  +  + F
  ->  +  +