Trees, Templates and other Folks

Lexical and syntactical analyzers

Let us start from the already known grammar. But, but all previously laboriously inserted actions are removed now. Presently, these actions will be inserted into the other file. The only thing we want here is to generate the tree (Abstract Syntax Tree).

grammar Expr;

options {
  output=AST;
  ASTLabelType=CommonTree;
}

output=AST means that we want to produce an abstract syntax tree. ASTLabelType=CommonTree denotes the class to which the created tree nodes will belong. You can create your own class but it should be derived from the CommonTree class.

@header {
// package com.sample;
}

If the grammar is placed in the package (java will like us for it!) we should write it here. Below the same for the lexical analyzer.

@lexer::header {
//  package com.sample;
}

prog
    : (stat )+ EOF!;

stat
    : expr NL -> expr

One way of determining how to construct a tree fragment: "get what the expr have brought and put it into the tree."

    
    | ID PODST expr NL -> ^(PODST ID expr)

More advanced version, "make PODST , and call it the root, and bind ID to it, and also what the expr have brought, and call them children from now."

    | NL ->
    ;

And here you have the simplest version: "Leave the trees alone, lie down and rest." In each version of the above NL does not go into the tree, because no one wants it here.

expr
    : multExpr
      ( PLUS^ multExpr
      | MINUS^ multExpr
      )*
    ;

Here, the another way of tree fragments construction is shown. When we meet the element of type marked here with ^, put it into the tree as its root and attach to it as a child all elements built already.

multExpr
    : atom
      ( MUL^ atom
      | DIV^ atom
      )*
    ;

atom
    : INT
    | ID
    | LP! expr RP!
    ;

Another element of the second method of the control the formation of a tree. Element ! should be ignored during the tree construction.
Important! Do not mix methods in one rule, either use a rewrite rule ( -> ) or ^ ! marks.

Below we have already known lexical rules.
ID : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;

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

NL : '\r'? '\n' ;

WS : (' ' | '\t')+ {$channel = HIDDEN;} ;


LP
	:	'('
	;

RP
	:	')'
	;

PODST
	:	'='
	;

PLUS
	:	'+'
	;

MINUS
	:	'-'
	;

MUL
	:	'*'
	;

DIV
	:	'/'
	;

Tree parser

Here we have a choice.

  1. If you want to perform calculations and print the result as during the previous laboratory - go here (Third classes)
  2. If you want (No, you do not) to create another, modified tree - go here
  3. If you want to use the templates - go here (Fourth classes)