乐者为王

Do one thing, and do it well.

Google Analytics中如何检测并防止垃圾流量

使用Google Analytics网站分析工具对博客进行数据统计。在经过一段时间的数据收集后,发现总是会有大量的垃圾流量存在。这里的垃圾流量,指的是对网站毫无作用且会影响网站数据报表质量的流量。通常Google Analytics中的垃圾流量可以分为以下两大类:

  • 一类被称为ghost referral,这些流量事实上从来没有来过你的网站,也不会出现在你网站服务器的日志中,但你可以在数据报表中发现它们,它们影响了Google Analytics中的数据;
  • 另一类是爬虫流量,包括搜索引擎爬虫流量和非搜索引擎爬虫流量,这些流量会影响Google Analytics中各渠道流量占比及会话次数、跳出率、停留时间等关键指标。

垃圾流量检测方法

打开报告 -> 受众群体 -> 技术 -> 广告网络 -> 主机名,统计报表如下图所示:

report-with-spam

可以看到,只有181个会话的主机名是我的博客域名,即真实来到我博客的流量,也就是说有超过一半的流量属于垃圾流量。并且这些垃圾流量基本都出现了不同程度的数据异常,如新会话百分比为0%、新用户为0、跳出率为100%、平均会话时长为00:00:00。这些垃圾流量的主机名与博客域名无关,说明是第一类垃圾流量。出现这类数据的原因可能是:

  • 别的网站使用了和你网站相同的媒体资源ID,这种情况一般来说不可能,除非恶意为之;
  • 有人使用Google Analytics中的Measurement Protocol做机器生成的访问流量,而你的媒体资源ID不幸躺枪。

使用过滤器屏蔽垃圾流量

打开“管理”页面,在博客帐号的“所有过滤器”下添加新的过滤条件,使用预定义或自定义均可,基本配置如下所示:

exclude-spam-filter

然后把“可选择的数据视图”中的选项添加到“选定的数据视图”中,保存即可。

过段时间后再回来查看报表,就会发现垃圾流量消失的干干净净了:

report-without-spam

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

  • action 动作
  • clause 子句

监听器和访问者机制是极好的。大多数时候,我们可以用监听器或访问者来构建语言应用,它们让特定应用的代码置身于语法之外,使语法容易被阅读。

但有时候我们需要额外的控制权和灵活性。为了达到这个目的,我们可以直接在语法中嵌入代码片段(这些嵌入的代码片段被称为动作)。这些动作会被注入到由ANTLR工具生成的分析器代码中。这些被注入的代码在分析期间执行,并且能像其它任意代码片段一样收集信息或生成输出。结合语义谓词,我们甚至可以在运行时让我们语法的某部分消失!例如,我们可能想打开或关闭Java语法中的enum关键字,分析语言的不同版本。没有语义谓词,我们就需要两个不同版本的语法。

下面我们将实现一个简单的程序,读入数据行,然后打印出在特定列中找到的值。

在语法中嵌入任意的动作

如果我们不想付出构建语法分析树的开销,或者想要在分析期间动态地计算值或把东西打印出来,那么可以通过在语法中嵌入任意代码来实现。它是比较困难的,因为我们必须明白在语法分析器上的动作的影响,以及在哪里放置这些动作。

为了解释嵌入在语法中的动作,让我们先来看下文件rows.txt中的数据:

1
2
3
parrt   Terence Parr    101
tombu   Tom Burns       020
bke     Kevin Edgar     008

这些列是由TAB分隔的,每行以一个换行符结束。匹配这种类型的输入在语法上还是相当简单的。下面是此语法文件Rows.g的内容:

1
2
file : (row NL)+ ;    // NL is newline token: '\r'? '\n'
row  : STUFF+ ;

我们需要创建一个构造器以便我们能传递我们想要的列号(从1开始计数),所以我们需要在规则中添加一些动作来做这个事情:

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
grammar Rows;

@parser::members {    // add members to generated RowsParser
    int col;

    public RowsParser(TokenStream input, int col) {    // custom constructor
        this(input);
        this.col = col;
    }
}

file: (row NL)+ ;

row
locals [int i=0]
    : ( STUFF
        {
            $i++;
            if ($i == col) System.out.println($STUFF.text);
        }
      )+
    ;

TAB  :  '\t' -> skip ;    // match but don't pass to the parser
NL   :  '\r'? '\n' ;      // match and pass to the parser
STUFF:  ~[\t\r\n]+ ;      // match any chars except tab, newline

在上述语法中,动作是被花括号括起来的代码片段;members动作的代码将会被注入到生成的语法分析器类中的成员区;在规则row中的动作访问的$i是由locals子句定义的局部变量,该动作也用$STUFF.text获取最近匹配的STUFF记号的文本内容。STUFF词法规则匹配任何非TAB或换行的字符,这意味着在列中可以有空格字符。

现在,是时候去思考如何使用定制的构造器传递一个列号给语法分析器,并且告诉语法分析器不要构建语法分析树了:

1
2
3
4
5
6
7
8
9
10
11
12
public class Rows {

    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        RowsLexer lexer = new RowsLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        int col = Integer.valueOf(args[0]);
        RowsParser parser = new RowsParser(tokens, col);    // pass column number!
        parser.setBuildParseTree(false);    // don't waste time bulding a tree
        parser.file();
    }
}

现在,让我们核实下我们的语法分析器能否正确匹配一些示例输入:

1
2
3
antlr -no-listener Rows.g  # don't need the listener
compile *.java
run Rows 1 < rows.txt

这时你会看到rows.txt文件的第1列内容被输出:

1
2
3
parrt
tombu
bke

如果将上面命令中的1换成2,你会看到文件的第2列内容被输出;如果换成3,那么第3列内容将会被输出。

一夜成名:这需要好几年时间

英文原文:http://blog.codinghorror.com/overnight-success-it-takes-years/

