乐者为王

Do one thing, and do it well.

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

在聚焦到具体的语法规则内部结构之前,我们要先讨论下语法的整体剖析以及如何形成一套初始的语法骨架。

语法文件通常是由一个命名语法的头和一系列可以彼此调用的规则组成。就像下面这样:

1
2
3
4
5
grammar MyG;

rule1 : «stuff» ;
rule2 : «more stuff» ;
...

设计语法就是要搞清楚«stuff»是什么?哪个规则是开始规则。这要求我们需要知道给定语言的一系列代表性的输入例子。当然,从语言参考手册甚至另一个语法分析器生成器格式而来的语法也是有帮助的。

正确设计语法的方法是借鉴功能分解或者自顶向下的设计,从粗粒度级别到细粒度级别逐步定义语言结构并把它们编码为语法规则。所以,我们的第一个任务就是找到粗粒度语言结构的名字,同时它也是开始规则。在英语中我们使用sentence,对于XML文件来说它则是document。

设计开始规则的内容是用英语伪代码描述整个输入格式的问题。例如,“a comma-separated-value (CSV) file is a sequence of rows terminated by newlines.”这段文字,在is a左边的至关重要的单词file是规则名字,在is a右边的所有内容则成为在规则定义右则的«stuff»的内容:

1
file : «a sequence of rows terminated by newlines» ;

然后我们通过描述在开始规则右侧被确定的元素来进行下一个粒度级别的设计。在规则右侧的名词通常是对记号或尚未定义的规则的引用,这些记号是那些我们在正常情况下视为单词、标点符号、运算符的元素。就像单词是英语句子中的原子成分那样,记号在语法规则中也是如此。规则引用则涉及到像row那样需要被分解为更详细部分的其它语言结构。

进入细节的另外一层,我们可以说row是一系列被逗号分隔的field,而field则是一个数字或字符串。就像以下所示:

1
2
row   : «a sequence of fields separated by commas» ;
field : «number or string» ;

当没有规则再需要定义时,我们就得到了语法的一个粗略的草图。

如果有其它格式的语法作为参考的话设计语法会容易的多,但要小心不要盲目地遵循它,否则你会误入歧途的。非ANTLR格式的语法只是让你知道别人是如何决定分解语言中的短语的,它最大的作用就是可以给我们一份规则名称的列表作为参考。

不推荐从参考手册上复制粘贴语法到ANTLR,然后再通过细微的调整让它工作。把它当作一套指南而不是一段代码是更好的办法。为了清晰地描述语法,参考手册通常是相当松散的。这意味着语法能识别大量不在语言中的句子,或者语法可能不够明确,可以用多种方法匹配相同的输入序列。例如,语法可能会说表达式可以调用一个构建器或者访问一个函数,问题是像T(i)这样的输入可以同时匹配两者。理想情况下,在语法中是不能有这样的二义性的,每个输入句子我们只需要一种解释。

在另一个极端,参考手册中的语法有时过于明确地说明了规则。有些约束是需要在分析完输入后实施的,而不是试图对语法结构实施约束。例如,W3C XML语法就显式地指定标签中什么地方必须要有空格以及什么地方的空格可以省略。但事实是我们可以简单地让词法分析器在把记号发送给语法分析器之前去除空格,不需要在语法中到处测试它。

规格还说<?xml ...>标签可以有两个附加属性encoding和standalone。我们需要知道约束,但它是很容易去允许任何属性名字,然后在语法分析后检查语法分析树,以确保所有这些限制都满足的。 归根结底,XML只是嵌在文本中的一对标签,因此它的语法结构是相当直白的。唯一的挑战是如何分别对待什么在标签内以及什么在标签外。

识别语法规则并用伪代码表示它们的右侧部分最初是个挑战,但当你为更多的语言构建语法后它会变得越来越容易。一旦我们有了伪代码,我们就需要把它转换成ANTLR表示法,以便能得到一个可以工作的语法。

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

对于大多数语法而言,注释和空格都是语法分析器可以忽略的东西。如果我们不想让注释和空格在语法中到处都是,那么就需要让词法分析器把它们扔掉。不幸的是,这意味着任何后续的处理步骤都不能再访问注释和空格。保留但忽略注释和空格的秘密是把这些发送给语法分析器的记号放到一个“隐藏通道”中。因为语法分析器只能调谐到单个通道,所以我们可以把任何我们想要的东西传递到其它通道中。这里是如何实现的语法:

