Search code examples
prologdcg

arithmetic expression in Prolog

I am given a context-free grammar that defines what a valid arithmetic expression is in the given situation. And the question is to write it in haskell and Prolog. Here is the CFG.

Expr ::= lit(i)
| add(Expr, Expr)
| sub(Expr, Expr)

In Haskell it is fairly simple. I just use a data type, call it Expr and off I go. Here's what I wrote:

data Expr = Lit Integer |
            Add Expr Expr |
            Sub Expr Expr

But I am fairly stuck about writing it in Prolog. Furthermore, running expr(E), where E is an arithmetic expression, should evaluate to true if it really is an expression that is valid by the definition of the CFG. So far, I wrote this, but I don't think it is correct. So help me figure it out.

expr(lit(i), i).
expr(add(expr(), expr()), Res).
expr(sub(expr(), expr()), Res).
Solution

  • Since you're not required to evaluate the expression, the code could be

    expr(lit(_)).
expr(add(E1,E2)) :- expr(E1), expr(E2).
expr(sub(E1,E2)) :- expr(E1), expr(E2).