乐者为王

Do one thing, and do it well.

ANTLR 4权威参考读书笔记(30)

有时我们在调试语法时需要ANTLR提供更好的消息提示,为达到这个目的,我们可以改变ANTLR的标准错误报告。

改变和重定向ANTLR错误消息

默认情况下,ANTLR把所有的错误发送给标准错误,但我们可以通过提供ANTLRErrorListener接口的实现来修改目标和内容。该接口有syntaxError()方法可以应用于词法分析器和语法分析器。方法syntaxError()接收各种有关错误的位置以及错误消息的信息。它也接收语法分析器的一个引用,因此我们可以查询关于识别的状态。

例如,这里是一个错误监听器,它打印规则调用栈以及随后的用有问题的记号信息来加强的通常错误消息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static class VerboseListener extends BaseErrorListener {
    @Override
    public void syntaxError(Recognizer<?, ?> recognizer,
                            Object offendingSymbol,
                            int line, int charPositionInLine,
                            String msg,
                            RecognitionException e)
    {
        List<String> stack = ((Parser)recognizer).getRuleInvocationStack();
        Collections.reverse(stack);
        System.err.println("rule stack: "+stack);
        System.err.println("line "+line+":"+charPositionInLine+" at "+
        offendingSymbol+": "+msg);
    }
}

使用这个定义,我们的应用可以很容易地在调用开始规则前给语法分析器添加一个错误监听器。

1
2
3
4
SimpleParser parser = new SimpleParser(tokens);
parser.removeErrorListeners();    // remove ConsoleErrorListener
parser.addErrorListener(new VerboseListener());    // add ours
parser.prog();    // parse as usual

在添加我们自己的错误监听器之前,必须先移除标准的终端错误监听器,否则的话就会得到重复的错误消息。

现在让我们看下包含一个额外类名以及缺少字段名的类定义的错误消息看起来是什么样子:

1
2
compile *.java
run TestE_Listener

以下是包含额外类名以及缺少字段名的类定义:

1
2
3
class T T {
  int ;
}

然后我们就会看到如下错误消息:

1
2
3
4
5
rule stack: [prog, classDef]
line 1:8 at [@2,8:8='T',<9>,1:8]: extraneous input 'T' expecting '{'
rule stack: [prog, classDef, member]
line 2:6 at [@5,18:18=';',<8>,2:6]: no viable alternative at input 'int;'
class T

栈[prog, classDef]指出语法分析器在规则classDef中,且被prog调用。注意,记号信息包含在输入流中的字符位置,这在高亮输入中的错误时是非常有用的。例如,记号[@2,8:8='T',<9>,1:8]指出它是记号流中的第3个记号(索引从0开始),字符范围从8到8,记号类型为9,位于第1行,并且在字符位置8(计数从0开始,且TAB被当作一个字符)。

作为另一个示例,让我们构建一个错误监听器TestE_Listener2.java,它打印带有被下划线强调的有错误的记号的行。

1
2
compile *.java
run TestE_Listener2

输入以下数据:

1
2
3
class T XYZ {
  int ;
}

然后就会看如如下错误信息:

1
2
3
4
5
6
7
line 1:8 extraneous input 'XYZ' expecting '{'
class T XYZ {
        ^^^
line 2:6 no viable alternative at input 'int;'
  int ;
      ^
class T

为了让事情变得更容易,我们将忽略TAB——charPositionInLine不是列号,因为TAB的大小不是统一定义的。这里是一个错误监听器实现,强调输入中的错误位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static class UnderlineListener extends BaseErrorListener {
    public void syntaxError(Recognizer<?, ?> recognizer,
                            Object offendingSymbol,
                            int line, int charPositionInLine,
                            String msg,
                            RecognitionException e) {
        System.err.println("line "+line+":"+charPositionInLine+" "+msg);
        underlineError(recognizer,(Token)offendingSymbol,
        line, charPositionInLine);
    }

    protected void underlineError(Recognizer recognizer,
                                  Token offendingToken, int line,
                                  int charPositionInLine) {
        CommonTokenStream tokens =
            (CommonTokenStream)recognizer.getInputStream();
        String input = tokens.getTokenSource().getInputStream().toString();
        String[] lines = input.split("\n");
        String errorLine = lines[line - 1];
        System.err.println(errorLine);
        for (int i=0; i<charPositionInLine; i++) System.err.print(" ");
        int start = offendingToken.getStartIndex();
        int stop = offendingToken.getStopIndex();
        if ( start>=0 && stop>=0 ) {
            for (int i=start; i<=stop; i++) System.err.print("^");
        }
        System.err.println();
    }
}

关于错误监听器还有一件事需要知道。当语法分析器侦测到一个模棱两可的输入序列时,它会通知错误监听器。默认的错误监听器ConsoleErrorListener实际上不会在终端打印任何东西,也就是说,语法分析器不会通知用户。让我们回顾下能用两种方式匹配输入f();的那段歧义语法。

1
2
3
4
5
6
7
8
9
10
11
12
13
grammar Ambig;

stat: expr ';'    // expression statement
    | ID '(' ')' ';'    // function call statement
    ;

expr: ID '(' ')'
    | INT
    ;

INT : [0-9]+ ;
ID  : [a-zA-Z]+ ;
WS  : [ \t\r\n]+ -> skip ;

如果我们测试这段语法,我们不会看到有关模棱两可的输入的警告。

1
2
3
antlr Ambig.g
compile *.java
grun Ambig stat

然后输入:

1
f();

ANTLR 4权威参考读书笔记(29)

当我们开发一套语法时,会有很多错误要去修复。在完成语法前,生成的语法分析器不会识别所有有效的句子。在这期间,提供有用信息的错误消息帮助我们追踪到语法问题。一旦我们有了一套正确的语法,然后我们就必须处理用户输入的不合语法的句子,或者甚至由其它程序发生故障生成的不合语法的句子。在这两种情况下,语法分析器对不合语法的输入的响应方式是一个需要重点考虑的问题。

在这里,我们将学习被ANTLR生成的语法分析器使用的自动错误报告和恢复策略。

错误展示

描述ANTLR的错误恢复策略的最好方式是观察由它生成的语法分析器对错误输入的响应。让我们看一个类Java语言的语法,它包含带有字段和方法成员的类定义。该方法有简单的语句和表达式。嵌入动作在语法分析器找到元素时就打印它们。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
grammar Simple;

prog: classDef+ ; // match one or more class definitions

classDef
    : 'class' ID '{' member+ '}' // a class has one or more members
      {System.out.println("class "+$ID.text);}
    ;

member
    : 'int' ID ';'    // field definition
      {System.out.println("var "+$ID.text);}
    | 'int' f=ID '(' ID ')' '{' stat '}'    // method definition
      {System.out.println("method: "+$f.text);}
    ;

stat: expr ';'
      {System.out.println("found expr: "+$stat.text);}
    | ID '=' expr ';'
      {System.out.println("found assign: "+$stat.text);}
    ;

expr: INT
    | ID '(' INT ')'
    ;

INT : [0-9]+ ;
ID  : [a-zA-Z]+ ;
WS  : [ \t\r\n]+ -> skip ;

现在,先让我们使用一些有效的输入运行语法分析器,借以观测正常的输出。

1
2
3
antlr Simple.g
compile *.java
grun Simple prog

输入以下数据:

1
class T { int i; }

你就会看到:

1
2
var i
class T

语法分析器没有显示任何错误,它执行打印语句,报告关于变量i和类定义T的正确识别。

接下来,让我们尝试一个带有方法定义的类,该方法含有一个虚假赋值表达式。

1
grun Simple prog -gui

输入测试数据:

1
2
3
class T {
  int f(x) { a = 3 4 5; }
}

然后你就会看到:

1
2
3
line 2:19 mismatched input '4' expecting ';'
method: f
class T

在4记号处,语法分析器没有找到它期待的“;”,所以它报告一个错误。line 2:19指出有问题的标记是在第2行第19列的字符位置(字符位置从0开始)。因为使用了-gui参数,我们可以看到带有高亮错误节点的语法分析树。

在这里,有两个额外的记号,并且语法分析器给出一个不匹配的通用错误消息。如果只有单个的额外记号,语法分析器可能会智能一点,指出它是一个额外的记号。在接下来的运行测试中,有个额外的“;”在类名和类体之间:

1
grun Simple prog

输入如下:

1
class T ; { int i; }

输出结果:

1
2
3
line 1:8 extraneous input ';' expecting '{'
var i
class T

在“;”处语法分析器报告一个错误,但给出了一个稍微翔实的答案,因为它知道下一个记号就是它实际上在寻找的那个。这个特性被称为单个记号删除(single-token deletion),因为语法分析器可以简单地装作额外的记号不存在并继续执行。

同样的,语法分析器可以在侦测到缺少一个记号时做单个记号插入(single-token insertion)。让我们删掉结束的“}”看看会发生什么。

1
grun Simple prog

然后输入:

1
2
class T {
  int f(x) { a = 3; }

结果是:

1
2
3
4
found assign: a=3;
method: f
line 3:0 missing '}' at '<EOF>'
class T

语法分析器报告它不能找到必须的结束记号“}”。

当语法分析器处于决策点时,会出现另一个常见的语法错误,并且剩余的输入与规则或子规则的任何选项都不一致。例如,如果我们忘记字段声明中的变量名,规则member中的选项都不匹配。语法分析器报告没有可行的选项。

1
grun Simple prog

输入以下代码:

1
class T { int ; }

然后结果是:

1
2
line 1:14 no viable alternative at input 'int;'
class T

在“int”和“;”之间没有空格,因为我们在WS()规则中告诉词法分析器skip()。

如果有词法错误,ANTLR也会放出错误消息,指出哪些字符不能匹配为记号。例如,如果我们提交一个完全未知的字符,我们将得到一个记号识别错误。

1
grun Simple prog

输入:

1
class # { int i; }

输出:

1
2
3
4
line 1:6 token recognition error at: '#'
line 1:8 missing ID at '{'
var i
class <missing ID>

因为没有给出有效的类名,单个记号插入机制召唤了“missing ID”名字,以致类名记号是非空值。如果想控制语法分析器如何召唤记号,可以覆盖DefaultErrorStrategy中的getMissingSymbol()。

ANTLR 4权威参考读书笔记(28)

  • scope 作用域

为了阐明Cymbol语法是可复用的,本节中我们将在不做修改的基础上再次使用它,用于构建一个完全不同的应用。不仅如此,我们还会在同样的树上使用两个不同的监听器做两次遍历。

验证程序符号的使用情况

为Cymbol这样的编程语言构建解释器、编译器或者转换器,我们需要验证Cymbol程序是否正确地使用符号(标志符)。接下来,我们将构建一个Cymbol验证器用于检查以下的条件:

  • 可见的变量引用有相应的定义(在作用域内)。
  • 函数引用有相应的定义(函数可以以任何顺序出现)。
  • 变量不作为函数使用。
  • 函数不作为变量使用。

让我们看一下有许多不同引用的Cymbol示例代码,其中有些是无效的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f(int x, float y) {
    g();      // forward reference is ok
    i = 3;    // no declaration for i (error)
    g = 4;    // g is not variable (error)
    return x + y;    // x, y are defined, so no problem
}
void g() {
    int x = 0;
    float y;
    y = 9;    // y is defined
    f();      // backward reference is ok
    z();      // no such function (error)
    y();      // y is not function (error)
    x = f;    // f is not a variable (error)
}

为验证程序中的一切都没问题,根据前面的条件,我们应该打印出函数列表和本地变量以及全局符号列表(函数和全局变量)。更进一步,当我们发现问题时应该给出一个错误。例如,使用上述输入,让我们构建一个称为CheckSymbols的应用。

1
java CheckSymbols vars.cymbol

在执行以上命令后会生成如下输出:

1
2
3
4
5
6
7
8
9
10
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
locals:[x, y]
function<g:tVOID>:[]
globals:[f, g]
line 3:4 no such variable: i
line 4:4 g is not a variable
line 13:4 no such function: z
line 14:4 y is not a function
line 15:8 f is not a variable

实现这类问题的关键是一个被称为符号表的相应的数据结构。我们的应用会把符号存在符号表中,然后通过在符号表中查找符号引用检查它们的正确性。在接下来的部分,我们将大概看一看数据结构看起来像什么,并且使用它去解决手头的验证问题。

符号表中的速成课

语言实现者通常称持有符号的数据结构为符号表。语言的实现决定符号表的结构和复杂性,如果一门语言允许相同的标志符在不同的上下文中指向不同的东西,符号表会将那些符号分组到不同的作用域中。作用域只是一组符号,例如函数的参数列表或变量列表以及在全局作用域内的函数。

符号表自身只是一个符号定义的存储库——它不作任何检查。为了验证代码,我们需要检查表达式中违反我们之前设置的规则的变量和函数引用。符号验证有两个基本操作:定义符号和解决符号。定义一个符号意味着把它添加到一个作用域中。解决一个符号意味着计算出符号指向哪个定义。在某种程度上,解决一个符号意味着找到最近的匹配定义。最近的作用域是最近的封闭作用域。例如,让我们看看另一个Cymbol例子,它在不同的作用域有符号定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
int x;
int y;
void a()
{
    int x;
    x = 1;
    // x resolves to current scope, not x in global scope
    y = 2;
    // y is not found in current scope, but resolves in global
    { int y = x; }
}
void b(int z)
{ }

全局作用域包含变量x和y以及函数a()和b()。函数处于全局作用域,但它们也构成新的作用域用于持有函数的参数,如果有的话。同样嵌套在函数作用域内的是函数本地代码块,它们构成另一个新的作用域。本地变量被约束在嵌套在函数作用域内的本地作用域内。

因为符号x被定义了两次,所以做不到仅把所有标识符都填充进单个集合而没有冲突。这也是作用域出现的原因。我们保留一组作用域,并且一个作用域中的每个标志符只允许有单个定义。我们还保留一个指向父作用域的指针,以便在外层作用域中找到符号定义。这些作用域形成了一棵树。

沿着从任何作用域到根(全局作用域)的路径的所有节点形成一堆作用域。为了找到一个符号的定义,我们从围绕着引用的作用域开始,并沿着作用域树向上遍历,直到找到它的定义。

验证器架构

开始构建验证器前,先让我们思考下大方向和总体策略。我们可以根据关键操作——定义和解决——把问题分解。对于定义,我们需要侦听变量和函数定义事件,然后把符号对象插入围绕着定义的作用域。在函数定义的开始处,我们需要压栈一个新的作用域,然后在函数定义的结尾处把它出栈。

为解决和检查符号引用,我们需要侦听在表达式中的变量和函数名字引用。针对每个引用,我们将验证是否有匹配的定义,以及引用是否正确使用符号。

这似乎很直截了当,但有个并发症:在源码文件中,Cymbol程序可以调用在它之后定义的一个函数。我们称它为前向引用。为支持这个特性,我们需要在语法分析树上执行两次遍历。第一遍,或者阶段,定义包含函数的符号,然后第二遍进行解决。用这种方法,第二遍可以看到文件中的所有函数。以下是用于触发在语法分析树上两次遍历的代码:

1
2
3
4
5
6
ParseTreeWalker walker = new ParseTreeWalker();
DefPhase def = new DefPhase();
walker.walk(def, tree);
// create next phase and feed symbol table info from def to ref phase
RefPhase ref = new RefPhase(def.globals, def.scopes);
walker.walk(ref, tree);

在定义阶段,我们将创建许多作用域。除非我们保持对它们的引用,否则垃圾收集器会回收它们。为了符号表能够度过从定义到解决阶段的转变,我们需要追踪这些作用域。储存它们最合乎逻辑的地方是在语法分析树本身(或者,从技术上讲,使用关联值与树节点的注解映射)。然后引用阶段就可以在它下行语法分析树时很简单地获得当前作用域的指针。与函数和本地块关联的树节点将可以获得它们的作用域的指针。

定义和解决符号

考虑到我们的基本策略,让我们从DefPhase开始构建我们的验证器。这个阶段类需要3个字段:一个全局作用域的引用、一个用于追踪我们创建的作用域的语法分析树注解器,以及一个当前作用域的指针。enterFile()的监听器代码在活动开始时创建全局变量。当活动结束时,exitFile()负责打印结果。

1
2
3
4
5
6
7
8
9
10
11
public class DefPhase extends CymbolBaseListener {
    ParseTreeProperty<Scope> scopes = new ParseTreeProperty<Scope>();
    GlobalScope globals;
    Scope currentScope;    // define symbols in this scope
    public void enterFile(CymbolParser.FileContext ctx) {
        globals = new GlobalScope(null);
        currentScope = globals;
    }
    public void exitFile(CymbolParser.FileContext ctx) {
        System.out.println(globals);
    }

当语法分析器找到函数声明时,应用需要创建一个FunctionSymbol对象。作为一个符号和作为一个包含参数的作用域,FunctionSymbol对象负有双重责任。为把函数作用域嵌套在全局作用域内,我们需要把函数作用域压栈。我们通过设置函数的封闭作用域为当前作用域并重置当前作用域来做到这点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    String name = ctx.ID().getText();
    int typeTokenType = ctx.type().start.getType();
    Symbol.Type type = CheckSymbols.getType(typeTokenType);

    // push new scope by making new one that points to enclosing scope
    FunctionSymbol function = new FunctionSymbol(name, type, currentScope);
    currentScope.define(function);    // Define function in current scope
    saveScope(ctx, function);         // Push: set function's parent to current
    currentScope = function;          // Current scope is now function scope
}