1
2
3
4
5
6
COMMENT
    : '/*' .*? '*/' -> channel(HIDDEN)    // match anything between /* and */
    ;

WS  : [ \r\t\n]+    -> channel(HIDDEN)
    ;

就像我们前面讨论过的-> skip那样,-> channel(HIDDEN)也是一个词法分析器指令。在这里,它设置那些记号的通道号码以便它们可以被语法分析器忽略。记号流仍然维护着原始的记号序列,但在传递记号给语法分析器时会略过隐藏通道中的记号。

逻辑题-谁养鱼

  1. 在一条街上,有5座房子,喷了5种颜色。
  2. 每座房子里住着不同国籍的人。
  3. 每个人喝不同的饮料,抽不同品牌的香烟,养不同的宠物。

问题是:谁养鱼?

提示:

  1. 英国人住红色房子。
  2. 瑞典人养狗。
  3. 丹麦人喝茶。
  4. 绿色房子在白色房子左面。
  5. 绿色房子主人喝咖啡。
  6. 抽Pall Mall香烟的人养鸟。
  7. 黄色房子主人抽Dunhill香烟。
  8. 住在中间房子的人喝牛奶。
  9. 挪威人住第一间房子。
  10. 抽Blends香烟的人住在养猫的人隔壁。
  11. 养马的人住抽Dunhill香烟的人隔壁。
  12. 抽Blue Master的人喝啤酒。
  13. 德国人抽Prince香烟。
  14. 挪威人住蓝色房子隔壁。
  15. 抽Blends香烟的人有一个喝水的邻居。

在回答上述问题前先画一个6行5列的表格,从上到下的每一行分别代表房子的顺序(A表示左边第一间房子)、哪国人、房子颜色、饮料、香烟、宠物。下表是问题的初始状态:

A B C D E
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?

根据提示8、9和14可以得到:

A B C D E
挪威人 ? ? ? ?
? 蓝色 ? ? ?
? ? 牛奶 ? ?
? ? ? ? ?
? ? ? ? ?

由提示4和5可以判定房子D的颜色是绿色,房子主人喝咖啡,房子E的颜色是白色。如下表所示:

A B C D E
挪威人 ? ? ? ?
? 蓝色 ? 绿色 白色
? ? 牛奶 咖啡 ?
? ? ? ? ?
? ? ? ? ?

结合提示1、7和11可以知道房子C是红色的,住的是英国人,房子A是黄色的。挪威人抽Dunhill香烟。住房子B的人养马。如下表所示:

A B C D E
挪威人 ? 英国人 ? ?
黄色 蓝色 红色 绿色 白色
? ? 牛奶 咖啡 ?
Dunhill ? ? ? ?
? ? ? ?

依据上表可知,挪威人喝的饮料是水、茶或者啤酒。结合提示3和12可以断定挪威人喝的是水。如下表所示:

A B C D E
挪威人 ? 英国人 ? ?
黄色 蓝色 红色 绿色 白色
? 牛奶 咖啡 ?
Dunhill ? ? ? ?
? ? ? ?

通过提示15可以得出住房子B的人抽Blends香烟。如下表所示:

A B C D E
挪威人 ? 英国人 ? ?
黄色 蓝色 红色 绿色 白色
? 牛奶 咖啡 ?
Dunhill Blends ? ? ?
? ? ? ?

结合提示12可以推断住房子E的人抽Blue Master香烟、喝啤酒。住房子B的人喝茶。如下表所示:

A B C D E
挪威人 ? 英国人 ? ?
黄色 蓝色 红色 绿色 白色
牛奶 咖啡 啤酒
Dunhill Blends ? ? Blue Master
? ? ? ?

由提示3、13得到房子B住的是丹麦人。房子D住的是德国人,抽Prince香烟。如下表所示:

A B C D E
挪威人 丹麦人 英国人 德国人 ?
黄色 蓝色 红色 绿色 白色
牛奶 咖啡 啤酒
Dunhill Blends ? Prince Blue Master
? ? ? ?

再由提示6和10确定住房子C的人抽Pall Mall香烟、养鸟。挪威人养猫。如下表所示:

