【记录】把通过TreeParser去解析树Tree的功能集成到(Android的)Java环境中

【背景】

之前已经把Antlr的基本环境，集成到Android中了，可以在ADT中调试了：

【记录】把ANTLR v3整合到Android的App中

现在接着尝试把TreeParser的功能，解析生成AST的功能，集成进来。

1.参考官网：

How do I use ANTLR v3 generated Lexer and Parser from Java?

的示例代码：

final fsqParser.formula_return parserResult = parser.formula();
final CommonTree ast = (CommonTree) parserResult.getTree();
if (ast == null) {
    // line is empty
    throw new ParseException(queryString, 0);
}

结果很明显，找不到这个所谓的fsqParser。

2.网上搜了半天，参考：

[antlr-interest] ‘Cannot find tokens file’

可以看出,是别的另外一个语法,相关的文件是

所以，此处无需关心其是啥，但是要搞懂如何写自己的，针对于自己的ExprSimple的代码。

不过，也找到了其解释：

de.uni_tuebingen.sfb.lichtenstein.formulas.parsing

4.但是此处，也没有对应的ExprSimpleTreeParser啊，所以，貌似，需要想办法，生成对应的

ExprSimpleTreeParser.java

5.后来用如下代码：

package com.mm.antlrv3demo;

import java.io.IOException;

import org.antlr.runtime.*;
import org.antlr.runtime.tree.CommonTree;
//import org.antlr.runtime.ANTLRStringStream;
//import org.antlr.runtime.CharStream;

import android.app.Activity;
import android.os.Bundle;
import android.view.Menu;

public class DDParser extends Activity {

	@Override
	protected void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.activity_ddparser);
		
		antlrV3Demo();
	}

	@Override
	public boolean onCreateOptionsMenu(Menu menu) {
		// Inflate the menu; this adds items to the action bar if it is present.
		getMenuInflater().inflate(R.menu.activity_ddparser, menu);
		return true;
	}
	
	public void antlrV3Demo()
	{
		String inputStr = "1*2+(3*4)\r\n";
		//String inputStr = "1*2\r\n";
		CharStream cs = new ANTLRStringStream(inputStr);
		
//		String file = "__Test___input.txt";
//		CharStream cs = null;
//		try {
//			cs = new ANTLRFileStream(file);
//		} catch (IOException e1) {
//			// TODO Auto-generated catch block
//			e1.printStackTrace();
//		}
		
		ExprSimpleLexer lexer = new ExprSimpleLexer(cs);
		CommonTokenStream tokens = new CommonTokenStream();
		tokens.setTokenSource(lexer);
		
		ExprSimpleParser parser = new ExprSimpleParser(tokens);
		try {
//			RuleReturnScope result = parser.prog();
//			Object outputTree = result.getTree();
			
			ExprSimpleParser.prog_return parserResult = parser.prog();
			//CommonTree outputTree = (CommonTree)parserResult.getTree();
			CommonTree outputTree = parserResult.tree;
			
			System.out.println(outputTree);
		} catch (RecognitionException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
//		final fsqParser.formula_return parserResult = parser.expr();
		
	}

}

去调试，最终，好像是，可以获得了所需要的AST。

6.即：

• 对于本身的antlr v3的代码：

grammar ExprSimple;

options {
	output = AST;
	ASTLabelType = CommonTree; // type of $stat.tree ref etc...
}

INT		:	'0'..'9'+ ;
NEWLINE	:	'\r'? '\n' ;
WS		:	(' '|'\t')+ {skip();} ;

prog	:	stat+ ;

stat	:	expr NEWLINE	-> expr
		;
	
expr	:	multExpr (('+'^|'-'^) multExpr)*
		;

multExpr:	atom ('*'^ atom)* ;

atom	:	INT
		|	'('! expr ')'!
		;

• 和对应的测试字符串：
  • antlrworks中Debug界面中：
  • android中的Java代码中：

对应的，用AntlrWorks 1.5rc2调试出来的结果是：

7.接下来，就是去想办法，如何搞懂那个TreeParser了。

网上找了半天，参考了：

[antlr-interest] ‘Cannot find tokens file’

也还是没搞懂如何去弄TreeParser，感觉像是系统自动生成的。

8.参考了：

[antlr-interest] On to the next issue: error(211)

也没啥帮助。

9.后来也找到fsqParser相关的东西：

Class fsqParser

Class fsqLexer

但是没帮助。

10.去搜CommonTreeNodeStream，找到：

Class: ANTLR3::AST::CommonTreeNodeStream

