ANTLR3完全参考指南读书笔记[06]

时间：2022-07-29 02:17:36

前言

这段时间在公司忙的跟狗似的，但忙的是没多少技术含量的活儿。
终于将AST IR和tree grammar过了一遍，计划明天写完这部分的读书笔记。
 
内容
1 内部表示AST构建
2 树文法
 
 
1 内部表示AST构建
内部表示(intermediate form, IR)的引入理由
分治策略，通常翻译程序语言的工作无法在单一步骤内完成，将其划分为一系列相互关联的步骤，如识别token、填充数据结构(符号表等)、提交输出；
有do one thing, do one thing well和decouple的含义。
一个典型的案例：解析变量引用，一遍识别变量token、一遍解析引用效率比较低，考虑识别过程中生成压缩后的输入(IR)，在识别后再遍历效率明显比两遍遍历高。
与解析树对应，IR可以是较之简化的抽象语法树AST。
 
AST应该具有的特性
记录有意义的输入token、以二维树结构编码、已被计算机识别和导航
为记述方便，采用串行AST标记： 
^(root ^(child1 leaf1 leaf2) child2)
 
虚构节点(imaginary node)的引入
语言构造不仅是表达式，它还可以表示语句等高层抽象，Parr建议采用伪机器指令表示这类高级抽象表示的操作，如定义一个变量^(VARDEF int i)；
识别器已经识别出标点符号，而标点符号在表示语言构造的高层抽象上几乎没什么用，故AST中不包含标点符号。
虚构节点可以表示可选但是识别过程中未发现(缺失)的子树
sample
文法规则 
forStat : 'for' '(' decl? ';' expr? ';' expr? ')' slit;

输入for(int i=0;;i++){...}的部分AST:

 ^(FOR ^(VARDEF int i 0) EXPR ^(++ i))
 
ANTLR的AST实现
不限制AST节点和树结构的具体Java类型和实现，但要求必须指定或实现TreeAdaptor。
ANTLR生成的parser可以构建树，树parser可以用TreeAdaptor遍历该树。
TreeAdaptor作为树节点/结构工厂和树导航工具。
树节点的默认实现类型是Object，所以也可以将Token作为树节点。
提供了默认树节点实现CommonTree。
对于虚拟节点，parser使用该虚拟节点对应的Token类型创建CommonToken对象，加入到树中。
CommonTreeAdaptor创建的CommonTree对象实现了接口Tree。CommonTree关于Tree的通用实现包含在BaseTree中，BaseTree不包含用户数据。
Tree接口:
Tree getChild(int i);
int getChildCount();
void addTree(Tree t);
boolean isNil();

TreeAdaptor的实例见代码//TreeAdaptor编程示例

 
ANTLR的AST实现机制
带上机制实现者的帽子，内容暂略。
 
使用AST构建操作符
步骤:
(1)开启output=AST选项开关
(2)用!后缀标识不想纳入AST的Token
(3)用^后缀标识作为AST子树根节点的Token
是在识别过程中还是识别后修改树结构？在识别过程中！
左结合和右结合运算符
2 samples
expr : INT ('+'^ INT)*;//左结合
输入:1+2+3 
解析: INT '+'^ INT '+'^ INT
AST:^('+' ^('+' 1 2) 3)
pow : INT ('^'^ pow)?;//右结合
输入:1^2^3
解析: INT '^'^ (INT '^'^ INT)
AST: ^('^' 1 ^('^' 2 3))
 
 
使用重写规则(rewrite rules)构建AST
推荐方式，标记:
rule : <<alt1>> -> <<build-this-form-alt1>>
     | <<alt2>> -> <<build-this-form-alt2>>
     ...
     | <<altn>> -> <<build-this-form-altn>>
     ;

重写规则是描述如何生成树的文法，Parr列出了重写机制常用的场景

(1)忽略输入元素
sample:
stat : 'break' ';' -> 'break' ;
expr : '(' expr ')' -> expr
     | INT    -> INT
     ;

