MENU

【编译原理】4、语义分析

June 1, 2020 • Read: 109 • 编程之路,编译原理

编译原理目录
1、词法分析
2、语法分析(重点)
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化

四、语义分析

语义分析任务: 抽象语法树 => 语义分析器 => 中间代码

语义分析也称为类型检查、 上下文相关分析。负责检查程序(抽象语法树)的上下文相关的属性,这是具体语言相关的,典型的情况包括:变量在使用前先进行声明、每个表达式都有合适的类型、函数调用和函数的定义一致 等等…

程序语言的语义

  • 传统上,大部分的程序设计语言都采用自然语言来表达程序语言的语义。例如,对于+运算:要求左右操作数都必须是整型数。
  • 编译器的实现者必须对语言中的语义规定有全面的理解。主要的挑战是如何能够正确高效的实现

接下来的内容,将讨论涉及的主要问题解决方案

4.1 语义检查

以 C-- 为例

4.1.1 类型检查算法:

文法:

E -> n
   | true
   | false
   | E + E
   | E && E

举例:

// 类型合法的程序:
3+4
false && true
// 类型不合法的程序:
3 + true
true + false
// 对这个语言,语义分析的任务是:对给定的一个表达式e,写一个函数
type check(e);
// 返回表达式e的类型;若类型不合法,则报错。

算法:

enum type {INT, BOOL};
enum type check_exp (Exp_t e)
  switch(e->kind)
    case EXP_INT: return INT;
    case EXP_TRUE: return BOOL;
    case EXP_FALSE: return BOOL;
    case EXP_ADD:
      t1 = check_exp (e->left);
      t2 = check_exp (e->right);
      if (t1!=INT || t2!=INT)
        error (“type mismatch”);
      else return INT;
    case EXP_AND:
      t1 = check_exp (e->left);
      t2 = check_exp (e->right);
      if ( (t1!=EXP_TRUE && t1!=EXP_FALSE) || (t2!=EXP_TRUE && t2!=EXP_FALSE) )
        error (“type mismatch”);
      else return BOOL;

示例1: $3+4$

算法执行流程: +作为参数传进去,匹配case EXP_ADDt1 = check_exp(3) = 3,同理t2 = 4,return INT,+的位置上接收到一个INT

示例2: $3+(4+true)$

算法执行流程:+作为参数传进去,匹配case EXP_ADDt1 = 3t2 = check_exp(+),t2调用的函数中,匹配case EXP_ADDt1 = 4, t2 = truet2 != INT报错。

4.1.2 变量声明的处理

文法:

P -> D E
D -> T id ; D
   |
T -> int
   | bool
E -> n
   | id
   | true
   | false
   | E + E
   | E && E

举例:

// 类型合法的程序:
int x;
x+4
// 类型合法的程序:
bool y;
false && y
// 类型不合法的程序:
x + 3
// 类型不合法的程序:
int x;
x + false

算法:

enum type {INT, BOOL};
Table_t table; // 符号表 <key, value>, 在这里<id, type>
 
enum type check_prog (Dec_t d, Exp_t e)
  table = check_dec (d)
  return check_exp (e)
 
Table_t check_dec (Dec_t d)
  foreach (T id ∈ d)
    table_enter (table, id, T)
 
enum type check_exp (Exp_t e)
  switch (e->kind)
    case EXP_ID:
    t = Table_lookup (table, id)
    if (id not exist)
      error (“id not found”)
    else return t

示例:

4.2 符号表

  • 用来存储程序中的变量相关信息:类型、作用域、访问控制信息等等。
  • 必须非常高效,程序中的变量规模会很大。

4.2.1 符号表的接口

#ifndef TABLE_H
#define TABLE_H
typedef … Table_t; // 符号表的数据结构
// 新建一个符号表
Table_t Table_new ();
// 符号表的插入
void Table_enter (Table_t, Key_t, Value_t);
// 符号表的查找
Value_t Table_lookup (Table_t, Key_t);
#endif

4.2.2 符号表的典型数据结构

// 符号表是典型的字典结构:
symbolTable: key -> value
// 一种简单的数据结构的定义(概念上的):
typedef char *key;
typedef struct value{
    Type_t type;
    Scope_t scope;
    … // 必要的其他字段
} value;
变量映射typescope...
xINT0...
yBOOL1...
............

4.2.3 符号表的高效实现

  • 为了高效,可以使用哈希表等数据结构来实现符号表,查找是O(1)时间。
  • 为了节约空间,也可以使用红黑树等平衡树,查找是O(logN)时间。

4.2.4 作用域 —— 符号表处理作用域的方法

方法1:一张表的方法

  • 进入作用域时, 插入元素
  • 退出作用域时, 删除元素

方法2:采用符号表构成的栈

  • 进入作用域时, 插入新的符号表
  • 退出作用域时, 删除栈顶符号表

4.2.5 名字空间 —— 用符号表处理名字空间

变量名、结构体名、标号名存在名称相同时,需要对这些名字进行处理。

  • 每个名字空间用一个表来处理。
  • 以C语言为例,有不同的名字空间:变量、结构体、标签、标号等等,可以每类定义一张符号表。

4.3 其它问题

  • 类型相容性?
  • 错误诊断?
  • 代码翻译?

4.3.1 类型相等

  • 类型检查问题往往归结为判断两个类型是否相等t1==t2?在实际的语言中,这往往是个需要谨慎处理的复杂问题
  • 示例1: 名字相等vs结构相等

    • 对采用名字相等的语言,可直接比较
    • 对采用结构相等的语言,需要递归比较各个域
  • 示例2: 面向对象的继承,子类赋值给父类

    • 需要维护类型间的继承关系

4.3.2 错误诊断

  • 要给出尽可能准确的错误信息
  • 要给出尽可能多的错误信息

    • 从错误中进行恢复
  • 要给出尽可能准确的出错位置

    • 程序代码的位置信息要从前端保留并传递过来

4.3.3 代码翻译

  • 现代的编译器中的语义分析模块,除了做语义分析外,还要负责生成中间代码或目标代码。
  • 代码生成的过程也同样是对树的某种遍历
  • 因此语义分析模块往往是编译器中最庞大也最复杂的模块
- - - 结束 - - -
  • 文章标题:【编译原理】4、语义分析
  • 文章链接:https://blog.canye365.cn/archives/309.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021