Why eos// violates the _context free_ property of DCGs?

Help!
1

In swipl\library\dcg\bascis.pl .

%%	eos//
%
%	Matches  end-of-input.  The  implementation    behaves   as  the
%	following portable implementation:
%
%	  ==
%	  eos --> call(eos_).
%	  eos_([], []).
%	  ==
%
%	@tbd	This is a difficult concept and violates the _context free_
%		property of DCGs.  Explain the exact problems.

eos([], []).

Why does eos// violate the context free property of DCGs? Could someone tell me why, or what book should I read?

1 Like
2

Neither do I.
As I leaned DCG clause

a--> b, c.

is just a shorthand for

a(X, Y):- b(X, Z), c(Z, Y).

So, your eos/2 seems to check that nothing remains in the rest of the current line. However it seems irrelevant to that this breaks context free property.

1 Like
3

In any context-free grammar, and in at least some forms of context-sensitive grammar, each nonterminal symbol generates a set of strings. In a context-sensitive grammar, the set of strings a nonterminal generates can depend upon its context: what appears to its left, and what appears to its right. In a context-free grammar, the meaning of a nonterminal (i.e. the set of strings it generates) is independent of the context. That is what the comment in the code you quote refers to as the “context free property of DCGs”.

If it’s not evident to you how the nonterminal eos//0 violates the property, ask yourself:

  • What strings does eos//0 recognize?
  • Does it recognize the same set of strings regardless of where the symbol eos occurs in the grammar and regardless of where it is applied in the input string?

The rule for eos//0 recognizes the empty string, as is clear from the fact that its difference-list arguments are the same: any nonterminal with a rule which expands to the form N(L,L) recognizes the empty string, because the difference list L, L represents the empty list.

If you write a grammar with a rule like

empty_string --> [].

you can see, using listing/1, that through term expansion it is translated into the predicate

empty_string(A, A).

We can use empty_string together with other nonterminals we have defined, or literals, in a call to phrase/3:

?- set_prolog_flag(double_quotes, chars).
true.

?- phrase([a, a], "aaa", Remainder).
Remainder = [a].

?- phrase((empty_string, [a, a]), "aaa", Remainder).
Remainder = [a].

?- phrase((empty_string, [a, a], empty_string), "aaa", Remainder).
Remainder = [a].

?- phrase((empty_string, [a], empty_string, [a], empty_string), "aaa", Remainder).
Remainder = [a].

If we specify a shorter list as the input, we get the expected result that we have an empty list as Remainder:

?- phrase([a, a], "aa", Remainder).
Remainder = [].

?- phrase((empty_string, [a, a]), "aa", Remainder).
Remainder = [].

?- phrase((empty_string, [a], empty_string, [a], empty_string), "aa", Remainder).
Remainder = [].

As you can see, the nonterminal empty_string//0 recognizes the empty string, and consumes nothing in the input sequence. It does so whether placed at the beginning of the phrase to be recognized, or at the end, or in the middle.

Now try replacing the references to empty_string with references to dcg_basics:eos and see what happens. It matches the empty sequence or empty string, just like empty_string – but only in some contexts, specifically only at the end of the input.

That is what the comment in the library is talking about.

If you would like to know more, the best introduction to formal grammars that I know is the book Parsing Techniques, by Dick Grune and Ceriel Jacobs. The first edition is out of print but may be found in many libraries; the second edition is a bit daunting (it’s a very thick, heavy book), but to understand the basics, it is sufficient to read the first chapters. There are of course other introductory texts; find one you have access to and like, and read it.

5 Likes