解析器在解析语句时需要触发某些动作。phase-action对表示语法和语言应用之间的接口。

有listener和visitor两种构造方式。listener负责响应parse-tree walker触发的entry和exit事件。visitor除此以外还负责控制如何遍历解析树,必须显式调用函数来访问子节点。

7.1 将嵌入式的动作进化到listener

grammar PropertyFile;
file : {«start file»} prop+ {«finish file»} ;
prop : ID '=' STRING '\n' {«process property»} ;
ID : [a-z]+ ;
STRING : '"' .*? '"' ;

{}中的是嵌入的Java代码,非常严重的耦合。

更好一点的办法是在语法文件里写函数原型,再继承生成的解析器:

grammar PropertyFile;
@members {
    void startFile() { } // blank implementations
    void finishFile() { }
    void defineProperty(Token name, Token value) { } 
}
file : {startFile();} prop+ {finishFile();} ;
prop : ID '=' STRING '\n' {defineProperty($ID, $STRING)} ;
ID : [a-z]+ ;
STRING : '"' .*? '"' ;

继承:

class PropertyFilePrinter extends PropertyFileParser {
    void defineProperty(Token name, Token value) {
	    System.out.println(name.getText()+"="+value.getText());
	}
}

class PropertyFileLoader extends PropertyFileParser {
    Map<String,String> props = new OrderedHashMap<String, String>();
    void defineProperty(Token name, Token value) {
    	props.put(name.getText(), value.getText());
	}
}

语法文件中仍然有部分Java代码。

7.2 Listener

public static class PropertyFileLoader extends PropertyFileBaseListener {
    Map<String,String> props = new OrderedHashMap<String, String>();
    public void exitProp(PropertyFileParser.PropContext ctx) {
        String id = ctx.ID().getText(); // prop : ID '=' STRING '\n' ;
        String value = ctx.STRING().getText();
        props.put(id, value);
} }
public class App{
    public static void main(String[] argv){
        ParseTreeWalker walker = new ParseTreeWalker();
        // create listener then feed to walker
        PropertyFileLoader loader = new PropertyFileLoader();
        walker.walk(loader, tree); // walk parse tree
        System.out.println(loader.props); // print results
    }
}

7.3 Visitor

public class PropertyFileBaseVisitor<T> extends AbstractParseTreeVisitor<T> implements PropertyFileVisitor<T>
{
    @Override public T visitFile(PropertyFileParser.FileContext ctx) { ... }
    @Override public T visitProp(PropertyFileParser.PropContext ctx) { ... } 
}

public static class PropertyFileVisitor extends PropertyFileBaseVisitor<Void> {
    Map<String,String> props = new OrderedHashMap<String, String>();
    public Void visitProp(PropertyFileParser.PropContext ctx) {
        String id = ctx.ID().getText(); // prop : ID '=' STRING '\n' ;
        String value = ctx.STRING().getText();
        props.put(id, value);
        return null; // Java says must return something even when Void
    } 
}

public class App{
	public static void main(String[] argv){
        PropertyFileVisitor loader = new PropertyFileVisitor();
        loader.visit(tree);
        System.out.println(loader.props); // print results
    }
}

7.4 规则标签

原始语法不用标签:

grammar Expr;
s	: e ;
e	: e op=MULT e // MULT is '*'
	| e op=ADD e // ADD is '+'
	| INT
	;

只能生成enterEexitE两个方法:

public interface ExprListener extends ParseTreeListener {
    void enterE(ExprParser.EContext ctx);
    void exitE(ExprParser.EContext ctx);
    ...
}

需要判断+*

public void exitE(ExprParser.EContext ctx) {
    if ( ctx.getChildCount()==3 ) { // operations have 3 children
        int left = values.get(ctx.e(0));
        int right = values.get(ctx.e(1));
        if ( ctx.op.getType()==ExprParser.MULT ) {
	        values.put(ctx, left * right);
        }
        else {
            values.put(ctx, left + right);
        } 
    }
    else {
    	values.put(ctx, values.get(ctx.getChild(0))); // an INT
    } 
}

