Grammar Rules

 

 

grammar_rule-->

      grammar_head,

      [-->],

      grammar_body.

 

grammar_head-->

      non_terminal,

      ([','],terminal|[]).

 

grammar_body-->

      grammar_arm,

      ([';'],grammar_body|[]).

 

grammar_arm-->

      grammar_and,

      (['-->'],grammar_and|[]).

 

grammar_and -->

      grammar_item,

      ([','],grammar_and|[]).

 

grammar_item-->

      variable

|     non_terminal

|     terminal

|     ['!']

|     ['('],grammar_body,[')']

|     ['{'],prolog_body,['}'].

 

non_terminal-->

      -a Prolog callable term -.

 

terminal-->

      ['[',']']

|     ['['],terminals,[']'].

 

terminals -->

      any_prolog_term,

      ([','],terminals|[]).

 

 

 

'C'/3

 

 

'C'([Token|Tokens],Token,Tokens).

 

 

 

 

 

The wrong way to translate grammar rules into Prolog

 

The obvious translation of grammar rules into Prolog is the one used in the Clocksin & Mellish book (2nd edition), but there is a mistake that must be corrected. See the following grammar rule, and how it is translated in Clocksin and Mellish.

 

Grammar 1 for relative clauses (p. 289):

 

rel_clause(X,P1,P1andP2) -->

  [that],

   verb_phrase(X,P2).

 

rel_clause(_,P,P) -->

   [].

 

Translation by Clocksin and Mellish:

 

rel_clause(X,P1,P1andP2,[that|S1],S):-

   verb_phrase(X,P2,S1,S).

 

rel_clause(_,P,P,S,S).

 

 

But we have a problem with this kind of translation, for instance, when we need to use a cut:

 

 

Grammar 2 for relative clauses (pages 289-290):

 

 rel_phrase(X,P1,P1&P2) -->

   {must_be_relativised(X,P1)},

   !,

   [that],

   verb_phrase(X,P2).

 

 rel_phrase(X, P1, P1&P2) -->

   {may_be_relativised(X,P1)},

   [that],

   verb_phrase(X,P2).

 

 rel_phrase(_,P,P) -->

    [].

 

Translation into Prolog by Clocksin and Mellish

 

 rel_phrase(X,P1,P1&P2,[that|S1],S):-

    must_be_relativised(X,P1),

    !,

    verb_phrase(X,P2).

 

 rel_phrase(X,P1,P1&P2,[that|S1],S):-

    may_be_relativised(X,P1),

    verb_phrase(X,P2).

 

  rel_phrase(_,P,P,S,S).

 

 

 

Phrase/[2,3]

 

 

phrase(P,L) is true iff list L can be parsed as a phrase of type P.

 

Calling phrase(P,L) is very like calling P(L,[]), except that the first argument of phrase/2 can be ANY term which would be accepted as a grammar rule body.

 

 

Some Examples

 

We can use grammar rules to define a version of append/3 except that the arguments will be the other way around.

 

%Program literal//1 (page 292):

 

literal([])-->[].

literal([X|Xs])-->[X], literal(Xs).

 

We read this, as a grammar, as

 

·         the segment between S0 and S can be parsed as a phrase of type literal ([]) if there is nothing ([]) between S0 and S.

 

 

·         the segment between S0 and S can be parsed as a phrase of type literal([X|Xs]) if there is an S1 such that there is an X between S0 and S1 and the segment between S1 and S can be parsed as a phrase of type literal(Xs).

 

 

Trace of literal//1 (page 292).

 

 

