A.9 Defining Definite Clause Grammars

The defgrammar macro can be used to define a definite clause grammar (DCG), which is a relation that determines whether the start of a list of tokens (a sentence) matches a particular grammar. The remaining tokens in the list become the sentence tail.

The relation has the form:

(<grammar name> <sentence> <sentence tail> <extra argument>*)

where the <extra argument> items are terms defined below.

The syntax of the defgrammar macro is:

(defgrammar <grammar name>
  <rule>*)
 
<rule> ::= (<lhs> <rhs>*)
 
<lhs> ::= <grammar name>
        | (<grammar name> <term>*)
        | ((<grammar name> <term>*) <newterm>*)
 
<rhs> ::= <atom>
        | <var>
        | (<other grammar name> <term>*)
        | <lisp clause>
        | (call <term>)
        | (cut)
 
<lisp clause> ::= (<non-atomic lisp form> <term>*)
 
<non-atomic lisp form> ::= (<lisp function name> <lisp arg>*)

<grammar name> is the same symbol as the one naming the defgrammar.

<other grammar name> is a symbol naming another defgrammar.

<atom> is an atom, which forms the words of the sentence to be matched.

<var> is a variable reference.

<term> and <newterm> are any Common Prolog logic expression, including a variable.

<lisp function name> is a symbol naming a Lisp function.

<lisp arg> is any Lisp form, which is evaluated and passed to the function.

Within the <lhs>, extra arguments can be added by specifying <term>s. Every <rule> must specify the same <grammar name> as the defgrammar form and have the same number of extra arguments.

If the <lhs> specifies <newterm> forms, then they are pushed onto start of the sentence tail if the rule matches. This corresponds to the "pushback lists" or "right-hand context" in traditional Prolog DCG syntax.

The meaning of the various <rhs> items is as follows:

• <atom> matches that atom in the sentence.
• <var> is unified with the next item in the sentence.
• (<other grammar name> <term>*) calls the grammar relation <other grammar name> on the rest of the sentence. The optional <term> arguments are passed to the relation as its extra arguments.
• <lisp clause> evaluates the <non-atomic lisp form> as a Lisp form and unifies the values that it returns with the <term>s that follow it.
• (call <term>) calls <term> as a normal Prolog relation.
• (cut) calls the normal Prolog cut relation.

The phrase predicate can be used to call a DCG.

A.9.1 Examples

Here are some examples of using defgrammar.

A.9.1.1 Example 1: A simple definition.

This example shows the Common Prolog translation of the grammar shown at the top of http://cs.union.edu/~striegnk/learn-prolog-now/html/node59.html.

(defgrammar gram-det
  (gram-det the)
  (gram-det a))
 
(defgrammar gram-n
  (gram-n woman)
  (gram-n man))
 
(defgrammar gram-v
  (gram-v shoots))
 
(defgrammar gram-np
  (gram-np (gram-det) (gram-n)))
 
(defgrammar gram-vp
  (gram-vp (gram-v) (gram-np))
  (gram-vp (gram-v)))
 
(defgrammar gram-s
  (gram-s (gram-np) (gram-vp)))

Note the use of symbols for terminals and lists for non-terminals. They all use the first form of the <lhs> and have no extra terms on the <rhs>, so all of the relations are binary.

The following will both succeed and bind ?x to the list (foo bar):

(clog:any '?x '(gram-s (a woman shoots foo bar) ?x))
(clog:any '?x '(gram-s (a woman shoots the man foo bar) ?x))

A.9.1.2 Example 2: Using extra arguments.

(defgrammar one-of
  ((one-of ?word) ?word))
 
(defgrammar two-of
   ((two-of ?word) (one-of ?word) (one-of ?word)))

Each of these defines a 3-ary relation, whose extra argument is the word to match. When the relations are called, the word will typically be bound to a symbol from the sentence to match.

The following will succeed and bind ?x to the list (foo bar):

(clog:any '?x '(two-of (start start foo bar) ?x start))

The following will both fail because the sentences do not begin with two start symbols:

(clog:any '?x '(two-of (not-start start foo bar) ?x start))
(clog:any '?x '(two-of (start not-start foo bar) ?x start))