Translation of Grammar Rules into Prolog Clauses

Grammar rules are merely a convenient abbreviation for ordinary Prolog clauses. Each grammar rule is translated into a Prolog clause as it is compiled. This translation is described below.

The procedural interpretation of a grammar 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) as output for further analysis. 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. The translations shown differ from the output of listing/[0,1] in that internal translations such as variable renaming are not represented. This is done in the interests of clarity. For example, a rule such as (A) will be depicted as translating into (B) rather than (C).

     p(X) --> q(X). (A)
     p(X, S0, S) :-
             q(X, S0, S). (B)
     p(A,B,C) :-
             q(A,B,C). (C)

If there is more than one non-terminal on the right-hand side, as in (D) the corresponding input and output arguments are identified, translating into (E):

     p(X, Y) --> q(X), r(X, Y), s(Y). (D)
     p(X, Y, S0, S) :- (E)
         q(X, S0, S1),
         r(X, Y, S1, S2),
         s(Y, S2, S).

Terminals are translated using the built-in predicate 'C'(S1, X, S2), read as "point S1 is connected by terminal X to point S2", and defined by the single clause

     'C'([X|S], X, S).

(This predicate is not normally useful in itself; it has been given the name uppercase c simply to avoid pre-empting a more useful name.) Then, for instance (F) is translated into (G):

     p(X) --> [go, to], q(X), [stop]. (F)
     p(X, S0, S) :- (G)
         'C'(S0, go, S1),
         'C'(S1, to, S2),
         q(X, S2, S3),
         'C'(S3, stop, S).

Extra conditions expressed as explicit procedure calls, enclosed in curly braces, naturally translate into themselves. For example (H) translates to (I):

     p(X) --> [X], {integer(X), X > 0}, q(X). (H)
     p(X, S0, S) :- (I)
         'C'(S0, X, S1),
         X > 0,
         q(X, S1, S).

Similarly, a cut is translated literally.

Terminals on the left-hand side of a rule, enclosed in square brackets, translate into 'C'/3 goals with the first and third arguments reversed. For example, (J) becomes (K):

     is(N), [not] --> [aint]. (J)
     is(N, S0, S) :- (K)
         'C'(S0, aint, S1),
         'C'(S, not, S1).

Disjunction has a fairly obvious translation. For example, (L), a rule that equates phrases like "(sent) a letter to him" and "(sent) him a letter", translates to (M):

     args(X, Y) --> (L)
             dir(X), [to], indir(Y) |
             indir(Y), dir(X).
     args(X, Y, S0, S) :- (M)
         (   dir(X, S0, S1),
             'C'(S1, to, S2),
             indir(Y, S2, S)
         |   indir(Y, S0, S1),
             dir(X, S1, S)