Skip to content

Chapter 4: Abstract Syntax

Parser 只判断句子是否属于某个语言，而编译器需要建立 abstract syntax tree，进行语义分析，生成 IR

4.1 Semantic Action

Semantic Action in Recursive Descent

  • 在递归下降的 parser 里，语义分析是 parser 函数的返回值或副作用（或者兼有）
  • 语义值的类型可以定义（union）alt text
  • 消除左递归后，只有右边的操作数，把左操作数传给右边alt text
  • 具体实现：保持一个 semantics values 的栈，reduce 时 pop 出相应的值

4.2 Abstract Parse Trees

上一节中，直接在 Yacc parser 里写语义分析难 read & maintain，只能按 parse 的顺序分析

最好先生成 parser tree，语义分析时遍历，将二者分开

解耦，可以先使用再声明

Parse Tree

Concrete parse tree (syntax):

  • one leaf for each token
  • one internal node for each grammar rule
  • 问题：有些节点不需要，太依赖语法了，耦合度高

Abstract syntax（不是用来 parsing 的）

  • 包含短语结构 alt text

Position

  • 有的编译器词法、语法、语义分析同时进行，记录 current pos
  • 有的编译器（Yacc）分三轮进行，需要记录中间符号的位置

Chapter 5: Semantic Analysis

语法分析的局限性：无法检测下面的错误 alt text

Semantic Analysis（语法分析）的作用

  • 变量使用需要先声明
  • 变量的类型是否正确（表达式、函数调用）
  • 生成 IR

Symbol Tables

Symbol Tables 也被称为 environment

  • Binding - 符号与类型进行绑定 e.g. a -> int
  • environment - binding 的集合

alt text

  • 进入新的作用域，新的同名变量会覆盖之前的
  • 离开作用域后，binding 会结束

符号表需要的操作接口

  • insert
  • lookup
  • beginScope
  • endScope

不同语言的多个符号表（如多个类）

alt text

Implement

命令式

  • 修改旧的环境
  • 维护一个全局 stack，在离开环境时 undo
  • 需要高效查找 - hash
  • 轻松删除 - hash table with external chaining（插到链表头）

alt text

函数式

  • 开个新的 environment
  • 全部复制太耗时耗空间
  • 用二分搜索树实现（字符串比较）
  • 进入新环境只需要复制根节点alt text

字符串比较耗时，转换成 symbol(int 值比较)

Type Checking

Recursive Declarations

相互调用的情况：f call g，g call f

  • First pass - gathers information about the header
  • Second pass - processes the bodies