General Description

Definite clause grammars (DCGs) are an extension of context free grammars that have proven useful for describing natural and formal languages, and that may be conveniently expressed and executed in Prolog. A Definite Clause Grammar rule is executable because it is just a notational variant of a logic rule that has the following general form:

Head -> Body.

with the declarative interpretation that ``a possible form for Head is Body''. The procedural interpretation of a grammar rule is that it takes an input sequence of symbols or character codes, analyses some initial portion of that list, and produces the remaining portion (possibly enlarged) as output for further analysis. In XSB, the exact form of this sequence is determined by whether XSB's DCG mode is set to use tabling or not, as will be discussed below. In either case, the arguments required for the input and output lists are not written explicitly in the DCG rule, but are added when the rule is translated (expanded) into an ordinary normal rule during parsing. Extra conditions, in the form of explicit Prolog literals or control constructs such as if-then-elses ('->'/2) or cuts ('!'/0), may be included in the Body of the DCG rule and they work exactly as one would expect.

The syntax of DCGs is orthogonal to whether tabling is used for DCGs or not. An overview of DCG syntax supported by XSB is as follows:

1. A non-terminal symbol may be any HiLog term other than a variable or a number. A variable which appears in the body of a rule is equivalent to the appearance of a call to the built-in predicate phrase/3 as it is described below.
2. A terminal symbol may be any HiLog term. In order to distinguish terminals from nonterminals, a sequence of one or more terminal symbols $\alpha$,$\beta$,$\gamma$,$\delta$,... is written within a grammar rule as a Prolog list [ $\alpha$,$\beta$,$\gamma$,$\delta$,... ], with the empty sequence written as the empty list []. The list of terminals may contain variables but it has to be a proper list, or else an error message is sent to the standard error stream and the expansion of the grammar rule that contains this list will fail. If the terminal symbols are ASCII character codes, they can be written (as elsewhere) as strings.
3. Extra conditions, expressed in the form of Prolog predicate calls, can be included in the body (right-hand side) of a grammar rule by enclosing such conditions in curly brackets, '{' and '}'. For example, one can write:
   positive_integer(N) -> [N], {integer(N), N > 0}. ^9.1
4. The left hand side of a DCG rule must consist of a single non-terminal, possibly followed by a sequence of terminals (which must be written as a unique Prolog list). Thus in XSB, unlike SB-Prolog version 3.1, ``push-back lists'' are supported.
5. The right hand side of a DCG rule may contain alternatives (written using the usual Prolog's disjunction operator ';' or using the usual BNF disjunction operator '|'.
6. The Prolog control primitives if-then-else ('->'/2), nots (not/1, fail_if/1, $\tt '\backslash+'\!/1$ or tnot/1) and cut ('!'/0) may also be included in the right hand side of a DCG rule. These symbols need not be enclosed in curly brackets. ^9.2 All other Prolog's control primitives, such as repeat/0, must be enclosed explicitly within curly brackets if they are not meant to be interpreted as non-terminal grammar symbols.