[trace] 16 ?- literal([2,4,5],[2,4,5,6,7],[6,7]).

   Call: (6) literal([2, 4, 5], [2, 4, 5, 6, 7], [6, 7]) ? creep

   Call: (7) 'C'([2, 4, 5, 6, 7], 2, _G640) ? creep

   Exit: (7) 'C'([2, 4, 5, 6, 7], 2, [4, 5, 6, 7]) ? creep

   Call: (7) literal([4, 5], [4, 5, 6, 7], [6, 7]) ? creep

   Call: (8) 'C'([4, 5, 6, 7], 4, _G640) ? creep

   Exit: (8) 'C'([4, 5, 6, 7], 4, [5, 6, 7]) ? creep

   Call: (8) literal([5], [5, 6, 7], [6, 7]) ? creep

   Call: (9) 'C'([5, 6, 7], 5, _G640) ? creep

   Exit: (9) 'C'([5, 6, 7], 5, [6, 7]) ? creep

   Call: (9) literal([], [6, 7], [6, 7]) ? creep

   Exit: (9) literal([], [6, 7], [6, 7]) ? creep

   Exit: (8) literal([5], [5, 6, 7], [6, 7]) ? creep

   Exit: (7) literal([4, 5], [4, 5, 6, 7], [6, 7]) ? creep

   Exit: (6) literal([2, 4, 5], [2, 4, 5, 6, 7], [6, 7]) ? creep

Yes

[debug] 17 ?-

 

%Program date//3 (page293):

 

date(YearCs,MonthCs,DayCs)-->

  literal(DayCs), "/", literal(MonthCs), "/", literal(YearCs).

 

This is logically equivalent to:

 

date(YearCs,MonthCs,DayCs,S0,S):-

   append(DayCs,[/|S2],S0),

   append(MonthCs,[/|S4],S2),

   append(YearCs,S,S4).

 

Trace of date/3 (page 293):

 

[trace] 3 ?- phrase(date("87","11","17"),Result).

   Call: (8) date([56, 55], [49, 49], [49, 55], _G557, []) ? creep

   Call: (9) literal([49, 55], _G557, _G640) ? creep

   Call: (10) 'C'(_G557, 49, _G643) ? creep

   Exit: (10) 'C'([49|_G635], 49, _G635) ? creep

   Call: (10) literal([55], _G635, _G643) ? creep

   Call: (11) 'C'(_G635, 55, _G646) ? creep

   Exit: (11) 'C'([55|_G638], 55, _G638) ? creep

   Call: (11) literal([], _G638, _G646) ? creep

   Exit: (11) literal([], _G638, _G638) ? creep

   Exit: (10) literal([55], [55|_G638], _G638) ? creep

   Exit: (9) literal([49, 55], [49, 55|_G638], _G638) ? creep

   Call: (9) 'C'(_G638, 47, _G649) ? creep

   Exit: (9) 'C'([47|_G641], 47, _G641) ? creep

   Call: (9) literal([49, 49], _G641, _G649) ? creep

   Call: (10) 'C'(_G641, 49, _G652) ? creep

   Exit: (10) 'C'([49|_G644], 49, _G644) ? creep

   Call: (10) literal([49], _G644, _G652) ? creep

   Call: (11) 'C'(_G644, 49, _G655) ? creep

   Exit: (11) 'C'([49|_G647], 49, _G647) ? creep

   Call: (11) literal([], _G647, _G655) ? creep

   Exit: (11) literal([], _G647, _G647) ? creep

   Exit: (10) literal([49], [49|_G647], _G647) ? creep

   Exit: (9) literal([49, 49], [49, 49|_G647], _G647) ? creep

   Call: (9) 'C'(_G647, 47, _G658) ? creep

   Exit: (9) 'C'([47|_G650], 47, _G650) ? creep

   Call: (9) literal([56, 55], _G650, []) ? creep

   Call: (10) 'C'(_G650, 56, _G661) ? creep

   Exit: (10) 'C'([56|_G653], 56, _G653) ? creep

   Call: (10) literal([55], _G653, []) ? creep

   Call: (11) 'C'(_G653, 55, _G664) ? creep

   Exit: (11) 'C'([55|_G656], 55, _G656) ? creep

   Call: (11) literal([], _G656, []) ? creep

   Exit: (11) literal([], [], []) ? creep

   Exit: (10) literal([55], [55], []) ? creep

   Exit: (9) literal([56, 55], [56, 55], []) ? creep

   Exit: (8) date([56, 55], [49, 49], [49, 55], [49, 55, 47, 49, 49, 47, 56, 55]

, []) ? creep

 

Result = [49, 55, 47, 49, 49, 47, 56, 55]

 

 

Flattening a Tree

 

 

labels(Tree,S):-

      labels(Tree,S,[]).

 

labels(empty)-->[].

