Are DCG's just "syntactic sugar"?

Help!
1

I’ve been doing some reading on DCG’s lately. So far though, they just seem to be a layer of “syntactic sugar” on top of plain old Prolog clauses so I haven’t done much with them lately.

Is there anything you can do with a DCG that you simply can’t do with equivalent Prolog rules? Or are only the advantages that of a more compact, terse representation that make the logic easier to decipher than standard Prolog clauses, due to the hiding of certain implementation details.

How often do you really use them over just knocking out the code in straight Prolog?

1 Like
2

No, they are just syntactic sugar but they do make working with certain types of data easier, e.g. list, difference list, bill of materials, fill gap parsing. See: dcg_translate_rule/2 and source code (GitHub)

If you are processing lots of list or difference list then you should consider using DCGs (example). If you are parsing input text that is anything more complicated then returning tokens by splitting at delimiters then I would say you should always use DCGs.

For the last few months I have been parsing many different types of data files, some a few gigabytes in size, some very complex, and over the decades have worked with many types of parsing technology, Regular Expressions,recursive decent parser, ANTLR, parser combinator, and others, but by far the one parsing technology I actually enjoy using and is powerful enough to tackle every problem I have is DCGs. Granted DCGs may not be the fastest parsers around, but for getting a parser up and working and running down the details of those odd transitions during development I have found no better means.

4 Likes
3

DCG’s are exactly syntax sugar – they are in fact implemented in Prolog, as term/goal_expansion rules.

I use them all the time for parsing; not only are they very useful for parsing (I virtual never bother using regular expressions in Prolog, because it’s easier to just write a parser), but they make “chaining” a bunch of operators together much less ugly (example of what I mean here – basically, saves you from having to write transform(A0, A3) :- foo(A0, A1), bar(A1, A2), baz(A2, A3) & can just do transform --> foo, bar, baz instead).

1 Like
4

Thanks Eric. Can you link me to a page that gives a simple example of what fill gap parsing is? I’ve never heard that term before and the search results I get for it are all over the map.

5

Googling for fill gap parser is one of those terms that Google just fails on; hard to believe.

I only saw the name used once and thought I would be able to find the page again but the idea was so simple that I didn’t bother to book mark the page.

So I will explain it here.

Normally with parsing the data is parsed from front to back, nothing is skipped and everything is present; it is determinate. However with DCGs you can define the head of the data and the end of the data and have a gap in the middle because with Prolog the solution does not have to be determinate, e.g.

Sentence --> 
    "Mary", Verb, "Dog".

So there is a gap in the sentence, in this case it is just the single variable Verb. The gap can be filled with verbs such as walks, trains, pets, etc. That is basically it. I don’t know of many parsers that can parse something and fill the gap.

While this example has the gap in the middle, there is nothing AFAIK that limits the gap from being at the start, the end, or even having more than one gap. If the entire output is just one variable, (everything is just one gap) then all of the possible answers are given.

However in Googling with "dcg" fill gap nlp found this.

Unification Grammars

which, while I have not read it before, appears to discus the idea in more detail.

1 Like
6

I read that Amzi tutorial and I want to ask a question to see if I don’t understand something, if you don’t mind.

In the Command Language example, copied below, there is a statement that I believe is a typo?:

main :-
   write('Fly Amzi! Air'), nl,
   repeat,
   do_command.

do_command :-
   write('enter command> '),
   read_string(STRING),
   string_tokens(STRING, TOKENS),
   command(CLIST, TOKENS, []),
   COMMAND =.. CLIST,
   call(COMMAND),
   !,
   COMMAND == exit.
  
command([OP|ARGS]) --> operation(OP), arguments(ARGS).

arguments([ARG|ARGS]) --> argument(ARG), arguments(ARGS).
arguments([]) --> [].

operation(report) --> [list].
operation(book) --> [book].
operation(exit) --> ([exit]; [quit]; [bye]).

argument(passengers) --> [passengers].
argument(flights) --> [flights].

argument(FLIGHT) --> [FLIGHT], {flight(FLIGHT)}.
argument(PASSENGER) --> [PASSENGER].

flight(aa101).
flight(aa102).
flight(aa103).

report(flights) :-
   flight(F),
   write(F), nl,
   fail.
report(_).

report(passengers, FLIGHT) :-
   booked(PASSENGER, FLIGHT),
   write(PASSENGER), nl,
   fail.
report(_, _).

book(PASSENGER, FLIGHT) :-
   assert(booked(PASSENGER, FLIGHT)).

exit.

I’m referring to this statement:

operation(report) --> [list].

I don’t see list declared anywhere so I’m wondering if that line should read:

operation(report) --> [report].

Or is list in this context something that I don’t understand yet?

7

I found this article on unification grammars and Prolog, now that you graciously provided me with the correct term to search with. Perhaps it is of interest to others given that the Norvig article on the subject linked to above uses Lisp:

