Translation of Definite Clause Grammar rules

The procedural interpretation of a DCG rule is that it takes an input list of symbols or character codes, analyzes some initial portion of that list, and produces the remaining portion (possibly enlarged, if pushback lists are used) as output for further analysis. As an abbreviation, the arguments required for the input and output lists are not written explicitly in a grammar rule, but are added when the rule is translated into an ordinary Prolog clause. In this section we informally describe this translation, which resembles the DCG rules of other Prologs in most particulars.

Each grammar rule is translated into a Prolog clause as it is consulted or compiled. This DCG term expansion is as follows:

A DCG rule such as:

 		 		 p(X) -> q(X). 

will be translated (expanded) into the Prolog rule:

 		 		 p(X, Li, Lo) :- 


q(X, Li, Lo). 

If there is more than one non-terminal on the right-hand side, as in

 		 		 p(X, Y) -> q(X), r(X, Y), s(Y). 

the corresponding input and output arguments are identified, translating into:

 		 		 p(X, Y, Li, Lo) :- 


q(X, Li, L1), 


r(X, Y, L1, L2), 


s(Y, L2, Lo). 

Terminals are translated using the built-in predicate 'C'/3 (See section 8.3 for its description). For instance:

 		 		 p(X) -> [go, to], q(X), [stop]. 

is translated into:

 		 		 p(X, S0, S) :- 

		 		 		 'C'(S0, go, S1), 

		 		 		 'C'(S1, to, S2), 


q(X, S2, S3), 

		 		 		 'C'(S3, stop, S). 

Extra conditions expressed as explicit procedure calls naturally translate into themselves. For example,

 		 		 positive_number(X) -> 
, $\{$integer(N), N > 0$\}$, 


fraction(F), $\{$form_number(N, F, X)$\}$. 

translates to:

 		 		 positive_number(X, Li, Lo) :- 

		 		 		 'C'(Li, N, L1), 


integer(N), 


N > 0, 


L1 = L2, 


fraction(F, L2, L3), 


form_number(N, F, N), 


L3 = Lo. 

 

Similarly, a cut is translated literally.

Push-back lists (a proper list of terminals on the left-hand side of a DCG rule) translate into a sequence of 'C'/3 goals with the first and third arguments reversed. For example,

 		 		 it_is(X), [is, not] -> [aint]. 

becomes

 		 		 it_is(X, Li, Lo) :- 

		 		 		 'C'(Li, aint, L1), 

		 		 		 'C'(Lo, is, L2), 

		 		 		 'C'(L2, not, L1). 

Disjunction has a fairly obvious translation. For example, the DCG clause:

 		 		 expr(E) -> 


expr(X), "+", term(Y), $\{$E is X+Y$\}$ 

		 		 		   | term(E). 

translates to the Prolog rule:

 		 		expr(E, Li, Lo) :- 

		 		 		   ( expr(X, Li, L1), 

		 		 		   'C'(L1, 43, L2), 		 % 0'+ = 43 


term(Y, L2, L3) 


E is X+Y, 


L3 = Lo 

		 		 		   ; term(E, Li, Lo) 

		 		 		   ).