I am trying to do an old archived java course for which there is no forum help. I have been stuck on one problem for a couple of days, would really appreciate any sort of help. I am supposed to make an abstract Syntax Tree using a parser. The parser reads from a Expression Grammar file, and then I have to make an Abstract tree using recursive call. The expression grammar that I have written is

    @skip whitespace{
    root ::= expr;
    expr ::=  (product | sum) ((add| multi)* (product | sum)*)*   ;
    sum ::= primitive ( add  primitive)*  ;
    product ::=  primitive (multi primitive)*;
    primitive ::= variable | number | '(' sum ')' | '(' product ')' ;
    
}

    whitespace ::= [ \t\r\n];
    number ::= [0-9] ('.'[0-9] )*;
    variable ::= [a-zA-Z] ;
    add ::= ' ';
    multi ::= '*';

with this grammar the tree I am generating is for the input 1 2 3*4 5 6*7 8 (3*2*1) is attached below

you can see that its picking the product when its in brackets but I dont seem to get how to write the grammar such that 3*4 and 6*7 are captured as a product too and in Sums the number that comes before a multiplication sign is not included in the previous sum node

CodePudding user response：

You could get rid of expr here, but it's maybe more scalable like this. In any case, it's really much simpler than you think:

root ::= expr;
expr ::= sum;
sum ::= product ( add product )* ;
product ::= primitive ( multi primitive )* ;
primitive ::= variable | number | '(' expr ')' ;

That should be intuitive (if you hone your intuitions :-) A sum is the sum of several products; a product cannot be the product of a sum. It can be the product of parenthesised sums, but a parenthesised sum is not a sum; it's a primitive, grammatically speaking.