Left associative evaluation of a right recursive grammar in Prolog

Question

I have an issue with evaluating a parsetree derived from a grammar. The parsetree is derived from this pice of code:

parse(block(LEFT_CURLY, STMTS, RIGHT_CURLY)) -->
        left_curly(LEFT_CURLY),
        statements(STMTS),
        right_curly(RIGHT_CURLY).

statements(statements) -->
        [].
        
statements(statements(ASSIGNMENT, STMTS)) -->
        assignment(ASSIGNMENT),
        statements(STMTS).

assignment(assignment(ID, ASSIGN_OP, EXPR, SEMICOLON)) -->
        ident(ID),
        assign_op(ASSIGN_OP),
        expression(EXPR),
        semicolon(SEMICOLON).

expression(expression(TERM)) -->
        term(TERM).

expression(expression(TERM, SUB_OP, EXPR)) -->
        term(TERM),
        sub_op(SUB_OP), 
        expression(EXPR).

expression(expression(TERM, ADD_OP, EXPR)) -->
        term(TERM),
        add_op(ADD_OP), 
        expression(EXPR).

term(term(TERM)) -->
        factor(TERM).

term(term(FACTOR, MULT_OP ,TERM)) -->
        factor(FACTOR),
        mult_op(MULT_OP),
        term(TERM).
        
term(term(FACTOR, DIV_OP ,TERM)) -->
        factor(FACTOR),
        div_op(DIV_OP),
        term(TERM).             

factor(factor(FACTOR)) -->
        int(FACTOR).

factor(factor(FACTOR)) -->
        ident(FACTOR).

factor(factor(LEFT_PAR, EXPR, RIGHT_PAR)) -->
        left_par(LEFT_PAR),
        expression(EXPR),
        right_par(RIGHT_PAR).


assign_op(assign_op) --> [=].
mult_op(mult_op) --> [*].
add_op(add_op) --> [+].
sub_op(sub_op) --> [-].
div_op(div_op) --> [/].
left_par(left_paren) --> ['('].
right_par(right_paren) --> [')'].
left_curly(left_curly) --> ['{'].
right_curly(right_curly) --> ['}'].
semicolon(semicolon) --> [;].

ident(ident(Y)) --> [Y] , {atom(Y)}.              
int(int(X)) --> [X], {integer(X)}.

The resulting parseTree from parse/3 looks like this (ex. inpt { b = 4 - 2 - 1; }:)

T = block(left_curly,statements(assignment(ident(b),assign_op,expression(term(factor(int(4))),sub_op,expression(term(factor(int(2))),sub_op,expression(term(factor(int(1)))))),semicolon),statements),right_curly)

I've had some success with evaluating the expression, and saving variable results. But I am for now evaluating "bottom up" resulting in a right associative evaluation (3), which is not how math works. 4 - 2 - 1 != 3.

An example of the evaluation which evaluates 4 - 2 - 1 to 3:

evaluate(expression(TERM, SUBOP, EXPR), OtherVariables, RESULT) :-
        SUBOP = sub_op,
        !,
        evaluate(TERM, OtherVariables, LHSResult),
        evaluate(EXPR, OtherVariables, RHSResult),
        RESULT is LHSResult - RHSResult.
evaluate(term(FACTOR), OtherVariables, RESULT) :-
        evaluate(FACTOR, RESULT).
evaluate(factor(INT), RESULT) :-
        evaluate(INT, RESULT).
evaluate(int(X), X). 

Is there anyone who could give me a hint on how to move forward with this issue? I have been able to do this in Java, but my Prolog knowledge is not as good. Unfortunately I am not allowed to change the grammar or the parsing.

Answer 1

Your parse tree is very explicit about whether the input contains parentheses. For example:

?- phrase(expression(Expr), [4, -, 2, -, 1]).
Expr = expression(term(factor(int(4))), sub_op, expression(term(factor(int(2))), sub_op, expression(term(factor(int(1)))))) .

?- phrase(expression(Expr), [4, -, '(', 2, -, 1, ')']).
Expr = expression(term(factor(int(4))), sub_op, expression(term(factor(left_paren, expression(term(factor(int(2))), sub_op, expression(term(factor(int(1))))), right_paren)))) .

This is good, because we can tell where the user really wanted us to evaluate 4 - (2 - 1), or whether the input was 4 - 2 - 1 and should really be interpreted as (4 - 2) - 1.

By far the simplest way of doing this is by thinking about the problem not as "left-associative evaluation of a right-associative tree", but about the two separate problems of "evaluation of a tree" and "getting a left-associative tree into right-associative form". That is, don't try to be clever inside your evaluate predicate, but first reassociate the tree and then evaluate that new tree.

A sketch:

op_associativity(add_op, right).
op_associativity(sub_op, left).
op_associativity(mult_op, right).
op_associativity(div_op, left).

expression_reassociated(expression(X, Op, expression(Y, Op, Z)),
                        expression(expression(X, Op, Y), Op, Z)) :-
    op_associativity(Op, left),
    !.
expression_reassociated(Expression, Expression).

With a slightly massaged version of your evaluate, this already gives:

?- phrase(expression(Expr), [4, -, 2, -, 1]), expression_reassociated(Expr, Reassociated), evaluate(Reassociated, Result).
Expr = expression(term(factor(int(4))), sub_op, expression(term(factor(int(2))), sub_op, expression(term(factor(int(1)))))),
Reassociated = expression(expression(term(factor(int(4))), sub_op, term(factor(int(2)))), sub_op, expression(term(factor(int(1))))),
Result = 1 ;
false.

Note that expression_reassociated needs more work: It must reassociate sub-expressions as well. Once you have a complete working solution, you can think about reassociating "on the fly" during evaluation without building the intermediate tree. But it's probably not worth it, unless explicitly requested by your professor.

All that said, it would really be best if the DCG produced the correctly associated parse tree from the start, but I understand that you have constraints.