Class CommonTreeNodeStream

结果也没找到有效帮助。

其中找到：

Can an Antlr Parser return a TreeNodeStream so as to not have to parse the whole file at once?

其只是获得了计算结果，没有用到我此处这种TreeParser。

11.最后是参考了：

ANTLR实现加法计算器（通过AST形式来实现）

才大概有了点概念，好像那个TreeParser，此处即

ExprSimpleTreeParser

其实是需要我们自己去写对应的

ExprSimpleTreeParser.g

才可以的。然后antlr会生成对应的

ExprSimpleTreeParser.java

然后我们代码中，才可以调用到对应的：

的代码的。

12.接下来，就是去参考官网：

4. Tree Parsing

和上面那个帖子:

ANTLR实现加法计算器（通过AST形式来实现）

然后去自己写对应的TreeParser的.g源文件了。

13.但是后来又看到：

How to build an ANTLR code generation target

提到有个参数是：

TREE_PARSER

Boolean indicating that a Tree Parser is being generated.

所以，再去找找，是不是antlr中哪里可以支持设置此参数，就可以自动生成对应的TreeParser了。

然后找到：

org.antlr.runtime.tree Class TreeParser

貌似可以有空去试试，是否可以利用antlr的TreeParser。

看到其构造函数是：

Constructor Summary

TreeParser(TreeNodeStream input)

TreeParser(TreeNodeStream input, RecognizerSharedState state)

所以，感觉好像是先要获得对应的

Interface TreeNodeStream

然后再继续调用函数，去解析tree的。

14.后来又看到：

ANTLR 介绍

中提到TreeParser，感觉其解释的好像更清晰，实际上，还是自己写treeparser，但是传递的是：

options {
    importVocab=ExprParser;
}

然后再写具体规则，就最终实现自己所需要的TreeParser了。他那里是实现了计算的功能。

我此处，需要的是，最先可以试试去打印出对应的表达式和其中的输入的数字等内容。

15.antlr简介 

中有对于参数的详细解释。

16.另外，这里：

ANTLR Tree Parsers

也有比较详细的解释。

然后参考其中的“An Example Tree Walker”去看看如何写出来自己此处的ExprSimple的tree walker，以及保存为何种文件，如何放到ANTLRWorks中，如何编译，如何写java代码调用。

17.想要尝试着把示例代码：

class CalcParser extends Parser;
options {
    buildAST = true;   // uses CommonAST by default
}

expr:   mexpr (PLUS^ mexpr)* SEMI!
    ;

mexpr
    :   atom (STAR^ atom)*
    ;

atom:   INT
    ;

放到ANTLRWorks中呢，结果很明显，有语法错误：

18.通过AntlrWorks去重新建立一个.g文件，选择对应的所支持的定义：

得到默认的文件：

然后再把之前的代码加进来：

很明显，还是缺少SEMI，PLUS等定义，所以还是不行。

18.感觉此示例代码，不是普通的Antlr v3的语法。

但是也不像是普通的java代码。

不过，继续参考教程，发现好像需要另外建立一个CalcLexer.g。

即：

• CalcParser.g

class CalcParser extends Parser;
options {
    buildAST = true;   // uses CommonAST by default
}

expr:   mexpr (PLUS^ mexpr)* SEMI!
    ;

mexpr
    :   atom (STAR^ atom)*
    ;

atom:   INT
    ;

• CalcLexer.g

class CalcLexer extends Lexer;

WS	:	(' '
	|	'\t'
	|	'\n'
	|	'\r')
		{ _ttype = Token.SKIP; }
	;

LPAREN:	'('
	;

RPAREN:	')'
	;

STAR:	'*'
	;

PLUS:	'+'
	;

SEMI:	';'
	;

INT	:	('0'..'9')+
	;

但是却不知道，如何用AntlrWorks去编译这两个文件，如何生成其所说的tree。

19.然后又重新新建一个

Calc.g：

class CalcParser extends Parser;
options {
    buildAST = true;   // uses CommonAST by default
}

expr:   mexpr (PLUS^ mexpr)* SEMI!
    ;

mexpr
    :   atom (STAR^ atom)*
    ;

atom:   INT
    ;
    
class CalcLexer extends Lexer;

WS	:	(' '
	|	'\t'
	|	'\n'
	|	'\r')
		{ _ttype = Token.SKIP; }
	;

LPAREN:	'('
	;

RPAREN:	')'
	;

STAR:	'*'
	;

PLUS:	'+'
	;

SEMI:	';'
	;

INT	:	('0'..'9')+
	;

