title: Parsing an expression in Prolog and returning an abstract syntax
body: <p>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.</p>
  
  <p>For example, </p>
  
  <pre><code>?- parse( [ num(3), plus, num(2), star, num(1) ], T ).
  
  T = add(integer(3), multiply(integer(2), integer(1))) ;
  No
  </code></pre>
  
  <p>I've attempted to implement + and * as follows</p>
  
  <pre><code>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)
    ).
  </code></pre>
  
  <p>Which finds the correct answer, but also returns answers that do not follow associativity or order of operations.</p>
  
  <p>ex) </p>
  
  <pre><code>parse( [ num(3), plus, num(2), star, num(1) ], T ). 
  </code></pre>
  
  <p>also returns </p>
  
  <pre><code>mult(add(integer(3), integer(2)), integer(1))
  </code></pre>
  
  <p>and</p>
  
  <pre><code>parse([num(1), plus, num(2), plus, num(3)], T)
  </code></pre>
  
  <p>returns the equivalent of 1+2+3 and 1+(2+3) when it should only return the former.</p>
  
  <p>Is there a way I can get this to work?</p>
  
  <p>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</p>
  
  <pre><code>&lt;expression&gt; ::= &lt;expression&gt; + &lt;term&gt;
                |  &lt;expression&gt; - &lt;term&gt;
                |  &lt;term&gt;
  
        &lt;term&gt; ::= &lt;term&gt; * &lt;factor&gt;
                |  &lt;term&gt; / &lt;factor&gt;
                |  &lt;factor&gt;
  
      &lt;factor&gt; ::= num
                |  ( &lt;expression&gt; )
  </code></pre>
  
  <p>Only with negate implemented as well.</p>
  
  <p>Edit2: I found a grammar parser written in Prolog (<a href="http://www.cs.sunysb.edu/~warren/xsbbook/node10.html" rel="nofollow">http://www.cs.sunysb.edu/~warren/xsbbook/node10.html</a>). 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]")</p>