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), integer(X), 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) ).