然后看看是否可以正常编译。

结果，果然的，出错了：

即，需要定义对应的grammar。

20.参考：

ANTLR笔记4 – AST构造，tree grammar，tree walker

貌似解释的还算清楚。

然后去搜：

antlr tree grammar

后来找到很多有价值的东西：

（1）antlr作者的主页：

Terence Parr

有兴趣的可以去看看。其中也有些相关的教程。

（2）其中关于Tree Walker的例子，官网就有：

这个是最简单和最完整的：

Expression evaluator

另外两个，也可以供参考：

Simple tree-based interpeter

Tree construction

（3）不过，后来在：

Systematic way to generate ANTLR tree grammar?

看到了，对于Tree Walker最全面的解释：

其实对于已经获得了AST之后的解析工作，有两种：

• 利用tree grammar去写tree grammar file，然后编译生成对应的代码，得到所需要的解析tree的输出
• 比如计算出表达式的结果等等。
• 自己手动hand by hand/mannuallly去写代码，直接解析对应的AST：
• 对应获得的AST的变量，就是之前我此处已经获得的CommonTree类型的变量，然后自己写java代码，去获得对应的children，parent等等。
• 比如自己写代码，打印出tree的结构，就是一种常见的需要的效果

通过tree grammar生成，还是mannual手动自己写代码，各有自己的好处。

其中，有人就写了个相关的帖子：

Manual Tree Walking Is Better Than Tree Grammars

（注：

1.此贴的原地址：

http://www.antlr.org/article/1170602723163/treewalkers.html

会自动跳转到新地址：

http://www.antlr3.org/article/1170602723163/treewalkers.html

但却已失效。

最新有效的地址是：

http://www.antlr2.org/article/1170602723163/treewalkers.html

2. 该贴说的内容，还是靠谱的。

因为已经被Antlr的作者Terence Parr，放到antlr官网中的Article List了，供大家所参考。

3. 不过，当然该贴也引起了很多的讨论：

[antlr-interest] Manual Tree Walking Vs. Tree Grammars

[antlr-interest] Translators Should Use Tree Grammars

算是各有各的观点。

）

而最终，对于你自己的AST，到底采用哪种方法，还是由你自己决定。

另外，对于antlr在tree walker方面的支持：

• antlr v3：做的不够好，仍需改进；
• antlr v4：以后，将要（很可能要），支持自动生成对应的tree walker
• 如果到时候支持了，倒是有机会去试试。看看是否好用。

21.我此处，目前看来，还是采用自己手动写代码，去检索AST，获得对应的值，比较有效。

因为不是类似于表达式的那种，不需要写对应的action去计算其结果。

而对于AST的CommonTree，找到一个API的解释：

Class: ANTLR3::AST::CommonTree

不过发现确实针对ruby的。

而当前的，自己项目中的CommonTree，自己试了试，目前支持如下一些接口：

其中的，属于CommonTree的，就是对应的所提供的接口，比如childindex，parent等等。

其他的：

BaseTree：属于AST提供的；

Object：属于Java本身就提供的；

22.关于如何自己写代码去解析，walk这个CommonTree。

倒是找到一个可以参考的东西，去试试：

Interfacing AST with Java

中的代码：

public void printTree(CommonTree t, int indent) {
	if ( t != null ) {
		StringBuffer sb = new StringBuffer(indent);
		
		if (t.getParent() == null){
			System.out.println(sb.toString() + t.getText().toString());	
		}
		for ( int i = 0; i < indent; i++ )
			sb = sb.append("   ");
		for ( int i = 0; i < t.getChildCount(); i++ ) {
			System.out.println(sb.toString() + t.getChild(i).toString());
			printTree((CommonTree)t.getChild(i), indent+1);
		}
	}
}

然后使用：

printTree(outputTree, 4);

去调用，最后输入的结果为：

所以，也算是之前ruby版本的CommonTree中的pretty_print(printer)之类的效果了。

其中，原始测试的数据为：

String inputStr = "1*2+(3*4)\r\n";

【总结】

对于一些，有必要的情况下，使用tree grammar去写tree walker去生成对应的代码， 执行对应的解析动作，是比较方便的；

比如计算出表达式的结果；

如果像我此处，没有这类需求，那么可以自己去写对应的代码， 去解析对应的CommonTree的AST变量，去实现自己需要的效果；

比如此处的，只是简单的打印出tree是什么样的，以及以后可能获得tree中特定的节点的各种信息。

转载请注明：在路上 » 【记录】把通过TreeParser去解析树Tree的功能集成到(Android的)Java环境中