void saveScope(ParserRuleContext ctx, Scope s) {
    scopes.put(ctx, s);
}

方法saveScope()使用函数作用域注解functionDecl规则节点,以便在随后的引用阶段可以获得它。当我们离开函数时就出栈函数作用域,因此当前作用域仍然是全局作用域。

1
2
3
4
public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    System.out.println(currentScope);
    currentScope = currentScope.getEnclosingScope();    // pop scope
}

本地作用域以类似的方式工作。我们在监听器方法enterBlock()中压栈一个作用域,然后在exitBlock()中出栈它。

在处理好作用域和函数定义后,我们就可以开始定义参数和变量。

1
2
3
4
5
6
7
8
9
10
11
12
public void exitFormalParameter(CymbolParser.FormalParameterContext ctx) {
    defineVar(ctx.type(), ctx.ID().getSymbol());
}
public void exitVarDecl(CymbolParser.VarDeclContext ctx) {
    defineVar(ctx.type(), ctx.ID().getSymbol());
}
void defineVar(CymbolParser.TypeContext typeCtx, Token nameToken) {
    int typeTokenType = typeCtx.start.getType();
    Symbol.Type type = CheckSymbols.getType(typeTokenType);
    VariableSymbol var = new VariableSymbol(nameToken.getText(), type);
    currentScope.define(var); // Define symbol in current scope
}

到此,定义阶段已经完成。

为构建引用阶段,让我们将当前作用域设置为从定义阶段传递过来的全局作用域。

1
2
3
4
5
6
7
public RefPhase(GlobalScope globals, ParseTreeProperty<Scope> scopes) {
    this.scopes = scopes;
    this.globals = globals;
}
public void enterFile(CymbolParser.FileContext ctx) {
    currentScope = globals;
}

然后,就像树遍历器触发Cymbol函数和块的进入与退出事件那样,监听器方法通过访问在定义阶段期间存储在树中的值来及时更新currentScope。

1
2
3
4
5
6
7
8
9
10
11
12
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentScope = scopes.get(ctx);
}
public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentScope = currentScope.getEnclosingScope();
}
public void enterBlock(CymbolParser.BlockContext ctx) {
    currentScope = scopes.get(ctx);
}
public void exitBlock(CymbolParser.BlockContext ctx) {
    currentScope = currentScope.getEnclosingScope();
}

随着遍历器的行进恰当地设置作用域,我们可以通过实现变量引用和函数调用的监听器方法解决符号。当遍历器遇到一个变量引用时,它调用exitVar(),该方法使用resolve()试图在当前作用域的符号表中查找变量名。如果resolve()在当前作用域中没有找到符号,它会查找封闭作用域链。如果必要,resolve()将寻找所有方式直到全局作用域。如果找不到一个合适的定义,它会返回null值。如果resolve()找到的符号是一个函数而不是变量,就需要生成一个错误消息。

1
2
3
4
5
6
7
8
9
10
public void exitVar(CymbolParser.VarContext ctx) {
    String name = ctx.ID().getSymbol().getText();
    Symbol var = currentScope.resolve(name);
    if ( var==null ) {
        CheckSymbols.error(ctx.ID().getSymbol(), "no such variable: "+name);
    }
    if ( var instanceof FunctionSymbol ) {
        CheckSymbols.error(ctx.ID().getSymbol(), name+" is not a variable");
    }
}

处理函数调用基本上是相同的,如果不能找到一个定义或找到了一个变量,都需要发出一个错误。

最后,是用来显示早先需要的输出的构建和测试序列:

1
2
3
antlr Cymbol.g
compile *.java
run CheckSymbols vars.cymbol

输出结果如下所示:

1
2
3
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
...

ANTLR 4权威参考读书笔记(27)

前面我们主要处理的是数据,今天我们就来做些编程语言方面的事情。

生成调用关系图

软件很难编写和维护,这就是为什么我们试图构建工具去提高我们的生产力和工作效率。例如,在过去的十年里,我们已经看到测试框架、代码覆盖工具和代码分析器的激增,也很高心看到类层次结构的可视化树,以及大部分开发环境支持这个功能。其中有种可视化被称为调用图,它由函数作为节点,并且函数调用作为节点间的有向边。

这本节中,我们将使用Cymbol语法构建一个调用图生成器。考虑以下函数和函数调用集:

1
2
3
4
5
6
7
8
9
10
11
int main() { fact(); a(); }
float fact(int n) {
    print(n);
    if (n == 0) then return 1;
    return n * fact(n - 1);
}
void a() { int x = b(); if false then {c(); d();} }
void b() { c(); }
void c() { b(); }
void d() { }
void e() { }

我们将会把它可视化成如下的调用图:

可视化的好处是人眼可以很容易地挑出偏差。例如,e()节点是个孤立节点,它意味着没有函数调用它,因此它是一段死代码。一目了然,我们找到一个可以被丢弃的函数。我们还可以通过在图中寻找像fact() -> fact()和b() -> c() -> d()这样的循环非常容易地检测递归。

为了可视化调用图,我们需要读入一段Cymol程序和创建一个DOT文件。例如,以下是我们需要为t.cymbol生成的DOT文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
digraph G {
    ranksep=.25;
    edge [arrowsize=.5]
    node [shape=circle, fontname="ArialNarrow",
    fontsize=12, fixedsize=true, height=.45];
    main; fact; a; b; c; d; e;
    main -> fact;
    main -> a;
    fact -> print;
    fact -> fact;
    a -> b;
    a -> c;
    a -> d;
    b -> c;
    c -> b;
}

上面的输出包括样本设置描述,例如ranksep=.25;和一列节点和边。为抓住孤立节点,我们需要确保为每个函数名生成节点定义,即使它没有出边和入边。否则它将不会出现在图中。注意在节点定义行末尾的e节点。

1
main; fact; a; b; c; d; e;

我们的策略很简单,当语法分析器找到一个函数声明时,应用会把当前函数名添加到一个列表,并且设置一个字段称为currentFunctionName。当语法分析器看到一个函数调用,应用会记录从currentFunctionName到被调用函数名的一条边。

开始之前,让我们给Cymbol.g中的一些规则选项打上标签,以便获得更精确的监听器方法。

1
2
3
4
5
6
7
8
9
10
11
expr: ID '(' exprList? ')'    # Call
    | expr '[' expr ']'       # Index
    | '-' expr                # Negate
    | '!' expr                # Not
    | expr '*' expr           # Mult
    | expr ('+'|'-') expr     # AddSub
    | expr '==' expr          # Equal
    | ID                      # Var
    | INT                     # Int
    | '(' expr ')'            # Parens
    ;

然后,作为语言应用的基础,把所有图相关的东西封装进一个类。

1
2
3
4
5
6
7
static class Graph {
    // I'm using org.antlr.v4.runtime.misc: OrderedHashSet, MultiMap
    Set<String> nodes = new OrderedHashSet<String>();    // list of functions
    MultiMap<String, String> edges = new MultiMap<String, String>();    // caller->callee
    public void edge(String source, String target) {
        edges.map(source, target);
    }

从节点和边的集合中,我们可以在类Graph的toDOT()中使用一些Java代码转储出适当的DOT代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String toDOT() {
    StringBuilder buf = new StringBuilder();
    buf.append("digraph G {\n");
    buf.append("    ranksep=.25;\n");
    buf.append("    edge [arrowsize=.5]\n");
    buf.append("    node [shape=circle, fontname=\"ArialNarrow\",\n");
    buf.append("    fontsize=12, fixedsize=true, height=.45];\n");
    buf.append("    ");
    for (String node : nodes) {    // print all nodes first
        buf.append(node);
        buf.append("; ");
    }
    buf.append("\n");
    for (String src : edges.keySet()) {
        for (String trg : edges.get(src)) {
            buf.append("    ");
            buf.append(src);
            buf.append(" -> ");
            buf.append(trg);
            buf.append(";\n");
        }
    }
    buf.append("}\n");
    return buf.toString();
}

现在我们要做的是使用监听器填满这些数据结构,监听器需要两个字段用于记录。

1
2
3
static class FunctionListener extends CymbolBaseListener {
    Graph graph = new Graph();
    String currentFunctionName = null;

然后应用只需要监听两个事件。首先,在语法分析器发现函数声明时记录当前的函数名。

1
2
3
4
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentFunctionName = ctx.ID().getText();
    graph.nodes.add(currentFunctionName);
}

其次,当语法分析器侦测到函数调用时,应用需要记录从当前函数到被调用函数的一条边。

1
2
3
4
5
public void exitCall(CymbolParser.CallContext ctx) {
    String funcName = ctx.ID().getText();
    // map current function to the callee
    graph.edge(currentFunctionName, funcName);
}

注意,函数调用不能隐藏在嵌套代码块或诸如a()这样的声明中。

1
void a() { int x = b(); if false then {c(); d();} }

无论什么时候,只要树遍历器发现函数调用就触发监听器方法exitCall()。

通过语法分析树和类FunctionListener,我们可以启动带有监听器的一个遍历器去产生输出。

1
2
3
4
ParseTreeWalker walker = new ParseTreeWalker();
FunctionListener collector = new FunctionListener();
walker.walk(collector, tree);
System.out.println(collector.graph.toString())

在转储DOT字符串前,该代码会打印出函数和边的列表。

1
2
3
antlr Cymbol.g
compile *.java
run CallGraph t.cymbol

以下是部分输出结果:

1
2
3
4
5
6
edges: {main=[fact, a], fact=[print, fact], a=[b, c, d], b=[c], c=[b]},
functions: [main, fact, a, b, c, d, e]
digraph G {
ranksep=.25;
edge [arrowsize=.5]
...

协议分析器的威力

英文原文:http://arstechnica.com/information-technology/2016/09/the-power-of-protocol-analyzers/

问题发生在错综复杂的网络世界里。但要在一时激动之下确定一种新型问题的确切原因变得有些冒险。在这种情况下,当Google-fu耗尽的时候甚至其他能干的工程师也可能会被迫去依赖试错法。

幸运的是,有个秘密武器等待乐意的工程师去部署——协议分析器。该工具允许你明确地确定几乎任何错误的根源,给你提供在底层协议上自我学习的能力。现在唯一的问题是,许多工程师因为(毫无根据的)恐惧而完全回避它。

什么是协议分析器?

协议分析器,或者数据包嗅探器,是一个用于拦截通信量,存储它们,并以一个已解码的、人类可读的状态呈现它们的工具。现代协议分析器比如Wireshark甚至可以靠自己发现基本的问题,然后使用捕获的数据执行统计分析。

不理会特性,数据包嗅探器都以基本相同的方式工作。它们把自己插入到网络堆栈中,把所有通信量复制到一个缓冲区或文件。大部分还会将网络驱动置于“混杂模式”,该模式从根本上说允许这些工具取回所有进入网络堆栈的通信量,而不是只采集前往系统本身的通信量。

协议分析仪如何帮助

在很多情况下,解决一个困难的网络问题的最难部分是找到和理解问题的根源。这种困难的部分源于这样的事实,你对大多数问题使用的工具不是正确的对底层问题的工具。

如果你是一个系统管理员,很有可能你经常用于数据采集的工具是某种日志和错误消息。通常,这些都是解释工具。这些实体试图把原始数据总结为对非开发者或非工程师有意义的东西。因为解释工具是从应用层的视角提供问题的汇总数据,它们往往不能帮助你解决底层的问题。

例如,一条事件日志消息可以告诉你应用程序无法连接到服务器。它甚至可以告诉你根本原因是超时。但这条消息不大可能告诉你超时是由一个黑洞路由器丢弃一个大帧引起。它不能,因为事件日志消息服务不知道错误为何发生。为了使工具知道那个,它需要预测(不解释)这个非常问题,在MTU稳步减少的情况下发送数据包,直到一个通过。如果一个事件日志消息服务早就被编写好要做那件事,从一开始你就不会有这个问题。

当使用错误的工具时,你可能会在某处花上几个小时甚至几周的时间,直到你侥幸得到解决方案。然而,通过使用协议分析器和历久弥新的ping命令,你可以非常容易地在大约5分钟内诊断这个问题。就像早在高中时我的汽车技术辅导员就告诉我的,它全都是关于对任务使用恰当的工具。

除了确定错误,协议分析器提供为数不多的方法之一去证实问题的根源。以前我在微软的时候,棘手问题在团队间来回穿梭是很常见的,因为每个组误解由解释工具提供的数据。首先,问题可能被发送到Exchange团队,接着它可能被穿梭到Active Directory团队,然后最后到Networking团队。

通常,这是因为在其它团队的能力范围之内一个问题好像是合理的。然而,烫手山芋的游戏往往停止在Networking团队。为什么?因为Networking团队的头号工具是证实问题根源的救世主。

网络,像所有的计算,其核心是完全合乎逻辑的。一旦你了解它在幕后是如何工作的,你就有能力在底层确定问题,不论问题是多么独特。作为协议分析的一个伟大副作用,你也将学到很多关于网络的知识,它们将帮助你解决各种各样的网络问题(即使那些不需要协议分析)。

Wireshark基础

现在,有各种各样的协议分析器可供选择,从免费的和相当功能的微软消息分析器到特性极其丰富但十分昂贵的Savvius Omnipeek。多年来我已经使用过大量的分析器,但我最喜欢的用于常规故障排除的协议分析器是Wireshark。它是免费的,开源的,多平台的具有很多特性的分析器。有个充满活力的社区站在它背后,而且Wireshark也相当容易习惯。这让它成为一个很好的开始的地方。

你可以从 https://www.wireshark.org/ 下载用于你操作系统的Wireshark。安装它没有什么特别的,但如果你是安装在Windows上,确保也安装了捆绑的WinPCAP驱动程序。这允许Wireshark实际上捕获数据包(没有它,你只能观看存档的数据包)。

Wireshark通常将你的NIC置于混杂模式。正常情况下,你的NIC只会保留前往你的MAC或者广播MAC(FF-FF-FF-FF-FF-FF)的帧。启用混杂模式后,不管怎样,你的NIC保留所有它听到的帧。

从理论上讲,这意味着你应该接收所有的在你Ethernet段上的数据包。不过,实际上如今几乎所有的Ethernet网络都是交换网络。如果你想接收所有的通信量,必须多做些工作。

一旦你已经安装了Wireshark,使用它是相当简单的。把它打开,你将看到如下显示的屏幕:

这个屏幕给你展示选择一个在它上面捕获数据包的NIC的选项和输入一个用于只捕获一部分入站数据包的过滤器的选项。如果你选择一个NIC然后点击在文件菜单下面的小鱼翅图标,Wireshark将立即开始捕获数据包。

随着数据包被捕获,Wireshark在主界面中实时地显示它们。当你准备停止时,你只需点击在鱼翅图标旁边的小红方块。

数据包列表部分显示在这个点捕获的每件事物,按它们被捕获的顺序排序(默认)。(你可以通过点击要作为排序依据的标题任意地排序这些数据包。)

数据包细节部分显示Wireshark解码的在数据包中的每个报头。基本上,Wireshark有几乎今天在用的每个协议的解码器,并且为了显示分成字段的数据,解码器工具自动应用到每个数据包。

举例来说,如下,我已经为一个典型的HTTP数据包增加了Ethernet II报头。

你可以清楚地看到Wireshark已经析出了Destination和Source的MAC地址,以及Type字段,它是0x0800。Type字段指出下个报头应该是一个IPv4报头,Wireshark很方便告诉你这个。

这个解码特性使你不必自己计算字节和解码它(不过,如果你愿意,你仍然还可以在原始字节部分做)。如果对原始字节部分有兴趣:Wireshark同时为所有数据提供ASCII转换,它有时提供令人惊讶的数据。在下图,你可以在ASCII视图里的这个数据包中清楚地看到HTTP请求发送的细节。

Wireshark同时也提供一些非常实用的分析和统计特性,包括测量响应时间和往返时间的能力。但到目前为止,最有用的特性是过滤功能。

在数据包列表直接的上方是一个文本框,那里你可以输入显示过滤器。默认不使用过滤器,意味着显示被捕获的所有数据包。然而,你经常最后得到信息过载,而过滤掉噪音是数据包分析的一个非常重要的部分。

Wireshark中的过滤器按照一门简单的语言结合协议字段、比较运算符和逻辑运算符以便过滤掉不匹配条件的数据包。例如,过滤器http将只显示HTTP通信量,而过滤器ip.addr == 192.168.1.10将只显示源或目标的IP地址是192.168.1.10的数据包。

当你是第一次开始的时候,过滤可能会有点令人生畏,但通常在Wireshark中学习过滤器的最简单的方法是使用内建的表达式工具。可以通过点击过滤器文本框右边的Expression按钮访问它。

这个工具允许你寻遍Wireshark本身支持的所有协议,挑选你想过滤的字段而不需要知道过滤器动词或语法。只需选择协议,填写呈现的字段,然后过滤器将会为你而建。这里,我使用表达式工具构建一个仅查找Ethernet广播的过滤器。

注意工具如何在底部的绿框中显示最终的过滤器语法。通过注意这个字段,你将最终变得熟悉你的最常用的过滤器。

然而,你不能用表达式工具做的一件事是把过滤器串起来。因为那个原因,你需要学习一些逻辑运算符。Wireshark的基本逻辑运算符是and(&&)、or(||)和not(!)。

and被用于结合过滤器,只有满足所有条件的数据包会被显示。例如,过滤器http && ip.addr == 192.168.1.10将只显示在第7层报头中的HTTP协议和在IP报头中的IP地址192.168.1.10两者都包括的数据包。

or被用于查找两者中的任何一个过滤器,因此满足你输入的任何条件的数据包都会被显示。举例来说,过滤器http || ip.addr == 192.168.1.10将显示在第7层报头中的HTTP协议或在IP报头中的IP地址192.168.1.10的数据包。

not被用于从结果中过滤掉一些东西。例如,过滤器ip.addr == 192.168.1.10 ! http将显示有在IP报头中的IP地址192.168.1.10但没有在第7层报头中的HTTP协议的数据包。

关于基本的Wireshark功能最后要注意的事是,除保存你的原始捕获外,你也有多种多样的选项导出捕获。

首先,你导出当前选择的数据包、所有数据包、你标记的数据包或者一段范围的数据包。在这些选项的每一个中,你可以选择导出所有被捕获的数据包或只是被显示的数据包(考虑当前应用的过滤器)。这些选项让你非常具体地知道你想导出哪些数据包。

此外,你可以把数据包导出成几乎任何常用的格式。在Wireshark中用于文档和电子邮件转出的最好的特性之一是以纯文本或CSV格式导出解剖数据包(完整的数据包解码)的能力。要做到这个,只需从文件菜单里选择“Export Packet Dissections”。

理解你所看到的

尽管所有这些功能都很好,底线是如果你不明白在每个报头中字段的目的它们都是无用的。幸运的是,除了少量专有协议,你遇到的几乎每个协议的规格说明都是免费在线的。

例如:Ethernet,你可以直接到IEEE下载标准;802.3标准可以在 http://standards.ieee.org/about/get/802/802.3.html 获得。它是免费的直接来自权威人士。如果你在查找802.3 Ethernet帧格式,你将发现真的只有3个感兴趣的字段:目标MAC地址、源MAC地址和类型/长度字段。下图中在Wireshark解剖体左边的是来自IEEE 802.3规格说明Section 1中Part 3.1.1的Figure 3-1:

如果你想知道preamble和SFD发生了什么,它们在帧从NIC到Wireshark向上传递给栈之前被移除。同样地,你通常不会在末尾看到FCS,因为它在向上传递帧之前被剥去。

在第2层上面,所有TPCTCP/IP协议由IETF管理和由RFCs(请求评论)定义。所有这些RFCs可以在站点 https://www.rfc-editor.org/ 上即刻地免费地获得。虽然它们有点简洁(并且因为这个原因有时难以理解),它们总是正确的,具体问题的澄清可以使用Google快速搜索获得。

举例来说,通常混淆新手的事情之一是大量TCP重置,或者在TCP报头中数据包有打开的RST标记。浏览RFC 793(TCP),你可能会得到RST总是用信号告知一些坏事情的印象。几乎所有的35个左右提到的RST与某种错误条件有关联。

然而,使用关键词“tcp rst from client”的Google快速搜索将让你得到大量的关于这个现象的很好的讨论。也许最好的是来自Wireshark论坛,在那里他们解释说这很平常,因为客户端应用仅仅被编码去重置链接而不是优雅地关闭它。在这种情况下,服务端已经发送一个FIN。作为回复一个FIN/ACK并等待最终的ACK的替换,客户端只需通过发送一个RST并中止会话来优化过程。在下面的示例中这可以清楚地被看到。

除了规格说明和Google,另一个学习协议通常如何运转的良好来源是示例跟踪的资料库。这些示例跟踪允许你去查看相当典型的既常见又晦涩的协议操作,以及一些十分罕见的平常可能不会碰到的错误。

一个很好的起点是Wireshark Wiki上的样板捕获:https://wiki.wireshark.org/SampleCaptures 。在这里有大量非常有用的捕获让你去下载以及用过滤和其它Wireshark特性做实验,包括像广播风暴、病毒和攻击套装这样有意思的错误。如果这些还不够,在这个页面上还有一些其它资源的链接去协助你。但是毫无疑问地,变得擅长协议分析的最快方式是仔细观看大量的捕获并试图理解被使用的协议。

如何得到好的捕获

如果不能捕获正确的数据,世界上所有的领悟都无济于事。在最基本的层面,目标是只捕获涉及你试图解决的问题的数据包,有效减少你跟踪里的噪音。

为了做到这点,你可以使用一个捕获过滤器去从捕获中排除那些匹配过滤器外的所有数据。如果你确切地知道你在寻找什么这会工作的很好,但往往这种方法会导致你不能觉察一些重要的事情。大多数时候你只有一个问题是什么的粗略想法,或者你忘了一些潜在的找到错误的关键的过程。如果这种情况发生,使用捕获过滤器就没那么幸运,而且你不能返回和没重设置它就不过滤捕获。

例如,在诊断一个网站的性能问题时,你可能决定使用一个捕获过滤器集从Web服务器自身取得捕获,以便只捕获在其与客户端系统和后台SQL服务器之间往返的数据。然而,这个问题实际上可能仅仅是Web服务器使用的身份验证服务器过载,等待身份验证才是引起整个性能问题的原因。使用你选择的捕获过滤器你将永远不会发现这个问题。

这是我倾向于捕获所有数据并且使用显示过滤器去减少跟踪里的噪音的原因。这不是说捕获过滤器完全不必要。捕获过滤器的一个常见用途是当你有一个非常繁忙的你正在捕获的千兆或万兆连接的时候,捕获过滤器变得有用仅仅是因为大量的数据。不过,你始终需要牢记过滤器的限制。

得到一个好的捕获的第二部分是正确识别你需要捕获的系统。举例来说,在前面关于Web服务器性能问题的例子中,我可能首先会从Web服务器和Web客户端两者取得同时发生的捕获。这样你可以看到两边的正常预期行为的任何偏差,这有助于你将问题隔离到服务器或客户端。

一旦查明延迟是一个与身份验证有关的服务端问题,然后我会从Web服务器和身份验证服务器两者取得其它的跟踪。这样,我可以看到是本地到身份验证服务器的问题还是等待像DNS这样其它服务的问题或者Global Catalog是实际上的罪魁祸首。

得到一个好的捕获的第三步是在成功和失败条件中都使用捕获。举例来说,如果你有一个间歇性的Web服务器性能问题,设法在站点正常和不正常工作时都得到跟踪。这能给你一个好的和坏的比较跟踪,可以使用它去隔离问题。

最后,当处理一个间歇性的问题时,你会发现很难得到一个失败捕获。在这种情况下,Wireshark有一个很重要的特性被称为环形缓冲区,它允许你持续地捕获。

通常,特别在一个繁忙的网络上,持续的捕获将冒填满磁盘的风险。但有了环形缓冲区,Wireshark会写入文件直到它达到指定大小或者经过一段时间,然后它会切换到一个新文件。一旦指定数量的文件已经被写入,程序删除最旧的文件。例如,看看下面我已经定义的设置:

这个配置告诉Wireshark不管文件大小每10分钟创建一个新文件,并且确保程序保留总计3个文件,根据需要删除最旧的。这确保从错误被通知的时间起我有30分钟去停止捕获。这是一个非常有用的技术用于捕获极其间歇性的问题。

这些是你需要的以便用Wireshark开始故障排除的所有基本技术。使用这些技术和资源,你会发现你经常能用比几乎任何其它技术更短的时间找到和验证网络问题的原因。快乐的故障排除。

ANTLR 4权威参考读书笔记(26)

今天准备做的是把JSON文本文件转换成XML文本文件。

把JSON转换成XML

许多Web服务返回的是JSON数据,但是我们可能会遇到一种情况,需要把JSON数据送给那些只接受XML数据的代码。这就需要我们构建一个JSON到XML的转换器。我们的目标是读入像下面这样的JSON数据:

1
2
3
4
5
6
7
{
"description" : "An imaginary server config file",
"logs" : {"level":"verbose", "dir":"/var/log"},
"host" : "antlr.org",
"admin": ["parrt", "tombu"],
"aliases": []
}

放出等价的XML数据,就像下面这样的:

1
2
3
4
5
6
7
8
9
10
11
<description>An imaginary server config file</description>
<logs>
  <level>verbose</level>
  <dir>/var/log</dir>
</logs>
<host>antlr.org</host>
<admin>
  <element>parrt</element>
  <element>tombu</element>
</admin>
<aliases></aliases>

正如我们对CSV做的那样,让我们给JSON语法中的一些选项打上标签,以便让ANTLR生成更精确的监听器方法。

1
2
3
4
5
6
7
8
object
    : '{' pair (',' pair)* '}'    # AnObject
    | '{' '}'                     # EmptyObject
    ;
array
    : '[' value (',' value)* ']'  # ArrayOfValues
    | '[' ']'                     # EmptyArray
    ;

我们将对规则value做同样的事,但是稍有不同。除3个选项外的其它所有选项只需要返回被匹配的值的文本,所以我们可以为其它所有选项使用相同的标签,使语法分析树遍历器为那些选项触发相同的监听器方法。

1
2
3
4
5
6
7
8
9
value
    : STRING    # String
    | NUMBER    # Atom
    | object    # ObjectValue
    | array     # ArrayValue
    | 'true'    # Atom
    | 'false'   # Atom
    | 'null'    # Atom
    ;

为构建这样的转换器,明智的做法是让每个规则返回被它匹配的输入短语的XML等价物。为追踪部分结构,我们使用字段xml和两个帮助方法来注解语法分析树。

1
2
3
4
public static class XMLEmitter extends JSONBaseListener {
    ParseTreeProperty<String> xml = new ParseTreeProperty<String>();
    String getXML(ParseTree ctx) { return xml.get(ctx); }
    void setXML(ParseTree ctx, String s) { xml.put(ctx, s); }

我们把每棵子树转换后的字符串挂载到该子树的根节点。在语法分析树更高节点上工作的方法可以捕获这些值以便计算更大的字符串。然后挂载在根节点上的字符串完成计算。

让我们从最简单的转换开始。value的Atom选项返回匹配记号的文本。

1
2
3
public void exitAtom(JSONParser.AtomContext ctx) {
    setXML(ctx, ctx.getText());
}

字符串基本上是相同的,只是我们必须去除双引号。

1
2
3
public void exitString(JSONParser.StringContext ctx) {
    setXML(ctx, stripQuotes(ctx.getText()));
}

如果value()规则方法找到一个对象或数组,它可以把组合元素的部分转换拷贝到它自己的语法分析树节点。以下代码是找到对象时的处理:

1
2
3
4
public void exitObjectValue(JSONParser.ObjectValueContext ctx) {
    // analogous to String value() {return object();}
    setXML(ctx, getXML(ctx.object()));
}

一旦我们可以转换所有的值,我们需要担心名-值对以及把它们转换成标签和文本。生成的XML的标签名字来源于STRING ':' value选项中的STRING。在左右尖括号之间的文本来源于挂载在value子节点上的文本。

1
2
3
4
5
6
public void exitPair(JSONParser.PairContext ctx) {
    String tag = stripQuotes(ctx.STRING().getText());
    JSONParser.ValueContext vctx = ctx.value();
    String x = String.format("<%s>%s</%s>\n", tag, getXML(vctx), tag);
    setXML(ctx, x);
}

JSON对象由名-值对组成。因此,对于被选项中标记为AnObject的object找到的每个对,我们把计算后的结果追加在语法分析树。

1
2
3
4
5
6
7
8
9
10
11
public void exitAnObject(JSONParser.AnObjectContext ctx) {
    StringBuilder buf = new StringBuilder();
    buf.append("\n");
    for (JSONParser.PairContext pctx : ctx.pair()) {
        buf.append(getXML(pctx));
    }
    setXML(ctx, buf.toString());
}
public void exitEmptyObject(JSONParser.EmptyObjectContext ctx) {
    setXML(ctx, "");
}

处理数组遵循相似的模式,只是简单地连接来自子节点的结果列表,然后把它们包裹在<element>标签中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void exitArrayOfValues(JSONParser.ArrayOfValuesContext ctx) {
    StringBuilder buf = new StringBuilder();
    buf.append("\n");
    for (JSONParser.ValueContext vctx : ctx.value()) {
        buf.append("<element>"); // conjure up element for valid XML
        buf.append(getXML(vctx));
        buf.append("</element>");
        buf.append("\n");
    }
    setXML(ctx, buf.toString());
}
public void exitEmptyArray(JSONParser.EmptyArrayContext ctx) {
    setXML(ctx, "");
}

最后,我们需要使用从一个对象或数组收集来的全部转换注解语法分析树的根节点。

1
2
3
json: object
    | array
    ;

我们可以在监听器里用一个集合运算做到这点。

1
2
3
public void exitJson(JSONParser.JsonContext ctx) {
    setXML(ctx, getXML(ctx.getChild(0)));
}

以下是构建和测试序列:

1
2
3
antlr JSON.g
compile *.java
run JSON2XML t.json

下面的是部分的输出结果:

1
2
3
4
<description>An imaginary server config file</description>
<logs>
<level>verbose</level>
...

有些转换不总是像JSON到XML那样直白的。但是,这个例子向我们表明如何通过拼凑部分翻译短语处理句子转换问题。

ANTLR 4权威参考读书笔记(25)

这次我们要做的是通过监听器实现CSV文件的加载器,用于建立一个二维列表数据结构。

加载CSV数据

我们的目标是构建一个监听器去加载CSV数据到一个映射列表数据结构中,这是任何数据格式阅读器或配置文件阅读器都会做的事。我们会收集每行的字段并放到一个映射中,构成头名-值组合。以下是示例文件t.csv的内容:

1
2
3
4
Details,Month,Amount
Mid Bonus,June,"$2,000"
,January,"""zippo"""
Total Bonuses,"","$5,000"

我们想要看到如下的映射列表被打印出:

1
2
3
[{Details=Mid Bonus, Month=June, Amount="$2,000"},
 {Details=, Month=January, Amount="""zippo"""},
 {Details=Total Bonuses, Month="", Amount="$5,000"}]

为了在监听器中得到精确的方法,我们给CSV语法中field规则的每个选项打上标签:

1
2
3
4
5
6
7
8
9
10
11
12
13
grammar CSV;

file : hdr row+ ;
hdr : row ;
row : field (',' field)* '\r'? '\n' ;
field
    : TEXT    # text
    | STRING  # string
    |         # empty
    ;

TEXT : ~[,\n\r"]+ ;
STRING : '"' ('""'|~'"')* '"' ;     // quote-quote is an escaped quote

我们可以从定义我们需要的数据结构开始监听器的实现。首先,我们需要的数据结构是称为rows的映射列表。我们也需要在头行中找到的列名列表header。为处理数据行,我们需要把字段值读到一个临时列表currentRowFieldValues中,然后把列名映射到那些值上。以下是监听器LoadCSV.java的实现代码:

1
2
3
4
5
6
7
8
public static class Loader extends CSVBaseListener {
    public static final String EMPTY = "";
    /** Load a list of row maps that map field name to value */
    List<Map<String,String>> rows = new ArrayList<Map<String, String>>();
    /** List of column names */
    List<String> header;
    /** Build up a list of fields in current row */
    List<String> currentRowFieldValues;

下面的3个规则方法通过计算适当的字符串处理字段值,并把它添加到currentRowFieldValues中。

1
2
3
4
5
6
7
8
9
public void exitString(CSVParser.StringContext ctx) {
    currentRowFieldValues.add(ctx.STRING().getText());
}
public void exitText(CSVParser.TextContext ctx) {
    currentRowFieldValues.add(ctx.TEXT().getText());
}
public void exitEmpty(CSVParser.EmptyContext ctx) {
    currentRowFieldValues.add(EMPTY);
}

在我们能处理数据行之前,我们需要从第一行取得列名列表。头行在语法上仅仅是另外的行,但我们在对待它时要不同于常规的数据行,那意味着我们需要检查上下文。暂时让我们假设在exitRow()执行后,currentRowFieldValues包含列名列表。要填充header,我们只需要捕获第一行的字段值。

1
2
3
4
public void exitHdr(CSVParser.HdrContext ctx) {
    header = new ArrayList<String>();
    header.addAll(currentRowFieldValues);
}

谈到行时,我们需要两个操作:一个是当我们开始一行时,另一个是当我们结束一行时。当我们开始一行时,我们需要分配或清除currentRowFieldValues,准备获取一组新的数据。

1
2
3
public void enterRow(CSVParser.RowContext ctx) {
    currentRowFieldValues = new ArrayList<String>();
}

在行结束的时候,我们必须考虑上下文。如果我们仅仅加载头行,那我们不能改变rows字段,因为列名不是数据。在exitRow()中,我们可以通过查看在语法分析树中的父节点的getRuleIndex()值(或者询问父节点是否是HdrContext类型)测试上下文。如果当前行是数据行,我们将通过同时遍历header中的列名和currentRowFieldValues中的值获取的内容创建映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void exitRow(CSVParser.RowContext ctx) {
    // If this is the header row, do nothing
    // if ( ctx.parent instanceof CSVParser.HdrContext ) return; OR:
    if ( ctx.getParent().getRuleIndex() == CSVParser.RULE_hdr ) {
        return;
    }
    // It's a data row
    Map<String, String> m = new LinkedHashMap<String, String>();
    int i = 0;
    for (String v : currentRowFieldValues) {
        m.put(header.get(i), v);
        i++;
    }
    rows.add(m);
}

到这里,加载CSV数据到数据结构中的任务就算已经完成。在使用ParseTreeWalker遍历树后,我们就可以紧接着打印出rows字段:

1
2
3
4
ParseTreeWalker walker = new ParseTreeWalker();
Loader loader = new Loader();
walker.walk(loader, tree);
System.out.println(loader.rows);

以下是构建和测试序列:

1
2
3
antlr CSV.g
compile *.java
run LoadCSV t.csv

下面显示的是输出结果:

1
2
[{Details=Mid Bonus, Month=June, Amount="$2,000"}, {Details=, Month=January,
Amount="""zippo"""}, {Details=Total Bonuses, Month="", Amount="$5,000"}]

ANTLR 4权威参考读书笔记(24)

在本节中,我们准备讲讲有时候事件方法需要传递部分结果或其它信息的问题。

在事件方法间共享信息

无论收集信息还是计算值,传递参数和返回值都是比使用字段和全局变量更方便良好的编程实践。问题是ANTLR自动生成的监听器方法的签名不需要特定应用的返回值或参数,ANTLR也自动生成访问者方法而不需要特定应用的参数。

接下来,我们将探讨让事件方法无需修改事件方法签名就能传递数据的机制。我们将构建同样的简单计算器的3个不同实现,基于前面章节的LExpr表达式语法。第一个实现使用访问者方法返回值,第二个定义了一个在事件方法间共享的字段,第三个则注解语法分析树节点以便储存感兴趣的值。

使用访问者遍历语法分析树

构建基于访问者的计算器,最简单的方法是让和规则expr相关的事件方法返回子表达式的值。例如,visitAdd()将返回两个子表达式相加的值,visitInt()将返回整型的值。传统的访问者不指定visit方法的返回值。当我们为特定应用需求实现一个类时添加返回类型是容易的,扩展LExprBaseVisitor并提供Integer作为类型参数。访问者代码看起来如下所示:

1
2
3
4
5
6
7
8
9
10
11
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());
    }
}

EvalVisitor从ANTLR生成的AbstractParseTreeVisitor类继承通用的visit()方法,我们的访问者使用它去准确地触发子树访问。

注意,EvalVisitor没有针对规则s的访问者方法。在LExprBaseVisitor中的visitS()的默认实现调用预定义的方法ParseTreeVisitor.visitChildren(). visitChildren()返回从最后的子节点访问返回的值。在这里,visitS()返回访问它唯一的子节点(节点e)时返回的表达式的值。我们可以使用这种默认的行为。

在测试文件TestLEvalVisitor.java中,我们有常用代码去启动LExprParser和打印语法分析树,然后我们需要编码去启动EvalVisitor和打印出当访问树时计算出的表达式的值。

1
2
3
EvalVisitor evalVisitor = new EvalVisitor();
int result = evalVisitor.visit(tree);
System.out.println("visitor result = " + result);

要构建计算器,需要告诉ANTLR使用-visitor参数去生成访问者。(如果我们不再需要生成监听器,可以使用-no-listener参数)以下是完整的构建和测试序列:

1
2
3
antlr -visitor LExpr.g
compile *.java
run TestLEvalVisitor

接着输入以下内容:

1
2
1+2*3
EOF

你就会看到如下结果:

1
2
(s (e (e 1) + (e (e 2) * (e 3))))
visitor result = 7

如果我们需要特定应用的返回值,访问者工作的相当好,因为我们使用了内建的Java返回值机制。如果我们不希望显式地调用访问者方法去访问子节点,我们可以切换到监听器机制,不幸的是,这意味着我们要放弃使用Java方法返回值的整洁。

使用栈模拟返回值

ANTLR生成的监听器事件方法没有返回值。为了给在语法分析树更高节点上执行的监听器方法返回值,我们可以把部分的值存储在监听器的一个字段中。我们会想到用栈来存储值,方法就是把计算一个子表达式的结果推送到栈中,在语法分析树上用于子表达式的方法则把运算元从栈中弹出。以下是完整的Evaluator计算器监听器(代码在TestLEvaluator.java文件中):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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()));
    }
}