A B C D E
挪威人 丹麦人 英国人 德国人 ?
黄色 蓝色 红色 绿色 白色
牛奶 咖啡 啤酒
Dunhill Blends Pall Mall Prince Blue Master
? ?

最后结合提示2推断得到房子E住的是瑞典人,养狗。如下表所示:

A B C D E
挪威人 丹麦人 英国人 德国人 瑞典人
黄色 蓝色 红色 绿色 白色
牛奶 咖啡 啤酒
Dunhill Blends Pall Mall Prince Blue Master
?

现在,结果已经出来了:德国人养鱼。

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

现在我们准备构建一个工具,用来把ANTLR 4权威参考读书笔记(7)中idata.txt里的数据按group分行显示,就像这样:

1
2
2 9 10
3 1 2 3

我们可以借助语法分析树的监听器机制来对词法分析结束后生成的记号流进行改写,我们不需要实现每一个监听器接口方法,只需要在捕获到group的时候把换行符插到它末尾就行。实现改写的代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
public class RewriteListener extends IDataBaseListener {
    TokenStreamRewriter rewriter;

    public RewriteListener(TokenStream tokens) {
        rewriter = new TokenStreamRewriter(tokens);
    }

    @Override
    public void enterGroup(IDataParser.GroupContext ctx) {
        rewriter.insertAfter(ctx.stop, '\n');
    }
}

接着就是写一个小程序来调用我们上面的改写类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class IData {

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

        ANTLRInputStream input = new ANTLRInputStream(is);
        IDataLexer lexer = new IDataLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        IDataParser parser = new IDataParser(tokens);
        ParseTree tree = parser.file();

        RewriteListener listener = new RewriteListener(tokens);

        System.out.println("Before Rewriting");
        System.out.println(listener.rewriter.getText());

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

        System.out.println("After Rewriting");
        System.out.println(listener.rewriter.getText());
    }
}

这里的关键是TokenStreamRewriter对象知道如何在不修改流的情况下提供一个记号流的修改过的视图。它把所有的操作方法当作指令并把它们排进队列,等到在遍历记号流把它作为文本渲染回去的时候再执行。每次我们调用getText()时rewriter就会执行那些指令。

最后就是构建和测试应用:

1
2
3
antlr IData.g
compile *.java
run IData idata.txt

以下是输出结果:

1
2
3
4
5
Before Rewriting
29103123
After Rewriting
2910
3123

仅用几行代码,我们就能够没有任何烦恼地对某些内容做轻微的调整。这种策略对于源代码检测或重构这类一般性的问题是非常有效的。TokenStreamRewriter是一个非常强大且有效的操作记号流的工具。

开发者被灯光蒙蔽了双眼

英文原文:http://programmingzen.com/2008/12/30/developers-are-blinded-by-the-light/

Blinded by the light,
revved up like a deuce,
another runner in the night
— Bruce Springsteen

人类在计算几率方面是异常地差。我们有限的经验强烈地影响着我们对事件的可能性的认知。例如,我们往往极大地高估由恐怖袭击、意外枪支走火或者飓风引起死亡的几率,并且极大地低估像坠落、溺水或者流感死亡的原因。其原因是媒体经常提醒我们恐怖主义、飓风的危险或者关于孩子们被意外射杀的瞬间故事。你很少发现关于一个人溺水、坠落或者由于流感死亡的故事在国家新闻频道上被报道。新闻报道有一种倾向是耸人听闻,为的是引起人们的注意和钩住大量的观众,因此当谈到估计什么可能/不可能发生时它们促成人们的偏见。

同样的,在电视和报纸上过度曝光心花怒放的彩票中奖者举起他们超大的支票往往歪曲人们对通过购买一注彩票胜利的可能性的认知。对这个问题持一个严谨和客观的态度将会很快揭露中奖的几率比它们表面上看起来的要差得多。[1]

我注意到这种情况也正在开发/创业的世界里发生。这是一波新的淘金热。太多的开发者正在试图建立下一个大的社交网络,成为下一个Facebook(或YouTube),聚集数以百万计的人群,希望被大公司以一笔数量荒谬的钱收购。媒体喜欢这类故事。

