Value by abstract syntax tree (AST)
Now you have seen the translation / calculation of basic syntax guidance, in this literacy / syntax, indicating when to perform actions. A more powerful strategy is to create a mediation expression, which has all or most of the input symbols, and encodes the relationship between these marks in the structure of the data. For example: Enter "3 4" will be reached with the AST shown below:
/ /
3 4
For this type of tree, you will use a tree travel program (generated from tree graphic syntax) to calculate the same value as before, but use different strategies.
In order to determine what is calculated, or perform a grammatical tree, you must conduct multiple traversal of the grammar tree. At this time, the effect of AST will become clear.
AST structure
For many grammar, let Antlr generate a useful AST are quite simple. In us, open the buildast option and add a little suffix operator to tell ANTLR those markers should be the root of the subtree.
Class Exprparser Extends Parser;
Options {
Buildast = True;
}
EXPR: MEXPR ((Plus ^ | minus ^) MEXPR) *
;
MEXPR
: Atom (star ^ atom) *
;
Atom: int
| Lparen! EXPAREN!
;
Similarly, Lexer does not change. In the main program, ask the target syntax tree and print it:
Import Antlr. *;
Import Antlr.collections. *;
Public class
Main
{
Public static void main (string [] args) throws exception {
ExprleXer Lexer = New ExprleXer (System.in);
Exprparser Parser = New Exprparser (Lexer);
Parser.expr ();
AST T = PARSER.GETAST ();
System.out.println (T.toStringTree ());
}
}
$ Java
Main
3 4
( 3 4)
$ Java
Main
3 4 * 5
( 3 (* 4 5)))
$ Java
Main
(3 4) * 5
(* ( 3 4) 5)
$
AST analysis and evaluation
The syntax tree created above with the above Parser is very simple. Single rules in the grammar tree parsing program are sufficient.
Class ExprtreeParser Extends TreeParser;
Options {
Importvocab = exprparser;
}
EXPR RETURNS [INT R = 0]
{Int a, b;
: # (Plus a = expr b = expr) {r = a b;}
| # (Minus A = EXPR B = EXPR) {r = a-b;}
| # (Star a = expr b = expr) {r = a * b;}
| I: int {r = (int) integer.parseint (i.getText ());}
;
The main program is modified to use the new syntax tree PARSER to evaluate:
Import Antlr. *;
Import Antlr.collections. *;
Public class
Main
{
Public static void main (string [] args) throws exception {
ExprleXer Lexer = New ExprleXer (System.IN); ExprParser Parser = New Exprparser (lexer);
Parser.expr ();
AST T = PARSER.GETAST ();
System.out.println (T.toStringTree ());
EXPRTREEPARSER TREEPARSER = New ExpRTreeParser ();
INT x = TreeParser.expr (t);
System.out.println (x);
}
}
Now you got the tree structure and results.
$ Java
Main
3 4
( 3 4)
Seduce
$ Java
Main
3 (4 * 5) 10
( ( 3 (* 4 5)) 10)
33
$
