Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 40 ยท Data Structures and Parsing

DCG Grammars and Parsing

Parse and generate text with Prolog definite clause grammars. Learn the --> notation, phrase/2, terminals, extra arguments, curly-brace goals, an agreement grammar and an arithmetic parser.

Prolog was invented for language processing, and its best tool for the job is the definite clause grammar (DCG). A DCG lets you write a grammar almost as you would on paper, and Prolog turns it into a parser, and often into a generator, for free. DCGs are used for natural-language fragments, configuration files, command languages, calculators, and any other task where you must make sense of a sequence of symbols.

This lesson introduces the notation, shows the translation to ordinary clauses, adds extra arguments to build results (parse trees and values), and builds an arithmetic expression evaluator.

Grammar rules

A DCG rule uses --> instead of :-. The body lists nonterminals (calls to other rules) and terminals (lists of the actual symbols):

PROLOG
greeting --> [hello], name.
name     --> [world].
name     --> [prolog].

Read the first rule as "a greeting is the word hello followed by a name". Run a grammar with phrase(NonTerminal, List):

PROLOG
?- phrase(greeting, [hello, world]).
true.

?- phrase(greeting, [hello, there]).
false.

?- phrase(greeting, L).
L = [hello, world] ;
L = [hello, prolog].

The last query shows the second superpower: the same grammar generates every sentence it accepts. phrase/3 takes a third argument, the rest of the input, so you can parse a prefix: phrase(greeting, [hello, world, and, more], Rest) gives Rest = [and, more].

What a DCG really is

Prolog translates every rule into an ordinary clause with two extra arguments: the list before parsing and the list that remains after. These two lists form a difference list:

PROLOG
% greeting --> [hello], name.   becomes roughly
greeting(S0, S) :- S0 = [hello|S1], name(S1, S).

% name --> [world].             becomes
name([world|S], S).

S0 is the input; S is what is left after greeting consumed hello and a name. Because there is no copying or appending, parsing is fast and takes time proportional to the input. Seeing this translation makes everything else obvious: a nonterminal is a predicate with two hidden arguments, and [hello] is "the next element of the input is hello".

flowchart LR
  A["[hello, world]"] -- "greeting" --> B["[]"]
  A -- "[hello]" --> C["[world]"]
  C -- "name" --> B

Each rule consumes a prefix of the input and hands the rest on.

Rule bodies

Notation Meaning
[a, b] terminals: the next two symbols must be a and b
[] the empty sequence (matches without consuming input)
a, b a then b
a ; b a or b
{ Goal } an ordinary Prolog goal; consumes no input
! cut, as in clauses
\+ a succeeds if a cannot match here (no input consumed)
call(G, Args...) call a nonterminal built at run time

Curly braces are what connect parsing to computation. Use them for arithmetic, type tests and anything that is not about the input.

Extra arguments build results

Nonterminals can have arguments of their own. A rule is translated by adding the two list arguments after yours. This is how a parser returns a value or a tree. The next grammar builds a parse tree and also enforces number agreement between subject and verb by passing sg or pl around:

PROLOG
s(s(NP, VP))        --> np(N, NP), vp(N, VP).
np(N, np(D, Noun))  --> det(N, D), noun(N, Noun).
vp(N, vp(V, NP))    --> verb(N, V), np(_, NP).
vp(N, vp(V))        --> verb(N, V).

det(_, the)  --> [the].
det(sg, a)   --> [a].
noun(sg, cat)  --> [cat].
noun(pl, cats) --> [cats].
noun(sg, dog)  --> [dog].
noun(pl, dogs) --> [dogs].
verb(sg, sees) --> [sees].
verb(pl, see)  --> [see].

The variable N is shared by subject and verb, so the cat sees parses, the cats see parses, but the cats sees does not.

Python Parse trees and agreement (Python stand-in engine)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first query returns T = s(np(the,cat), vp(sees, np(a,dog))). The fifth query uses the grammar as a generator and prints the first five sentences it can produce.

An arithmetic expression parser

