编译原理(5) 语义分析

2023-08-09 14:53:19 # NJU # 编译原理

语义分析

本节课代码见https://github.com/courses-at-nju-by-hfwei/2022-compilers-coding

一、类型系统与类型检查

1. 类型系统

1.1 JS 糟糕的类型系统

2. 类型检查

2.1 类型检查

2.2 类型转换

不要写这样的代码!!!

Conversion @ cppreference.com

2.3 类型综合

根据子表达式的类型确定表达式的类型

2.4 类型推导

根据某语言结构的使用方式确定表达式的类型

3. 数组类型文法

3.1 语法分析树

3.2 Listener

3.3 ParseTreeProperty

通过 ANTLR4 提供的 ParseTreeProperty<> 来存储 basicType 与 arrayType

private final ParseTreeProperty<Type> arrayTypeProperty = new ParseTreeProperty<>();
private final ParseTreeProperty<Type> basicTypeProperty = new ParseTreeProperty<>();

赋值语句类型检查，详见代码

4. 类型声明文法

与数组类似，需要保存最左侧的类型

5. 类型系统

https://youtu.be/SWTWkYbcWU0

二、属性文法

1. 属性文法

$\textcolor{red}{\textbf{属性文法}\text{(Attribute Grammar)}:} 为上下文无关文法赋予\textcolor{blue}{\textbf{语义}}$

终结符或非终结符上的属性就可以看作语义

属性分为两类:

综合属性

继承属性

1.1 关键问题

如何基于上下文无关文法做上下文相关分析?

上下文相关文法分析复杂度太高

关键: 语法分析树上的有序信息流动

通过 DFS 来遍历

2. 计算属性值

2.1 Offline 方式

但因为要先建立语法分析树，实际上遍历了两遍，效率并不高

2.2 语法分析过程中

在语法分析过程中实现属性文法

基本思想: 一个动作在它左边的所有文法符号都处理过之后立刻执行

时机(Timing)

语义动作嵌入在什么地方? 这决定了何时执行语义动作。

2.3 实现迷你计算器

expr 的 value 只依赖于子节点的 value

@header {
package ag;
import java.util.*;
}

@parser::members {
  Map<String, Integer> memory = new HashMap<>();

  int eval(int left, int right, int op) {
    switch (op) {
      case ADD : return left + right;
      case SUB : return left - right;
      case MUL : return left * right;
      case DIV : return left / right;
      default : return 0;
    }
  }
}

prog : stat* EOF ;

stat : expr         { System.out.println($expr.val); }
     | ID '=' expr  { memory.put($ID.text, $expr.val); }  // $ID.text -> ID.getText()
     ;

expr returns [int val]
    : left = expr op = ('*' | '/') right = expr     { $val = eval($left.val, $right.val, $op.type); }
    | left = expr op = ('+' | '-') right = expr     { $val = eval($left.val, $right.val, $op.type); }
    | '(' expr ')'                                  { $val = $expr.val; }
    | ID                                            { String id = $ID.text; $val = memory.getOrDefault(id, 0); }
    | INT                                           { $val = $INT.int; }
    ;