DCG, right-recursion and how to express it clearly

Question

I have read a lot of the suggested questions but I am still stuck with my learning problem right now, I am trying to write a simple Lisp s-expression parser and I cannot figure out how to tackle the recursive nature of an s-expression without tying my brain into knots!

Here is what I have, the input is a list of tokenised terms from the source file from my lexer module which works fine: (GNU Prolog by the way)

lisp_term(T) -->
        (
     null(T)
        ;
         token(T)
        ;
         sexp_open(_), lisp_term(T2), sexp_close(_), {T = lnode(T2)}
        ).

lisp_term(T) --> [], {T=end}.


sexp_open(Pos)  --> [popen(Pos)].
sexp_close(Pos) --> [pclose(Pos)].

token(token(Pos,Token)) --> [token(Pos,Token)].

null(null(Pos1)) --> [popen(Pos1), pclose(_)].

and here is my calling code...

lisplex('../test.lisp',X),
lexpp(X),
phrase(lisp_term(A), X, Y),
format("Result:    ~w~n", [A]),
format("Remainder: ~w~n", [Y]).

the output from the lexer is a list like this, the source: "(hello)"

[popen(pos(1,1)),token(pos(1,2),[h,e,l,l,o]),pclose(pos(1,7))]

I continually get tied up trying to figure out how to deal with an expression like:

(defun whizzle (a1 b2)
    (munge (* 10 a1) (+ b2 a1)))

That is, how to deal generally with turning the lexer stream into a parse tree. You can see that my DCG rules are attempting to do that.

I would really appreciate some help and pointers to good stuff to read or advice on how to better understand dealing with right-recursive situations. I have been teaching myself Prolog for a few months now and love it to bits BUT I am stuck on being able to proceed with my understanding of DCG-s and situations like this.

Thanks, Sean.

Answer 1

I think you are missing the list ! Try (untested)

lisp_term(T) --> token(T).
lisp_term(lnode(T)) -->
     sexp_open(_), lisp_list(T), sexp_close(_).

lisp_list([H|T]) -->
     lisp_term(H), lisp_list(T).
lisp_list([]) --> [].

Then take a look to Lisprolog, available from Markus Triska' page.