乐者为王

Do one thing, and do it well.

贫富差距精简版

英文原文:http://paulgraham.com/sim.html

2016年1月

正如经常发生的那样——当说一些有争议的话题时,已经有我刚写的一篇贫富差距的文章的一些非常新奇的解释。我想这可能有助于澄清问题,如果我试着写一个简简单单、没有误解的版本。

很多人谈论贫富差距。几乎所有人都说贫富差距增大是坏的,贫富差距缩小是好的。

但是贫富差距本身并非坏事。它有多方面的原因。很多是坏的,但有些是好的。

例如,高入狱率和税收漏洞是增大贫富差距的不良因素。

但是创业同样地增大贫富差距。创业成功的创始人最终会得到值很多钱的股票。

而且不像高入狱率和税收漏洞,创业整体上是好的。

既然贫富差距本身并非坏事,我们就不应该攻击它。相反,我们应该攻击那些造成贫富差距的不良因素。

例如,我们应该攻击贫穷,而不是攻击贫富差距。

攻击贫富差距是双重错误。它会损害好的和坏的原因。但更糟的是,这是一个攻击坏的原因的无效方式。

除非我们直接攻击坏的贫富差距原因,否则我们不能做好解决它们的工作。

但是,如果我们解决了所有坏的贫富差距原因,我们依然将增加贫富差距的水平,因为正在增长的技术力量。

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

  • sentence 句子

一门语言由有效的句子组成,一个句子由短语组成,一个短语由子短语和词汇符号组成。要实现一门语言,我们必须构建一个能读取句子以及对发现的短语和输入符号作出适当反应的应用。

这样的应用必须能够识别特定语言的所有有效的句子、短语和子短语。识别一个短语意味着我们能够确定短语的各种组件并能指出它与其它短语的区别。例如,我们把输入sp=100识别为赋值语句,这就意味着我们知道sp是赋值目标以及100是要存储的值。识别赋值语句sp=100也意味着应用认为它是明显不同于,比如说,a+b语句的。在识别后,应用将执行适当的操作,例如performAssignment("sp", 100)或者translateAssignment("sp", 100)。

识别语言的程序被称为语法分析器。语法指代控制语言成员的规则,每条规则都表示一个短语的结构。为了更容易地实现识别语言的程序,通常我们会把识别语言的语法分析拆解成两个相似但不同的任务或阶段。

把字符组成单词或符号(记号)的过程被称为词法分析或简单标记化。我们把标记输入的程序称为词法分析器。词法分析器能把相关的记号组成记号类型,例如INT(整数)、ID(标志符)、FLOAT(浮点数)等。当语法分析器只关心类型的时候,词法分析器会把词汇符号组成类型,而不是单独的符号。记号至少包含两块信息:记号类型(确定词法结构)和匹配记号的文本。

第二阶段是真正的语法分析器,它使用这些记号去识别句子结构,在本例中是赋值语句。默认情况下,ANTLR生成的语法分析器会构建一个称为语法分析树或语法树的数据结构,它记录语法分析器如何识别输入句子的结构和它的组件短语。下图阐明了语言识别器的基本数据流:

basic-data-flow

语法分析树的内部节点是分组和确认它们子节点的短语名字。根节点是最抽象的短语名字,在本例中是stat(“statement”的缩写)。语法分析树的叶子节点永远是输入记号。

通过生成语法分析树,语法分析器给应用的其余部分提供了方便的数据结构,它们含有关于语法分析器如何把符号组成短语的完整信息。树是非常容易处理的,并且也能被程序员很好的理解。更好的是,语法分析器能自动地生成语法分析树。

通过操作语法分析树,需要识别相同语言的多个应用能复用同一个语法分析器。当然,你也可以选择直接在语法中嵌入特定应用的代码片段,这是语法分析器生成器传统的做法。ANTLR v4仍然允许这样做,但是语法分析树有助于更简洁更解耦的设计。

语法分析树对于需要多次树遍历的转换也是非常有用的,因为在计算依赖关系的阶段通常会需要前一个阶段的信息。相比于在每个阶段都要准备输入字符,我们只需要遍历语法分析树多次,更具有效率。

我们使用一套规则指定短语:语法分析树子树根节点对应于语法规则名。这里的语法规则对应于上图中assign子树的第一层:

1
assign : ID '=' expr ;    // 匹配赋值语句像"sp = 100"

明白ANTLR如何把这些规则转换为人类可读的语法分析代码是使用和调试语法的基础,可以让我们更深入地挖掘语法分析是如何工作的。

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

ANTLR 4权威参考读书笔记(6)中的这些动作仅仅是提取和打印被语法分析器匹配的值,它们并没有改变语法分析器本身。

实际上,动作还可以影响语法分析器如何识别输入短语。这类特殊的动作被称为语义谓词。下面我们会用一个简单的例子来展示语义谓词的强大能力:动态地打开和关闭语法的某个部分。

使用语义谓词改变语法分析

有一个读入整数序列的语法,它的玄机是由输入的部分指定有多少个整数组合在一起,所以我们必须等到运行时才能知道有多少个整数被匹配。这里是示例输入文件idata.txt的内容:

1
2 9 10 3 1 2 3

第一个数字表示匹配后续两个数字9和10;紧跟着10的数字3表示匹配接下来的三个数字。我们的目的是设计一个语法IData.g,把9和10组合在一起,把1、2和3组合在一起。在语法上执行下面的命令后显示的语法分析树能够清楚地标识出整数的分组,就像下图显示的那样:

1
2
3
antlr -no-listener IData.g
compile *.java
grun IData file -gui idata.txt

idata-parse-tree

要达成这个目标,以下语法中的关键是一个被称为语义谓词的布尔值操作:{$i <= $n}?。当谓词计算结果为true时,语法分析器匹配整数直到超过规则参数n要求的数量;当计算结果为false时,谓词让相关的选项从生成的语法分析器中“消失”。 在这个案例中,值为false的谓词让(...)*循环从规则里终止并返回。

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

file : group+ ;

group: INT sequence[$INT.int] ;

sequence[int n]
locals [int i=1]
     : ( {$i <= $n}? INT {$i++;} )*    // match n integers
     ;

INT  : [0-9]+ ;  // match integers
WS   : [ \t\n\r]+ -> skip ;    // toss out all whitespace

被语法分析器使用的规则sequence的内部语法表示看起来就像下图这样:

idata-rule-sequence

虚线表明谓词可以剪断那条路径,只给语法分析器留下一个选择:退出的路径。

虽然大部分时间我们不需要这样的微管理,但它至少让我们知道我们有这样的武器可以处理病理分析问题。

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 使用更快但稍弱的分析策略。