因此,正在试图构建下一个Facebook的开发者类似于彩票买家。他们中的一些人会成功和获胜,但大部分人会惨遭失败。我们真正需要多少社交网络?广告支撑的模式适合某些设法吸引庞大的人群同时保持其费用最低(例如PlentyOfFish)或者被收购(例如YouTube,它也在花Google的钱)的幸运的公司。在这个过程中其他人都是在烧钱以及浪费VC的钱和诚意。

我担心很多开发者被灯光蒙蔽了双眼。他们对获得成功的真实几率的认知受到了媒体连续报道的百万——如果不是10亿——美元收购和成功故事的扭曲。而且有些VC鼓励这种行为,希望能在他们的投资上看到高回报。毕竟这些都是非常富有的人,他们对小规模的成功不感兴趣。

除了明显的浪费时间和资源之外,我认为许多开发者为了追求极不可能的结果放弃了极好的机会。用一个传统商业计划挣1,000万的可能性和按YouTube的方式挣10亿的可能性的比例,与这些金额能负担得起你的不同生活质量不成正比。如果你破产了,有3万美元的信用卡债务,或者你是中产阶级,你会发现1,000万美元可以提高的生活质量总是远远超过从1,000万到10亿能提高的。而且重要的是,我们要认识到瞄准尽管更小,但更有可能的结果不会以任何方式阻止你以后的“伟大梦想”,一旦你的第一次(或者第一次成功的)创业已经取得了成功。

你愿意参加20次有1次胜利机会的100万美元抽奖,还是50,000,000次有1次机会的5亿美元抽奖?理性的人会选择第1个,然而在今天,大部分创业公司都倾向于选择第2个。他们这么做是因为他们极大地高估了他们以第2个抽奖成功的几率。

创建一个产品并让人们为它付费。不要拿VC的钱,除非你真的不考虑依靠自己的力量启动你的公司。软件世界的主要优点之一是在开始的时候极少量的资本需要。如果你想做Web应用,可以使用软件即服务(SaaS)模型,让你的用户为你提供的软件和服务付费。你将会有更加少的受众,更少的可伸缩性问题和费用,以及有更多的收入和更大的盈利机会。Joel Spolsky(和他那华丽的办公空间)挣得数百万收入是因为他的公司在出售一套Web版的bug追踪器。你知道有多少免费的bug追踪器?在这个市场上存在多少竞争对手?我确信有许多。然而,虽然Joel的人气毫无疑问地帮助到了他的公司,但此案例仍然展示了一个企业如何通过构建一个更好的产品而成功。

就像David Heinemeier Hansson提及的,有无数不受关注的公司在像那样挣钱。[2]如果你把视线从聚光灯上移开,你将看到许多公司在它们所做的事情上面非常成功,尽管它们不出名或者没有制造新闻头条。它们中的有些公司实际上努力不去吸引太多的关注到它们的成功上(经常用数百万美元来衡量),以便防止竞争对手的涌现。

不管你的名字是不是家喻户晓,你甚至不必创建Web应用才能非常成功。你可能会想到为智能手机包括iPhone开发移动应用。但是良好的老式桌面应用让各种各样的软件公司继续发展。这就是为什么“你不能再用商业桌面软件挣钱,或者桌面应用都死了”的扭曲的认知太荒谬的原因。作为开发者/微型ISV/创业公司,你用良好设计的桌面软件挣钱的机会远远高于构建任何一款YouTube、Flickr或者Facebook复制品的机会。

要了解我们的认知是怎么被扭曲的,你只需要和那些公开分享它们软件销售统计的公司交谈。你将会被用相对普通的软件挣到钱的数额震惊。Balsamiq制作了一款UI草图应用卖79美元。作者成功挣到了10万美元收入在前5个月,大部分是通过销售应用的桌面版本。在这个产业里他当然远非最大的赢家之一。我提到这个不过是因为它表明那是一个非常不错的想法,很好执行,当你让你的用户付费时能很快带来收入。如果你认为在5个月里10万美元很少,那我来问你有多少免费网站达成一个类似的每月收入净额。如果你正在寻找更大的收入,了解下Omni Graffle,它给Omni Group赚取了数百万美元,或者把你的目光放到B2B应用上(在那个市场里某些应用卖上千美元一份)。

当许多开发者被灯光蒙蔽了双眼的时候,有创业想法的智者正在建立真正的软件业务。我请你走出来做同样的事情。

脚注

[1] 我在这里总结的概念被Dan Gilbert在这个TED演讲里更详细地说明了。

