Create abstract tree problem from parser

Question

I need big help, I have two simple classes Tree and Node ( I put just interface to use less space on forum, I can easy modify those classes ), I also have flex file and parser file and need to create AST ( abstract syntax tree - to put tokens in Node objects and fill Tree in right way ).

public class Tree {
    Node root;
    public void AddNode(Node n){}
    public void Evaluate(){}
}

public class Node {
    public String value;
    public int type;
    Node left, right;
}

This is parser file

import java_cup.runtime.*;

parser code {:

    public boolean result = true; 

    public void report_fatal_error(String message, Object   info) throws java.lang.Exception {
        done_parsing();
        System.out.println("report_fatal_error");
        report_error();
    }

    public void syntax_error(Symbol cur_token) {
        System.out.println("syntax_error");
        report_error();
    }

    public void unrecovered_syntax_error(Symbol cur_token) throws java.lang.Exception {
        System.out.println("unrecovered_syntax_error");
        report_fatal_error("Fatalna greska, parsiranje se ne moze nastaviti", cur_token);
    }

    public void report_error(){
        System.out.println("report_error");
        result = false;
    }
:}

init with {: result = true; :};

/* Terminals (tokens returned by the scanner). */
terminal           AND, OR, NOT;
terminal           LPAREN, RPAREN;
terminal           ITEM;
terminal           OPEN, CLOSE, MON, MOFF, TIMEOUT, ESERR, BAE, I, O, BUS, EXT, PUSHB;
terminal           VAL, OK, BUS_BR_L, BUS_BR_R, SH_CRT_L, SH_CRT_R, BUS_ALL, EXT_ALL, NO_TIMEOUT, NO_ES_ERR, IBUS_OK, CFG_OK, SYNTAX;
terminal           OUT;

/* Non-terminals */
non terminal        extension;
non terminal Integer    expr;

/* Precedences */
precedence left AND, OR;

/* The grammar */

expr      ::= 
          |
            expr:e1 AND expr:e2 
          {: 
            //System.out.println("AND"); 
            RESULT = 1; 
            :} 
          | 
              expr:e1 OR expr:e2 
          {: 
            //System.out.println("OR"); 
            RESULT = 2; 
            :} 
          | 
              NOT expr:e1
          {: 
            //System.out.println("NOT"); 
            RESULT = 3; 
            :}
          | 
              LPAREN expr:e RPAREN     
          {: 
            //System.out.println("()"); 
            RESULT = 4; 
            :} 
          | 
              ITEM extension:e1
          {: 
            //System.out.println("ITEM."); 
            RESULT = 5; 
            :}
          | 
              error
          {: 
            System.out.println("error"); 
            parser.report_error();
            RESULT = 0; 
            :}
          ;

extension ::= 
              OPEN
          |   
              MON
          |   
              CLOSE
          |
              MOFF
          |
              TIMEOUT
          |
              ESERR
          |
              BAE
          |
              I
          |
              O
          |
              BUS
          |
              EXT
          |
              PUSHB
          |
              VAL
          |
              OK
          |
              BUS_BR_L
          |
              BUS_BR_R
          |
              SH_CRT_L
          |
              SH_CRT_R
          |
              BUS_ALL
          |
              EXT_ALL
          |
              NO_TIMEOUT
          |
              NO_ES_ERR
          |
              IBUS_OK
          |
              CFG_OK 
          |
              SYNTAX
          | 
              OUT
          ;

This is grammar

%%

%{
    public boolean result = true;

    //Puni expression sa tokenima radi reimenovanja
    public Expression expression=new Expression();
    //

    public ArrayList<String> items = new ArrayList<String>();
    public ArrayList<Integer> extensions = new ArrayList<Integer>();
    // ukljucivanje informacije o poziciji tokena
    private Symbol new_symbol(int type) {
            return new Symbol(type, yyline+1, yycolumn);
    }
    // ukljucivanje informacije o poziciji tokena
    private Symbol new_symbol(int type, Object value) {
            return new Symbol(type, yyline+1, yycolumn, value);
    }
%}

%cup

%xstate COMMENT

%eofval{ 
return new_symbol(sym.EOF);
%eofval}

%line
%column

%%
" " {}
"\b" {}
"\t" {}
"\r\n" {}
"\f" {}
"open" {extensions.add(sym.OPEN); return new_symbol(sym.OPEN);}
"close" {extensions.add(sym.CLOSE); return new_symbol(sym.CLOSE);}
"m_on" {extensions.add(sym.MON); return new_symbol(sym.MON);}
"m_off" {extensions.add(sym.MOFF); return new_symbol(sym.MOFF);}
"timeout" {extensions.add(sym.TIMEOUT); return new_symbol(sym.TIMEOUT);}
"es_err" {extensions.add(sym.ESERR); return new_symbol(sym.ESERR);}
"bae" {extensions.add(sym.BAE); return new_symbol(sym.BAE);}
"i" {extensions.add(sym.I); return new_symbol(sym.I);}
"o" {extensions.add(sym.O); return new_symbol(sym.O);}
"bus" {extensions.add(sym.BUS); return new_symbol(sym.BUS);}
"ext" {extensions.add(sym.EXT); return new_symbol(sym.EXT);}
"pushb" {extensions.add(sym.PUSHB); return new_symbol(sym.PUSHB);}
"val" {extensions.add(sym.VAL); return new_symbol(sym.VAL);}
"ok" {extensions.add(sym.OK); return new_symbol(sym.OK);}
"bus_br_l" {extensions.add(sym.BUS_BR_L); return new_symbol(sym.BUS_BR_L);}
"bus_br_r" {extensions.add(sym.BUS_BR_R); return new_symbol(sym.BUS_BR_R);}
"sh_crt_l" {extensions.add(sym.SH_CRT_L); return new_symbol(sym.SH_CRT_L);}
"sh_crt_r" {extensions.add(sym.SH_CRT_R); return new_symbol(sym.SH_CRT_R);}
"bus_all" {extensions.add(sym.BUS_ALL); return new_symbol(sym.BUS_ALL);}
"ext_all" {extensions.add(sym.EXT_ALL); return new_symbol(sym.EXT_ALL);}
"no_timeout" {extensions.add(sym.NO_TIMEOUT); return new_symbol(sym.NO_TIMEOUT);}
"no_es_err" {extensions.add(sym.NO_ES_ERR); return new_symbol(sym.NO_ES_ERR);}
"ibus_ok" {extensions.add(sym.IBUS_OK); return new_symbol(sym.IBUS_OK);}
"cfg_ok" {extensions.add(sym.CFG_OK); return new_symbol(sym.CFG_OK);}
"syntax" {extensions.add(sym.SYNTAX); return new_symbol(sym.SYNTAX);}
"out" {extensions.add(sym.OUT); return new_symbol(sym.OUT);}
"!" { return new_symbol(sym.NOT);}
"&" { return new_symbol(sym.AND);}
"|" { return new_symbol(sym.OR);}
"(" { return new_symbol(sym.LPAREN);}
")" { return new_symbol(sym.RPAREN);}
([[:jletter:]])[[:jletterdigit:]]* \. {items.add(yytext().substring(0, yytext().length()-1)); return new_symbol (sym.ITEM);}
. {result = false;}

Probem is how to create AST from here, I got on input expression something like

A.open && b.i ? Can anybody help ?

Answer 1

The lines in your Parser where you have commented out print statements like:

        //System.out.println("OR"); 

is where you'll want to maintain your AST using the Tree data structure you have. Find out which token will create the tree, add something somewhere in the tree, etc based on your grammar.