Parsing an expression in Prolog and returning an abstract syntax

Viewed 2290

I have to write parse(Tkns, T) that takes in a mathematical expression in the form of a list of tokens and finds T, and return a statement representing the abstract syntax, respecting order of operations and associativity.

For example,

?- parse( [ num(3), plus, num(2), star, num(1) ], T ).

T = add(integer(3), multiply(integer(2), integer(1))) ;
No

I've attempted to implement + and * as follows

parse([num(X)], integer(X)).
parse(Tkns, T) :-
  (  append(E1, [plus|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = add(T1,T2)
  ;  append(E1, [star|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = multiply(T1,T2)
  ).

Which finds the correct answer, but also returns answers that do not follow associativity or order of operations.

ex)

parse( [ num(3), plus, num(2), star, num(1) ], T ). 

also returns

mult(add(integer(3), integer(2)), integer(1))

and

parse([num(1), plus, num(2), plus, num(3)], T)

returns the equivalent of 1+2+3 and 1+(2+3) when it should only return the former.

Is there a way I can get this to work?

Edit: more info: I only need to implement +,-,*,/,negate (-1, -2, etc.) and all numbers are integers. A hint was given that the code will be structured similarly to the grammer

<expression> ::= <expression> + <term>
              |  <expression> - <term>
              |  <term>

      <term> ::= <term> * <factor>
              |  <term> / <factor>
              |  <factor>

    <factor> ::= num
              |  ( <expression> )

Only with negate implemented as well.

Edit2: I found a grammar parser written in Prolog (http://www.cs.sunysb.edu/~warren/xsbbook/node10.html). Is there a way I could modify it to print a left hand derivation of a grammar ("print" in the sense that the Prolog interpreter will output "T=[the correct answer]")

3 Answers
Related