要测试上面的这段代码,我们可以创建和使用在代码TestLEvaluator中的ParseTreeWalker,以下是完整的构建和测试序列:

1
2
3
antlr LExpr.g
compile *.java
run TestLEvaluator

接着输入以下内容:

1
2
1+2*3
EOF

你就会看到如下结果:

1
2
(s (e (e 1) + (e (e 2) * (e 3))))
stack result = 7

使用栈字段有点别扭但工作得很好。我们必须确保事件方法以正确的顺序压入和弹出跨越监听器事件的值。带有返回值的访问者没有栈的这种笨拙但却需要手工访问树的节点。第三种实现是通过把部分值隐藏在树节点中来捕获它们。

注解语法分析树

作为使用临时存储在事件方法间共享数据的替代,我们可以把这些值存储在语法分析树本身中。使用树注解方法时我们可以带有监听器或访问者,但在这里我们使用监听器来阐明如何使用它。让我们首先看一下用部分结果注解的1+2*3的LExpr语法分析树。

每个子表达式对应一个子树根(和对应一个e规则调用)。从e节点发出的水平线指向的数字是我们想要返回的部分结果。

让我们看看节点注解策略将如何工作在来自LExpr语法的规则e上。

1
2
3
4
e : e MULT e    # Mult
  | e ADD e     # Add
  | INT         # Int
  ;

