Parsing with DCGs in Scheme (without Prolog)?

Question

Lots of Prolog-in-Scheme implementations are out there. E.g. Kanren, Schelog.

Apparently in "Paradigms of AI Programming" Norvig implements Prolog-to-Lisp compiler in Lisp in order to use Definite Clause Grammars.

But is there a simpler cleaner way? Maybe some clever use of amb to avoid implementing a full "Prolog"? What is the easiest way to have DCG-based parsing in Scheme?

Mineral

Answer 1

DCGs use both unification and backtracking, so there's no avoiding implementing the core of Prolog. That is, you can represent any pure Prolog program as a DCG parsing the empty list.

You might do it if you only care about some special case of DCGs, like ones without variables (good only for recognizing, not parsing).

Odin