Definite clause grammars (DCG) are an extension of context free grammars . DCGs allow arbitrary tree structures to be built in the course of parsing and they allow extra conditions dependent on auxiliary computations. A grammar rule can have one of the following two forms. The second form is known as a push-back grammar rule, since it will complete with reinstalling R:
P --> Q. % DCG rule without push back
P, R --> Q. % DCG rule with push back
The term expansion augments the head by two additional parameters that are to represent the sentence position before and after the non-terminal that is defined. A grammar head with predicate identifier p/n will be turned into a normal Prolog head with predicate identifier p/n+2. The new predicate identifier can be used in system predicates such as listing/1, spy/1, etc... The outcome of this first expansion is basically:
phrase(P, I, O) :- phrase(Q, I, O).
phrase(P, I, O) :- phrase(Q, I, H), phrase(R, O, H).
The term expansion will then go to work and tackle the head of the new Prolog rule, whereas the goal expansion will tackle the body. The goal expansion will introduce unifications (=)/2 here and then to keep the expansion steadfast. One requirement is that the two queries phrase(G, I, O) and (phrase(G, I, H), H = O) should return the same results. This allows for example for a consistent definition of phrase(G, I) as an expansion to phrase(G, I, ).Example:
factor(X) --> "(", expr(X), ")".
factor(X, [40|A], B) :- expr(X, A, [41|B]).
We see in the example that the translation does not make use of
the connection predicate ‘C’/3 for terminals. Instead terminals
are directly based on the list definition of ‘C’/3 and translated
into corresponding list equations. If possible these equations are
merged into the head or into the body goals of the grammar rule.
This gives better performance but renders the grammar mechanism
not anymore customizable via ‘C’/3.
The following grammar rule operators are provided. The (grammar)
marking indicates that this operator is only understood in the
context of the head position of the grammar operator (-->)/2: