编译原理学习笔记05_解析树和AST
在C语言中模拟含有默认参数的函数

编译原理学习笔记06_antlr初步

nonoob posted @ Sun, 23 Sep 2012 22:11:10 +0800 in Programming , 2097 readers

antlr是什么

权威解释见官方wikipedia,我只负责八卦。作者Terence Parr似乎是个有洁癖的人,写了antlr第一个版本之后觉得效率不高又写了v2,因为同样的理由又推倒重来写了v3。尽管以java为主打,但这个antlr非常有野心,Java/C#/Python/Ruby/Scala等语言通吃;由grammar生成lexer和parser使得这玩意儿非常适合教学用,也非常适合菜鸟级程序员提高编写编译器的自信。虽说没有JavaCC这么正统,但是个人觉得非常实用,现在Hibernate framework/Jython/Groovy可都是基于antlr的哦!这哥们还开发了一套template engine,同样是一个妄图大一统文本解析的干活。有了antlr这把锤子他就开始到处乱敲:paper自不用说,然后是《The Definitive ANTLR Reference》、《Language Implementation Patterns》。后者近期被译成中文,号称“屠龙”;虽说的确过誉了,但是不得不承认这本书的确深入浅出。尽管作者一直在自卖自夸antlr和StringTemplate,但是对于java系的人来讲这的确是学习编译原理基础知识的好东西;连Guido大叔和Dalvik设计者Dan Bornstein也对这本书颇有好评。

安装工具

antlr:http://www.antlr.org/download.html

对于我这样的习惯了eclipse的懒人来说antlrworks并不是上上之策,插件才是王道http://antlrv3ide.sourceforge.net/

该插件特点:

  1. 新建一般的java project(如果要生成的目标语言是java的话)并convert成antlr即可,之后只需写grammar文件。
  2. 默认情况下保存每一次grammar文件就会进行自动生成对应的lexer和parser的java文件(默认target language是java)和对应tokens文件;每次打开eclipse时会重新解析一次。
  3. 似乎生成的lexer和parser并不会添加grammar文件所在package信息(吐槽:这一点和上面一个特点加起来足以让人抓狂!!!)。
  4. 编辑器的content assit功能和java编辑器的功能有不少出入,括号、引号、缩进等功能做得并不好。
  5. grammar(g文件)除编辑器的两个tab Interpreter和Railroad view非常棒,一个用于傻瓜式写,一个用于GUI显示,并且可以导出成html。

还可以考虑使用StringTemplate:http://www.stringtemplate.org/download.html

开始使用

以含有加减乘法的计算器且目标语言java为例。

  • 在g文件中写出所要定义的grammer(一般是词法和语法的综合)
grammar Expr;

prog : stat+;
stat : expr NEWLINE
     | ID '=' expr NEWLINE
     | NEWLINE
     ;
expr: multiExpr (('+'|'-') multiExpr)*
    ;  
multiExpr : atom('*' atom)*
    ;   
atom : INT
     | ID
     | '(' expr ')'
     ;
     
ID : ('a'..'z'|'A'..'Z')+ ;
INT : '0'..'9'+;
NEWLINE : '\r'?'\n';
WS : (' '|'\t'|'\n'|'\r')+{skip();};
  • 生成的ExprLexer.java文件中会将'(',')'等涉及判定的字符用新的identifier如T__8等来对应,识别这样的字符的方法形如T__8。新生成的ExprLexer类继承了antlr定义的Lexer类,封装了一些方法。ExprParser继承Parser类,诸如expr等g文件中的左式会有个对应的方法(例如expr())来处理它;为了处理出错和从错误状态恢复,该类还生成了FOLLOW_expr_in_stat34这样的变量并调用了pushFollow()这类方法。
  • 这样,从输入流中可以生成lexer对象,将由lexer得到的tokens作为输入就得到一个parser对象;调用顶层的方法就可以完成语法分析了。
public static void main(String[] args) throws IOException, RecognitionException {
		// TODO Auto-generated method stub
		ANTLRInputStream input = new ANTLRInputStream(System.in);
		ExprLexer lexer =  new ExprLexer(input);
		CommonTokenStream tokens = new CommonTokenStream(lexer);
		ExprParser parser = new ExprParser(tokens);
		parser.prog();
	}
  • 上述代码对于符合grammar的输入不会有输出,如果需要给出相应的输出的话仍可以在g文件中添加(java)代码。
  1. 添加包含的package
@header{
import java.util.HashMap;
}
  1. 添加parser中的成员变量
@members{
/** Map variable name to Integer object holding value */
HashMap memory = new HashMap();
}
  1. 添加parser中左式处理函数的返回值(前面代码中的方法的返回值都为void),并且在每个生成式上在{}里添加特定的方法。值得注意的是对于诸如INT这样在lexer中得到的Token用的是antlr定义好的Token类的一个对象,包含了getText()方法;故不需要定义INT的text返回值。如下面的一段:
expr returns [int value]
     : e=multExpr {$value = $e.value;}
     ( '+' e=multExpr {$value+=$e.value;}
     | '-' e=multExpr {$value-=$e.value;}
     )*
    ;

multExpr returns [int value]
     : e = atom {$value=$e.value;}('*' e=atom {$value *= $e.value;})*

atom returns [int value]
    :   // value of an INT is the int computed from char sequence
     INT {$value=Integer.parseInt($INT.text);}
     | ID	// variable reference
     {
        // look up value of variable
        Integer v = (Integer)memory.get($ID.text);
        // if found, set return value else error
        if(v!=null) $value = v.intValue();
        else System.err.println("undefined variable "+$ID.text);
     }
        // value of parenthesized expression is just the expr value
     | '(' expr ')'{$value=$expr.value;}
     ;

--------------------------------------------------

参考自《The Definitive ANTLR Reference》,又是一本没付版权费的电子书:(

PS:通过antlr生成的代码,我才知道java对于退出多重循环有个不错的做法,就是在指定的循环前面添加上某个label,然后在要退出的时候加上break label。我们都知道尽管java把goto作为保留字,但是在咱码农是没法用goto的。使用这样break的做法肯定没有C/C++来得凶残;但是无疑很好地避免了goto带来的无结构编程恶习,同时又保留了灵活性(似乎该对D.E.Knuth致敬?)。

middleware said:
Wed, 26 Sep 2012 09:33:05 +0800

ANTLR 确实不错。LL'(k) basically makes LALR obsolete. 而且还支持回溯 parsing(通过 exception),基本解决了左递归和不确定语法的问题。这是我 04 年看的时候的成果。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter