ISO/IEC TS 13211-3:2025

Technical
Specification
ISO/IEC TS 13211-3
First edition
Programming languages —
2025-06
Prolog —
Part 3:
Definite clause grammar rules as an
extension of ISO/IEC 13211-1
Langages de programmation — Prolog —
Partie 3: Règles de grammaire en clauses définies en tant
qu'extension de l'ISO/IEC 13211-1
Reference number
© ISO/IEC 2025
All rights reserved. Unless otherwise specified, or required in the context of its implementation, no part of this publication may
be reproduced or utilized otherwise in any form or by any means, electronic or mechanical, including photocopying, or posting on
the internet or an intranet, without prior written permission. Permission can be requested from either ISO at the address below
or ISO’s member body in the country of the requester.
ISO copyright office
CP 401 • Ch. de Blandonnet 8
CH-1214 Vernier, Geneva
Phone: +41 22 749 01 11
Email: copyright@iso.org
Website: www.iso.org
Published in Switzerland
© ISO/IEC 2025 – All rights reserved
ii
Contents Page
Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Normative references . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3 Terms and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.3 Grammar terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
4 Symbols and abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5 Conformance — (ISO/IEC 13211–1:1995: 5 Compliance) . . . . . . . . . . . . . . . . 4
5.1 Prolog processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5.5 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5.5.13 Grammar control constructs and built-in non-terminals . . . . . . . . . . . 4
6 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.1.2 Abstract term syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.2.1 Prolog text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
7 Language concepts and semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.4 Prolog text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.4.2 Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.4.4 Grammar rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.5 Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.5.1 Preparing a Prolog text for execution . . . . . . . . . . . . . . . . . . . . . 7
7.13 Grammar rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.13.1 Format of grammar rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7.13.2 Terminals and non-terminals, semicontext . . . . . . . . . . . . . . . . . . 8
7.13.3 Non-terminal indicator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.13.4 Executing clauses expanded from grammar rules . . . . . . . . . . . . . . 10
7.13.5 Logical expansion of grammar rules . . . . . . . . . . . . . . . . . . . . . . 11
7.13.6 Definitions of grammar control constructs . . . . . . . . . . . . . . . . . . 12
7.14 Grammar control constructs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.14.1 []//0 – empty terminal sequence . . . . . . . . . . . . . . . . . . . . . . . 13
7.14.2 ’.’//2 – terminal sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.14.3 (’,’)//2 – concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.14.4 (;)//2 – alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.14.5 (;)//2 with(->)//2 – if-then-else . . . . . . . . . . . . . . . . . . . . . . 14
7.14.6 (’|’)//2 – second form of alternative . . . . . . . . . . . . . . . . . . . . 14
7.14.7 {}//1 – grammar body goal . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.14.8 call//1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.14.9 phrase//1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.14.10 !//0 – grammar body cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.14.11 (\+)//1 – grammar body not . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.14.12 (->)//2 – if-then . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8 Built-in predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.18 Grammar processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.18.1 phrase/3,phrase/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
© ISO/IEC 2025 — All rights reserved
iii
ISO/IEC TS 13211–3:2025 (en)
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotech-
nical Commission) form the specialized system for worldwide standardization. National bod-
ies that are members of ISO or IEC participate in the development of International Standards
through technical committees established by the respective organization to deal with particular
fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual in-
terest. Other international organizations, governmental and non-governmental, in liaison with
ISO and IEC, also take part in the work.
The procedures used to develop this document and those intended for its further maintenance
are described in the ISO/IEC Directives, Part 1. In particular, the different approval criteria
needed for the different types of document should be noted. This document was drafted in ac-
cordance with the editorial rules of the ISO/IEC Directives, Part 2 (see www.iso.org/directives
or www.iec.ch/members_experts/refdocs).
ISO and IEC draw attention to the possibility that the implementation of this document may
involve the use of (a) patent(s). ISO and IEC take no position concerning the evidence, validity
or applicability of any claimed patent rights in respect thereof. As of the date of publication
of this document, ISO and IEC had not received notice of (a) patent(s) which may be required
to implement this document. However, implementers are cautioned that this may not rep-
resent the latest information, which may be obtained from the patent database available at
www.iso.org/patents and http://patents.iec.ch. ISO and IEC shall not be held responsible for
identifying any or all such patent rights.
Any trade name used in this document is information given for the convenience of users and
does not constitute an endorsement.
For an explanation of the voluntary nature of standards, the meaning of ISO specific terms and
expressions related to conformity assessment, as well as information about ISO’s adherence to
the World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT) see
www.iso.org/iso/foreword.html. In the IEC, see www.iec.ch/understanding-standards.
This document was prepared by Joint Technical Committee ISO/IEC JTC 1, Information tech-
nology, Subcommittee SC 22, Programming languages, their environments and system soft-
ware interfaces.
A list of all parts in the ISO/IEC 13211 series can be found on the ISO and IEC websites.
Any feedback or questions on this document should be directed to the user’s national standards
body. A complete listing of these bodies can be found at www.iso.org/members.html and
www.iec.ch/national-committees.
© ISO/IEC 2025 — All rights reserved
iv
ISO/IEC TS 13211–3:2025 (en)
Introduction
Definite clause grammar rules provide convenient functionality for parsing and processing text
and structured lists in Prolog. They have been implemented in many Prolog processors.
This document extends ISO/IEC 13211–1. For convenience, it has been numbered to refer to
relevant subclauses of the base standard. In particular, this document adds new subclauses to,
and extends existing subclauses of ISO/IEC 13211–1.
© ISO/IEC 2025 — All rights reserved
v
Technical Specification ISO/IEC TS 13211-3:2025(en)
Programming languages —
Prolog —
Part 3:
Definite clause grammar rules as an extension of ISO/IEC
13211-1
1 Scope
This document promotes the applicability and portability of Prolog grammar rules in data
processing systems that support standard Prolog as defined in ISO/IEC 13211–1:1995/Cor
1:2007/Cor 2:2012/Cor 3:2017 and ISO/IEC 13211–2:2000. This document specifies:
a) The representation, syntax, and constraints of Prolog grammar rules
b) A logical expansion of grammar rules into Prolog clauses
c) A set of built-in predicates for parsing with grammar rules
2 Normative references
The following documents are referred to in the text in such a way that some or all of their
content constitutes requirements of this document. For dated references, only the edition cited
applies. For undated references, the latest edition of the referenced document (including any
amendments) applies.
ISO/IEC 13211–1:1995, Informationtechnology—Programminglanguages—Prolog—Part1: Gen-
eralcore.
ISO/IEC 13211–2:2000, Information technology — Programming languages — Prolog — Part 2:
Modules.
ISO/IEC 13211–1:1995/Cor.1:2006, Information technology — Programming languages — Prolog
—Part1: Generalcore—TechnicalCorrigendum1
ISO/IEC 13211–1:1995/Cor.2:2012, Information technology — Programming languages — Prolog
—Part1: Generalcore—TechnicalCorrigendum2
ISO/IEC 13211–1:1995/Cor.3:2017, Information technology — Programming languages — Prolog
—Part1: Generalcore—TechnicalCorrigendum3
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
3 Terms and definitions
For the purposes of this document, the terms and definitions given in ISO/IEC 13211–1:1995
and the following apply.
ISO and IEC maintain terminology databases for use in standardization at the following ad-
dresses:
— ISO Online browsing platform: available at www.iso.org/obp
— IEC Electropedia: available at www.electropedia.org
3.3 Grammar terms
3.3.1
alternative
compound term with principal functor (;)/2 or with principal functor (’|’)/2 with each
argument being a grammar rule body
3.3.2
clause-term
read-term in Prolog text which has neither principal functor (:-)/1 nor principal functor
(-->)/2
Note 1 to entry: This term has been adapted from ISO/IEC 13211–1:1995, 3.33.
3.3.3
covered
being such a terminal sequence that the grammar rule body generates or parses the terminal
sequence
3.3.4
definite clause grammar
set of non-terminal definitions
3.3.5
expansion of a grammar rule
preparation for execution of a grammar rule
Note 1 to entry: See ISO/IEC 13211–1:1995, 7.5.1 for more information on preparation for execution.
3.3.6
generating (w.r.t. a non-terminal and a definite clause grammar)
producing a terminal sequence of that definite clause grammar, obeying semicontexts, if any
3.3.7
grammar body cut
the atom !
3.3.8
grammar body element
grammar body cut, or a grammar goal, or a non-terminal, or a terminal sequence
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
3.3.9
grammar body not
compound term with principal functor (\+)/1 whose argument is a grammar rule body
3.3.10
grammar body sequence
compound term with principal functor (’,’)/2 and each argument a grammar rule body
3.3.11
grammar goal
compound term with principal functor {}/1 whose argument is a goal
3.3.12
grammar rule
compound term with principal functor (-->)/2
3.3.13
grammar rule body
compound term which forms, or is in the form of, the second argument of a grammar rule
being a grammar body sequence, or an alternative, or a grammar body not, or a grammar body
element, or a grammar goal
3.3.14
grammar rule head
first argument of a grammar rule ; either a non-terminal, or a compound term whose principal
functor is (’,’)/2, with first argument a non-terminal, and second argument a semicontext
3.3.15
new variable with respect to a term T
variable that is not a member of the variable set of T
3.3.16
non-terminal
callable term, i.e., an atom or a compound term
Note 1 to entry: See ISO/IEC 13211–1:1995, 3.25 for a definition of "callable term".
3.3.17
non-terminal definition
sequence of grammar rules belonging to the same non-terminal
3.3.18
non-terminal indicator
compound term A//N with A an atom and N a non-negative integer, denoting a non-terminal
3.3.19
parsing (w.r.t. a definite clause grammar)
successively accepting or consuming terminal sequences, assigning them to corresponding non-
terminals and obeying semicontexts, if any
3.3.20
semicontext
terminal sequence occurring optionally after the non-terminal of a grammar rule head
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
3.3.21
steadfastness of a goal w.r.t. its N-th argument
property that a goal G is equivalent to a goal ( Gv, V = T ) where Gv is identical to G except
for the N-th argument being a term T which has been replaced by a new variable V
3.3.22
terminal
any Prolog term denoting a terminal symbol of the grammar
3.3.23
terminal sequence
list which is either the empty list or a non-empty list whose first argument is a terminal, and
the second argument is a terminal sequence
Note 1 to entry: See ISO/IEC 13211–1:1995, 3.99, 6.3.5 and 6.3.1.3 for a definition of "list".
3.3.24
terminal sequence, comprehensive
terminal sequence containing a prefix, and the prefix covered by a grammar rule body, i.e.
accepted or generated by phrase/3
3.3.25
terminal sequence, remaining
rest of a comprehensive terminal sequence without the leading terminal sequence being cov-
ered by a grammar rule body
4 Symbols and abbreviations
None.
5 Conformance — (ISO/IEC 13211–1:1995: 5 Compliance)
5.1 Prolog processor
In addition to the specifications of ISO/IEC 13211–1:1995, 5.1, list items a), b), and c), the re-
quirements of this document also apply. Moreover, after preparing Prolog text for execution,
executing Prolog goals and rejecting any non-conforming Prolog text, the user shall specify all
permitted variations of this document and ISO/IEC 13211–1:1995.
5.5 Extensions
5.5.13 Grammar control constructs and built-in non-terminals
A processor may support additional grammar control constructs (7.14) and built-in non-terminals
as an implementation specific f eature. Additional control constructs shall be treated as non-
terminals when executed in strictly conforming mode (5.1e).
EXAMPLE Additional grammar control constructs include higher-order phrase//2 and phrase//3.
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
6 Syntax
6.1 Notation
6.1.2 Abstract term syntax
In addition to the specifications in ISO/IEC 13211–1:1995, 6.1.2, Prolog text (6.2) is represented
abstractly by an abstract list x where x is:
c) g.t whereg is the abstract syntax for a grammar rule, andt is Prolog text, or
d) nil, the empty list.
6.2.1 Prolog text
6.2.1.1 Prolog text and directives
In addition to the specifications of ISO/IEC 13211-1:1995, 6.2.1, Prolog text is a sequence of
read-terms which denote (1) directives, (2) clauses, and (3) grammar rules of user-defined pro-
cedures.
prolog text = p text
Abstract: pt pt
p text = directive term, p text
Abstract: g.t g t
p text = clause term, p text
Abstract: d.t d t
p text = grammar rule term, p text
Abstract: c.t c t
p text = ;
Abstract: nil
6.2.1.2 Clauses
clause term = term, end
Abstract: c c
Priority: 1201
Condition: The principal functor ofc is not(:-)/1
Condition: The principal functor ofc is not(-->)/2
NOTE ISO/IEC 13211-1:1995 7.5 and 7.6 define how clauses become part of the database.
6.2.1.3 Grammar rules
grammar rule term = term, end
Abstract: gt gt
Priority: 1201
Condition: The principal functor ofgt is(-->)/2
NOTE 7.13.5 defines how a grammar rule in Prolog text is expanded into an equivalent clause when
_
Prolog text is prepared for execution. The first clause in dcg rule/2 defines how a semicontext is
expanded.
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
6.3.4.3 Operator table
The specifications of ISO/IEC 13211-1:1995, 6.2 Table 7 apply and in addition, the following
entry.
Priority Specifier Operator(s)
1105 xfy ’|’
NOTE The operator of the principal functor of a grammar rule, (-->)/2, is already in the table.
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
7 Language concepts and semantics
7.4 Prolog text
7.4.2 Directives
In addition to the directives of ISO/IEC 13211–1:1995, the directivesdynamic/1,multifile/1,
and discontiguous/1 are applicable to non-terminal indicators (7.13.3) which are used like
predicate indicators for the predicates which result from expanding these non-terminals.
7.4.4 Grammar rules
A grammar rule term in Prolog text (6.2.1.3) enables corresponding clauses to be added to the
database.
The non-terminal indicator NT//N of the non-terminal of the grammar rule head shall not
be the non-terminal indicator of a grammar control construct. Further the predicate indica-
tor NT/M where M is N+2, and NT//N is the non-terminal indicator of the non-terminal of
the grammar rule head shall not be the predicate indicator of a built-in predicate or a control
construct. Conversely, predicates NT/M shall not be defined or used when a corresponding
definition as non-terminal or grammar control construct exists.
During preparation for execution the Prolog processor converts grammar rule terms to Prolog
procedures of the database. 7.13.5 of this document defines a correspondence between gram-
mar rule terms and suitable clauses of a procedure in the database.
7.5 Database
7.5.1 Preparing a Prolog text for execution
If a Prolog grammar rule with non-terminal indicator NT//N is prepared for execution, and a
Prolog clause with predicate-indicator NT/M, where M is N+2, is already part of the extended
database, or vice versa, then the effect of this preparation for execution shall be implementation
defined.
7.13 Grammar rules
7.13.1 Format of grammar rules
A grammar rule has the format GRHead --> GRBody. where GRHead, the grammar rule head,
can be rewritten by GRBody, its grammar rule body. The head and the body of grammar rules
are constructed from terminals and non-terminals, including special non-terminals, the gram-
mar control constructs. The grammar rule head is a non-terminal, or a non-terminal, followed
by a semicontext):
NonTerminal --> GRBody.
NonTerminal, Semicontext --> GRBody.
The effect of aSemicontext which is not a terminal sequence shall be implementation defined.
The control constructs that may be used in a body are described in 7.14. An empty body is
represented by an empty terminal sequence: GRHead --> [].
© ISO/IEC 2025 — All rights reserved
ISO/IEC TS 13211–3:2025 (en)
NOTE There is no (-->)/1 form for grammar rules.
This document uses variables named S0, S1, ., S to represent the terminal sequences used as
arguments when processing grammar rules or when expanding grammar rules into clauses. In
this notation, the variables S0, S1, ., S can be regarded as a sequence of states, with S0 repre-
senting the initial state and the variable S representing the final state. Thus, if the variable Si
represents the terminal sequence in a given state, the variable Si+1 will represent the remaining
terminal sequence after parsing Si with a grammar rule.
7.13.2 Terminals and non-terminals, semicontext
In grammar
...