[2] David Heinemeier Hansson在他的一篇帖子中持类似的观点,该帖给了本文以灵感。

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

  • sentinel 哨兵
  • tag 标签

目前我们看到的输入文件都只包含一种语言,但在实际应用中我们可能会遇到某些包含多种语言的文件格式。例如,Java的文档注释,XML文件等。这些环绕着模板表达式的文本需要不同的处理方式,它们被称为孤岛语言。

ANTLR有提供一个称之为“词法模型”的词法分析器特性,它让我们可以很容易地处理包含混合格式的文件。基本思路是:当词法分析器看到特殊的哨兵字符序列时,就让它在模式之间来回切换。

XML是个很好的例子,它通常会在同一个文件中包含不同的词法结构。一个XML语法分析器会把除标签和实体引用(例如&hearts;)之外的任何东西当作文本块。当词法分析器看到<时,它切换到INSIDE模式;当它看到>/>时,就切换回默认模式。以下的语法展示了该特性是如何工作的:

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

// Default "mode": Everything OUTSIDE of a tag
OPEN        :   '<'                 -> pushMode(INSIDE) ;
COMMENT     :   '<!--' .*? '-->'    -> skip ;
EntityRef   :   '&' [a-z]+ ';' ;
TEXT        :   ~('<'|'&')+ ;    // match any 16 bit char minus < and &

// ----------------- Everything INSIDE of a tag ---------------------
mode INSIDE;

CLOSE       :   '>'                 -> popMode ;    // back to default mode
SLASH_CLOSE :   '/>'                -> popMode ;
EQUALS      :   '=' ;
STRING      :   '"' .*? '"' ;
SlashName   :   '/' Name ;
Name        :   ALPHA (ALPHA|DIGIT)* ;
S           :   [ \t\r\n]           -> skip ;

fragment
ALPHA       :   [a-zA-Z] ;

fragment
DIGIT       :   [0-9] ;

把上述语法保存为XMLLexer.g文件,然后使用包含以下内容的t.xml文件作为输入来测试它:

1
2
3
<tools>
  <tool name="ANTLR">A parser generator</tool>
</tools>

以下是构建和运行测试的命令:

1
2
3
antlr XMLLexer.g
compile *.java
grun XML tokens -tokens t.xml

这里是输出的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[@0,0:0='<',<1>,1:0]
[@1,1:5='tools',<10>,1:1]
[@2,6:6='>',<5>,1:6]
[@3,7:10='\r\n  ',<4>,1:7]
[@4,11:11='<',<1>,2:2]
[@5,12:15='tool',<10>,2:3]
[@6,17:20='name',<10>,2:8]
[@7,21:21='=',<7>,2:12]
[@8,22:28='"ANTLR"',<8>,2:13]
[@9,29:29='>',<5>,2:20]
[@10,30:47='A parser generator',<4>,2:21]
[@11,48:48='<',<1>,2:39]
[@12,49:53='/tool',<9>,2:40]
[@13,54:54='>',<5>,2:45]
[@14,55:56='\r\n',<4>,2:46]
[@15,57:57='<',<1>,3:0]
[@16,58:63='/tools',<9>,3:1]
[@17,64:64='>',<5>,3:7]
[@18,65:66='\r\n',<4>,3:8]
[@19,67:66='<EOF>',<-1>,4:0]

上面输出的每一行代表一个记号,包含记号索引、开始和结束字符、记号文本、记号类型,最后的行和字符位置则告诉我们词法分析器如何标记化输入。

在命令行中,XML tokens序列处通常是一个语法名字后面跟着开始规则,但在这里,我们使用语法名字后面跟着特殊的规则名字tokens来告诉TestRig应该运行词法分析器而不是语法分析器。接着使用选项-tokens打印出匹配的记号列表。

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

为制作语言应用,我们必须为每个输入短语或子短语执行一些适当的代码,那样做最简单的方法是操作由语法分析器自动创建的语法分析树。

早些时候我们已经学习了词法分析器处理字符和把记号传递给语法分析器,然后语法分析器分析语法和创建语法分析树的相关知识。对应的ANTLR类分别是CharStream、Lexer、Token、Parser和ParseTree。连接词法分析器和语法分析器的管道被称为TokenStream。下图说明了这些类型的对象如何连接到内存中其它的对象。