(2)输入元素重排序

sample:
decl : 'var' ID ':' type -> type ID;

(3)将某输入元素作为其他元素的根节点

sample:
stat : 'return' expr ';' -> ^('return' expr);
decl : 'var' ID ':' type -> ^('var' type ID);//与默认机制一致

(4)添加虚构节点

 sample:
decl :type ID ';' -> ^(VARDEF type ID);
forLoopConditional
  : expression -> ^(EXPR expression)
  | -> EXPR //需添加此虚构节点，否则会造成信息丢失，压缩的IR不能过分压缩！
  ;

(5)收集输入元素一起提交

sample:
list : ID (',' ID)* -> ID+ ;
formalArgs : formalArg (',' formalArg)* -> formalArg+
  |
  ;
decl : 'int' ID (',' ID)* -> ^('int' ID+);
compilationUnit : packageDef? importDef* typeDef+
-> ^(UNIT packageDef? importDef* typeDef+)
;

(6)复制节点和树

sample:
dup : INT -> INT INT;
decl : 'int' ID (',' ID)* -> ^('int' ID)+ ;
decl : type ID (',' ID)* -> ^(type ID)+ ;
decl : modifier? type ID (',' ID)* -> ^(type modifier? ID)+ ;

(7)运行时选择树结构：语义谓词

sample:
variableDefinition : modifiers types ID ('=' expression)? ';'
                     -> {inMethod}? ^(VARIABLE ID modifier* expression?)
                     ->  ^(FIELD ID modifier* expression?)
                     ;
a[int which] : ID INT -> {which==1}? ID
             -> {which==2}? INT
             ->
             ;
(8)重写规则中引用标签($)
sample:
forStat : 'for' '(' decl? ';' cond=expr? ';' iter=expr? ')' slist
          -> ^('for' decl? ^(CONDITION $cond)? ^(ITERATE $iter)?)
;

(9)用任意动作创建节点

sample:
a : INT -> {new CommonTree(new CommonToken(FLOAT, $INT.text+".0"));} ;
typeDefinition : modifiers! classDefinition[$modifiers.tree]
      | modifiers! iterfaceDefinition[$modifiers.tree]
      ;
