Garden of John

三 语义分析 属性文法

5分钟阅读

编译原理

其实是龙书第五章的内容

今天 文法。另一种。之前已经看过了两种文法。regular expression 词法分析；context-free grammar 语法分析 。分词 建树。

问题：用什么样的文法刻画语言的语义？语义分析的两大任务：类型检查 符号检查 上下文相关的信息。无法用之前的文法表达。

36岁图灵奖 knuth the youngest

属性文法(attribute grammar)：为上下文无关赋予语义。 类似面向对象，对象所有的属性。终结符和非终结符赋予属性。meaning semantics. 关心这个对象的什么属性赋予什么属性，语法树的节点。你关心什么什么就是语义。

语法分析树的计算问题 action.动作。使用动作计算属性

综合属性

继承属性

antlr4 例子 迷你计算器 交互式

offline离线方式计算属性值：已有语法分析树

在语法分析过程中实现属性文法。计算属性的动作嵌入到语法分析过程。

 
grammar ExprCalcAG;
 
  
 
@head{
 
packages ag.expr
 
import java.util.*;
 
}
 
  
 
prog: state+;
 
state: expr {System.out.println($expr.val);}
 
| ID '=' expr {memory.put($ID.text,$expr.val);}
 
;
 
  
 
expr returns [int val]
 
: l=expr op=('*'|'/') r=expr {$val=eval($l.val,$r.val,$op.type);}
 
| l= expr op =('+'|'-')r=expr {$val=eval($l.val,$r.val,$op.type);}
 
|'(' expr ')' {$val=$expr.val;}
 
| ID {$val=memory.getOrDefault($ID.text,0);}
 
| INT {$val=$INT.int;}
 
;
 
ADD: '+';
 
SUB: '-';

区分左右表达式 l r, 为表达式赋值。从递归角度 加返回值 intreturns [int val]

  • 花括号放在最右端，要算的value要依赖于左右都处理过了。

  • 每个规则加上相应的动作。

  • 这里的hash map memory 怎么来 ？ eval方法？

  • 定义成员，希望只在parser里有一份 在lexer中没有

 
@parser::members{
 
Map<String,Integer> memory = new HashMap<>();
 
int eval(int left,int right,int op){
 
switch(op){
 
case ADD: return left + right;
 
.
 
.
 
.
 
default: return 0;
 
}
 
}
 
  
 
}

通过 return +花括号计算属性值；在文法当中设置属性添加动作计算属性做成属性文法。

类型声明文法

D→T L declar type list

列表声明，需要把大T的信息传给L

  • 另两种依赖关系，兄弟依赖 右左t l, l l1子对父依赖。

  • 父依赖子 返回值。另两种依赖 参数 传递信息。

  • antlr4如何支持？ 属性计算的动作

  • type的text传递给vars

 
decl:type vars[$type.text] ;
 
type: 'int'
 
| 'float'
 
;
 
vars[String typeStr]
 
: vars[$typeStr] ',' ID {System.out.println($ID.text+":"+$typeStr);}
 
| ID {System.out.println($ID.text+":"+$typeStr);}
 
;

  • id 已经知道了类型信息。

  • 嵌入java代码。

  • 但是写完了是错误的 左递归的处理不了。

  • 改为迭代的形式。没有左递归。stackoverflow

  • vars[String typeStr]: ID{System.out.println($ID.text+":"+ $typeStr);}(',' ID{System.out.println($ID.text+":"+ $typeStr);})*

语法制导定义(Syntax-Directed Definition; SDD)

SDD 是一个上下文无关文法和属性及规则的结合

  • 在属性文法的基础上给每个终结符或非终结符 赋予属性再赋予规则 规则对应动作 描述属性间的依赖关系。

注意的点：

  1. SDD唯一确定了语法分析树上每个非终结符节点的属性值。

  2. SDD没有规定以什么方式什么顺序计算这些属性值。右侧的语义规则仅仅描述了属性之间的依赖关系，理解成方程组。先算哪一个后算哪一个 没有确定。解耦。

注释语法分析树：标注属性值的语法分析树

综合属性 synthesized attribute

节点N上的综合属性只能通过N的子节点或N本身的属性来定义

S属性定义 S-attributed defintion

如果一个SDD的每个属性都是综合属性，则它是S属性定义。

父节点依赖于子节点，S属性刻画了属性实例之间自底向上的信息流动

关系图谱