这些ANTLR数据结构共享尽可能多的数据以便节省内存的需要。上图显示在语法分析树中的叶子(记号)节点含有在记号流中记号的点。记号记录开始和结束字符在CharStream中的索引,而不是复制子串。这里没有与空格字符有关的记号,因为我们假设我们的词法分析器扔掉了空格。

下图显示的是ParseTree的子类RuleNode和TerminalNode以及它们所对应的子树根节点和叶子节点。RuleNode包含有方法如getChild()和getParent()等,但RuleNode并不专属于特定语法所有。为了能更好地访问在特定节点中的元素,ANTLR为每个规则生成一个RuleNode的子类。下图显示了赋值语句例子的子树根节点的特定类,它们是StatContext、AssignContext和ExprContext:

它们记录了通过规则对短语识别的每件事情,所以被称为上下文对象。每个上下文对象都知道被识别短语的开始和结束记号以及提供对所有短语的元素的访问。例如,AssignContext提供方法ID()和expr()去访问标志符节点和表达式子树。

给出了具体类型的描述后,我们可以手工编写代码去执行树的深度优先遍历。当我们发现和完成节点时我们可以执行任何我们想要的动作。典型的动作是诸如计算结果,更新数据结构,或者生成输出。相比每次为每个应用编写同样的树遍历样板代码,使用ANTLR自动生成的树遍历机制更方便、更容易。

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

一个模棱两可的短语或句子通常是指它有不止一种解释。换句话说,短语或句子能匹配不止一种语法结构。要解释或转换一个短语,程序必须要能唯一地确认它的含义,这意味着我们必须提供无歧义的语法,以便生成的语法分析器能用明确的一个方法匹配每个输入短语。

在这里,让我们展示一些有歧义的语法以便让二义性的概念更具体。如果你以后在构建语法时陷入二义性,你可以参考本节的内容。

一些明显有歧义的语法:

1
2
3
4
5
6
7
assign
    : ID '=' expr    // 匹配一个赋值语句,例如f()
    | ID '=' expr    // 前面选项的精确复制
    ;

expr
    : INT ;

大多数时候二义性是不明显的,就像下面的语法,它能通过规则stat的两个选项匹配函数调用:

1
2
3
4
5
6
7
8
9
stat
    : expr          // 表达式语句
    | ID '(' ')'    // 函数调用语句
    ;

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

这里是输入f()的两个解释,从规则stat开始:

左边的语法分析树显示f()匹配规则expr。右边的语法分析树显示f()匹配规则stat的第二个选项。

因为大部分语言它们的语法都被设计成无歧义的,有歧义的语法类似于编程缺陷,所以我们需要识别语法并为每个输入短语提交单一选择给语法分析器。如果语法分析器发现一个有歧义的短语,它必须选一个可行的选项。ANTLR通过选择涉及决定的第一个选项解决二义性。在本例中,语法分析器将选择与左边的语法分析树有关的f()的解释。

二义性可以发生在词法分析器中也能发生在语法分析器中,但ANTLR可以自动地解决它们。ANTLR通过使输入字符串和语法中第一个指定的词法规则匹配来解决词法二义性。为了明白这是如何工作的,让我们看看对大部分编程语言都很普遍的二义性:在关键字和标志符规则中的二义性。关键字begin(后面有个非字母)也是标志符,至少词法上,因此词法分析器可以匹配b-e-g-i-n到两者中的任何一个规则。

1
2
BEGIN : 'begin' ;    // 匹配b-e-g-i-n序列,即把二义性解析为BEGIN
ID    : [a-z]+ ;     // 匹配一个或多个任意小写字母

注意,词法分析器会试着为每个记号尽可能匹配最长的字符串,这意味着输入beginner将仅仅匹配规则ID。词法分析器不会把beginner匹配成BEGIN然后ID匹配输入ner。

有时候语言的语法就明显有歧义,没有任何的语法重组能改变这个事实。例如,算术表达式的自然语法可以用两种方式解释像1+2*3这样的输入,要么从左到右执行运算符,要么像大部分语言那样按优先级顺序。

C语言展示了另一种二义性,但我们可以使用上下文信息比如标志符如何被定义来解决它。考虑代码片段i*j;。在语法上,它看起来像是一个表达式,但它的含义或者语义依赖i是类型名还是变量。如果i是类型名,那么这个片段不是表达式,而是一个声明为指向类型i的指针变量j。

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

  • predication 断定
  • predict 预判
  • lookahead 预读

