CS515, Fall 2005, October 25, 2005
A Note about DCG Grammar rules (in our tokenizer)

This note is to further explain how our scanner (i.e., tokenizer)
works in the Prolog project.  What we are using is called a Definite
Clause Grammar to express Prolog rules that pretty much resemble an
actual PL grammar.

When we see a construct such as X --> Y in the scanner, it roughly
corresponds to a production X ::= Y in a context-free grammar and
means X can produce Y.  The statements in the scanner are actually
an "encoding" of a Prolog program with certain implicit assumptions.
There are "hidden" parameters in the terms within the rules, that
effectively use a list as input and consume elements from that list as
the subgoals are satisfied, one by one. (See the example below).  

The parts of these rules that appear within { }, are actual Prolog
code.  The built-in name(X,Y) predicate is used to translate a list of
ascii character codes in Y, into a corresponding Prolog construct; for
example, 
name(X,[the ascii integer code for 1]) binds the integer 1 to X.

name(Y,[the ascii codes for a,b,c as list elements]) binds the Prolog
atom abc to X.

Now let's look at a rule in the scanner and rewrite it as it is interpreted
by Prolog.

RULE: digit(D) --> [D], {47 < D, D < 58}.

INTERPRETATION: digit([D|T],T,D) :- 47<D, D<58.

RULE: nedigits([D|T]) --> digit(D), !, digits(T).

INTERPRETATION: nedigits([D|W],X,[D|T]) := digit([D|W],W,D), !, digits(W,X,T).

RULE: digits(L) --> nedigits(L).

INTERPRETATION: digits(X,Y,L):- nedigits(X,Y,L).

RULE: digits([]) --> [].

INTERPRETATION:  digits([],_,[]) :- [].

(note: this rule stops the forward recursion in nedigits -- so when 
the input list is empty, the recursion stops.)