labels(node(Label,L,R))-->labels(L),[Label],labels(R).

 

 

 

{trace}

| ?- labels(node(a,empty,node(b,empty,node(c,empty,node(d,empty,empty)))),X).

        1      1 Call: labels(node(a,empty,node(b,empty,node(c,empty,node(d,empty,empty)))),_367) ?

        2      2 Call: labels(node(a,empty,node(b,empty,node(c,empty,node(d,empty,empty)))),_367,[]) ?

        3      3 Call: labels(empty,_367,_1304) ?

        4      4 Call: _1304=_367 ?

        4      4 Exit: _367=_367 ?

        3      3 Exit: labels(empty,_367,_367) ?

        5      3 Call: 'C'(_367,a,_1297) ?

        5      3 Exit: 'C'([a|_1297],a,_1297) ?

        6      3 Call: labels(node(b,empty,node(c,empty,node(d,empty,empty))),_1297,[]) ?

        7      4 Call: labels(empty,_1297,_3805) ?

        8      5 Call: _3805=_1297 ?

        8      5 Exit: _1297=_1297 ?

        7      4 Exit: labels(empty,_1297,_1297) ?

        9      4 Call: 'C'(_1297,b,_3798) ?

        9      4 Exit: 'C'([b|_3798],b,_3798) ?

       10      4 Call: labels(node(c,empty,node(d,empty,empty)),_3798,[]) ?

       11      5 Call: labels(empty,_3798,_6300) ?

       12      6 Call: _6300=_3798 ?

       12      6 Exit: _3798=_3798 ?

       11      5 Exit: labels(empty,_3798,_3798) ?

       13      5 Call: 'C'(_3798,c,_6293) ?

       13      5 Exit: 'C'([c|_6293],c,_6293) ?

       14      5 Call: labels(node(d,empty,empty),_6293,[]) ?

       15      6 Call: labels(empty,_6293,_8789) ?

       16      7 Call: _8789=_6293 ?

       16      7 Exit: _6293=_6293 ?

       15      6 Exit: labels(empty,_6293,_6293) ?

       17      6 Call: 'C'(_6293,d,_8782) ?

       17      6 Exit: 'C'([d|_8782],d,_8782) ?

       18      6 Call: labels(empty,_8782,[]) ?

       19      7 Call: []=_8782 ?

       19      7 Exit: []=[] ?

       18      6 Exit: labels(empty,[],[]) ?

       14      5 Exit: labels(node(d,empty,empty),[d],[]) ?

       10      4 Exit: labels(node(c,empty,node(d,empty,empty)),[c,d],[]) ?

        6      3 Exit: labels(node(b,empty,node(c,empty,node(d,empty,empty))),[b,c,d],[]) ?

        2      2 Exit: labels(node(a,empty,node(b,empty,node(c,empty,node(d,empty,empty)))),[a,b,c,d],[]) ?

        1      1 Exit: labels(node(a,empty,node(b,empty,node(c,empty,node(d,empty,empty)))),[a,b,c,d]) ?

 

X = [a,b,c,d] ?

 

yes

 

 

 

Replacing one Sublist by Another

 

Program replace/4 (page 294):

 

 

replace(OldSub,NewSub,OldStr,NewStr):-

  divide3(Before,OldSub,After,OldStr,[]),

  divide3(Before,NewSub,After,NewStr,[]).

 

divide3(Before,Middle,After)-->

  literal(Before),literal(Middle),literal(After).

 

 

 