ANTLR工具根据语法规则,例如我们刚才看到的assign,生成递归下降语法分析器。递归下降语法分析器只是递归方法的一个集合,每个规则一个方法。下降这个术语指的是分析从语法分析树的根开始向着叶子进行(记号)。我们首先调用的规则,即stat符号,成为语法分析树的根。那也就意味着对ANTLR 4权威参考读书笔记(8)中的语法分析树来说需要调用方法stat()。这类分析更通用的术语是自顶向下分析:递归下降语法分析器仅仅是自顶向下语法分析器实现的一种。

要了解递归下降语法分析器是什么样子,可以看看下面ANTLR为规则assign生成的方法(稍微做过整理):

1
2
3
4
5
6
// assign : ID '=' expr ;
void assign() {    // 根据规则assign生成的方法
    match(ID);     // 比较ID和当前输入符号然后消费
    match('=');
    expr();        // 通过调用expr()匹配表达式
}

递归下降语法分析器最酷的部分是通过跟踪调用方法stat()、assign()和expr()绘制出的调用关系图反映了内部的语法分析树节点。match()的调用对应语法分析树叶子。为了在一个手工构建的语法分析器中手动构建一颗语法分析树,我们需要在每个规则方法的开始处插入“添加新子树根”操作,以及给match()一个“添加新叶子节点”操作。

方法assign()只是检查确保所有必要的记号存在且以正确的顺序。当语法分析器进入assign()时,它不必在多个选项之间进行选择。选项是规则定义右边的选择之一。例如,调用assign的stat规则可能有其它类型的语句。

1
2
3
4
5
6
7
/** 匹配起始于当前输入位置的任何语句 */
stat
    : assign    // 第一个选项('|'是选项分隔符)
    | ifstat    // 第二个选项
    | whilestat
    ...
    ;

stat的分析规则看起来像一条switch语句:

1
2
3
4
5
6
7
8
9
void stat() {
    switch ( «current input token» ) {
        CASE ID : assign(); break;
        CASE IF : ifstat(); break;    // IF是关键字'if'的记号类型
        CASE WHILE : whilestat(); break;
        ...
        default : «raise no viable alternative exception»
    }
}

方法stat()必须通过检查下一个输入记号作出分析决定或断定。分析决定预判哪一个选项将会成功。在本例中,当看到WHILE关键字时会预判是规则stat的第三个选项。规则方法stat()然后就会调用whilestat()。你以前可能听说过术语预读记号,那只是下一个输入记号。预读记号可以是语法分析器在匹配和消费输入记号之前嗅探的任何记号。

有时候,语法分析器需要一些预读记号去预判哪个选项会成功。它甚至必须考虑从当前位置直到文件结尾的所有的记号。ANTLR默默地为你处理所有的这些事情,但是对决策过程有个基本的了解是有帮助的,可以让调试生成的语法分析器更容易。

为更好地理解分析决定,想象有一个单一入口和单一出口的迷宫,有单词写在地板上。每个沿着从入口到出口路径的单词序列表示一个句子。迷宫的结构与定义一门语言的语法规则类似。为测试一个句子在一门语言中的成员身份,我们在穿越迷宫时把句子的单词和沿着地板的单词作比较。如果通过句子的单词我们能到达出口,那么句子就是有效的。

为了通过迷宫,我们必须在每个岔口选择一条有效路径,正如我们必须在语法分析器中选择选项一样。通过把我们句子中下一个单词(们)和沿着来自每个岔口的每条路径上可见的单词比较,我们做出决定该走哪条路。我们能从岔口看到的单词与预读记号类似。当每条路径以唯一的单词开始时决定是相当容易的。在规则stat中,每个选项从唯一的记号开始,因此stat()可以通过查看第一个预读记号识别选项。

当单词从一个岔口重叠部分开始每条路径时,语法分析器需要继续往前看,扫描可以识别选项的单词。ANTLR可以根据需要为每个分析决定自动上下调节预读数量。如果预读的结果是多条同样的到出口的路径,那说明当前的输入短语有多种解释,这会导致二义性。

贫富差距精简版

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

2016年1月

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

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

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

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

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

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

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

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

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

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

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