The classic grammar for arithmetic needs care: a rule such as expr --> expr, [+], term is left-recursive and loops forever in Prolog, which tries the first alternative first and calls itself without consuming input. The remedy is to rewrite the left recursion as repetition, passing an accumulator that carries the partial result:

PROLOG
expr(V)           --> term(T), expr_rest(T, V).
expr_rest(Acc, V) --> [+], term(T), { A1 is Acc + T }, expr_rest(A1, V).
expr_rest(Acc, V) --> [-], term(T), { A1 is Acc - T }, expr_rest(A1, V).
expr_rest(V, V)   --> [].

term(V)           --> factor(F), term_rest(F, V).
term_rest(Acc, V) --> [*], factor(F), { A1 is Acc * F }, term_rest(A1, V).
term_rest(V, V)   --> [].

factor(N) --> [N], { number(N) }.
factor(V) --> ['('], expr(V), [')'].

The structure mirrors precedence: expr handles + and - and is built from terms; term handles * and is built from factors. Multiplication binds tighter because term sits lower in the hierarchy. Evaluation happens as the parse goes, through the { ... } goals.

Python An arithmetic evaluator in DCG (Python stand-in engine)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Parsing characters and numbers

A real parser usually starts from text rather than from a token list. In SWI-Prolog, convert text to a list of character codes (string_codes/2, atom_codes/2) and write rules over codes. The library dcg/basics provides ready-made nonterminals such as integer//1, number//1, blanks//0 and string//1:

PROLOG
:- use_module(library(dcg/basics)).

point(X-Y) --> "(", integer(X), ",", blanks, integer(Y), ")".
PROLOG
?- string_codes("(3, 4)", Cs), phrase(point(P), Cs).
P = 3-4.

Here "(" inside a DCG body is a literal list of codes, which is why the rule can read like the text it matches. The notation X//1 just names a nonterminal with one argument (it is arity 3 as a predicate).

A hand-written digit parser shows the pattern behind these library rules:

PROLOG
digits([D|T]) --> digit(D), digits(T).
digits([D])   --> digit(D).
digit(D)      --> [D], { code_type(D, digit) }.

Collect the codes into a list Ds and convert with number_codes(N, Ds). Note the order of the clauses: the longer alternative first makes the rule greedy.

Tips and pitfalls

  • Left recursion loops forever. Rewrite with an accumulator, or use tabling (see Tabling and Performance).
  • Ambiguous grammars give several parses on backtracking. Use once(phrase(...)) or phrase/2 followed by a cut when you want the first.
  • Put the most specific alternative first (for example the longer match) to avoid needless backtracking.
  • Use { } for all non-parsing goals, and remember the call is placed at that point in the translation, so a test like { N > 0 } after the symbol it concerns works as a guard.
  • Always check the input is fully consumed: phrase/2 demands this; with phrase/3 and a leftover, make sure it is [] when you require it.
  • Trace a failing grammar with the translated clauses: listing(expr_rest) shows the two extra arguments.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a DCG rule a --> b, c. compile to?

    Two extra arguments (a difference list) are threaded through the body: each nonterminal consumes a prefix and passes the rest on.
  2. 2. What is the purpose of { Goal } in a DCG body?

    Curly braces escape to plain Prolog, for arithmetic, tests and so on.
  3. 3. Why does expr --> expr, [+], term. loop forever?

    The first thing the rule does is call itself with the same input, so recursion never makes progress.
  4. 4. How do you run a grammar so that it must consume the whole list?

    phrase/2 succeeds only if the rule matches the entire list; phrase/3 lets you inspect the remainder.

Summary

  • DCG rules use -->; terminals are lists, nonterminals are calls, { } embeds Prolog goals.
  • Each rule becomes a clause with two extra arguments, a difference list: input before and after.
  • phrase/2,3 runs a grammar; the same grammar parses and generates.
  • Extra arguments return parse trees or values and carry agreement features.
  • Avoid left recursion with accumulators; use library(dcg/basics) for numbers and whitespace.

Next: Input, Output and Error Handling