目录

Compiler3_语法制导翻译&AST

语法制导翻译(Syntax Directed Translation)的任务

解析输入的字符串时,在特定位置执行指定的动作。

基本思想

https://blog-1256556944.file.myqcloud.com/compiler/direct.png

抽象语法树

分析树与抽象语法树

https://blog-1256556944.file.myqcloud.com/compiler/parsetree.png

分析树:

  • 编码了句子的推导过程
  • 但是包含很多不必要的信息,节点占用存储空间
  • 需要知道那些信息是重要的
    • 对于表达式而言,只需要知道运算符和运算数
      • 优先级,结合性等已经在语法分析部分处理掉了
    • 对于语句,函数等其他构造而言也一样
      • 比如,编译器不关心赋值符号是=还是:=

具体语法和抽象语法

  • 具体语法是语法分析器使用的语法

    • 必须适合于语法分析,如各种分隔符,消除左递归,提取公因子等
  • 抽象语法是用来表达语法结构的内部表示

    • 现代编译器一般采用抽象语法作为前端(词法/语法分析器)和后端(代码生成)的接口
  • 早期的编译器有的不采用抽象语法树数据结构

    • 直接在语法制导翻译中生成代码
  • 现代编译器一般都采用抽象语法树作为语法分析器的输出

    • 更好的系统的支持
    • 简化编译器的设计

抽象语法树的自动生成

  • 在语法动作中,加入生成语法树的代码片段
    • 片段一般是语法树的构造函数
  • 在产生式规约的时候,会自底向上构造整棵数
    • 从叶子到根

https://blog-1256556944.file.myqcloud.com/compiler/ast.png

  • 抽象语法树是编译器前端和后端的接口
    • 程序一旦被转换成抽象语法树,则源代码即被丢弃
    • 后续阶段只处理抽象语法树
  • 所以抽象语法树必须编码足够多的源代码信息
    • 例如,语法结构所在位置(文件、行号、列号等)

ps:我觉得自动生成方面LL比LR好,自顶向下更符合人类认知,代表生成器:antlr