https://www.aclweb.org/anthology/J95-1005

1 Like
8

That rule is saying “match the atom list next in the input”. For example,

operation(report) --> [list].

?- phrase(operation(Op), [list, foobar], Rest).
Op = report,
Rest = [foobar].
10

I’m still having trouble. I can understand operation(report) --> [report] because like some of the other DCG statements, “report” maps to a callable Prolog predicate “report/1” and thus that call would execute during the execution of the DCG model if the user began a request with the word “report”. I don’t see how the given model supports the interpretation of the statement as it is, that of “operation(report) → [list]” because I don’t see what user input would end up translating to an actionable transaction in the given DCG model using the resulting token of “list”.

So I understand your “reading” of that statement as it stands with “list” as the terminal, but I don’t see how the current model supports it as I expressed above.

11

It seems to be just an unlucky example. It seems to want the user to type list ... and that be handled as report(...). As DCGs are about lists, using list here is misleading. The author probably couldn’t imagine this would be a problem :slight_smile:

2 Likes
12

I’m guessing that’s what string_tokens/2 is doing, converting the characters in the string to a list of atoms.

EDIT: e.g., something like string_tokens(String, Tokens) :- atomic_list_concat(String, " ", Tokens).

14

I am still working on translating the Amzi to SWI but do know enough now to answer this specific part.

[list] in Amzi DCG matches with the input word list and gets returned as operation report, so operation(report) --> [list]. is correct.

When the command report is combined with the argument flights via =.. it becomes the command report(flights) which is the desired predicate and parameter to be called which list the flights

aa101
aa102
aa103
15

Here is my first translation to SWI-Prolog. It works but is not done in the same manner as done with Amzi. In Amzi they parse the input into tokens then process the tokens using DCG. In my version I let the DCG do the parsing and processing. If I get a chance latter I will do the Amzi to SWI the way Amzi intended.

Here is my code


:- set_prolog_flag(double_quotes, codes).
:- set_prolog_flag(back_quotes, string).

:- dynamic
    booked/2.

main :-
    write('Fly Amzi! Air'), nl,
    repeat,
    do_command.

do_command :-
    write('enter command> '),
    read_string(user_input, "\n", "\r", _End, Input),
    string_codes(Input,Codes),
    DCG = command(Command_list),
    phrase(DCG,Codes,_Rest),
    Command =.. Command_list,
    call(Command),
    !,
    Command == exit.

command([Op|Args]) -->
    operation(Op),
    " ",
    arguments(Args).
command([Op]) -->
    operation(Op).

arguments([Arg|Args]) -->
    argument(Arg),
    optional_arguments(Args).

optional_arguments([Arg|Args]) -->
    " ",
    argument(Arg),
    optional_arguments(Args).
optional_arguments([]) --> [].

operation(report) --> "list".
operation(book) --> "book".
operation(exit) --> ("exit"; "quit"; "bye").

argument(passengers) --> "passengers".
argument(flights) --> "flights".

argument(Flight) -->
    argument_item(Flight),
    {
        flight(Flight)
    }.
argument(Passenger) -->
    argument_item(Passenger).

argument_item(Argument) -->
    argument_codes(Codes),
    { atom_codes(Argument,Codes) }.

argument_codes([C|Cs]) -->
    argument_code(C),
    argument_codes(Cs).
argument_codes([]) --> [].

argument_code(C) -->
    \+ " ",
    \+ "\r",
    \+ "\n",
    [C].

flight(aa101).
flight(aa102).
flight(aa103).

report(flights) :-
    flight(Flight),
    write(Flight), nl,
    fail.
report(_).

report(passengers, Flight) :-
    booked(Passenger, Flight),
    write(Passenger), nl,
    fail.
report(_, _).

book(Passenger, Flight) :-
    assert(booked(Passenger, Flight)).

exit.

Example run.

?- main.
Fly Amzi! Air
enter command> list flights
aa101
aa102
aa103
enter command> book leona aa102
enter command> book ivan aa102
enter command> list passengers aa102
leona
ivan
enter command> quit
true .
2 Likes
16

Logic Grammars by Abramson & Dahl has some more advanced flavours of DCGs.

I’m working on reviving a tutorial I wrote a long time ago on DCTGs. (I’ve recovered the text and am in the slow process of fixing OCR mistakes.)

2 Likes
17

A tutorial by Richard O’Keefe:
https://groups.google.com/d/msg/comp.lang.prolog/aLkeCNbjayc/nkO1VV3Sl6UJ

2 Likes
18

Is this paper related to that subject?

typo: you typed “falvours”

19

Here’s another paper I found that mentions “filler gap” techniques:

20

One thing I miss with DCGs is that there’s no way to prove that the grammar is unambiguous. If you use a tool such as yacc, you get the proof for free.

21

DCGs are similar to Attribute Grammars or van Wijngaarden grammars, combining both synthesized and inherited attributes using unification.

1 Like