Gmail的原首席开发者Paul Buchheit说过Gmail的成功花了很长时间

我们在2001年8月开始开发Gmail。很长一段时间里,几乎每个人都不喜欢它。有些人使用它因为搜索,但他们有着无尽地抱怨。很多人认为我们应该杀死这个项目,又或者重启它作为一个有本地客户端软件的企业产品,而不是这个疯狂的JavaScript东西。甚至在2004年4月1日当我们到达发布它的那个点时——在开始开发它两年半之后——Google内部的很多人都在预测它的死亡。他们觉得这个产品太怪异了,并且没有人想去更换电子邮件服务。我被告知我们永远不会得到100万用户。

但在我们发布后,除了因为各种原因讨厌它的人,反响出人意外地好。尽管如此,它还是经常被描述为“小众产品(niche)”和“不会被硅谷之外的人使用”。

现在,在我们开始开发Gmail差不多七年半后,我看到一篇文章叙述Gmail如何在去年增长40%,相比Yahoo的2%和Hotmail的-7%。

Paul已经离开Google,现在在从事他自己的创业公司FriendFeed(译者注:FriendFeed已于2015年4月9日关闭)。许多业内人士对待FriendFeed不太友善。Stowe Boyd甚至竟然称FriendFeed就是个失败(译者注:Stowe Boyd评论FriendFeed的文章已经被删除了)。Paul从容应对批评:

创建一个重要的新产品通常需要时间。FriendFeed需要继续追求创新,就像Gmail六年以前做的那样。FriendFeed显示了很好的前景,但它仍然是一个“在制品”。

我的预期是很大的成功需要好几年时间,没有许多反例(除了YouTube,但现在它其实还没有到达挣成堆钱的那个点)。Facebook成长非常快,但它此时已经五岁了。Larry和Sergey 开始开发Google在1996年——当我开始在那里是1999年,几乎没人听说过它。

一夜成名的观念非常具有误导性,而且相当有害。如果你开始新的东西,那会是一次长途旅行。没有借口去行动缓慢。相反,你必须行动的非常快,否则你将不会到达,因为它是一次长途旅行!这也是为什么节俭是重要的——你不想饿死在半山腰上

Stowe Boyd用一张Twitter和FriendFeed的流量对比图说明他关于FriendFeed的观点。这里请允许我把我自己的数据也加到Boyd先生的图上:

three-traffic-comparison

我觉得Paul的态度令人耳目一新,因为对于我们的创业公司Stack Overflow我也采用同样的态度。我没有期望或甚至渴望一夜成名。我计划的是花上几年的时间去打磨,持续地、稳步地提升。

这项商业计划和我的职业生涯发展计划没有太多区别:成功需要好几年时间。当我说年的时候,我是认真的!不是在说像“更聪明地工作,而不是更努力地工作”那样的陈词滥调。我是在说真正的日历年。你知道的,12个月的,365天的那种。你必须花上你生命的多年时间孜孜不倦地钻研这些东西,每天醒来后一遍又一遍地做它。每天练习和收集反馈去不断变得更好。有时它可能是不愉快的,甚至偶尔是很无趣的,但它是必需的。

这几乎不是唯一的或有趣的建议。Peter Norvig的经典用十年自学编程也谈到过这个话题,而且讲得比我更好。

研究人员发现在任何领域都需要大约10年时间才能培养出专业技能,包括国际象棋、音乐作曲、电报操作、绘画、钢琴演奏、游泳、网球、以及神经心理学和拓扑学的研究。关键是刻意(deliberative)练习:不仅仅是一次又一次地做它,而是用略微超出你当前能力的任务来挑战自己,尝试它,在做时和做后分析你的表现,并且纠正所有错误。然后重复。再重复。