[trace] 7 ?- replace([a,b],[c,d],[x,a,b,s],[x,c,d,s]).

   Call: (6) replace([a, b], [c, d], [x, a, b, s], [x, c, d, s]) ?creep

   Call: (7) divide3(_G679, [a, b], _G681, [x, a, b, s], []) ? creep

   Call: (8) literal(_G679, [x, a, b, s], _G681) ? creep

   Exit: (8) literal([], [x, a, b, s], [x, a, b, s]) ? creep

   Call: (8) literal([a, b], [x, a, b, s], _G681) ? creep

   Call: (9) 'C'([x, a, b, s], a, _G684) ? creep

   Fail: (9) 'C'([x, a, b, s], a, _G684) ? creep

   Fail: (8) literal([a, b], [x, a, b, s], _G681) ? creep

   Redo: (8) literal(_G679, [x, a, b, s], _G681) ? creep

   Call: (9) 'C'([x, a, b, s], _G675, _G687) ? creep

   Exit: (9) 'C'([x, a, b, s], x, [a, b, s]) ? creep

   Call: (9) literal(_G676, [a, b, s], _G684) ? creep

   Exit: (9) literal([], [a, b, s], [a, b, s]) ? creep

   Exit: (8) literal([x], [x, a, b, s], [a, b, s]) ? creep

   Call: (8) literal([a, b], [a, b, s], _G684) ? creep

   Call: (9) 'C'([a, b, s], a, _G687) ? creep

   Exit: (9) 'C'([a, b, s], a, [b, s]) ? creep

   Call: (9) literal([b], [b, s], _G684) ? creep

   Call: (10) 'C'([b, s], b, _G687) ? creep

   Exit: (10) 'C'([b, s], b, [s]) ? creep

   Call: (10) literal([], [s], _G684) ? creep

   Exit: (10) literal([], [s], [s]) ? creep

   Exit: (9) literal([b], [b, s], [s]) ? creep

   Exit: (8) literal([a, b], [a, b, s], [s]) ? creep

   Call: (8) literal(_G682, [s], []) ? creep

   Call: (9) 'C'([s], _G678, _G690) ? creep

   Exit: (9) 'C'([s], s, []) ? creep

   Call: (9) literal(_G679, [], []) ? creep

   Exit: (9) literal([], [], []) ? creep

   Exit: (8) literal([s], [s], []) ? creep

   Exit: (7) divide3([x], [a, b], [s], [x, a, b, s], []) ? creep

   Call: (7) divide3([x], [c, d], [s], [x, c, d, s], []) ? creep

   Call: (8) literal([x], [x, c, d, s], _G687) ? creep

   Call: (9) 'C'([x, c, d, s], x, _G690) ? creep

   Exit: (9) 'C'([x, c, d, s], x, [c, d, s]) ? creep

   Call: (9) literal([], [c, d, s], _G687) ? creep

   Exit: (9) literal([], [c, d, s], [c, d, s]) ? creep

   Exit: (8) literal([x], [x, c, d, s], [c, d, s]) ? creep

   Call: (8) literal([c, d], [c, d, s], _G687) ? creep

   Call: (9) 'C'([c, d, s], c, _G690) ? creep

   Exit: (9) 'C'([c, d, s], c, [d, s]) ? creep

   Call: (9) literal([d], [d, s], _G687) ? creep

   Call: (10) 'C'([d, s], d, _G690) ? creep

   Exit: (10) 'C'([d, s], d, [s]) ? creep

   Call: (10) literal([], [s], _G687) ? creep

   Exit: (10) literal([], [s], [s]) ? creep

   Exit: (9) literal([d], [d, s], [s]) ? creep

   Exit: (8) literal([c, d], [c, d, s], [s]) ? creep

   Call: (8) literal([s], [s], []) ? creep

   Call: (9) 'C'([s], s, _G690) ? creep

   Exit: (9) 'C'([s], s, []) ? creep

   Call: (9) literal([], [], []) ? creep

   Exit: (9) literal([], [], []) ? creep

   Exit: (8) literal([s], [s], []) ? creep

   Exit: (7) divide3([x], [c, d], [s], [x, c, d, s], []) ? creep

   Exit: (6) replace([a, b], [c, d], [x, a, b, s], [x, c, d, s]) ? creep

 

Yes

 

 

 

 

Finding a Pattern in a String

 

 

 

index(Pattern,Sequence,Index):-

      index(Pattern,0,Index,Sequence,_).

 

index(Pattern,Index,Index)-->

      Pattern.

index(Pattern,Index0,Index)-->

      [_],%skip a character

      {Index1 is Index0+1},

      index(Pattern,Index1,Index).

 

 

 

 