e选项的监听器方法每个都会存储一个结果在相对应的e语法分析树节点中。任何随后的在语法分析树更高节点上的add或multiply事件将通过查看存储在它们对应的子节点中的值来抓取子表达式的值。

现在,让我们假设每个语法分析树节点(每个规则上下文对象)都有一个字段value,那么exitAdd()看起来将是这样;

1
2
3
4
public void exitAdd(LExprParser.AddContext ctx) {
    // e(0).value is the subexpression value of the first e in the alternative
    ctx.value = ctx.e(0).value + ctx.e(1).value;    // e '+' e # Add
}

这看起来相当合理,但不幸的是,在Java中我们不能扩展类ExprContext去动态地添加字段。为了让语法分析树注解生效,我们需要一种方法去注解各式各样的节点而不需要手工修改由ANTLR生成的关联节点类。

注解语法分析树节点最简单的方式是使用与节点任意值相关联的一个Map。因此,ANTLR提供了一个简单的帮助类ParseTreeProperty。让我们在文件TestLEvaluatorWithProps.java中构建称作EvaluatorWithProps的另一个计算器版本,它使用ParseTreeProperty关联了LExpr语法分析树节点和部分结果。以下是在监听器开始处的适当的定义:

1
2
3
public static class EvaluatorWithProps extends LExprBaseListener {
    /** maps nodes to integers with Map<ParseTree,Integer> */
    ParseTreeProperty<Integer> values = new ParseTreeProperty<Integer>();

注意:如果你想使用自己的Map类型字段代替ParseTreeProperty,确保它继承自IdentityHashMap,而不是通常的HashMap。我们需要去注解特殊的节点,进行同一性测试而不是equals()。两个e节点可能是equals(),但在内存中不是同一个物理节点。

为注解一个节点,我们使用values.put(node, value)。为得到和一个节点有关联的值,我们使用values.get(node)。这很好,但是让我们创建一些有直白名字的帮助方法以便让代码更容易阅读。

1
2
public void setValue(ParseTree node, int value) { values.put(node, value); }
public int getValue(ParseTree node) { return values.get(node); }

让我们从最简单的表达式选项Int开始监听器方法。我们想使用它匹配的INT记号的整型值去注解它的语法分析树e节点。

1
2
3
4
public void exitInt(LExprParser.IntContext ctx) {
    String intText = ctx.INT().getText();    // INT    # Int
    setValue(ctx, Integer.valueOf(intText));
}

对于加法树,我们得到两个子表达式子节点的值(运算元)和带有和的注释的子树跟。

1
2
3
4
5
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);
}

