Re: DCG

On 12/07/2013, at 7:50 AM, Anne Ogborn wrote:

> I sometimes need a similar thing.
> 
> Given a DCG and a list, what are the possible next tokens in the list?

I don't understand this.

I *suspect* that you want the derivative of a grammar.
The derivative of a regular language is well understood.
The derivative of a context-free grammar has been studied
and turns out to be quite practical.  See
http://matt.might.net/articles/parsing-with-derivatives/

Or are you meaning FIRST(S,G,L) =
  {x | exists R : S -->* L++[x]++R according to G}?

That's doable for context-free grammars.
The problem is that DCGs are not context-free.

You can encode any Turing machine as a DCG whose
starting node has one argument (the initial state
of the tape) such that start(Tape) matches [] if
the machine halts in a success state, fails if the
machine halts in a failure state, and loops forever
if the machine does not halt.  Now try

	nt(Tape) --> tm(Tape), [a].
	nt(_)    -->           [b].

You can compute an *approximation* of FIRST(S,G,L),
I suppose.