【记录】把通过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’

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

fsqLexer.g

fsqParser.g

fsqTreeParser.g

所以,此处无需关心其是啥,但是要搞懂如何写自己的,针对于自己的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

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

new ExprSimpleTreeParser(new CommonTreeNodeStream(outputTree));

的代码的。

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中呢,结果很明显,有语法错误:

some symbol not defined for antlr file

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

file new for antlr file

antlr 3 grammar

calc use all supported symbols

得到默认的文件:

got default g file

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

some undefined references

很明显,还是缺少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')+
	;

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

generate code for calc g file

结果,果然的,出错了:

[10:50:09] error(10):  internal error:  : java.lang.Error: Error parsing D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g: ‘class’ not expected ‘grammar’

org.antlr.tool.GrammarSpelunker.match(GrammarSpelunker.java:70)

org.antlr.tool.GrammarSpelunker.grammarHeader(GrammarSpelunker.java:108)

org.antlr.tool.GrammarSpelunker.parse(GrammarSpelunker.java:80)

org.antlr.Tool.sortGrammarFiles(Tool.java:572)

org.antlr.Tool.process(Tool.java:426)

org.antlr.works.generate.CodeGenerate.generate(CodeGenerate.java:104)

org.antlr.works.generate.CodeGenerate.run(CodeGenerate.java:185)

java.lang.Thread.run(Unknown Source)

[10:50:09] error(100): D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g:1:1: syntax error: antlr: NoViableAltException(80@[])

[10:50:09] error(8):  file D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g contains grammar class; names must be identical

[10:50:09] error(100): D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g:1:7: syntax error: antlr: MissingTokenException(inserted [@-1,0:0='<missing SEMI>’,<82>,1:6] at CalcParser)

[10:50:09] error(100): D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g:1:18: syntax error: antlr: MissingTokenException(inserted [@-1,0:0='<missing COLON>’,<22>,1:17] at extends)

[10:50:09] error(100): D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g:2:1: syntax error: antlr: MissingTokenException(inserted [@-1,0:0='<missing EOF>’,<-1>,2:0] at options {)

[10:50:09] error(100): D:\DevRoot\IndustrialMobileAutomation\HandheldDataSetter\ANTLR\projects\v1.5\CalcParser\Calc.g:1:1: syntax error: assign.types: NoViableAltException(43@[])

cannot generate the grammar because class not expected grammar

即,需要定义对应的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,自己试了试,目前支持如下一些接口:

common tree functions

其中的,属于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);

去调用,最后输入的结果为:

02-27 13:32:46.048: I/System.out(1574): +

02-27 13:33:33.459: I/System.out(1574):             *

02-27 13:33:37.818: I/System.out(1574):                1

02-27 13:33:37.818: I/System.out(1574):                2

02-27 13:33:39.659: I/System.out(1574):             *

02-27 13:33:39.979: I/System.out(1574):                3

debug output printed tree

 

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

其中,原始测试的数据为:

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

 

【总结】

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

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

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

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



发表评论

电子邮件地址不会被公开。 必填项已用*标注

无觅相关文章插件,快速提升流量