方法exitMult()是相同的,只是运算的时候用multiply代替了add。

我们的测试代码从分析规则s开始。因此我们必须确保语法分析树根有e子树的值。为把值从e节点冒泡到根s节点,我们实现了exitS()。

1
2
3
4
/** Need to pass e's value out of rule s : e ; */
public void exitS(LExprParser.SContext ctx) {
    setValue(ctx, getValue(ctx.e()));    // like: int s() { return e(); }
}

以下是如何启动监听器以及打印出来自语法分析树根节点的表达式的值:

1
2
3
4
ParseTreeWalker walker = new ParseTreeWalker();
EvaluatorWithProps evalProp = new EvaluatorWithProps();
walker.walk(evalProp, tree);
System.out.println("properties result = " + evalProp.getValue(tree));

以下是构建和测试序列:

1
2
3
antlr LExpr.g
compile *.java
run TestLEvaluatorWithProps

接着输入以下内容:

1
2
1+2*3
EOF

你就会看到如下结果:

1
2
(s (e (e 1) + (e (e 2) * (e 3))))
stack result = 7

现在我们已经看到了相同计算器的3个实现,并且我们也已经准备好把我们的知识用于构建真实案例。因为每个方法都有它的优势和劣势,下面就让我们来比较下不同的技术。

比较信息共享方法

为得到可复用和可重定目标的语法,我们需要让它们完全清除用户定义的动作。这意味着要把所有特定应用的代码放到语法外的某些监听器和访问者中。监听器和访问者操作语法分析树,ANTLR自动生成合适的树遍历接口和默认实现。因为事件方法签名是固定的和不特定于应用的,所以事件方法可以共享信息的方式有3种:

  • 本地Java调用栈:访问者返回用户定义类型的一个值。如果访问者需要传递参数,它也必须使用下面两种技术的一种。
  • 基于栈:一个栈字段模仿参数和返回值,像Java调用栈那样。
  • 注解者:一个Map字段使用有用的值注解节点。

所有这3种方法是和语法本身完全解耦的,并且很好地封装在专门的对象中。除此之外,它们也都有各自的优点和缺点。我们可以根据问题的需要和个人的喜好决定采取哪种方法。你甚至可以在同一个应用中使用多种方法。

访问者方法很好懂,因为它们直接调用其它访问者方法去获取部分结果,并且能像其它任何方法那样返回值。这也是它们的缺点,访问者方法必须显式地访问它们的子节点。而监听器就不需要。因为访问者有个通用的接口,所以它不能定义参数。访问者必须使用其它解决方案的一种去传递参数给它在子节点上调用的访问者方法。访问者的空间效率很好,因为它在任何时间仅需保留少数的部分结果。在树遍历后没有部分结果保留。当访问者方法可以返回值时,每个值必须是同种类型,不想其它的解决方案。

基于栈的解决方案可以模仿参数和返回带有一个栈的值,但在手动管理栈时有个断开的机会。这可能会发生,因为监听器方法不能直接调用彼此。作为程序员,我们必须确定推入栈中的在将来事件方法调用能适当地弹出。栈可以传递多个值和多个返回值。基于栈的解决方案也是空间有效的,因为它不会把任何东西固定到树上。在树遍历后所有的部分结果存储消失。

注解者通常可以作为默认解决方案采用,因为它允许你任意地提供信息给事件方法操作语法分析树中上上下下的节点。你也可以传递多个值,它们可以是任意类型。在许多情况下注解胜于使用带有短暂值的栈。在各种方法的数据传递准备间很少有断开的机会。比起在编程语言中说返回值,使用setValue(ctx, value)注解树不太直观,但是更通用。超过其它两种的这种方法的唯一缺点是在树遍历期间部分结果是保留的,因此它有较大的内存占用。

从另一方面来说,在某些应用中能够注解树正是我们需要的。应用需要在树上通过多遍,第一遍是很方便在树上计算和储存数据的。当语法分析树遍历器重新遍历树的时候第二遍然后就很容易访问数据。总的来说,树注解非常灵活,有一个可接受的内存负担。

ANTLR 4权威参考读书笔记(23)

默认情况下,ANTLR为每个规则生成一个单一的事件类型,而不管语法分析器匹配了哪个选项。这很不方便,因为监听器和访问者方法必须确定哪个选项被语法分析器匹配。在本节中,我们将看到如何得到更细粒度的事件。

为规则选项贴标签以得到精确的事件方法

为阐明事件粒度问题,让我们为以下的表达式语法构建一个带有监听器的简单计算器:

1
2
3
4
5
6
grammar Expr;
s : e ;
e : e op=MULT e    // MULT is '*'
  | e op=ADD e     // ADD is '+'
  | INT
  ;

按照上面的语法,规则e会产生一个相当无用的监听器,因为规则e的所有选项导致树遍历器触发相同的enterE()和exitE()方法。

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

监听器方法必须使用op记号标签和ctx的方法进行测试以查看语法分析器为每个e子树匹配了哪个选项。

1
2
3
4
5
6
7
8
9
10
11
12
13
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
    }
}

在exitE()中引用的MULT字段是在ExprParser中由ANTLR自动生成的:

1
2
public class ExprParser extends Parser {
    public static final int MULT=1, ADD=2, INT=3, WS=4;

如果我们查看在类ExprParser中的类EContext,我们可以看到ANTLR把来自3个选项的所有元素都塞进了相同的上下文对象。

1
2
3
4
5
public static class EContext extends ParserRuleContext {
    public Token op;                     // derived from label op
    public List<EContext> e() { ... }    // get all e subtrees
    public EContext e(int i) { ... }     // get ith e subtree
    public TerminalNode INT() { ... }    // get INT node if alt 3 of e

为得到更精确的监听器事件,ANTLR让我们使用#运算符给任何规则最外层的选项打标签。让我们从Expr派生语法LExpr,并给e的选项打上标签,以下是修改后的e规则:

1
2
3
4
e : e MULT e  # Mult
  | e ADD e   # Add
  | INT       # Int
  ;

现在,ANTLR为e的每个选项生成了单独的监听器方法,因此,我们不再需要op记号标签。对于选项标签X,ANTLR生成方法enterX()和exitX()。

1
2
3
4
5
6
7
8
9
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);
    ...
}

注意,ANTLR也为选项生成特定的以标签命名的上下文对象(EContext的子类)。专门的上下文对象的getter方法只限于应用在那些相关的选项。例如,IntContext只有一个INT()方法,我们可以在enterInt()中调用ctx.INT(),但在enterAdd()中就不能。

监听器和访问者是极好的。我们只需要通过充实事件方法就可以得到可复用和可重定目标的语法以及封装的语言应用。ANTLR甚至会为我们自动生成骨架代码。

如何创建有效的图标

英文原文:http://www.awwwards.com/how-to-create-effective-icons.html

我可能就是你所说的图标爱好者。我喜欢图标,而且我更加喜欢制作它们!作为一个艺术家,我的背景在很大程度上是绘画——我喜欢绘画,并且我已经画了一辈子(甚至远远早于我知道什么是图形设计)。我想,这是我理解创建图标的一个关键。绘画教你看——然后把你所看到的转化成纸上的线条和图形——而这正是如何创建有效的图标。

几何图形

因此,对初学者而言,基本上任何东西都可以用这四种图形组合而成:

当我想把某事物转换成一个图标时,我观察它然后尽可能地将其拆分为最简单的图形。例如,水滴可以用一个三角形和一个圆形组成。

心形图标可以由两个圆形和一个三角形构成。

我每次都是在Adobe Illustrator中创建这些图形。使用矢量图形可以让我控制线条的粗细,以及图形和其锚点的相互作用。Illustrator也可以让我自由地把线条转换成图形,反之亦然。这一切也许看起来十分基础,但它是我用于创建最复杂图标的同样的方法。下面是我最近在做的一个略微更加复杂些的《权利法案》图标的示例,在这里我应用了同样的原则。

界面图标

我最近有机会为一款超赞的iPhone应用Parker Planner制作一组图标。我很喜欢做这个项目,这个项目其中最重要的一个方面是创建一组易懂的、私有的、实用的和美观的用户界面图标,可以帮助用户浏览操作这款略微复杂的计划应用。

让我们选取这些图标的其中之一分解看看我如何创建它。例如,垃圾桶图标是由三个圆角矩形和三条线构成。

1、选择圆角矩形工具。

2、拖动出一个图形。

3、调整笔划宽度直到你满意。

我通常选择在整组图标中使用一到两种笔划宽度。

这使它们看起来更一致和感觉更有整体性。

4、用另一个圆角矩形创建盖子。

5、再一个圆角矩形创建盖子的把手。

6、擦除圆角矩形的下半部分。

7、现在,通过添加三条竖线到桶身上给桶添加条纹。

8、然后你就获得了它!一个垃圾桶图标……如果你喜欢,你可以用颜色或线条宽度做进一步调整。

我在创建图标时经常使用的一些其它真正有用的工具是Pathfinder,我使用它来剪切、连接和挖空图形。

Stroke/Fill工具,它帮助你将图形在填满和笔划间切换。

以及我非常喜欢的工具Stroke Panel,它帮助你将拐角和线的末端从直角转换到圆角。

当我完成一组图标,我通常将它们全体紧挨着排成一排,看看是否有哪个看起来很奇怪或不到位。然后我会做任何必要的修改。

最后,我总是在应用中测试它们以确保它们感觉正确和功能良好。

最终,我想说创建优秀图标的方法不仅仅是学习Illustrator技巧,尽管它们也是必需的。最好的做法是练习把你周围看到的事物分解成简单图形。你在这点上越是变得更好,你越是能够成为更高超的图标设计师!加油!