(Prolog) Parsing Lisp s-expressions in Prolog conditions
I wrote a parser in Prolog that takes a tokenized list and must return an expression where the variable is unified with the value of the evaluated equation:
Tokens = ['(', is, v('X',3),'(', +, 1, 2, ')', ')' ]
Expr = (3 is 1 + 2)
Currently my parser is returning the following:
Expr [is, _G32432, '(', +, 1, 2, ')'|_G19343]
Does anyone have an idea how I can fix this parser? I have included the following code:
%Definite Clause Grammar (DCG) for Lisp s-expressions
expression(N) --> atom(N).
expression(N) --> integer(N).
expression(N) --> variable(N).
expression(N) --> list(N).
list(N) --> ['('], sequence(N), [')'].
sequence(_) --> [].
sequence([H|T]) --> expression(H), sequence(T).
%atom(_) --> [].
atom(N) --> [N],{atom(N)}.
%variable(_) --> [].
variable(N) --> [v(_,N)],{var(N)}.
%integer(_) --> [].
integer(N) --> [N],{integer(N)}.
evaluate(String, Expr):-
tokenize(String, Tokens),
expression(Expr,Tokens,[]),
write('Expression: '), write_term(Expr, [ignore_ops(true)]).
EDIT: Below is my working version of the parser:
expression(N) --> atom(N). %an atom is a type of expression
expression(N) --> integer(N). %an integer is a type of expression
expression(N) --> variable(N). %a variable is a type of expression
expression(M) --> list(N),{M=..N}.
list(N) --> ['('], sequence(N), [')']. %a sequence within parens is a type of list
sequence([]) --> []. %a sequence can be empty
sequence([H|T]) --> expression(H), sequence(T). %a sequence can be composed of an expression
% sequence([]) --> []. %and a sequence atom(_) --> [].
atom(N) --> [N],{atom(N),N \= '(', N \= ')'}. %parens are not atoms, but all other Prolog atoms
% If N is a variable and it is within the v(Label,X) data structure,
% then it is a var in this grammar
variable(N) --> [v(_,N)],{var(N)}.
%variable(_) --> [].
%integer(_) --> [].
integer(N) --> [N],{integer(N)}.
source to share
One of your input tokens is [1]. Note that it will never match your rule [2], since it N
is an integer, not a variable (also, it 'X'
is an atom, not a variable).
[1] v('X',3)
[2] variable(N) --> [v(_,N)],{var(N)}.
Change [2] - [3] fixes this problem.
[3] variable(N) --> [N], {var(N)}.
PS. Also make sure you close the resulting expression in the base case for sequence//1
by replacing the corresponding line with [4].
[4] sequence([]) --> [].
source to share