Roger Scowen
ISO/IEC DTR xxxxx:2004Grammar rules in Prolog
Introduction
This report is the first stage to defining Part 3 (Definite Clause Grammars) for the International Standard for Prolog, ISO/IEC 13211.
Prolog (Programming in Logic) combines the concepts of logical and algorithmic programming, and is recognized not just as an important tool in AI (Artificial Intelligence) and expert systems, but as a general purpose high-level programming language with some unique properties.
Grammar rules provide convenient and simple functionality for parsing and processing texts in a variety of languages. They have been implemented in many Prolog processors. The need to complete ISO/IEC 13211-1, the general core, as soon as possible meant it was not possible to include them in that standard. The gap would be filled with the completion of this part of ISO/IEC 13211.
This Draft Technical Report is written to have the same sequence and structure of clauses as ISO/IEC 13211-1 Prolog - Part 1 except that clauses that would be identical have not been reproduced.
Annex A is a suite of programs that are designed to show how an existing Prolog processor has implemented Grammar Rules. The results will help to show whether the standardization of Grammar Rules is desirable, and how precisely they can be defined.
Annex B is a logical definition of rules that define the expansion of grammar rules.
Roger Scowen
9 Birchwood Grove, Hampton, Middlesex
United Kingdom TW12 3DU
Tel: +44 (0)20 8979 7429;
Fax: +44 (0)20 8287 3810;
E-mail: (1)
(2)
2 September 2004
1 Scope
This part of ISO/IEC 13211 is designed to promote the applicability and portability of Prolog grammar rules in data processing systems that support standard Prolog as defined in ISO/IEC 13211-1:1995.
This part of ISO/IEC 13211 will specify:
a) The representation, syntax and constraints of Prolog grammar rules,
b) The semantic rules for interpreting Prolog grammar rules.
NOTE — This part of ISO/IEC 13211 will supplement ISO/IEC 13211 -1:1995
2 Normative references
The following standards contain provisions which, through reference in this text, constitute provisions of this part of ISO/IEC 13211. At the time of publication, the editions indicated were valid. All standards are subject to revision, and parties to agreements based on this part of ISO/IEC 13211 are encouraged to investigate the possibility of applying the most recent editions of the standards listed below. Members of IEC and ISO maintain registers of currently valid International Standards.
ISO/IEC 13211-1 : 1995 Information technology --- Programming languages --- Prolog --- Part 1: General core.
3 Definitions
This terminology for Prolog has a format modelled on that of ISO 2382.
An entry consists of a phrase (in bold type) being defined, followed by its definition. Words and phrases defined in the glossary are printed in italics when they are used in other entries. When a definition contains two words or phrases defined in separate entries directly following each other (or separated only by a punctuation sign), * (an asterisk) separates them.
Words and phrases not defined in this glossary are assumed to have the meaning given in ISO 2382-15; if they do not appear in ISO 2382-15, then they are assumed to have their usual meaning.
For the purposes of ISO/IEC 13211, the following additional definitions apply:
1 body (of a grammar-rule): The second argument of a grammar-rule. A grammar-body-sequence, or a grammar-body-alternatives, or a grammar-body-choice, or a grammar-body-element.
2 clause-term: A read-term T. in Prolog text where T does not have principal functor (:-)/1 nor principal functor (-->)/2.
3 grammar-body-alternatives: A compound term with principal functor (';')/2 and each argument is a body (of a grammar-rule).
4 grammar-body-choice: A compound term with principal functor ('->')/2, the first argument is a body (of a grammar-rule), and the second argument is a grammar-body-alternatives.
5 grammar-body-cut: The atom !.
6 grammar-body-element: A grammar-body-cut, or a grammar-body-goal, or a grammar-body-nonterminal, or a grammar-body-terminal.
7 grammar-body-goal: A compound term with principal functor ('{}')/1 whose argument is a goal.
8 grammar-body-nonterminal: A non-terminal (of a grammar).
9 grammar-body-sequence: A compound term with principal functor (',')/2 and each argument is a body (of a grammar-rule).
10 grammar-body-terminal: A terminal (of a grammar).
11 grammar-rule: A compound term with principal functor (-->)/2.
12 grammar-rule-term: A read-term T. in Prolog text where T is a grammar-rule.
13 head (of a grammar-rule): The first argument of a grammar-rule. Either a non-terminal (of a grammar), or a compound term whose principal functor is (',')/2 the first argument is a non-terminal (of a grammar), and the second argument is a sequence of terminals.
14 new variable with respect to a term T: A variable that is not an element of the variable set of T.
15 non-terminal (of a grammar): An atom or compound term that denotes a non-terminal symbol of the grammar.
16 sequence of terminals: A terminal (of a grammar), or a compound term whose principal functor is (',')/2, the first argument is a terminal (of a grammar), and the second argument is a sequence of terminals.
17 terminal (of a grammar): A list whose elements denote successive terminal symbols of the grammar.
18 variable, new with respect to a term T: See 14 new variable with respect to a term T.
4 Symbols and abbreviations
Not applicable.
5 Compliance
5.1 Prolog processor
A conforming Prolog processor that supports grammar rules shall:
a) Correctly prepare for execution Prolog text which conforms to:
1) the requirements of this part of ISO/IEC 13211, and
2) the requirements of part 1 of ISO/IEC 13211, and
3) the implementation defined and implementation specific features of the Prolog processor,
b) Correctly execute Prolog goals which have been prepared for execution and which conform to:
1) the requirements of this part of ISO/IEC 13211, and
2) the implementation defined and implementation specific features of the Prolog processor,
c) Reject any Prolog text or read-term whose syntax fails to conform to:
1) the requirements of this part of ISO/IEC 13211, and
2) the implementation defined and implementation specific features of the Prolog processor,
d) Specify all permitted variations from this part of ISO/IEC 13211 in the manner prescribed by this part of ISO/IEC 13211, and
e) Offer a strictly conforming mode which shall reject the use of an implementation specific feature in Prolog text or while executing a goal.
5.2 Prolog text
5.3 Prolog goal
5.4 Documentation
A conforming Prolog processor shall be accompanied by documentation that completes the definition of every implementation defined and implementation specific feature specified in this part of ISO/IEC 13211.
5.5 Extensions
A processor may support, as an implementation specific feature, any construct that is implicitly or explicitly undefined in the part of ISO/IEC 13211.
6 Syntax
Prolog text (6.2) is represented abstractly by an abstract list x where x is:
a) d . t where d is the abstract syntax for a directive, and t is Prolog text, or
b) g . t where g is the abstract syntax for a grammar rule, and t is Prolog text, or
c) c . t where c is the abstract syntax for a clause, and t is Prolog text, or
d) nil, the empty list. \end{enumerate}
6.1 Notation
6.2 Prolog text and data
Prolog text is a sequence of read-terms which denote (1) directives, (2) grammar rules, and (3) clauses of user-defined procedures.
Subclause 7.4 defines the correspondence between Prolog text and the complete database .
6.2.1 Prolog text
Prolog text is a sequence of directive-terms, grammar-rule terms, and clause-terms.
prolog text = / p textAbstract: / pt / pt
p text = / directive term , / p text
Abstract: / d . t / d / t
p text = / grammar rule term , / p text
Abstract: / g . t / g / t
p text = / clause term , / p text
Abstract: / c . t / c / t
p text = / ;
Abstract: / nil
6.2.1.1 Directives
directive term = / term, endAbstract: / dt / dt
Priority: / 1201
Condition: / The principal functor of dt is (:-)/1
directive = / directive term
Abstract: / d / :-(d)
NOTE — Subclause 7.4.2 defines the possible directives and their meaning.
6.2.1.2 Clauses
clause term = / term, endAbstract: / c / c
Priority: / 1201
Condition: / The principal functor of c is not (:-)/1
Condition: / The principal functor of c is not (-->)/2
NOTE — Subclause 7.4.3 defines how each clause becomes part of the database.
6.2.1.3 Grammar rules
grammar rule term = / term, endAbstract: / gt / gt
Priority: / 1201
Condition: / The principal functor of c is (-->)/2
grammar rule = / grammar rule term
Abstract: / g / g
NOTE —Subclause 7.13 defines how a grammar rule in Prolog text is expanded into an equivalent clause when Prolog text is prepared for execution.
6.2.2 Prolog data
7 Language concepts and semantics
7.13 Grammar rules
8 Built-in predicates
8.18 Grammar rules
8.18.1 'C'/3
8.18.2 term_expansion/2
8.18.3 expand_term/2
8.18.4 phrase/2
8.18.5 phrase/3
9 Evaluable functors
Annex A - GRIND: Grammar rules in depth: A test suite
This package of Prolog Programs tests the implementation of Grammar Rules in a Prolog system.
Note that 'ok' does not necessarily imply the results are correct, or that the standard would make similar requirements.
Sometimes it is necessary to comment out some of the tests when running GRIND on a particular Prolog system because it causes a loop or other system failure.
A.1 GRIND (r382)
% ------GRIND ------
% (Prolog Grammar Rules IN Depth)
%
% An investigation of grammar rules for
% standard Prolog (ISO/IEC 13211-3)
% (1) Load a file to simulate any features
% of Standard Prolog that are not in the
% system being tested, for example
% consult(r382sics38).
% or
% consult(r382sics21).
% or
% consult(r382bim).
%
% This file must also define a procedure
% system_tested(A)
% where A is an atom identifying the
% system being tested.
% (2) Load this file
% consult(r382).
% (3) Run all tests (which sends the
% results to r382r1)
% run_all_tests.
% (4) Check the results of the tests
% by running the program r382check
% Known errors
% 1) None
% To be done
% xxx
% ------Define operators ------
% None yet required
% ------Utility predicates ------
% ------Output predicates ------
% write_list(L) outputs a message defined by L
write_list([]).
write_list([T | Tail]) :-
( T == nl ->
nl
; write(T)
),
write_list(Tail).
% ------
% write_list_as_table(H, L)
% outputs the heading H using
% write_list/2 and then outputs each
% element of L on a line by itself
% using write_list/2
write_list_as_table(H, _) :-
write_list(H),
write_list([nl]),
fail.
write_list_as_table(_, L) :-
write_each_line_of_table(L).
write_each_line_of_table([]).
write_each_line_of_table([H | T]) :-
write_list([H]),
write_list([nl]),
write_each_line_of_table(T).
% ------Run all tests ------
% Test expand_term/2
run_1 :-
test_gr(GR),
expand_term(GR, EGR),
write_list(['gr(( ']),
writeq(GR),
write_list([' ), ', nl, ' (']),
writeq(EGR),
write_list([')).', nl, nl]),
fail.
run_1.
% Test whether required built-in procedures exist
run_2 :-
test_gr_procs(GRP),
findall(P, predicate_property(GRP, P),
L),
write_list(['grp(( ']),
writeq(GRP),
write_list([' ), ', nl, ' (']),
writeq(L),
write_list([')).', nl, nl]),
fail.
run_2.
% Are grammar rule clauses consistent
% with expand_term/2
run_3 :-
clause(a(N, S0, S1), B1),
write_list([nl]),
writeq(( a(N, S0, S1) :- B1 )),
write_list(['.', nl]),
fail.
run_3 :-
write_list([nl]).
run_all_tests :-
open('r382r1', write, S),
set_output(S),
write_list([nl, ' :- dynamic (grind/1,
gr/2, grp/2).', nl]),
system_tested(SYS),
write_list(['grind(']),
writeq(SYS),
write_list([').', nl]),
run_1,
run_2,
write_list([nl, ':- dynamic a/3.',
nl]),
run_3,
write_list([nl]),
close(S, []).
% ------Test cases ------
% Test cases (1) expand_term
test_gr(( a(1) --> b )).
test_gr(( a(2) --> [b] )).
test_gr(( a(3) --> [] )).
test_gr(( a(4) --> "b" )).
test_gr(( a(5) --> {b} )).
test_gr(( a(6) --> b, c )).
test_gr(( a(7) --> b ; c )).
test_gr(( a(8) --> b -> c )).
test_gr(( a(9) --> b1, b2 -> c ; d )).
test_gr(( a(10) --> b -> c1, c2 ; d )).
test_gr(( a(11) --> b -> c ; d1, d2 )).
test_gr(( a(12) --> b, !, c, d )).
test_gr(( a(13) --> b, !, c ; d )).
test_gr(( a(14) --> [abc, xyz] )).
test_gr(( a(15) --> [abc | xyz] )).
test_gr(( a(16) --> [_] )).
test_gr(( a(17) --> [[], {}, 3, 3.2,
a(b)] )).
test_gr(( a(18) --> _ )).
test_gr(( a(19) --> '{}'((c,d)) )).
test_gr(( a(20) --> {c,d} )).
test_gr(( a(21), [t] --> b, c )).
test_gr(( a(22), [t] --> b, [t] )).
test_gr(( a(23), [t] --> b, [s, t] )).
test_gr(( a(24), [t] --> b, [s], [t] )).
test_gr(( a(25), [t], [t2] --> b, c )).
test_gr(( a(26), b --> c )).
test_gr(( [b], a(27) --> c )).
test_gr(( a(28) --> \+ b, c )).
test_gr(( a(29) --> true, c )).
test_gr(( a(30) --> false, c )).
test_gr(( a(31) --> b, \+ c, d )).
test_gr(( a(32, X) --> call(X), c )).
test_gr(( '[' --> b, c )).
test_gr(( '=' --> b, c )).
test_gr(( c(X) --> b(X) )).
% Test cases (2) Built-in predicates and
% user defined procedures
test_gr_procs('C'(_, _, _)).
test_gr_procs(term_expansion(_, _)).
test_gr_procs(expand_term(_, _)).
test_gr_procs(phrase(_, _)).
test_gr_procs(phrase(_, _,_)).
% Test cases (3) Consulting grammar
% rules
:- dynamic a/3.
:- dynamic '['/2.
:- dynamic a/4.
a(1) --> b.
a(2) --> [b].
a(3) --> [].
a(4) --> "b".
a(5) --> {b}.
a(6) --> b, c.
a(7) --> b ; c.
a(8) --> b -> c.
a(9) --> b1, b2 -> c ; d.
a(10) --> b -> c1, c2 ; d.
a(11) --> b -> c ; d1, d2.
a(12) --> b, !, c, d.
a(13) --> b, !, c ; d.
a(14) --> [abc, xyz].
a(15) --> [abc | xyz].
a(16) --> [_].
a(17) --> [[], {}, 3, 3.2, a(b)].
a(18) --> _.
a(19) --> '{}'((c,d)).
a(20) --> {c,d}.
a(21), [t] --> b, c.
a(22), [t] --> b, [t].
a(23), [t] --> b, [s, t].
a(24), [t] --> b, [s], [t].
a(25), [t], [t2] --> b, c.
a(26), b --> c.
[b], a(27) --> c.
a(28) --> \+ b, c.
a(29) --> true, c.
a(30) --> false, c.
a(31) --> b, \+ c, d.
a(32, X) --> call(X), c.
'[' --> b, c .
'=' --> b, c .
c(X) --> b(X) .
A.2 Example of a file defining the required predicates (r382sics21)
This file defines the system_tested/1 procedure and those built-in predicates that are defined in ISO standard Prolog, but not in the system being tested.
system_tested('SICStus 2.1 # 9').
close(S, _) :-
close(S).
A.3 Check results from running GRIND (r382check)
% ------Check GRIND ------
% (Prolog Grammar Rules IN Depth)
%
% Check an investigation of grammar
% rules for standard Prolog
% (ISO/IEC 13211-3)
% (1) Load a file to simulate any
% features of Standard Prolog that are
% not in the system being tested, for
% example
% consult(r382sics38).
% or
% consult(r382sics21).
% or
% consult(r382bim).
%
% This file must also define a procedure
% system_tested(A)
% where A is an atom identifying the
% system being tested.
% (2) Load this file
% consult(r382check).
% (3) Load the file of results obtained
% from running GRIND
% consult(r382r1).
% (4) Checking the results.
% run_all_checks.
% Known errors
% 1) None
% To be done
% xxx
% ------Define operators ------
% None yet required
% ------Utility predicates ------
% ------Output predicates ------
% write_list(L) outputs a message
% defined by L
write_list([]).
write_list([T | Tail]) :-
( T == nl ->
nl
; write(T)
),
write_list(Tail).
% ------
% write_list_as_table(H, L)
% outputs the heading H using
% write_list/2 and then outputs each
% element of L on a line by itself
% using write_list/2
write_list_as_table(H, _) :-
write_list(H),
write_list([nl]),
fail.
write_list_as_table(_, L) :-
write_each_line_of_table(L).
write_each_line_of_table([]).
write_each_line_of_table([H | T]) :-
write_list([H]),
write_list([nl]),
write_each_line_of_table(T).
% ------
expand(( a(1)-->b ),
(a(1, S0, S1):-b( S0, S1))).
expand(( a(2)-->[b] ),
(a(2, S0, S1):- 'C'( S0,b, S1))).
expand(( a(3)-->[] ),
(a(3, S1, S2):- S2= S1)).
expand(( a(4)-->[98] ),
(a(4, S0, S1):- 'C'( S0,98, S1))).
expand(( a(5)-->{b} ),
(a(5, S0, S1):-b, S1= S0)).
expand(( a(6)-->b,c ),
(a(6, S1, S3):-b( S1, S2),c( S2, S3))).
expand(( a(7)-->b;c ),
(a(7, S1, S3):-b( S1, S3);c( S1, S3))).
expand(( a(8)-->b->c ),
(a(8, S1, S3):-b( S1, S2)->c( S2, S3))).
expand(( a(9)-->b1,b2->c;d ),
(a(9, S2, S5):-b1( S2, S3),b2( S3, S4)->c( S4, S5);d( S2, S5))).
expand(( a(10)-->b->c1,c2;d ),
(a(10, S2, S5):-b( S2, S3)->c1( S3, S4),c2( S4, S5);d( S2, S5))).
expand(( a(11)-->b->c;d1,d2 ),
(a(11, S2, S5):-b( S2, S3)->c( S3, S5);d1( S2, S4),d2( S4, S5))).
expand(( a(12)-->b,!,c,d ),
(a(12, S2, S5):-b( S2, S3),!,c( S3, S4),d( S4, S5))).
expand(( a(13)-->b,!,c;d ),
(a(13, S2, S5):-b( S2, S4),!,c( S4, S5);d( S2, S5))).
expand(( a(14)-->[abc,xyz] ),
(a(14, T1, T3):-'C'( T1,abc, T2),'C'( T2,xyz, T3))).
expand(( a(15)-->[abc|xyz] ),
(a(15,_1361,_1362):-'C'(_1361,abc, T2),xyz( T2,_1362))).
expand(( a(16)-->[_1343] ),
(a(16,_1361,_1362):-'C'(_1361,_1343,_1362))).
expand(( a(17)-->[[],{},3,3.2,a(b)] ),
(a(17,_1375,_1376):-'C'(_1375,[],_1396),'C'(_1396,{},_1389),'C'(_1389,3,_1382),'C'(_1382,3.2,_1378),'C'(_1378,a(b),_1376))).
expand(( a(18)-->_1347 ),
(a(18, S1, S2):-phrase(_1347, S1, S2))).
expand(( a(19)-->{c,d} ),
(a(19, T3,_1365):-(c,d),_1365= T3)).
expand(( a(20)-->{c,d} ),
(a(20, T3,_1365):-(c,d),_1365= T3)).
expand(( a(21),[t]-->b,c ),
(a(21,_189, S2):-(b(_189,_195),c(_195,_200)), 'C'( S2,t,_200))).
expand(( a(22),[t]-->b,[t] ),
(a(22,_1372,_1373):-
(b(_1372,_1378),'C'(_1378,t,_1382)),'C'(_1373,t,_1382))).
expand(( a(23),[t]-->b,[s,t] ),
(a(23,_1374,_1375):-
(b(_1374,_1380),
'C'(_1380,s,_1382),'C'(_1382,t,_1384)),'C'(_1375,t,_1384))).
expand(( a(24),[t]-->b,[s],[t] ),
(a(24,_1377,_1378):-
(b(_1377,_1383),
'C'(_1383,s,_1387),'C'(_1387,t,_1391)),'C'(_1378,t,_1391))).
expand(( a(25),[t],[t2]-->b,c ),
(a(25,_194,_195):-
(b(_194,_200),c(_200,_205)), 'C'(_195,t,_212), 'C'(_212,t2,_205))).
expand(( a(26),b-->c ),
(a(26,_1365, T2):-c(_1365,_1371),b( T2,_1371))).
expand(( [b],a(27)-->c ),
('.'(b,[],_1368,_1369):-c(_1368,_1374),a(27,_1369,_1374))).
expand(( a(28)--> \+b,c ),
(a(28,_608,_609):-(b(_608,_619)->fail;_617=_608),c(_617,_609))).
expand(( a(29)-->true,c ),
(a(29,_606,_607):-true(_606,_612),c(_612,_607))).
expand(( a(30)-->false,c ),
(a(30,_606,_607):-false(_606,_612),c(_612,_607))).
expand(( a(31)-->b,\+c,d ),
(a(31,_611,_612):-
b(_611,_617),(c(_617,_627)->fail;_625=_617),d(_625,_612))).
expand(( a(32,_574)-->call(_574),c ),
(a(32,_574,_610,_611):-call(_574,_610,_617),c(_617,_611))).
expand(( '[' -->b,c ),
('['( S1, S3):-b( S1, S2),c( S2, S3))).
expand(( '=' -->b,c ),
('='( S1, S3):-b( S1, S2),c( S2, S3))).
expand(( c(_168)-->b(_168) ),
(c(_168,_183,_184):-b(_168,_183,_184))).
bip( 'C'(_175,_176,_177) ).
bip( term_expansion(_175,_176) ).
bip( expand_term(_175,_176) ).
bip( phrase(_175,_176) ).
bip( phrase(_175,_176,_177) ).
% ------
% Check the results
% ------
output_system_tested :-
grind(Sys),
system_tested(S),
write_list([nl,
'Checking Grammar Rules in ']),
write_list(['system ', Sys, nl,
' using ']),
write_list(['system ', S, nl]).
check_expand_term :-
write_list([nl,
'(1) - Does expand_term/3']),
write_list([' work as expected?',
nl]),
clause(gr(T, ET1), true),
( expand(T, ET) ->
( ET = ET1 ->
write_list([' ok - expanding ',
T, nl])
;
write_list([' fail- expanding ',
T, nl]),
write_list([' correct = ', ET,
nl]),
write_list([' wrong = ', ET1,
nl])
)
;
write_list([' ?? - expanding ', T,
nl])
),
fail.
check_expand_term :-
expand(T, _),
\+ clause(gr(T, _), true),
write_list([
' not tested - expanding ', T, nl]),
fail.
check_expand_term.
check_existence_of_procedures :-
write_list([nl,
'(2a) - The following procedures']),
write_list([' exist in the system',
nl]),
grp(BIP, Property_list),
functor(BIP, F, N),
write_list([' ', F, '/', N, ' - ']),
write_list([Property_list, nl]),
fail.
check_existence_of_procedures :-
write_list([nl,
'(2b) - The following procedures ',
'do not exist in the system', nl]),
bip(BIP),
\+ grp(BIP, _),
functor(BIP, F, N),
write_list([' ', F, '/', N]),
fail.
check_existence_of_procedures.
check_grammar_rule_clauses :-
write_list([nl, '(3) - Are grammar ',
'rule clauses consistent ',
'with expand_term/3?', nl]),
check_grammar_rule_clauses(_).
check_grammar_rule_clauses.
check_grammar_rule_clauses(N) :-
clause(a(N, S0, S1), ET),
expand((a(N) --> B), EB),
( ( a(N, S0, S1) :- EB ) = ET ->
write_list([nl, ' ok - a(', N,
')'])
; write_list([nl, ' fail- ', a(N),
' --> ', B]),
write_list([nl, ' expected:',
a(N, S0, S1), ' :- ', EB]),
write_list([nl, ' expanded:', ET])
),
fail.
run_all_checks :-
open('r382c1', write, S),
set_output(S),
output_system_tested,
check_expand_term,
check_existence_of_procedures,
check_grammar_rule_clauses,
write_list([nl]),
close(S, []).
A.3 Running GRIND – An example
GRIND was run on SICStus 3.8 with the following results. It was necessary to comment out tests 15, 25, 26, 27 because they gave errors. The following results show what happened after this was done.
A.3.1 Define system_tested/1 for SICStus 3.8 (r382sics38)
system_tested('SICStus 3.8 (sparc-solaris-5.5.1)').
A.3.2 Results from GRIND (r382r1)
:- dynamic (grind/1, gr/2, grp/2).
grind('SICStus 3.8 (sparc-solaris-5.5.1)').
gr(( a(1)-->b ),
(a(1,_603,_604):-b(_603,_604))).
gr(( a(2)-->[b] ),
(a(2,_605,_606):-'C'(_605,b,_606))).
gr(( a(3)-->[] ),
(a(3,_603,_604):-_604=_603)).
gr(( a(4)-->[98] ),
(a(4,_605,_606):-'C'(_605,98,_606))).
gr(( a(5)-->{b} ),
(a(5,_605,_606):-b,_606=_605)).
gr(( a(6)-->b,c ),
(a(6,_606,_607):-b(_606,_612),c(_612,_607))).
gr(( a(7)-->b;c ),
(a(7,_606,_607):-b(_606,_607);c(_606,_607))).
gr(( a(8)-->b->c ),
(a(8,_606,_607):-b(_606,_615)->c(_615,_607))).
gr(( a(9)-->b1,b2->c;d ),
(a(9,_612,_613):-b1(_612,_624),b2(_624,_629)->c(_629,_613);d(_612,_613))).
gr(( a(10)-->b->c1,c2;d ),
(a(10,_612,_613):-b(_612,_624)->c1(_624,_629),c2(_629,_613);d(_612,_613))).
gr(( a(11)-->b->c;d1,d2 ),
(a(11,_612,_613):-b(_612,_624)->c(_624,_613);d1(_612,_634),d2(_634,_613))).
gr(( a(12)-->b,!,c,d ),
(a(12,_612,_613):-b(_612,_618),!,c(_618,_623),d(_623,_613))).
gr(( a(13)-->b,!,c;d ),
(a(13,_612,_613):-b(_612,_621),!,c(_621,_613);d(_612,_613))).
gr(( a(14)-->[abc,xyz] ),
(a(14,_607,_608):-'C'(_607,abc,_612),'C'(_612,xyz,_608))).
gr(( a(16)-->[_567] ),
(a(16,_605,_606):-'C'(_605,_567,_606))).
gr(( a(17)-->[[],{},3,3.2,a(b)] ),
(a(17,_619,_620):-'C'(_619,[],_642),'C'(_642,{},_635),'C'(_635,3,_628),'C'(_628,3.2,_624),'C'(_624,a(b),_620))).
gr(( a(18)-->_571 ),
(a(18,_603,_604):-phrase(_571,_603,_604))).
gr(( a(19)-->{c,d} ),
(a(19,_608,_609):-(c,d),_609=_608)).
gr(( a(20)-->{c,d} ),
(a(20,_608,_609):-(c,d),_609=_608)).
gr(( a(21),[t]-->b,c ),
(a(21,_614,_615):-(b(_614,_620),c(_620,_625)),'C'(_615,t,_625))).
gr(( a(22),[t]-->b,[t] ),
(a(22,_616,_617):-(b(_616,_622),'C'(_622,t,_628)),'C'(_617,t,_628))).
gr(( a(23),[t]-->b,[s,t] ),
(a(23,_618,_619):-(b(_618,_624),'C'(_624,s,_628),'C'(_628,t,_630)),'C'(_619,t,_630))).
gr(( a(24),[t]-->b,[s],[t] ),
(a(24,_621,_622):-(b(_621,_627),'C'(_627,s,_633),'C'(_633,t,_639)),'C'(_622,t,_639))).
gr(( a(28)--> \+b,c ),
(a(28,_608,_609):-(b(_608,_619)->fail;_617=_608),c(_617,_609))).
gr(( a(29)-->true,c ),
(a(29,_606,_607):-true(_606,_612),c(_612,_607))).
gr(( a(30)-->false,c ),
(a(30,_606,_607):-false(_606,_612),c(_612,_607))).
gr(( a(31)-->b,\+c,d ),
(a(31,_611,_612):-b(_611,_617),(c(_617,_627)->fail;_625=_617),d(_625,_612))).
gr(( a(32,_574)-->call(_574),c ),
(a(32,_574,_610,_611):-call(_574,_610,_617),c(_617,_611))).
gr(( '['-->b,c ),
('['(_603,_604):-b(_603,_609),c(_609,_604))).
gr(( = -->b,c ),
(_603=_604:-b(_603,_609),c(_609,_604))).
gr(( c(_570)-->b(_570) ),
(c(_570,_605,_606):-b(_570,_605,_606))).
grp(( 'C'(_581,_582,_583) ),
([built_in])).
grp(( term_expansion(_581,_582) ),
([])).
grp(( expand_term(_581,_582) ),
([built_in])).
grp(( phrase(_581,_582) ),
([(meta_predicate phrase(:,?)),built_in])).
grp(( phrase(_581,_582,_583) ),
([(meta_predicate phrase(:,?,?)),built_in])).
:- dynamic a/3.
a(1,_668,_669):-b(_668,_669).
a(2,_668,_669):-'C'(_668,b,_669).
a(3,_668,_669):-_669=_668.
a(4,_668,_669):-'C'(_668,98,_669).
a(5,_668,_669):-b,_669=_668.
a(6,_668,_669):-b(_668,_696),c(_696,_669).
a(7,_668,_669):-b(_668,_669);c(_668,_669).
a(8,_668,_669):-b(_668,_696)->c(_696,_669).
a(9,_668,_669):-b1(_668,_702),b2(_702,_699)->c(_699,_669);d(_668,_669).
a(10,_668,_669):-b(_668,_705)->c1(_705,_699),c2(_699,_669);d(_668,_669).
a(11,_668,_669):-b(_668,_705)->c(_705,_669);d1(_668,_696),d2(_696,_669).
a(12,_668,_669):-b(_668,_705),!,c(_705,_696),d(_696,_669).
a(13,_668,_669):-b(_668,_702),!,c(_702,_669);d(_668,_669).
a(14,_668,_669):-'C'(_668,abc,_698),'C'(_698,xyz,_669).
a(16,_668,_669):-'C'(_668,_693,_669).
a(17,_668,_669):-'C'(_668,[],_725),'C'(_725,{},_718),'C'(_718,3,_711),'C'(_711,3.2,_704),'C'(_704,a(b),_669).
a(18,_668,_669):-phrase(user:_693,_668,_669).
a(19,_668,_669):-(c,d),_669=_668.
a(20,_668,_669):-(c,d),_669=_668.
a(21,_668,_669):-(b(_668,_700),c(_700,_697)),'C'(_669,t,_697).
a(22,_668,_669):-(b(_668,_701),'C'(_701,t,_698)),'C'(_669,t,_698).
a(23,_668,_669):-(b(_668,_708),'C'(_708,s,_702),'C'(_702,t,_698)),'C'(_669,t,_698).
a(24,_668,_669):-(b(_668,_708),'C'(_708,s,_702),'C'(_702,t,_698)),'C'(_669,t,_698).
a(28,_668,_669):-(b(_668,_699)->fail;_695=_668),c(_695,_669).
a(29,_668,_669):-true(_668,_696),c(_696,_669).
a(30,_668,_669):-false(_668,_696),c(_696,_669).
a(31,_668,_669):-b(_668,_711),(c(_711,_699)->fail;_695=_711),d(_695,_669).
A3.3 Report produced by checking GRIND (r382c1)
Checking Grammar Rules in system SICStus 3.8 (sparc-solaris-5.5.1)
using system SICStus 3.8 (sparc-solaris-5.5.1)
(1) - Does expand_term/3 work as expected?
ok - expanding a(1)-->b
ok - expanding a(2)-->[b]
ok - expanding a(3)-->[]
ok - expanding a(4)-->[98]
ok - expanding a(5)-->{b}
ok - expanding a(6)-->b,c
ok - expanding a(7)-->b;c
ok - expanding a(8)-->b->c
ok - expanding a(9)-->b1,b2->c;d
ok - expanding a(10)-->b->c1,c2;d
ok - expanding a(11)-->b->c;d1,d2
ok - expanding a(12)-->b,!,c,d
ok - expanding a(13)-->b,!,c;d
ok - expanding a(14)-->[abc,xyz]
ok - expanding a(16)-->[_886]
ok - expanding a(17)-->[[],{},3,3.2,a(b)]
ok - expanding a(18)-->_890
ok - expanding a(19)-->{c,d}
ok - expanding a(20)-->{c,d}
ok - expanding a(21),[t]-->b,c
ok - expanding a(22),[t]-->b,[t]
ok - expanding a(23),[t]-->b,[s,t]
ok - expanding a(24),[t]-->b,[s],[t]
ok - expanding a(28)--> \+b,c
ok - expanding a(29)-->true,c
ok - expanding a(30)-->false,c
ok - expanding a(31)-->b,\+c,d
ok - expanding a(32,_900)-->call(_900),c
ok - expanding [-->b,c
ok - expanding = -->b,c
ok - expanding c(_889)-->b(_889)
not tested - expanding a(15)-->[abc|xyz]
not tested - expanding a(25),[t],[t2]-->b,c
not tested - expanding a(26),b-->c
not tested - expanding [b],a(27)-->c
(2a) - The following procedures exist in the system
C/3 - [built_in]
term_expansion/2 - []
expand_term/2 - [built_in]
phrase/2 - [(meta_predicate phrase(:,?)),built_in]
phrase/3 - [(meta_predicate phrase(:,?,?)),built_in]
(2b) - The following procedures do not exist in the system
(3) - Are grammar rule clauses consistent with expand_term/3?
ok - a(1)
ok - a(2)
ok - a(3)
ok - a(4)
ok - a(5)
ok - a(6)
ok - a(7)
ok - a(8)
ok - a(9)
ok - a(10)
ok - a(11)
ok - a(12)
ok - a(13)
ok - a(14)
ok - a(16)
ok - a(17)
ok - a(18)
ok - a(19)
ok - a(20)
ok - a(28)
ok - a(29)
ok - a(30)
ok - a(31)
A.4 Problem cases
Note that
?- expand_term((a --> [X]), X).
results in an infinite term in SICStus 2.1 #9: Wed Sep 20 15:29:20 BST 1995.
X = (a(_B,_A):-'C'(_B,(a(_B,_A):-'C'(_B,(a(_B,_A):-'C'(_B,(a(_B,_A):- ...
but
% capulin% sicstus
% SICStus 3.8 (sparc-solaris-5.5.1): Mon Nov 22 10:54:50 MET 1999
% Licensed to npl.co.uk
% | ?- expand_term((a --> [X]), X).
%
% X = a(_A,_B):-'C'(_A,(a(_A,_B):-'C'(_A,(a(_A,_B):-'C'(_A,(a(_A,_B)
% :-'C'(_A,(a(...):-'C'(...)),_B)),_B)),_B)),_B) ? ;
no
c:\rs4\standard\st88.doc12004-09-02
Roger Scowen
Annex B - A logical expansion of grammar rules
These tables present a logical view for the expansion of grammar rules.
B.1 Expand a grammar rule
‘-->‘(‘,’(Head, Terminal_list), Body) / ‘:-’(head(Head, S0, S2), ‘,’(body(Body, S0, S1), terminals(Terminal_list, S1, S2))‘-->‘(Head, Body) / ‘:-’(head(Head, S0, S2), body(Body, S0, S2))
B.2 Expand a terminal list
terminals([], S0, S1)terminals(‘.’(T, []), S0, S1) / T_t = ‘C’(S0, T, S1)
terminals(‘.’(T1, T2), S0, S2) / T_t1 = ‘C’(S0, T1, S1)
T_t2 = ‘C’(S1, T2, S2)
T_t = ‘,’(T_t1, T_t2)
B.3 Expand a head
head(Head, S0, S2) / Head =.. Univ_head,append(Univ_head, [S0, S2], Univ_H),
H =.. Univ_H
B.4 Expand a body
body(‘;’(‘->‘(If, Then), Else), S0, S2) / B_if = body(If, S0, S1),B_then = body(Then, S1, S2),
B_else = body(Else, S1, S2),
B = ‘;’(‘->‘(B_if, B_then), B_else)
body(‘->‘(If, Then), S0, S2) / B_if = body(If, S0, S1),
B_then = body(Then, S1, S2),
B = ‘->‘(B_if, B_then)
body(‘;‘(Either, Or), S0, S1) / B_either = body(Either, S0, S1),
B_or = body(Or, S0, S1),
B = ‘;‘(B_either, B_or)
body(‘,’(First, Second), S0, S1) / B_first = body(First, S0, S1),
B_second = body(Second, S1, S2),
B = ‘,’(B_first, B_second)
body(!, S0, S2) / B = ‘,’(!, S0 = S2)
body(‘{}’(Goal), S0, S2) / B = ‘,’(Goal, S0 = S2)
body([], S0, S2)
body(‘.’(T, []), S0, S1) / B = terminals(‘.’(T, []), S0, S1)
body(‘.’(T1, T2), S0, S2) / B = terminals(‘.’(T1, T2), S0, S2)
body(Body, S0, S2) / Body =.. Univ_body,
append(Univ_body, [S0, S2], Univ_B),
B =.. Univ_B
c:\rs4\standard\st88.doc12004-09-02
Roger Scowen
c:\rs4\standard\st88.doc12004-09-02