Prolog - Analysis

Question

I am new to the language prologue and have been given a task regarding parsing the prologue. I need help solving a problem.

In reasoning, we have a grammar:

Expr ::= + Expr Expr | * Expr Expr | Num | Xer Xer ::= x | ^ x Num Num ::= 2 | 3 | .... a Integer (bigger than 1) ... 

Token ^ is the same as in mathematics. 5^5 equals 25 .

Parse should work in both directions: a call with an instantiated list to generate Ast, while a call with an Ast instance should generate a similar list of prefixes.

My evaluation says I need to make a syntax example that does this:
Example (when deleting Ast value):

 ?- parse([+, *, 2, x, ^, x, 5 ], Ast), parse(L, Ast). X = ..., L = [+, *, 2, x, ^, x, 5] 

I would also like to know what the parse tree will look like.

Answer 1

The prologue has a special formalism for directly accessing context-free grammars: DCG (literate marginal phrases). Your example translates almost immediately to DCG:

 expr --> [+], expr, expr | [*], expr, expr | num | xer. xer --> [x] | [^], [x], num. num --> [2] | [3] | [4] | [5]. 

Now you can test the sentences:

 ?- phrase(expr, [+, *, 2, x, ^, x, 5 ]). true ; false. ?- phrase(expr, [+, *, *, 2, x, ^, x, 5 ]). false. 

You can even generate all possible sentences like this:

 ?- length(L, N), phrase(expr, L). L = [2], N = 1 ; L = [3], N = 1 ; ... 

And finally, you can add an abstract syntax tree to your definition.

 expr(plus(A,B)) --> [+], expr(A), expr(B). expr(mul(A,B)) --> [*], expr(A), expr(B). expr(Num) --> num(Num). expr(Xer) --> xer(Xer). xer(var(x)) --> [x]. xer(pow(var(x),N)) --> [^], [x], num(N). num(num(2)) --> [2]. num(num(3)) --> [3]. num(num(4)) --> [4]. num(num(5)) --> [5]. 

So now you can use it as you wish:

 ?- phrase(expr(AST), [+, *, 2, x, ^, x, 5 ]), phrase(expr(AST),L). AST = plus(mul(num(2), var(x)), pow(var(x), num(5))), L = [+, *, 2, x, ^, x, 5] ; false. 

Just nitpick: an interface predicate for DCGs phrase/2 not parse/2 .