Translation of Definite Clause Grammar rules

In this section we informally describe the translation of DCG rules into normal rules in XSB. Each grammar rule is translated into a Prolog clause as it is consulted or compiled. This is accomplished through a general mechanism of defining the hook predicate term_expansion/2, by means of which a user can specify any desired transformation to be done as clauses are read by the reader of XSB's parser. This DCG term expansion is as follows:

A DCG rule such as:

 		 		 p(X) -> q(X). 

will be translated (expanded) into:

 		 		 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 9.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) 

).