| ?- index("ab","cdabtre",V).

        1      1 Call: index([97,98],[99,100,97,98,116,114,101],_233) ?

        2      2 Call: index([97,98],0,_233,[99,100,97,98,116,114,101],_688) ?

        3      3 Call: phrase(user:[97,98],[99,100,97,98,116,114,101],_688) ?

        4      4 Call: 'C'([99,100,97,98,116,114,101],97,_1459) ?

        4      4 Fail: 'C'([99,100,97,98,116,114,101],97,_1459) ?

        3      3 Fail: phrase(user:[97,98],[99,100,97,98,116,114,101],_688) ?

        5      3 Call: 'C'([99,100,97,98,116,114,101],_1074,_1075) ?

        5      3 Exit: 'C'([99,100,97,98,116,114,101],99,[100,97,98,116,114,101]) ?

        6      3 Call: _1067 is 0+1 ?

        6      3 Exit: 1 is 0+1 ?

        7      3 Call: index([97,98],1,_233,[100,97,98,116,114,101],_688) ?

        8      4 Call: phrase(user:[97,98],[100,97,98,116,114,101],_688) ?

        9      5 Call: 'C'([100,97,98,116,114,101],97,_3311) ?

        9      5 Fail: 'C'([100,97,98,116,114,101],97,_3311) ?

        8      4 Fail: phrase(user:[97,98],[100,97,98,116,114,101],_688) ?

       10      4 Call: 'C'([100,97,98,116,114,101],_2927,_2928) ?

       10      4 Exit: 'C'([100,97,98,116,114,101],100,[97,98,116,114,101]) ?

       11      4 Call: _2920 is 1+1 ?

       11      4 Exit: 2 is 1+1 ?

       12      4 Call: index([97,98],2,_233,[97,98,116,114,101],_688) ?

       13      5 Call: phrase(user:[97,98],[97,98,116,114,101],_688) ?

       14      6 Call: 'C'([97,98,116,114,101],97,_5159) ?

       14      6 Exit: 'C'([97,98,116,114,101],97,[98,116,114,101]) ?

       15      6 Call: 'C'([98,116,114,101],98,_688) ?

       15      6 Exit: 'C'([98,116,114,101],98,[116,114,101]) ?

       13      5 Exit: phrase(user:[97,98],[97,98,116,114,101],[116,114,101]) ?

?      12      4 Exit: index([97,98],2,2,[97,98,116,114,101],[116,114,101]) ?

?       7      3 Exit: index([97,98],1,2,[100,97,98,116,114,101],[116,114,101]) ?

?       2      2 Exit: index([97,98],0,2,[99,100,97,98,116,114,101],[116,114,101]) ?

?       1      1 Exit: index([97,98],[99,100,97,98,116,114,101],2) ?

 

V = 2 ?

 

yes

{trace}

 

 

 

 

Perspective on a Problem

 

 

 

Suppose we have the following grammar:

 

command(delete(File))   --> [rm],file(File).

command(copy(From,To))  --> [cp],file(From),file(To).

command(print(File))    --> [lpr],file(File).

 

 

?-phrase(command(X),[rm,example]).

 

or equivalently,

 

?-phrase(command(X),[rm,example],[]).

 

 

command(Interpretation)-->

      [Token],

      command(Token,Interpretation).

 

command(rm,delete(File)) -->file(File).

command(cp,copy(From,To)) -->file(From),file(To).

command(lpr(print(File))  -->file(File).

 

 

 

 

 

Program list//1 (page 298-299):

 

 

1) First version:

 

 

  sexpr(A) --> [number(A)].

  sexpr(A) --> [atom(A)].

  sexpr(A) --> ['('],list(A).

 

  list([]) --> [')'].

  list(A) --> ['.'], sexpr(A), [')'].

  list([X|Xs]) --> sexpr(X), list(Xs).

 

 

2) Second version:

 

 

  look_ahead(Token),[Token] --> [Token].

 

  list(Xs) --> look_ahead(Token), list(Token,Xs).

 

  list(')',         [])      --> [')'].

  list('.',         A)       --> ['.'], sexpr(A), [')'].

  list(number(_),   [X|Xs])  --> sexpr(X), list(Xs).

  list(atom(_),     [X|Xs])  --> sexpr(X), list(Xs).

  list('(',         [X|Xs])  --> sexpr(X), list(Xs).