RednaxelaFX
- 浏览: 3023452 次
- 性别:
- 来自: 海外
-
文章分类
- 全部博客 (430)
- Programming Languages (23)
- Compiler (20)
- Virtual Machine (57)
- Garbage Collection (4)
- HotSpot VM (26)
- Mono (2)
- SSCLI Rotor (1)
- Harmony (0)
- DLR (19)
- Ruby (28)
- C# (38)
- F# (3)
- Haskell (0)
- Scheme (1)
- Regular Expression (5)
- Python (4)
- ECMAScript (2)
- JavaScript (18)
- ActionScript (7)
- Squirrel (2)
- C (6)
- C++ (10)
- D (2)
- .NET (13)
- Java (86)
- Scala (1)
- Groovy (3)
- Optimization (6)
- Data Structure and Algorithm (3)
- Books (4)
- WPF (1)
- Game Engines (7)
- 吉里吉里 (12)
- UML (1)
- Reverse Engineering (11)
- NSIS (4)
- Utilities (3)
- Design Patterns (1)
- Visual Studio (9)
- Windows 7 (3)
- x86 Assembler (1)
- Android (2)
- School Assignment / Test (6)
- Anti-virus (1)
- REST (1)
- Profiling (1)
- misc (39)
- NetOA (12)
- rant (6)
- anime (5)
- Links (12)
- CLR (7)
- GC (1)
- OpenJDK (2)
- JVM (4)
- KVM (0)
- Rhino (1)
- LINQ (2)
- JScript (0)
- Nashorn (0)
- Dalvik (1)
- DTrace (0)
- LLVM (0)
- MSIL (0)
最新评论
-
mldxs：
虽然很多还是看不懂，写的很好！
虚拟机随谈（一）：解释器，树遍历解释器，基于栈与基于寄存器，大杂烩 -
HanyuKing：
Java的多维数组 -
funnyone：
Java 8的default method与method resolution -
ljs_nogard：
Xamarin workbook - .Net Core 中不 ...
LINQ的恶搞…… -
txm119161336：
allocatestlye1 顺序为 // Fields o ...
最近做的两次Java/JVM分享的概要
这几天在休假在家，有空的时候在用ANTLR 3.2来写D 2.0的语法。每次用ANTLR写比较大的语言的语法时都会碰到不少问题，这次也不例外；其中有一处虽然很快就解决了，但还是值得一记。
话说用ANTLR写语法最经常碰到的问题就是很多语言规范都是用LR语法写的，但ANTLR是LL的，要自己做LR到LL的变换，然后经常为了迁就left-factoring最终写出来的语法跟原本规范里的语法看起来会比较不同；而D语言官网文档里的语法写得乱七八糟更使得这工作进行得不顺利。
这次要记的主要是给子规则做迭代匹配时设定额外配置项（options { greedy = false; }）的注意点。
---------------------------------------------------------------------------
先从正常的情况开始看。例如说我们要写一个匹配C风格的行注释的词法规则，可以这样写：
对应的自动机图：
在ANTLR中，词法规则的名字的首字母必须是大写的。上面两条词法规则的意思是：一个Comment由以下几个元素构成：
1、1个行注释的起始标记，“//”
2、0或多个非'\n'或'\r'的字符（ANTLR语法中，~是“非”，“|”是或，“*”是0到多个，“+”是1到多个，“?”是0或1个，括号是分组用的）
3、1个换行符
其中换行符写成了一个子规则EndOfLine，又包含三种可能性。注意到EndOfLine被fragment关键字修饰，说明它只能被用作别的词法规则的子规则，而不能用于单独匹配出一个token。
在上面的词法规则中，*之所以能正确的迭代，是因为它迭代的内容与它后面的规则的起始字符没有交集——迭代的内容只能是除了'\n'或'\r'以外的内容，而EndOfLine只能以'\n'或'\r'开始，所以迭代总是会在最近的一个换行符出现的地方停止。
ANTLR的Java后端为上面的词法规则生成的lexer代码是（经过简单编辑/格式化，下同）：
代码中input.LA(n)是向前看第n个位置上的字符的意思。input.LA(1)是接下来要马上匹配的字符，input.LA(2)是下一个，以此类推。
上面的代码中input.LA(n)的n最大值是2，也就是说为了匹配这条词法规则，最多只需要向前看两个字符。
如果用Ruby的正则表达式来表示上面的行注释词法规则，则是：
简单演示一下：
---------------------------------------------------------------------------
如果要匹配的是C风格的块注释的话，可以把上面的词法规则变为：
对应的自动机图：
C风格的块注释以'/*'开始，以最近的一个'*/'结束，不能嵌套；在/*与*/之间可以是任意多个任意字符。也简单的写为：
ANTLR的迭代运算符，“*”与“+”默认都是“贪婪的”，也就是会取最长匹配；这里我们要的是匹配“最近的一个'*/'”，要的是最短匹配，于是ANTLR默认的匹配方式就不满足需求了。为了解决这个问题，ANTLR提供了options { greedy = false; }语法来指定某个迭代子规则中使用最短匹配，同时也把“.*”与“.+”作为特例，在这两种情况下自动使用最短匹配，如果这两种情况下需要最长匹配需要显式指定options { greedy = true; }。
ANTLR的Java后端为使用了最短匹配版本的块注释词法规则生成的lexer代码如下：
留意到这段匹配代码在循环中一发现'*/'就会选择退出循环。
也留意到上面的代码中input.LA(n)的n最大值是2，也就是说为了匹配这条词法规则，最多只需要向前看两个字符。
而相应的，使用最长匹配的版本，生成的代码则是：
与前一版不同，这个版本的代码中input.LA(n)的n最大值是3，也就是说为了匹配这条词法规则，最多需要向前看三个字符。不同之处在于：即便循环中已经发现了'*/'，如果进一步发现后面还没到输入字符流的末尾，则继续循环匹配下去，试图找到最长匹配。
如果用Ruby的正则表达式来表示上面的最短匹配版的块注释词法规则，则是：
留意到中间匹配任意个任意字符用的是 .*? 而不是 .* ，因为Ruby的正则表达式里 * 是用最长匹配而 *? 是用最短匹配。
简单演示一下：
---------------------------------------------------------------------------
好吧，前面码了那么多字其实还没进入正题，现在赶紧跳回来。
在D语言中，除了上述两种C风格的注释外，还支持一种“嵌套注释”，以配对的'/+'和'+/'来标记其起始与终结。例如说：
这个语句在经过解析、抛弃掉注释后，等同于：
官网文档对此给出的词法规则是：
把这个LR规则简单转换为LL规则，用ANTLR的语法表示为：
（为方便起见，在ANTLR规则里添加了一个顶层词法规则Comment，而把原本的三条词法规则标记为fragment）
一眼看上去貌似没啥问题了，但实际用这样生成的lexer来匹配D语言源码时会发现无法正确匹配嵌套注释。
那么观察一下ANTLR的Java后端生成的lexer代码：
可以看到 mNestingBlockCommentCharacters() 方法的循环是只要未遇到输入字符流的末尾就会继续循环匹配下去，跟前面讲解块注释的最长匹配版一样。但这里我们需要的是最短匹配。想起ANTLR提供了options { greedy = false; }，这里不是正好派上用场么？
把词法规则改为：
这会儿可好，ANTLR直接不肯生成出lexer了，抱怨词法规则有错：
问题出在哪里呢？这就是这帖真正的主题了：ANTLR 3.2的options语法只能管其所在的子规则“字面上”出现的选择结构；指定用最短匹配后ANTLR不知道NestingBlockCommentCharacters能匹配什么了，也不知道最短匹配应该以什么来标志结束，直接报个错。
解决的办法也很简单，只要把选择结构以字面量形式写到迭代中，并且把最短匹配与它后面的内容写在同一条大规则里，就好了，如下：
对应生成的代码是：
看，这次循环里的匹配逻辑就变回我们所需要的了：一遇到'+/'就退出循环。
这种嵌套规则其实已经超出了正则语法及其对应的有限状态自动机的计算能力，需要使用上下文无关语法/下推式自动机（PDA）才可以处理。ANTLR生成的lexer与parser都是递归下降式的，lexer自身具有PDA级别的能力（加上断言就比PDA更强），所以可以正确处理嵌套规则。
所以这个例子就没办法用Ruby的正则表达式来对比了。好吧Ruby的正则表达式本身已经超出DFA的范围了，不过还没达到PDA的范围
用Perl 6的rule倒是能表示出来，不过那个已经远远不是正则表达式了……这里不深入了。
---------------------------------------------------------------------------
于是ANTLR想告诉我们的是：别把规则分得太细了……
嗯顶你个肺不休假在公司做俯卧撑
话说用ANTLR写语法最经常碰到的问题就是很多语言规范都是用LR语法写的，但ANTLR是LL的，要自己做LR到LL的变换，然后经常为了迁就left-factoring最终写出来的语法跟原本规范里的语法看起来会比较不同；而D语言官网文档里的语法写得乱七八糟更使得这工作进行得不顺利。
这次要记的主要是给子规则做迭代匹配时设定额外配置项（options { greedy = false; }）的注意点。
---------------------------------------------------------------------------
先从正常的情况开始看。例如说我们要写一个匹配C风格的行注释的词法规则，可以这样写：
Comment
: '//' ~( '\n' | '\r' )* EndOfLine
;
fragment
EndOfLine
: '\n'
| '\r'
| '\r\n'
;
对应的自动机图：
在ANTLR中，词法规则的名字的首字母必须是大写的。上面两条词法规则的意思是：一个Comment由以下几个元素构成：
1、1个行注释的起始标记，“//”
2、0或多个非'\n'或'\r'的字符（ANTLR语法中，~是“非”，“|”是或，“*”是0到多个，“+”是1到多个，“?”是0或1个，括号是分组用的）
3、1个换行符
其中换行符写成了一个子规则EndOfLine，又包含三种可能性。注意到EndOfLine被fragment关键字修饰，说明它只能被用作别的词法规则的子规则，而不能用于单独匹配出一个token。
在上面的词法规则中，*之所以能正确的迭代，是因为它迭代的内容与它后面的规则的起始字符没有交集——迭代的内容只能是除了'\n'或'\r'以外的内容，而EndOfLine只能以'\n'或'\r'开始，所以迭代总是会在最近的一个换行符出现的地方停止。
ANTLR的Java后端为上面的词法规则生成的lexer代码是（经过简单编辑/格式化，下同）：
// $ANTLR start "Comment"
public final void mComment() throws RecognitionException {
int _type = Comment;
int _channel = DEFAULT_TOKEN_CHANNEL;
// D:\\GrammarDemo\\T.g:4:5: ( '//' (~ ( '\\n' | '\\r' ) )* EndOfLine )
// D:\\GrammarDemo\\T.g:4:9: '//' (~ ( '\\n' | '\\r' ) )* EndOfLine
match("//");
// D:\\GrammarDemo\\T.g:4:14: (~ ( '\\n' | '\\r' ) )*
loop1:
do {
int alt1=2;
int LA1_0 = input.LA(1);
if ( (LA1_0 >= '\u0000' && LA1_0 <= '\t')
|| (LA1_0 >= '\u000B' && LA1_0 <= '\f')
|| (LA1_0 >= '\u000E' && LA1_0 <= '\uFFFF') ) {
alt1=1;
}
switch (alt1) {
case 1 :
// D:\\GrammarDemo\\T.g:4:14: ~ ( '\\n' | '\\r' )
if ( (input.LA(1) >= '\u0000' && input.LA(1) <= '\t')
|| (input.LA(1) >= '\u000B' && input.LA(1) <= '\f')
|| (input.LA(1) >= '\u000E' && input.LA(1) <= '\uFFFF') ) {
input.consume();
} else {
MismatchedSetException mse = new MismatchedSetException(null, input);
recover(mse);
throw mse;
}
break;
default :
break loop1;
}
} while (true);
mEndOfLine();
state.type = _type;
state.channel = _channel;
}
// $ANTLR end "Comment"
// $ANTLR start "EndOfLine"
public final void mEndOfLine() throws RecognitionException {
// D:\\GrammarDemo\\T.g:10:5: ( '\\r' | '\\n' | '\\r\\n' )
int alt2 = 3;
int LA2_0 = input.LA(1);
if ( (LA2_0 == '\r') ) {
int LA2_1 = input.LA(2);
if ( (LA2_1 == '\n') ) {
alt2 = 3;
} else {
alt2 = 1;
}
} else if ( (LA2_0 == '\n') ) {
alt2 = 2;
} else {
throw new NoViableAltException("", 2, 0, input);
}
switch (alt2) {
case 1 :
// D:\\GrammarDemo\\T.g:10:9: '\\r'
match('\r');
break;
case 2 :
// D:\\GrammarDemo\\T.g:11:9: '\\n'
match('\n');
break;
case 3 :
// D:\\GrammarDemo\\T.g:12:9: '\\r\\n'
match("\r\n");
break;
}
}
// $ANTLR end "EndOfLine"
代码中input.LA(n)是向前看第n个位置上的字符的意思。input.LA(1)是接下来要马上匹配的字符，input.LA(2)是下一个，以此类推。
上面的代码中input.LA(n)的n最大值是2，也就是说为了匹配这条词法规则，最多只需要向前看两个字符。
如果用Ruby的正则表达式来表示上面的行注释词法规则，则是：
%r{//[^\r\n]*(?:\r\n?|\n)}m
简单演示一下：
irb(main):001:0> s = "abc //\ndef //ghi\r\njkl"
=> "abc //\ndef //ghi\r\njkl"
irb(main):002:0> r = %r{//[^\r\n]*(?:\r\n?|\n)}m
=> /\/\/[^\r\n]*(?:\r\n?|\n)/m
irb(main):003:0> s.scan(r)
=> ["//\n", "//ghi\r\n"]
---------------------------------------------------------------------------
如果要匹配的是C风格的块注释的话，可以把上面的词法规则变为：
Comment
: '/*' ( options { greedy = false; } : . )* '*/'
;
对应的自动机图：
C风格的块注释以'/*'开始，以最近的一个'*/'结束，不能嵌套；在/*与*/之间可以是任意多个任意字符。也简单的写为：
Comment
: '/*' .* '*/'
;
ANTLR的迭代运算符，“*”与“+”默认都是“贪婪的”，也就是会取最长匹配；这里我们要的是匹配“最近的一个'*/'”，要的是最短匹配，于是ANTLR默认的匹配方式就不满足需求了。为了解决这个问题，ANTLR提供了options { greedy = false; }语法来指定某个迭代子规则中使用最短匹配，同时也把“.*”与“.+”作为特例，在这两种情况下自动使用最短匹配，如果这两种情况下需要最长匹配需要显式指定options { greedy = true; }。
ANTLR的Java后端为使用了最短匹配版本的块注释词法规则生成的lexer代码如下：
// $ANTLR start "Comment"
public final void mComment() throws RecognitionException {
int _type = Comment;
int _channel = DEFAULT_TOKEN_CHANNEL;
// D:\\GrammarDemo\\T.g:4:5: ( '/*' ( options {greedy=false; } : . )* '*/' )
// D:\\GrammarDemo\\T.g:4:9: '/*' ( options {greedy=false; } : . )* '*/'
match("/*");
// D:\\GrammarDemo\\T.g:4:14: ( options {greedy=false; } : . )*
loop1:
do {
int alt1 = 2;
int LA1_0 = input.LA(1);
if ( (LA1_0 == '*') ) {
int LA1_1 = input.LA(2);
if ( (LA1_1 == '/') ) {
alt1 = 2;
} else if ( (LA1_1 >= '\u0000' && LA1_1 <= '.')
|| (LA1_1 >= '0' && LA1_1 <= '\uFFFF') ) {
alt1 = 1;
}
} else if ( (LA1_0 >= '\u0000' && LA1_0 <= ')')
|| (LA1_0 >= '+' && LA1_0 <= '\uFFFF') ) {
alt1 = 1;
}
switch (alt1) {
case 1 :
// D:\\GrammarDemo\\T.g:4:46: .
matchAny();
break;
default :
break loop1;
}
} while (true);
match("*/");
state.type = _type;
state.channel = _channel;
}
// $ANTLR end "Comment"
留意到这段匹配代码在循环中一发现'*/'就会选择退出循环。
也留意到上面的代码中input.LA(n)的n最大值是2，也就是说为了匹配这条词法规则，最多只需要向前看两个字符。
而相应的，使用最长匹配的版本，生成的代码则是：
// $ANTLR start "Comment"
public final void mComment() throws RecognitionException {
int _type = Comment;
int _channel = DEFAULT_TOKEN_CHANNEL;
// D:\\GrammarDemo\\T.g:5:5: ( '/*' ( options {greedy=true; } : . )* '*/' )
// D:\\GrammarDemo\\T.g:5:9: '/*' ( options {greedy=true; } : . )* '*/'
match("/*");
// D:\\GrammarDemo\\T.g:5:14: ( options {greedy=true; } : . )*
loop1:
do {
int alt1 = 2;
int LA1_0 = input.LA(1);
if ( (LA1_0 == '*') ) {
int LA1_1 = input.LA(2);
if ( (LA1_1 == '/') ) {
int LA1_3 = input.LA(3);
if ( (LA1_3 >= '\u0000' && LA1_3 <= '\uFFFF') ) {
alt1 = 1;
}
} else if ( (LA1_1 >= '\u0000' && LA1_1 <= '.')
|| (LA1_1 >= '0' && LA1_1 <= '\uFFFF') ) {
alt1 = 1;
}
} else if ( (LA1_0 >= '\u0000' && LA1_0 <= ')')
|| (LA1_0 >= '+' && LA1_0 <= '\uFFFF') ) {
alt1 = 1;
}
switch (alt1) {
case 1 :
// D:\\GrammarDemo\\T.g:5:45: .
matchAny();
break;
default :
break loop1;
}
} while (true);
match("*/");
state.type = _type;
state.channel = _channel;
}
// $ANTLR end "Comment"
与前一版不同，这个版本的代码中input.LA(n)的n最大值是3，也就是说为了匹配这条词法规则，最多需要向前看三个字符。不同之处在于：即便循环中已经发现了'*/'，如果进一步发现后面还没到输入字符流的末尾，则继续循环匹配下去，试图找到最长匹配。
如果用Ruby的正则表达式来表示上面的最短匹配版的块注释词法规则，则是：
%r{/\*.*?\*/}m
留意到中间匹配任意个任意字符用的是 .*? 而不是 .* ，因为Ruby的正则表达式里 * 是用最长匹配而 *? 是用最短匹配。
简单演示一下：
irb(main):001:0> s = "abc /* def */ ghi */"
=> "abc /* def */ ghi */"
irb(main):002:0> r = %r{/\*.*?\*/}m
=> /\/\*.*?\*\//m
irb(main):003:0> s.scan(r)
=> ["/* def */"]
---------------------------------------------------------------------------
好吧，前面码了那么多字其实还没进入正题，现在赶紧跳回来。
在D语言中，除了上述两种C风格的注释外，还支持一种“嵌套注释”，以配对的'/+'和'+/'来标记其起始与终结。例如说：
a = /+ some comment /+ some nesting comment +/ ... +/ 1;
这个语句在经过解析、抛弃掉注释后，等同于：
a = 1;
官网文档对此给出的词法规则是：
NestingBlockComment:
/+ NestingBlockCommentCharacters +/
NestingBlockCommentCharacters:
NestingBlockCommentCharacter
NestingBlockCommentCharacter NestingBlockCommentCharacters
NestingBlockCommentCharacter:
Character
NestingBlockComment
把这个LR规则简单转换为LL规则，用ANTLR的语法表示为：
Comment
: NestingBlockComment
;
fragment
NestingBlockComment
: '/+' NestingBlockCommentCharacters '+/'
;
fragment
NestingBlockCommentCharacters
: NestingBlockCommentCharacter*
;
fragment
NestingBlockCommentCharacter
: NestingBlockComment
| .
;
（为方便起见，在ANTLR规则里添加了一个顶层词法规则Comment，而把原本的三条词法规则标记为fragment）
一眼看上去貌似没啥问题了，但实际用这样生成的lexer来匹配D语言源码时会发现无法正确匹配嵌套注释。
那么观察一下ANTLR的Java后端生成的lexer代码：
// $ANTLR start "Comment"
public final void mComment() throws RecognitionException {
int _type = Comment;
int _channel = DEFAULT_TOKEN_CHANNEL;
// D:\\GrammarDemo\\T.g:4:5: ( NestingBlockComment )
// D:\\GrammarDemo\\T.g:4:9: NestingBlockComment
mNestingBlockComment();
state.type = _type;
state.channel = _channel;
}
// $ANTLR end "Comment"
// $ANTLR start "NestingBlockComment"
public final void mNestingBlockComment() throws RecognitionException {
// D:\\GrammarDemo\\T.g:9:5: ( '/+' NestingBlockCommentCharacters '+/' )
// D:\\GrammarDemo\\T.g:9:9: '/+' NestingBlockCommentCharacters '+/'
match("/+");
mNestingBlockCommentCharacters();
match("+/");
}
// $ANTLR end "NestingBlockComment"
// $ANTLR start "NestingBlockCommentCharacters"
public final void mNestingBlockCommentCharacters() throws RecognitionException {
// D:\\GrammarDemo\\T.g:14:5: ( ( NestingBlockCommentCharacter )* )
// D:\\GrammarDemo\\T.g:14:9: ( NestingBlockCommentCharacter )*
loop1:
do {
int alt1 = 2;
int LA1_0 = input.LA(1);
if ( (LA1_0 >= '\u0000' && LA1_0 <= '\uFFFF') ) {
alt1 = 1;
}
switch (alt1) {
case 1 :
// D:\\GrammarDemo\\T.g:14:9: NestingBlockCommentCharacter
mNestingBlockCommentCharacter();
break;
default :
break loop1;
}
} while (true);
}
// $ANTLR end "NestingBlockCommentCharacters"
// $ANTLR start "NestingBlockCommentCharacter"
public final void mNestingBlockCommentCharacter() throws RecognitionException {
// D:\\GrammarDemo\\T.g:19:5: ( NestingBlockComment | . )
int alt2 = 2;
int LA2_0 = input.LA(1);
if ( (LA2_0 == '/') ) {
int LA2_1 = input.LA(2);
if ( (LA2_1 == '+') ) {
alt2 = 1;
} else {
alt2 = 2;
}
} else if ( (LA2_0 >= '\u0000' && LA2_0 <= '.')
|| (LA2_0 >= '0' && LA2_0 <= '\uFFFF') ) {
alt2 = 2;
} else {
throw new NoViableAltException("", 2, 0, input);
}
switch (alt2) {
case 1 :
// D:\\GrammarDemo\\T.g:19:9: NestingBlockComment
mNestingBlockComment();
break;
case 2 :
// D:\\GrammarDemo\\T.g:20:7: .
matchAny();
break;
}
}
// $ANTLR end "NestingBlockCommentCharacter"
可以看到 mNestingBlockCommentCharacters() 方法的循环是只要未遇到输入字符流的末尾就会继续循环匹配下去，跟前面讲解块注释的最长匹配版一样。但这里我们需要的是最短匹配。想起ANTLR提供了options { greedy = false; }，这里不是正好派上用场么？
把词法规则改为：
Comment
: NestingBlockComment
;
fragment
NestingBlockComment
: '/+' NestingBlockCommentCharacters '+/'
;
fragment
NestingBlockCommentCharacters
: ( options { greedy = false; } : NestingBlockCommentCharacter )*
;
fragment
NestingBlockCommentCharacter
: NestingBlockComment
| .
;
这会儿可好，ANTLR直接不肯生成出lexer了，抱怨词法规则有错：
问题出在哪里呢？这就是这帖真正的主题了：ANTLR 3.2的options语法只能管其所在的子规则“字面上”出现的选择结构；指定用最短匹配后ANTLR不知道NestingBlockCommentCharacters能匹配什么了，也不知道最短匹配应该以什么来标志结束，直接报个错。
解决的办法也很简单，只要把选择结构以字面量形式写到迭代中，并且把最短匹配与它后面的内容写在同一条大规则里，就好了，如下：
Comment
: NestingBlockComment
;
fragment
NestingBlockComment
: '/+' ( options { greedy = false; } : ( NestingBlockComment | . ) )* '+/'
;
对应生成的代码是：
// $ANTLR start "Comment"
public final void mComment() throws RecognitionException {
int _type = Comment;
int _channel = DEFAULT_TOKEN_CHANNEL;
// D:\\GrammarDemo\\T.g:4:5: ( NestingBlockComment )
// D:\\GrammarDemo\\T.g:4:9: NestingBlockComment
mNestingBlockComment();
state.type = _type;
state.channel = _channel;
}
// $ANTLR end "Comment"
// $ANTLR start "NestingBlockComment"
public final void mNestingBlockComment() throws RecognitionException {
// D:\\GrammarDemo\\T.g:9:5: ( '/+' ( options {greedy=false; } : ( NestingBlockComment | . ) )* '+/' )
// D:\\GrammarDemo\\T.g:9:9: '/+' ( options {greedy=false; } : ( NestingBlockComment | . ) )* '+/'
match("/+");
// D:\\GrammarDemo\\T.g:9:14: ( options {greedy=false; } : ( NestingBlockComment | . ) )*
loop2:
do {
int alt2 = 2;
int LA2_0 = input.LA(1);
if ( (LA2_0 == '+') ) {
int LA2_1 = input.LA(2);
if ( (LA2_1 == '/') ) {
alt2 = 2;
} else if ( (LA2_1 >= '\u0000' && LA2_1 <= '.')
|| (LA2_1 >= '0' && LA2_1 <= '\uFFFF') ) {
alt2 = 1;
}
} else if ( (LA2_0 >= '\u0000' && LA2_0 <= '*')
|| (LA2_0 >= ',' && LA2_0 <= '\uFFFF') ) {
alt2 = 1;
}
switch (alt2) {
case 1 :
// D:\\GrammarDemo\\T.g:9:46: ( NestingBlockComment | . )
// D:\\GrammarDemo\\T.g:9:46: ( NestingBlockComment | . )
{
int alt1 = 2;
int LA1_0 = input.LA(1);
if ( (LA1_0 == '/') ) {
int LA1_1 = input.LA(2);
if ( (LA1_1 == '+') ) {
alt1 = 1;
}
else if ( (LA1_1 >= '\u0000' && LA1_1 <= '*')
|| (LA1_1 >= ',' && LA1_1 <= '\uFFFF') ) {
alt1 = 2;
}
else {
throw new NoViableAltException("", 1, 1, input);
}
} else if ( (LA1_0 >= '\u0000' && LA1_0 <= '.')
|| (LA1_0 >= '0' && LA1_0 <= '\uFFFF') ) {
alt1 = 2;
} else {
throw new NoViableAltException("", 1, 0, input);
}
switch (alt1) {
case 1 :
// D:\\GrammarDemo\\T.g:9:48: NestingBlockComment
mNestingBlockComment();
break;
case 2 :
// D:\\GrammarDemo\\T.g:9:70: .
matchAny();
break;
}
}
break;
default :
break loop2;
}
} while (true);
match("+/");
}
// $ANTLR end "NestingBlockComment"
看，这次循环里的匹配逻辑就变回我们所需要的了：一遇到'+/'就退出循环。
这种嵌套规则其实已经超出了正则语法及其对应的有限状态自动机的计算能力，需要使用上下文无关语法/下推式自动机（PDA）才可以处理。ANTLR生成的lexer与parser都是递归下降式的，lexer自身具有PDA级别的能力（加上断言就比PDA更强），所以可以正确处理嵌套规则。
所以这个例子就没办法用Ruby的正则表达式来对比了。好吧Ruby的正则表达式本身已经超出DFA的范围了，不过还没达到PDA的范围
用Perl 6的rule倒是能表示出来，不过那个已经远远不是正则表达式了……这里不深入了。
---------------------------------------------------------------------------
于是ANTLR想告诉我们的是：别把规则分得太细了……
分享到：
评论
5 楼
night_stalker
2010-09-27
呃…… 是 include Rsec::Helpers
4 楼
night_stalker
2010-09-27
Regexp combinator！
require 'rsec'
include Rsec::Helper
@nest_comment = [/\/\+.*?(?=\/\+|\+\/)/, lazy{@nest_comment} ** 0, /.*?\+\//].r
3 楼
lwwin
2010-09-27
实在难得啊，你能够在家了^-^
2 楼
RednaxelaFX
2010-09-27
dogstar 写道
顶你个肺,在家玩躲猫猫.
嗯顶你个肺不休假在公司做俯卧撑
1 楼
dogstar
2010-09-27
顶你个肺,在家玩躲猫猫.
发表评论
-
Sun JDK1.4.2_28有TieredCompilation
2014-05-12 08:48 0原来以前Sun的JDK 1.4.2 update 28就已经有 ... -
IBM JVM notes (2014 ver)
2014-05-11 07:16 0Sovereign JIT http://publib.bou ... -
HotSpot Server Compiler与data-flow analysis
2014-01-07 17:41 0http://en.wikipedia.org/wiki/Da ... -
基于LLVM实现VM的JIT的一些痛点
2014-01-07 17:25 0同事Philip Reames Sanjoy Das http ... -
《自制编程语言》的一些笔记
2013-11-24 00:20 0http://kmaebashi.com/programmer ... -
对C语义的for循环的基本代码生成模式
2013-10-19 23:12 21782之前有同学在做龙书（第二版）题目，做到8.4的练习，跟我对答案 ... -
Nashorn各种笔记
2013-07-15 17:03 0http://bits.netbeans.org/netbea ... -
《深入理解Java虚拟机（第二版）》书评
2013-07-08 19:19 0值得推荐的中文Java虚拟机入门书 感谢作者赠与的样书，以下 ... -
豆列：从表到里学习JVM实现
2013-06-13 14:13 48152刚写了个学习JVM用的豆列跟大家分享。 豆列地址：http: ... -
Building Blocks of a JavaScript Engine
2013-05-23 00:49 0sketches of my new book "B ... -
读《JavaScript语言精髓与编程实践（第二版）》
2013-05-21 00:32 02008年逛书店的时候偶 ... -
添加一个bool C1LateInline参数？
2011-11-25 16:03 0之前我试过给Phi加exact_type不行，那如果像C2一样 ... -
别测空循环
2011-06-23 21:56 5204今天有朋友提到一个叫 ReflectASM的库，为Java环境 ... -
javac在编译创建内部类对象时生成的奇怪的getClass()调用是什么？
2011-06-14 22:17 4191有人问下面这段代码里，main()方法里的outer.new ... -
confluence property
2011-06-08 20:41 0http://en.wikipedia.org/wiki/Co ... -
JIT编译找不到类？
2011-05-09 22:28 5142今天开始Sun的老blog真的搬迁了，从blogs.sun.c ... -
几个简答题
2011-01-10 16:08 2421某题目 写道 龙书 写道In addition to a c ... -
循环中的字符串拼接的优化
2010-12-09 20:46 0public class StringConcatDemo { ... -
Velocity模板的编译
2010-11-15 14:49 0http://ecee.colorado.edu/ecen45 ... -
反编译的代码比原本人写的代码更易读一例
2010-08-20 08:48 0http://www.eclipse.org/articles ...
相关推荐
另外一个强大的新功能是ANTLR 4极大地简化了匹配某些句法结构（如编程语言中的算术表达式）所需的语法规则。长久以来，处理表达式都是ANTLR语法（以及手工编写的递归下降语法分析器）的难题。识别表达式最自然的...
antlr-2.7.7
基于ANTLR4的CMM语言编译器，内附.g4文件
antlr 2.7.7源码，下载自：http://repo.spring.io/plugins-release/org/antlr/com.springsource.antlr/2.7.7/
开源项目-antlr-antlr4.zip,antlr 4.6发布，支持go代码生成
JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源...
基于antlr4的语义action和属性的编译器前端例子
ANTLR v3 Overview (for ANTLR v2 users)
antlr4 hello world。antlr4 hello world。antlr4 hello world。antlr4 hello world
NULL 博文链接：https://rednaxelafx.iteye.com/blog/314507
antlr-2.7.7.jar和antlr-2.7.6.jar
ANTLR 1989-2006 Developed by Terence Parr @ University of San Francisco We reserve no legal rights to the ANTLR--it is fully in the public domain. An individual or company may do whatever they ...
赠送jar包：antlr-3.5.jar； 赠送原API文档：antlr-3.5-javadoc.jar； 赠送源代码：antlr-3.5-sources.jar； 赠送Maven依赖信息文件：antlr-3.5.pom； 包含翻译后的API文档：antlr-3.5-javadoc-API文档-中文(简体)版...
赠送jar包：antlr4-runtime-4.2.jar； 赠送原API文档：antlr4-runtime-4.2-javadoc.jar； 赠送源代码：antlr4-runtime-4.2-sources.jar； 赠送Maven依赖信息文件：antlr4-runtime-4.2.pom； 包含翻译后的API文档：...
The definitive ANTLR 4 reference