/* DEFINITE CLAUSE GRAMMARS (~ CONTEXT FREE GRAMMARS)

Example context free grammar:

Exp --> Var
Exp --> ( Exp Op Exp )

Op --> +
Op --> -
Op --> *
Op --> /

Var --> x
Var --> y
Var --> z


A parser for this grammar could be made by the following predicates:

exp(String, Rest) :- var(String, Rest).
exp(String, Rest) :- String = ['('|A],
                     exp(A,B),
                     op(B,C),
                     exp(C,D),
                     D = [')'|Rest].

op(String, Rest) :- String = [+|Rest].
op(String, Rest) :- String = [-|Rest].
op(String, Rest) :- String = [*|Rest].
op(String, Rest) :- String = [/|Rest].

var(String, Rest) :- String = [x|Rest].
var(String, Rest) :- String = [y|Rest].
var(String, Rest) :- String = [z|Rest].


Prolog has (often, not part of ISO definition) syntactic sugar for
easily generating such predicates. A parser for the grammar above can
be implemented by the code below.

*/


exp --> var.
exp --> ['('], exp, op, exp, [')'].

op --> [+].
op --> [-].
op --> [*].
op --> [/].

var --> [x].
var --> [y].
var --> [z].


/* 






/* Test run:

| ?- phrase(exp, ['(', x, + , y, ')']).

true ? 

| ?- phrase(exp, ['(', x, + , y, '(']).

no

| ?- phrase(exp, ['(', '(', z, *, x, ')', + , y, ')'], R).

R = [] ? 

| ?- phrase(exp, ['(', '(', z, *, x, ')', + , y, ')', x, x, x],R).

R = [x,x,x] ? 


*/