似乎没有真正的捷径:即使是莫扎特,4岁的音乐天才,在他开始创作世界级音乐前也花了超过13年。甲壳虫乐队似乎以一连串的冠军歌曲(a string of #1 hits)横空出世,并且在1964年出现在《埃德·沙利文秀》。但其实自1957年以来他们就已经在利物浦和汉堡的小俱乐部里演出了,虽然他们在早期有广泛的吸引力,但他们最最成功的《Sgt. Pepper's Lonely Hearts Club Band》发布在1967年。

老实说,我期待着有一天醒来,从现在起的2年或3年之后,做着和今天我在做的完全相同的事:为Stack Overflow编写代码,增加另一个微小的改进或有用的功能。很明显我们想要成功。但在某种程度上,成功是无关紧要的,因为这个过程本身是令人满意的。每天醒来做你喜欢的事情——甚至更好的是,周围社区的人也喜欢它——这本身就是一种奖赏。尽管有着成吨的工作要做。

博客也不例外。我经常给有抱负的博客作者这个很重要的建议:如果你开始你的博客,在六个月内别指望有人来读它。如果你这样做,我可以保证你将会非常失望。 可是,如果你能坚持发布计划并且每周写1篇或2篇高质量的博文一整年……然后,也只有到那个时候,你才可以看到稀稀落落的读者。我开始这个博客于2004年,花了整整3年的时间,每周写3到5篇博文,才使得它在软件开发社区内流行开来。

我非常期望在这个博客上一直写,以一种形式或另一种,用我的余生。它是我是谁的一部分。至于那种戏剧性的成名方式,我不抱有任何幻想:归根结底,我只是在网上写博客的那个人

pearls-before-swine

那样挺好的对我来说。我从来没有说过我是聪明的。

不管你最终获得多少读者,或页面浏览量,或任何我们这周正在度量的高分排行榜 ,请记住,你正在做的事情是值得去做的,因为——嗯——你正在做的事情是值得去做的。

如果你一直这样坚持下去,谁知道会发生什么?很有可能某天你醒过来,发现自己一夜成名了。

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

ANTLR 4权威参考读书笔记(3)以及ANTLR 4权威参考读书笔记(4)中我们分别用访问者和监听器机制实现了计算器的解释执行和编译执行。但并没有给出这两种机制的太多细节,这次就来详细地讲讲。

ANTLR在它的运行库中为两种树遍历机制提供支持。默认情况下,ANTLR生成一个语法分析树监听器接口,在其中定义了回调方法,用于响应被内建的树遍历器触发的事件。

在监听器和访问者机制之间最大的不同是:监听器方法被ANTLR提供的遍历器对象调用;而访问者方法必须显式的调用visit方法遍历它们的子节点,在一个节点的子节点上如果忘记调用visit方法就意味着那些子树没有得到访问。

让我们首先从监听器开始。在我们了解监听器之后,我们也将看到ANTLR如何生成遵循访问者设计模式的树遍历器。

语法分析树监听器

在Calc.java中有这样两行代码:

1
2
ParseTreeWalker walker = new ParseTreeWalker();
walker.walk(new DirectiveListener(), tree);

类ParseTreeWalker是ANTLR运行时提供的用于遍历语法分析树和触发监听器中回调方法的树遍历器。ANTLR工具根据Calc.g中的语法自动生成ParseTreeListener接口的子接口CalcListener和默认实现CalcBaseListener,其中含有针对语法中每个规则的enter和exit方法。DirectiveListener是我们编写的继承自CalcBaseListener的包含特定应用代码的实现,把它传递给树遍历器后,树遍历器在遍历语法分析树时就会触发DirectiveListener中的回调方法。

calc-listener-hierarchy

下图左边的语法分析树显示ParseTreeWalker执行了一次深度优先遍历,由粗虚线表示,箭头方向代表遍历方向。右边显示的是语法分析树的完整调用序列,它们由ParseTreeWalker触发调用。当树遍历器遇到规则assign的节点时,它触发enterAssign()并且给它传递AssignContext这个语法分析树节点的上下文。在树遍历器访问完assign节点的所有子节点后,它触发exitAssign()。

listener-call-sequence

监听器机制的强大之处在于所有都是自动的。我们不必要写语法分析树遍历器,而且我们的监听器方法也不必要显式地访问它们的子节点。

语法分析树访问者

有些情况下,我们实际想要控制的是遍历本身,在那里我们可以显式地调用visit方法去访问子树节点。参数-visitor告诉ANTLR工具从相应语法生成访问者接口和默认实现,其中含有针对语法中每个规则的visit方法。

下图是我们熟悉的访问者模式操作在语法分析树上。左边部分的粗虚线表示语法分析树的深度优先遍历,箭头方向代表遍历方向。右边部分指明访问者中的方法调用序列。

visitor-call-sequence

下面是Calc.java中的两行代码:

1
2
3
EvalVisitor eval = new EvalVisitor();
// To start walking the parse tree
eval.visit(tree);

我们首先初始化自制的树遍历器EvalVisitor,然后调用visit()去访问整棵语法分析树。ANTLR运行时提供的访问者支持代码会在看到根节点时调用visitProg()。在那里,visitProg()会把子树作为参数调用visit方法继续遍历,如此等等。

calc-visitor-hierarchy

ANTLR自动生成的访问者接口和默认实现可以让我们为访问者方法编写自己的实现,让我们避免必须覆写接口中的每个方法,仅仅聚焦在我们感兴趣的方法上。这种方式减少了我们学习ANTLR必须要花费的时间,让我们回到我们所熟悉的编程语言领域。

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

ANTLR 4权威参考读书笔记(3)中的计算器是以解释的方式执行的,现在我们想要把它转换成以编译的方式执行。编译执行和解释执行相比,需要依赖于特定的目标机器。在这里我们假设有一台这样的机器,它用堆栈进行运算,支持如下表所示的几种指令:

指令 说明 运算元数目 用途
LDV Load Variable 1 变量入栈
LDC Load Constant 1 常量入栈
STR Store Value 1 栈顶一个元素存入指定变量
ADD Add 0 栈顶两个元素出栈,求和后入栈
SUB Subtract 0 栈顶两个元素出栈,求差后入栈
MUL Multiply 0 栈顶两个元素出栈,求积后入栈
DIV Divide 0 栈顶两个元素出栈,求商后入栈
RET Return 0 栈顶一个元素出栈,计算结束

做这个最简单的方法是使用ANTLR的语法分析树监听器机制实现DirectiveListener类,然后它通过监听来自树遍历器触发的事件,输出对应的机器指令。

监听器机制的优势是我们不必要自己去做任何树遍历,甚至我们不必要知道遍历语法分析树的运行时如何调用我们的方法,我们只要知道我们的DirectiveListener类得到通知,在与语法规则匹配的短语开始和结束时。这种方式减少了我们学习ANTLR必须要花费的时间,让我们回到我们所熟悉的编程语言领域。

这里不需要创建新的语法规则,还是继续沿用前文Calc.g所包含的语法,标签也要保留:

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
30
31
32
grammar Calc;

prog
    : stat+
    ;

stat
    : expr                   # printExpr
    | ID '=' expr            # assign
    ;

expr
    : expr op=(MUL|DIV) expr # MulDiv
    | expr op=(ADD|SUB) expr # AddSub
    | INT                    # int
    | ID                     # id
    | '(' expr ')'           # parens
    ;

MUL : '*' ;

DIV : '/' ;

ADD : '+' ;

SUB : '-' ;

ID  : [a-zA-Z]+ ;

INT : [0-9]+ ;

WS  : [ \t\r\n]+ -> skip ;    // toss out whitespace

然后,我们可以运行ANTLR工具:

1
antlr Calc.g

它会生成后缀名为tokens和java的六个文件:

1
2
Calc.tokens         CaclLexer.java          CalcParser.java
CalcLexer.tokens    CalcBaseListener.java   CalcListener.java

正如这里我们看到的,ANTLR会为我们自动生成监听器基础设施。其中CalcListener是语法和监听器对象之间的关键接口,描述我们可以实现的回调方法:

1
2
3
4
public interface CalcListener extends ParseTreeListener {
    void enterProg(CalcParser.ProgContext ctx);
    void exitProg(CalcParser.ProgContext ctx);
    void enterPrintExpr(CalcParser.PrintExprContext ctx);

CalcBaseListener则是ANTLR生成的一组空的默认实现。ANTLR内建的树遍历器会去触发在监听器中像enterProg()和exitProg()这样的一串回调方法,如同它对语法分析树执行了一次深度优先遍历。为响应树遍历器触发的事件,我们的DirectiveListener需要继承CalcBaseListener并实现一些方法。我们不需要实现全部的接口方法,我们也不需要去覆写每个enter和exit方法,我们只需要去覆写那些我们感兴趣的回调方法。

在本例中,我们需要通过覆写6个方法对6个事件——当树遍历器exit那些有标签的选项时触发——作出响应。我们的基本策略是当这些事件发生时打印出已转换的指令。以下是完整的实现代码:

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
30
31
32
33
34
35
36
37
38
39
40
41
public class DirectiveListener extends CalcBaseListener {

    @Override
    public void exitPrintExpr(CalcParser.PrintExprContext ctx) {
        System.out.println("RET\n");
    }

    @Override
    public void exitAssign(CalcParser.AssignContext ctx) {
        String id = ctx.ID().getText();
        System.out.println("STR " + id);
    }

    @Override
    public void exitMulDiv(CalcParser.MulDivContext ctx) {
        if (ctx.op.getType() == CalcParser.MUL) {
            System.out.println("MUL");
        } else {
            System.out.println("DIV");
        }
    }

    @Override
    public void exitAddSub(CalcParser.AddSubContext ctx) {
        if (ctx.op.getType() == CalcParser.ADD) {
            System.out.println("ADD");
        } else {
            System.out.println("SUB");
        }
    }

    @Override
    public void exitId(CalcParser.IdContext ctx) {
        System.out.println("LDV " + ctx.ID().getText());
    }

    @Override
    public void exitInt(CalcParser.IntContext ctx) {
        System.out.println("LDC " + ctx.INT().getText());
    }
}

为了让它运行起来,余下我们唯一需要做的事是创建一个主程序去调用它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Calc {

    public static void main(String[] args) throws Exception {
        InputStream is = args.length > 0 ? new FileInputStream(args[0]) : System.in;

        ANTLRInputStream input = new ANTLRInputStream(is);
        CalcLexer lexer = new CalcLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalcParser parser = new CalcParser(tokens);
        ParseTree tree = parser.prog();

        ParseTreeWalker walker = new ParseTreeWalker();
        walker.walk(new DirectiveListener(), tree);

        // print LISP-style tree
        System.out.println(tree.toStringTree(parser));
    }
}

这个程序和前文Calc.java中的代码极度相似,区别只在12-13行。这两行代码负责创建树遍历器,然后让树遍历器去遍历那颗从语法分析器返回的语法分析树,当树遍历器遍历时,它就会触发调用到我们的DirectiveListener中实现的方法。此外,通过传入一个不同的监听器实现我们能简单地生成完全不同的输出。监听器机制有效地隔离了语法和语言应用,使语法可以被其它应用再次使用。

现在一切完备,让我们尝试着去编译和运行它吧!下面是完整的命令序列:

1
2
compile *.java
run Calc calc.txt

编译的输出结果如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LDC 19
RET

LDC 5
STR a
LDC 6
STR b
LDV a
LDV b
LDC 2
MUL
ADD
RET

LDC 1
LDC 2
ADD
LDC 3
MUL
RET

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

  • lexical 词法的
  • alternative 选项
  • notation 表示法
  • directive 指令
  • label 标签

了解ANTLR最好的方法就是实例。构建一个简单的计算器是个不错的主意。为了使它容易理解且保持简单,我们将只允许基本的算术运算符(加、减、乘、除)、括号表达式、整数和变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
grammar Calc;

prog
    : stat+
    ;

stat
    : expr
    | ID '=' expr
    ;

expr
    : expr ('*'|'/') expr
    | expr ('+'|'-') expr
    | INT
    | ID
    | '(' expr ')'
    ;

ID  : [a-zA-Z]+ ;

INT : [0-9]+ ;

WS  : [ \t\r\n]+ -> skip ;    // toss out whitespace

在上述的语法中,程序是由空格(换行符也被当作空格)终止的语句序列,语句可以是表达式或者赋值。那些以小写字母开头的像stat和expr是语法规则;由大写字母开头的诸如ID和INT为词法规则,用于识别标志符和整数这样的记号。我们用“|”分隔规则的选项,我们也可以用“()”把符号分组成子规则。例如,子规则('*'|'/')匹配乘法符号或者除法符号。

ANTLR v4最重要的新特性是它有能力处理(大多数类型的)左递归规则。例如,规则expr前两个选项就在左边缘递归地调用了expr自身。这种指定算术表达式表示法的方法比那些典型的自顶向下语法分析器策略更容易。当然,在这种策略下,我们需要定义多个规则,每个运算符优先级一个规则。

记号定义的表示法对那些有正则表达式经验的应该很熟悉。唯一不寻常的是在WS规则上的-> skip指令,它告诉词法分析器去匹配但丢弃空格,不要把它们放到记号流中,这样在语法分析树上空格就不会有对应的记号。(每个可能的输入字符都必须被至少一个词法规则匹配。)我们通过使用形式化的ANTLR表示法避免捆绑语法到某个特定的目标语言,而不是在语法中插入任意代码片段来告诉词法分析器去忽略。

这里是一些用来评估所有语法特性的测试序列:

1
2
3
4
5
193
a=5
b=6
a+b*2
(1+2)*3

把它们放入文件calc.txt中,然后执行以下命令:

1
2
3
antlr Calc.g
compile *.java
grun Calc prog -gui calc.txt

TestRig会弹出一个显示语法分析树的窗口:

calc-parse-tree

使用访问者模式计算结果

为了让前面的算术表达式语法分析器计算出结果,我们还需要做些其它的事情。

ANTLR v4鼓励我们使用语法分析树访问者和其它遍历器来实现语言应用,以保持语法的整洁。不过在接触这些之前,我们需要对语法做些修改。

首先,我们需要用标签标明规则的选项,标签可以是和规则名没有冲突的任意标志符。如果选项上没有标签,ANTLR只会为每个规则生成一个visit方法。

在本例中,我们希望为每个选项生成一个不同的visit方法,以便每种输入短语都能得到不同的事件。在新的语法中,标签出现在选项的右边缘,且以“#”符号开头:

1
2
3
4
5
6
7
8
9
10
11
12
stat
    : expr                   # printExpr
    | ID '=' expr            # assign
    ;

expr
    : expr op=(MUL|DIV) expr # MulDiv
    | expr op=(ADD|SUB) expr # AddSub
    | INT                    # int
    | ID                     # id
    | '(' expr ')'           # parens
    ;

接下来,让我们为运算符字面量定义一些记号名字,以便以后可以在visit方法中引用作为Java常量的它们:

1
2
3
4
5
6
7
MUL : '*' ;

DIV : '/' ;

ADD : '+' ;

SUB : '-' ;

现在,我们有了一个增强型的语法。接下来要做的事情是实现一个EvalVisitor类,它通过遍历表达式语法分析树计算和返回值。

执行下面的命令,让ANTLR生成访问者接口和它的默认实现,其中-no-listener参数是告诉ANTLR不再生成监听器相关的代码:

1
antlr -no-listener -visitor Calc.g

所有被标签标明的选项在生成的访问者接口中都定义了一个visit方法:

1
2
3
4
5
6
public interface CalcVisitor<T> extends ParseTreeVisitor<T> {
    T visitProg(CalcParser.ProgContext ctx);
    T visitPrintExpr(CalcParser.PrintExprContext ctx);
    T visitAssign(CalcParser.AssignContext ctx);
    ...
}

接口定义使用的是Java泛型,visit方法的返回值为参数化类型,这允许我们根据表达式计算返回值的类型去设定实现的泛型参数。因为表达式的计算结果是整型,所以我们的EvalVisitor应该继承CalcBaseVisitor<Integer>类。为计算语法分析树的每个节点,我们需要覆写与语句和表达式选项相关的方法。这里是全部的代码:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class EvalVisitor extends CalcBaseVisitor<Integer> {
    /** "memory" for our calculator; variable/value pairs go here */
    Map<String, Integer> memory = new HashMap<String, Integer>();

    /** ID '=' expr */
    @Override
    public Integer visitAssign(CalcParser.AssignContext ctx) {
        String id = ctx.ID().getText();  // id is left-hand side of '='
        int value = visit(ctx.expr());   // compute value of expression on right
        memory.put(id, value);           // store it in our memory
        return value;
    }

    /** expr */
    @Override
    public Integer visitPrintExpr(CalcParser.PrintExprContext ctx) {
        Integer value = visit(ctx.expr()); // evaluate the expr child
        System.out.println(value);         // print the result
        return 0;                          // return dummy value
    }

    /** INT */
    @Override
    public Integer visitInt(CalcParser.IntContext ctx) {
        return Integer.valueOf(ctx.INT().getText());
    }

    /** ID */
    @Override
    public Integer visitId(CalcParser.IdContext ctx) {
        String id = ctx.ID().getText();
        if ( memory.containsKey(id) ) return memory.get(id);
        return 0;
    }

    /** expr op=('*'|'/') expr */
    @Override
    public Integer visitMulDiv(CalcParser.MulDivContext ctx) {
        int left = visit(ctx.expr(0));  // get value of left subexpression
        int right = visit(ctx.expr(1)); // get value of right subexpression
        if ( ctx.op.getType() == CalcParser.MUL ) return left * right;
        return left / right; // must be DIV
    }

    /** expr op=('+'|'-') expr */
    @Override
    public Integer visitAddSub(CalcParser.AddSubContext ctx) {
        int left = visit(ctx.expr(0));  // get value of left subexpression
        int right = visit(ctx.expr(1)); // get value of right subexpression
        if ( ctx.op.getType() == CalcParser.ADD ) return left + right;
        return left - right; // must be SUB
    }

    /** '(' expr ')' */
    @Override
    public Integer visitParens(CalcParser.ParensContext ctx) {
        return visit(ctx.expr()); // return child expr's value
    }
}

以前开发和测试语法都是使用的TestRig,这次我们试着编写计算器的主程序来启动代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Calc {

    public static void main(String[] args) throws Exception {
        InputStream is = args.length > 0 ? new FileInputStream(args[0]) : System.in;

        ANTLRInputStream input = new ANTLRInputStream(is);
        CalcLexer lexer = new CalcLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalcParser parser = new CalcParser(tokens);
        ParseTree tree = parser.prog();

        EvalVisitor eval = new EvalVisitor();
        // 开始遍历语法分析树
        eval.visit(tree);

        System.out.println(tree.toStringTree(parser));
    }
}

创建一个运行主程序的脚本:

1
2
#!/bin/sh
java -cp .:./antlr-4.5.1-complete.jar:$CLASSPATH $*

把它保存为run.sh后,执行以下命令:

1
2
compile *.java
run Calc calc.txt

然后你就会看到文本形式的语法分析树以及计算结果:

1
2
3
4
5
6
193
17
9
(prog (stat (expr 193)) (stat a = (expr 5)) (stat b = (expr 6))
 (stat (expr (expr a) + (expr (expr b) * (expr 2)))) (stat (expr
 (expr ( (expr (expr 1) + (expr 2)) )) * (expr 3))))

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

  • token 记号
  • ambiguity 二义性

安装ANTLR

ANTLR是由Java写成的,所以在安装ANTLR前必须保证已经安装有Java 1.6或以上版本。你可以到 http://www.antlr.org/download.html 下载ANTLR的最新版本,或者也可使用命令行工具下载:

1
curl -O http://www.antlr.org/download/antlr-4.5.1-complete.jar

antlr-4.5.1-complete.jar包含运行ANTLR工具的所有必要依赖,以及编译和执行由ANTLR生成的识别器所需的运行库。ANTLR工具将由语法文件描述的语法转换成识别程序,识别程序利用ANTLR运行库中的某些支持类识别输入的语句。该jar包还包含两个支持库:TreeLayout(一个复杂的树布局库)StringTemplate(一个用于生成代码和其它结构化文本的模板引擎)

现在来测试下ANTLR工具是否工作正常:

1
java -jar antlr-4.5.1-complete.jar  # 启动org.antlr.v4.Tool

如果正常的话会看到以下帮助信息:

1
2
3
4
ANTLR Parser Generator  Version 4.5.1
 -o ___              specify output directory where all output is generated
 -lib ___            specify location of grammars, tokens files
 ...

每次运行ANTLR工具都要输入这么长的命令是否有些痛苦?写个脚本来解放我们的手指吧!

1
2
#!/bin/sh
java -cp .:./antlr-4.5.1-complete.jar:$CLASSPATH org.antlr.v4.Tool $*

把它保存为antlr.sh,以后就可以使用下列命令来运行ANTLR工具了:

1
antlr

执行ANTLR和测试识别器

先看下面这段用于识别像hello world那样短语的简单语法:

1
2
3
4
5
grammar Hello;               // 定义语法的名字

s  : 'hello' ID ;            // 匹配关键字hello,后面跟着一个标志符
ID : [a-z]+ ;                // 匹配小写字母标志符
WS : [ \t\r\n]+ -> skip ;    // 跳过空格、制表符、回车符和换行符

把以上语法保存为Hello.g,然后执行以下命令来生成识别器:

1
antlr Hello.g

该命令会在相同目录下生成后缀名为tokens和java的六个文件:

1
2
Hello.tokens        HelloLexer.java         HelloParser.java
HelloLexer.tokens   HelloBaseListener.java  HelloListener.java

现在开始准备编译由ANTLR生成的Java代码。先写个脚本把编译命令包装起来:

1
2
#!/bin/sh
javac -cp .:./antlr-4.5.1-complete.jar:$CLASSPATH $*

把它保存为compile.sh文件,然后你就可以用以下命令编译代码了:

1
compile *.java

到此,我们已经有了一个可以被执行的识别器,只缺一个主程序去触发语言识别了。

ANTLR运行库有提供称之为TestRig的测试工具,可以让你不创建主程序就能测试语法。TestRig使用Java反射调用编译后的识别器,它能显示关于识别器如何匹配输入的大量信息。

同样地,创建一个脚本grun.sh来简化以后的打字数:

1
2
#!/bin/sh
java -cp .:./antlr-4.5.1-complete.jar:$CLASSPATH org.antlr.v4.gui.TestRig $*

现在,让我们来打印出识别期间创建的那些记号(记号是指像关键字hello和标识符world那样的词汇符号):

1
grun Hello s -tokens

敲入上述命令并按回车,接着输入以下内容:

1
2
hello world  # 输入并按回车
EOF          # Unix系统输入Ctrl+D或Windows系统输入Ctrl+Z并按回车

TestRig会打印出记号列表,每一行输出表示一个记号以及它的有关信息:

1
2
3
[@0,0:4='hello',<1>,1:0]
[@1,6:10='world',<2>,1:6]
[@2,13:12='<EOF>',<-1>,2:0]

这里详细讲解下[@1,6:10='world',<2>,1:6]的意义。@1表示记号索引(从0开始);6:10表示记号开始与结束的位置(从0开始);<2>表示记号类型,具体数值和类型存储在后缀名为tokens的文件中;最后的1:6表示记号在第一行(从1开始),从第6个字符开始(从0开始,制表符作为单个字符计算)。

除此之外,还可以以LISP风格的文本形式查看记号:

1
grun Hello s -tree

它会输出如下形式的记号:

1
(s hello world)  # (root children)

你也可以以可视化的方式查看语法分析树:

1
grun Hello s -gui

hello-parse-tree

以下是TestRig可用的所有参数:

  • -tokens 打印出记号流。
  • -tree 以LISP风格的文本形式打印出语法分析树。
  • -gui 在对话框中可视化地显示语法分析树。
  • -ps file.ps 在PostScript中生成一个可视化的语法分析树表示,并把它存储在file.ps文件中。
  • -encoding encodingname 指定输入文件的编码。
  • -trace 在进入/退出规则前打印规则名字和当前的记号。
  • -diagnostics 分析时打开诊断消息。此生成消息仅用于异常情况,如二义性输入短语。
  • -SLL 使用更快但稍弱的分析策略。

PBL文件格式解析

PBL文件是PowerBuilder库文件,在其中存储了应用程序所使用到的所有系统对象和用户自定义对象的集合,同时PBL文件中还存储了源代码控制信息(Source Code Control,简称SCC)。对其文件格式的研究,可以准确地了解程序结构并能对PBL文件中的对象进行修改,同时也有利于库文件的修复,程序动态执行等方面的工作。

PBL文件的存储结构

PBL文件存储信息时是以块(Block)为单位为对象分配存储空间的,每个块的大小固定为512字节,块号从0开始计算,块号与块首字节的偏移地址有如下关系:

1
块号 = 块首字节的偏移地址 / 512

整个PBL文件由Header块、Bitmap块、Node块、Data块组成。其中除Header块外,其它块均以链表结构组织,其中Data块是Node块中Entry表项的具体内容,是从属于Node块的。下图说明了这些块的关系。

pbl-datastruct

图中Header块、首个Bitmap块及首个Node块在存储空间上是相邻的,其中Node块比较特别,占6个块共3072字节,其余块只占512字节,其空间大小及起始地址如下表所示:

块号 地址范围 描述
0 0000-01FF Header块
1 0200-03FF 首个Bitmap块
2-7 0400-0FFF 首个Node块

Header块解析

Header块是整个PBL的描述信息,它包含了PBL的版本标志,库注释,首个SCC数据块的偏移地址等信息。具体内容如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'HDR*'
0004-0011 14 char 'PowerBuilder' + 0x00 + 0x00
0012-0015 4 char PBL格式版本(如0900表示9.0版本)
0016-0019 4 long 创建/修改日期时间
001A-001B 2 byte 保留
001C-011B 256 char 库注释
011C-011F 4 long 首个SCC数据块的偏移地址
0120-0123 4 long SCC数据块实际大小
0124-01FF 220 byte 保留

Bitmap块解析

Bitmap块中存放的是表示PBL文件存储空间的使用情况。该块数据结构如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'FRE*'
0004-0007 4 long 下一个Bitmap块的偏移地址或0
0008-01FF 504 bit 位图(每个位标识一个块)

由上表可知,包含一个Bitmap块的PBL文件最多可使用504 * 8 = 4032个块。当文件空间超过4032个块时,就需要使用第二个Bitmap块,它的偏移地址由当前Bitmap块块内偏移0004-0007处的值表示。如果是最后一个Bitmap块,则对应的字节处为00 00 00 00,即偏移地址为0。这样就形成了Bitmap块的单向链表。

bitmap-block-chain

位图用于标识块的使用/空闲情况。在位图中为1的位,表示与该位序号对应的块已被使用;反之,表示对应块未使用。例如FF FF 40 00还原为位图则为11111111 11111111 01000000 00000000,该位图表示PBL文件共有18个块,其中的第16号块空闲未使用。

注意:在实际分析多个PBL文件后发现,位图中的位并不能真实反映对应块的空闲/使用情况,只是记录PBL文件使用了多少个块。

Node块解析

Node块是目录块,主要用于存放Entry目录表项。下表是Node块的数据结构:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'NOD*'
0004-0007 4 long 左Node块的偏移地址或0
0008-001B 4 long 父Node块的偏移地址或0
000C-000F 4 long 右Node块的偏移地址或0
0010-0011 2 short 块内可用空间(初始值3040)
0012-0013 2 short 按字母顺序最后一个对象名的位置
0014-0015 2 short 该Node块中的Entry表项数
0016-0017 2 short 按字母顺序第一个对象名的位置
0018-001F 8 char 保留
0020-00BF 3040 chunks Entry目录表

其中Entry目录表是顺序表。当一个Node块的空间不足以存储所有Entry表项时,可以再使用一个Node块来存储,并且Entry表项不能跨Node块存储,因此Node块中的空间不能完全利用,会有一定的剩余,这个值记录在块内偏移0010-0011处。

Node块的链接方式有些复杂,它使用一种称之为三叉链表(节点包含四个域:数据域、左指针域、右指针域、父指针域)的链式存储结构把所有Node块组织成为一颗二叉树,这可能是PowerBuilder为了提高查找速度而做的一些优化吧。

node-block-tree

Entry表项解析

每个Entry表项对应于一个对象的源代码或PCODE的描述信息,因此Entry目录表就是整个库中各个对象的索引表,存储了各对象的索引信息。例如,在编程中创建一个名为“pbltest”的Window对象类型,那么在Entry目录表中要存放该对象的两个索引表项,分别为“pbltest.srw”用于存储源代码,“pbltest.win”用于存储PCODE。在Entry目录表中存储的对象有以下这些:

对象类型 源代码后缀 PCODE后辍
Application sra apl
Window srw win
DataWindow srd dwo
Menu srm men
Function srf fun
Query srq -
Structure srs str
User object sru udo
Pipeline srp -
Project srj -
? - pra
? - prp

Entry表项的具体数据结构如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'ENT*'
0004-0007 4 char PBL格式版本(如0900表示9.0版本)
0008-000B 4 long 首个Data块的偏移地址
000C-000F 4 long 对象的实际大小
0010-0013 4 long 对象的创建/修改日期时间
0014-0015 2 short 对象的注释长度
0016-0017 2 short 对象名的长度
0018-???? ? char 对象名 + 0x00

这里需要说明的是,每个Entry表项的长度并不是固定的,它随着对象名的长度变化而变化,所以要读取下一个Entry表项,只能通过计算上一个Entry表项的长度即24 + 对象名长度来得 到,或者通过搜索下一个ENT*得到。

Data块解析

在Entry目录表中的各对象的实际数据内容是存储在Data块中的。Data块的数据结构如下表所示:

块内地址范围 所占字节 数据类型 描述
0000-0003 4 char 'DAT*'
0004-0007 4 char 下一个Data块的偏移地址或0
0008-0009 2 short 本块内存储的数据的实际长度
0010-01FF 502 char 对象的实际数据

由上表可知,若对象的数据内容在502字节以上时,就需用多个Data块存放,这些Data块形成一个单向链表。链表的最后一个Data块的0004-0007中存储的偏移地址为00 00 00 00,表示链表结束。0010-01FF处存放的是对象的实际数据,只有最后一个Data块的长度有可能小于502,且以0x00字节表示结束。

根据上面对PBL文件格式的解析,使用Ruby开发了一个小工具,用来输出PBL文件中存储的各种信息。源代码被放在GitHub上面,供大家参考。

代码下载:https://github.com/dohkoos/pblanalyzer

带权随机函数

  • 设计抽奖活动时,我们总是要控制抽奖物品出现的概率,让好的东西很难被抽到;
  • 设计游戏打怪时,我们要控制打怪时的命中概率,要控制宝物掉出的概率;
  • 网站的置顶广告,我们也要根据广告主的广告费用控制广告的出现时间;
  • 设计负载均衡算法时,我们要根据服务器的性能控制服务器被选中的可能。

深入思考这些需求,你会发现它们都有相通的概念:每次从多个候选项中随机选取其中一项,要求每个候选项的出现都有一定的概率。

假设有这样的候选项和对应概率:a:20%,b:25%,c:40%,d:15%。现在,把每个候选项的概率用一个称之为权重的正整数表示(最简单的方法是把百分符号去掉)。那么,

1
实际概率 = 候选项权重 / 权重总和 * 100%

事实上,权重的总和不一定要等于100,可以是任意大小。

算法描述

依次将各候选项的权重从原点开始放在x轴坐标上首尾相连。这样,每个候选项对应一个取值区间,在总区间范围内随机选取一个值,该值所在区间就对应了选中的项。

random-with-weight

Ruby代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def random(weight)
  # 获取所有候选项的权重总和
  total_weight = weight.inject { |r, e| r + e }

  # 随机选取一个介于0到权重总和之间的整数
  rand_value = rand(total_weight)  # [0, total_weight)

  # 扫描所有候选项,并且保留候选项权重的累积数。
  # 每当随机数小于累积数时,就停止并选出当前项。
  weight_barrier = 0
  weight.each_index do |i|
    weight_barrier += weight[i]

    break i if rand_value < weight_barrier
  end
end

该实现不能保证每个候选项都恰好按正确的比例被选中,但当次数足够多时,应该会十分接近预先设定的比例。

实际案例

要求写int[] get_weight(int[] weight)函数,返回的是权重的索引。其中weight是权重的数字数组,最终的结果是要大概保证按照给定的比例。

  • 比如weight为[1, 2, 2],那么权重比例为1:2:2,执行10次后,大概的输出是0 1 1 0 1 1 2 2 2 2;
  • 比如weight为[100, 0],那么权重比例为100:0,执行10次后,大概的输出是0 0 0 0 0 0 0 0 0 0;
  • 比如weight为[1, 1],那么权重比例为1:1,执行10次后,大概的输出是0 1 0 1 0 0 1 1 0 1。
1
2
3
4
5
6
7
8
9
10
11
12
def get_weight(weight)
  10.times.map { random(weight) }
end

weight = [1, 2, 2]
puts get_weight(weight).join(' ')

weight = [100, 0]
puts get_weight(weight).join(' ')

weight = [1, 1]
puts get_weight(weight).join(' ')

逻辑题-共打了多少鱼

abcde五人打渔,打完睡觉,a先醒来,扔掉1条鱼,把剩下的分成5份,拿1份走了;b再醒来,也扔掉1条,把剩下的分成5份,拿1份走了;然后cde都按上面的方法取鱼。问他们最少打了多少条鱼?

渔民 醒来时鱼的总数 取走的鱼数
a x1 = x (x1 - 1) / 5
b x2 = 4 * (x1 - 1) / 5 (x2 - 1) / 5
c x3 = 4 * (x2 - 1) / 5 (x3 - 1) / 5
d x4 = 4 * (x3 - 1) / 5 (x4 - 1) / 5
e x5 = 4 * (x4 - 1) / 5 (x5 - 1) / 5

由于扔掉1条鱼后,还能被分成5份,设渔民醒来时鱼的总数为remain,那么(remain - 1) % 5的值为0,即remain % 5的值为1。

最简单的方法就是枚举,最小值从1开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fishmen = [0, 0, 0, 0, 0]  # 渔民取走的鱼数
total = 1

while true do
  remain = total  # 渔民a醒来时鱼的总数
  5.times do |i|  # 5个渔民轮流取鱼
    break if remain % 5 != 1  # 如果不符合扔掉1条鱼后还能分成5份的条件,就枚举下个值
    fishmen[i] = (remain - 1) / 5  # 渔民取走的鱼数
    remain = 4 * fishmen[i]  # 渔民取走鱼后剩下的鱼数
  end
  break if fishmen[4] != 0  # 如果渔民e也取到了鱼,那么就得到了鱼的总数
  total += 1
end

puts total  # 结果是3121条鱼

上面的代码总过做了3901次循环,下面来做进一步的优化。

从表格可以看出,因为(x5 - 1) % 5 == 0,推导出x5 >= 6;又x1 % 5 == 1,因此x1的个位数必须是1或者6。所以,枚举的最小值可以从11开始,每次步进为5。优化后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fishmen = Array.new(n, 0)
total = 11

while true do
  remain = total
  5.times do |i|
    break if remain % 5 != 1
    fishmen[i] = (remain - 1) / 5
    remain = 4 * fishmen[i]
  end
  break if fishmen[4] != 0
  total += 5
end

puts total

总的循环次数减少到1401次,减少了整整64%的循环。

推而广之:n个渔民打渔,每个渔民依次扔掉1条鱼后,把鱼分成n份,然后拿走其中一份,求最少打了多少条鱼?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fishmen = Array.new(n, 0)
total = 2 * n + 1

while true do
  remain = total
  n.times do |i|
    break if remain % n != 1
    fishmen[i] = (remain - 1) / n
    remain = remain - 1 - fishmen[i]
  end
  break if fishmen[n - 1] != 0
  total += n
end

puts total

这下子无论多少个渔民打渔都可以用这段代码搞定了。我试了试9个渔民,发现竟然可以打近3.9亿条鱼,那得有多少鱼啊!另外,计算时间也明显开始变长了。不知道还能不能做更进一步的优化。如果你有更好的算法,请快点告诉我吧!