classDefinition[CommonTree mod] ://parser规则的参数是CommonTree
      'class' ID ('extend' sup=typename)?
      ('implements' i+=typename (',' i+=typename)*)?
      '{'
      (variableDefinition|methodDefinition|constructorDefiniton)*
      '}'
      -> ^('class' ID {$mod} ^('extends $sup)? ^('implements' $i+)?//这里$i+是汇总列表，对应多个子节点
      variableDefinition* methodDefinition* constructorDefiniton*)
;

(10)重写规则元素的基数

EBNF操作符? * +
这里^(VARDEF atom+), ('int' ID)+的'+'相应的含义是什么？
^(VARDEF atom+)中VARDEF是根节点，所有atom作为其子节点；
('int' ID)+中构建多个以'int'为根节点，ID为其子节点的'森林'(其实还是有个nil根节点的)
总结: 闭包操作符+构建n个节点或树，至于它会不会复制同样的节点，不用关心
 
下面这种情况，只有在?肯定为1时才会产生子树
intValue : expr? -> ^(EXPR expr)? ;

(11)子规则中的重写规则

sample:
ifStat : 'if' '(' equalityExpression ')' s1=statement
       ('else' s2=statement -> ^('if' ^(EXPR equalityExpression) $s1 $s2)
       |          -> ^('if' ^(EXPR equalityExpression) $s1)
       )
       ;
decl : type
     (ID '=' INT -> ^(DECL_WITH_INT type ID INT)
     |ID     -> ^(DECL type ID)
     )
     ;

(12)在重写规则中引用之前规则生成的AST

sample:
expr : (INT -> INT ('+' i=INT -> ^('+' $expr $i))* ;

其部分AST: ^('+' $expr 3)

(13)从世界Token中获得虚构节点
虚构节点中没有行、列和Token在stream中的索引信息，报告错误和恢复时需要这些信息
sample:
compoundStatement : lp='{' statement* '}' -> ^(SLIST[$lp] statement*) ;

(14)结合重写规则与自动默认的AST构造

sample:
primary : INT | FLOAT | '(' expression ')' -> expression ;

 

2 树文法
树文法(tree grammar)描述了AST的结构信息。
由tree grammar生成的tree parser接收一维的节点流，其中包含标识子树开始和结束的UP/DOWN虚构节点。
树文法的结构：
tree grammar
options {
tokenVocab=;
ASTLabelType=CommonTree;
}
运行示例(C-)
C-语言支持变量和函数定义，只有两种类型:int和char。
语句支持for语句、函数调用、赋值、嵌套代码块和空语句(用;表示)。
表达式支持条件、+、×和()表达式。
下面是C-程序的一个例子：
char c;
int x;
int foo(int y, char d){
    int i;
    ; i!=; i=i+){
        x=;
    y=;
    }
}
C-翻译的目标：指出定义了那些类型变量和函数
展示步骤：(a)生成AST的parser文法；(b)描述AST结构的tree文法
 
(a)生成AST的parser文法
(a.1)文法见代码//combined grammar: CMinus
(a.2)用命令生成CMinusLexer.java、CMinusParser.java、CMinus.tokens：
java -classpath antlr-3.5-complete.jar org.antlr.Tool CMinus.g
(a.3)解析生成的AST结构验证代码见代码//生成AST的combined文法的解析器结果验证程序
输出： 
(VAR char c) (VAR int x) (FUNC int foo (ARG int y) (ARG char d) (SLIT (VAR int i) (for (= i 0) (!= i 3) (= i (+ i 1)) (SLIT (= x 3) (= y 5)))))
 
注意尽量不要使用antlrworks在output目录中生成代码，直接用IDE环境中用的jar包直接执行(a.2)
 
(b)描述AST结构的tree文法
(b.1)见代码//tree grammar: CMiusWalker
(b.2)用命令生成CMiusWalker.java、CMiusWalker.tokens：
java -classpath antlr-3.5-complete.jar org.antlr.Tool CMinus.g CMiusWalker.g

(b.3)生成的tree解析器验证代码见代码//tree解析器结果验证程序

输出：...
define char c
define int x
define int i
define int foo()
省略部分为DOT代码，将其拷贝到ast.dot文件中，安装graphviz后执行命令：
dot ast.dot -Tpng -o ast.png

生成结果见下图

ANTLR3完全参考指南读书笔记[06]
graphviz生成的AST
 
 
 
 
代码
因3.5版本的ANTLR不支持中文、甚至包括注释，文法中中文注释是为说明用途等后添加上去的。
 
//TreeAdaptor编程示例
public class TreeAdaptorDemo {

public static void main(String[] args) {
// 定义虚构Token类型
int LIST = 1;
int ID = 2;
TreeAdaptor adaptor = new CommonTreeAdaptor();
// CommonTree root = (CommonTree) adaptor.nil();
CommonTree root = (CommonTree) adaptor.create(LIST, "LIST");
root.addChild((CommonTree) adaptor.create(ID, "x"));
root.addChild((CommonTree) adaptor.create(ID, "y"));
root.addChild((CommonTree) adaptor.create(ID, "z"));

System.out.println(root.toStringTree());
}
}

//combined grammar: CMinus

grammar CMinus;
options {output=AST;}

tokens { //用于生成AST中虚构节点的Token
VAR;FUNC;ARG;SLIST;
}

program : declaration+
;

declaration
: variable
| function
;

variable: type ID ';' -> ^(VAR type ID);

type : 'int'|'char';

function: type ID '(' (formalParameter (',' formalParameter)*)? ')' block
-> ^(FUNC type ID formalParameter* block)
;

formalParameter
: type ID -> ^(ARG type ID)
;
block : lb='{' variable* stat* '}' -> ^(SLIST[$lb, "SLIT"] variable* stat*)
;
stat : forStat
| expr ';'!
| assignStat ';'!
| ';'!
;
forStat : 'for' '(' init=assignStat ';' expr ';' inc=assignStat ')' block
-> ^('for' $init expr $inc block)
;
assignStat
: ID '=' expr -> ^('=' ID expr)
;
expr : condExpr;
condExpr: aexpr (('=='^|'!='^) aexpr)?;
aexpr : mexpr ('+'^ mexpr)*;
mexpr : atom ('*'^ atom)*;
atom : ID
| INT
| '('! expr ')'!
;

ID  : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;

INT : '0'..'9'+
    ;

WS  :   ( ' '| '\t'| '\r'| '\n') {$channel=HIDDEN;}
    ;
//生成AST的combined文法的解析器结果验证程序
public class ParserTest {

public static void main(String[] args) throws Exception {
InputStream is = new FileInputStream(new File("D:/workspace/maven/antlrv3/language/CMinus.test"));
// create a CharStream that reads from standard input
// ANTLRInputStream input = new ANTLRInputStream(System.in);
ANTLRInputStream input = new ANTLRInputStream(is);

// create a lexer that feeds off of input CharStream
CMinusLexer lexer = new CMinusLexer(input);

// create a buffer of tokens pulled from the lexer
CommonTokenStream tokens = new CommonTokenStream(lexer);

// create a parser that feeds off the tokens buffer
CMinusParser parser = new CMinusParser(tokens);
// begin parsing at rule program to get its return tree
CMinusParser.program_return program = parser.program();

CommonTree tree = (CommonTree) program.getTree();
System.out.println(tree.toStringTree());
System.out.println(tree.toString());// 仅显示root
}

}

//tree grammar: CMiusWalker

tree grammar CMiusWalker;
options {tokenVocab=CMinus; ASTLabelType=CommonTree;}

program : declaration+
;

declaration
: variable
| function
;

variable: ^(VAR type ID) {System.out.println("define "+$type.text +" "+ $ID.text);}
;

type : 'int'|'char';

function: ^(FUNC type ID formalParameter* block) {System.out.println("define " +$type.text + " " +$ID.text + "()");}
;

formalParameter
: ^(ARG type ID)
;
block : ^(SLIST variable* stat*)
;
stat : forStat
| expr
| assignStat
;
forStat : ^('for' assignStat expr assignStat block)
;
assignStat
: ^('=' ID expr)
;
expr : ^('==' expr expr)
| ^('!=' expr expr)
| ^('+' expr expr)
| ^('*' expr expr)
| ID
| INT
;
//tree解析器结果验证程序
public class FinalTest {

public static void main(String[] args) throws Exception {
InputStream is = new FileInputStream(new File("D:/workspace/maven/antlrv3/language/CMinus.test"));
// create a CharStream that reads from standard input
// ANTLRInputStream input = new ANTLRInputStream(System.in);
ANTLRInputStream input = new ANTLRInputStream(is);

// create a lexer that feeds off of input CharStream
CMinusLexer lexer = new CMinusLexer(input);

// create a buffer of tokens pulled from the lexer
CommonTokenStream tokens = new CommonTokenStream(lexer);

// create a parser that feeds off the tokens buffer
CMinusParser parser = new CMinusParser(tokens);
// begin parsing at rule program to get its return tree
CMinusParser.program_return program = parser.program();

CommonTree tree = (CommonTree) program.getTree();
System.out.println(tree.toStringTree());

// DOT tree generate
DOTTreeGenerator dotTreeGenerator = new DOTTreeGenerator();
StringTemplate st = dotTreeGenerator.toDOT(tree);
System.out.println(st);

CommonTreeNodeStream nodes = new CommonTreeNodeStream(tree);
nodes.setTokenStream(tokens);
CMiusWalker walker = new CMiusWalker(nodes);
walker.program();

}

相关文章