添加标签后:

e	: e MULT e # Mult
    | e ADD e # Add
    | INT # Int
    ;

会根据每个标签生成一个方法:

public interface LExprListener extends ParseTreeListener {
    void enterMult(LExprParser.MultContext ctx);
    void exitMult(LExprParser.MultContext ctx);
    void enterAdd(LExprParser.AddContext ctx);
    void exitAdd(LExprParser.AddContext ctx);
    void enterInt(LExprParser.IntContext ctx);
    void exitInt(LExprParser.IntContext ctx);
    ...
}

7.5事件函数之间共享信息

用Visitor遍历解析树

public static class EvalVisitor extends LExprBaseVisitor<Integer> {
    public Integer visitMult(LExprParser.MultContext ctx) {
	    return visit(ctx.e(0)) * visit(ctx.e(1));
    }
    public Integer visitAdd(LExprParser.AddContext ctx) {
    	return visit(ctx.e(0)) + visit(ctx.e(1));
    }
    public Integer visitInt(LExprParser.IntContext ctx) {
	    return Integer.valueOf(ctx.INT().getText());
    } 
}

public class App{
    public static void main(String[] argv){
        EvalVisitor evalVisitor = new EvalVisitor();
        int result = evalVisitor.visit(tree);
        System.out.println("visitor result = "+result);
    }
}

用栈模拟返回值,在Listener中使用

public static class Evaluator extends LExprBaseListener {
    Stack<Integer> stack = new Stack<Integer>();
    public void exitMult(LExprParser.MultContext ctx) {
        int right = stack.pop();
        int left = stack.pop();
        stack.push( left * right );
    }
    public void exitAdd(LExprParser.AddContext ctx) {
        int right = stack.pop();
        int left = stack.pop();
        stack.push(left + right);
    }
    public void exitInt(LExprParser.IntContext ctx) {
	    stack.push( Integer.valueOf(ctx.INT().getText()) );
    } 
}

标记解析树 tree annotation

简单的方法,直接在解析树中储存结果,在语法文件中写返回值,但是会导致代码耦合:

e returns [int value]
    : e '*' e # Mult
    | e '+' e # Add
    | INT # Int
    ;

更好的方法:

e
	: e MULT e # Mult
    | e ADD e # Add
    | INT # Int
    ;

在Listener中添加一个ParseTreeProperty类型的成员变量,这个是比较通用的方法。

public static class EvaluatorWithProps extends LExprBaseListener {
    /** maps nodes to integers with Map<ParseTree,Integer> */
    ParseTreeProperty<Integer> values = new ParseTreeProperty<Integer>();
    public void setValue(ParseTree node, int value) { values.put(node, value); }
    public int getValue(ParseTree node) { return values.get(node); }
    public void exitInt(LExprParser.IntContext ctx) {
        String intText = ctx.INT().getText(); // INT # Int
        setValue(ctx, Integer.valueOf(intText));
    }
    public void exitAdd(LExprParser.AddContext ctx) {
        int left = getValue(ctx.e(0)); // e '+' e # Add
        int right = getValue(ctx.e(1));
        setValue(ctx, left + right);
    }
    public void exitS(LExprParser.SContext ctx) {
        setValue(ctx, getValue(ctx.e())); // like: int s() { return e(); }
    }
}
public class App{
    public static void main(String[] args){
        ParseTreeWalker walker = new ParseTreeWalker();
        EvaluatorWithProps evalProp = new EvaluatorWithProps();
        walker.walk(evalProp, tree);
        System.out.println("properties result = " +evalProp.getValue(tree));
    }
}

Python不需要ParseTreeProperty对象,直接dict就行了,非常方便。

三种共享方法比较

  • 原生Java调用栈:使用Visitor,需要显式调用,比较麻烦。
  • 栈数据结构:必须把函数调用转换成栈,逻辑比较复杂,修改困难。
  • 标记:比较通用的方法。