BNF to DCG generator in prolog

217 views
Skip to first unread message

Luc De Keyser

unread,
Sep 2, 2016, 6:07:27 AM9/2/16
to SWI-Prolog
Hello, The BNF of a Snomed-CT (international controlled medical vocabulary) based query language is still in flux. It is quite tedious to keep the DCG in sync with the BNF versions. Is it naive to think that there is already a generator (preferably in prolog) to convert BNF specs to DCG.rules? 
If already discussed I did not find it on this or any other forum.
Thank you in advance. Luc

Wouter Beek

unread,
Sep 2, 2016, 6:36:16 AM9/2/16
to Luc De Keyser, SWI-Prolog
Hi Luc,

I've asked exactly the same question many moons ago...  Someone responded that it was a super trivial exercise you would give to students (ca. 10 lines of code!).  Unfortunately, the 10 lines of code were not included back then.

Most operators can be implemented by m*n, where m is the min number of consecutive rule applications and n is the max number of consecutive rule applications.  n may be inf.  You also want the number of times the rule is applied back, ideally.  It should non-deterministically generate all strings.  It has to work for parsing and generating.  It has to be able to take arguments that are given or returned in a list.

The core API would look like this:

    'm*n'//3, % ?Low, ?High, -Count, :Dcg_0
    'm*n'//4, % ?Low, ?High, -Count, :Dcg_1, -Args1
    'm*n'//5, % ?Low, ?High, -Count, :Dcg_2, -Args1, -Args2

You can then define m*, *n, ?, +, #, *.

Implementing this in a naive way, my DCGs still look crappy when compared to the ABNF definition:

    [ABNF]   field-body = *(continuation 1*character)

    [DCG]    field_body(S) --> parsing, continuation, +(character, Cs), {string_codes(S, Cs)}.

Here I am at the end of my PhD, still scratching my head as to how to do this properly :-)

---
Cheers,
Wouter.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

Luc De Keyser

unread,
Sep 3, 2016, 4:56:05 AM9/3/16
to SWI-Prolog
I am just a "kitchen and home garden" (recognize the Dutch idiom?) prolog user. The BNF's of BNF I found also do not extend beyond the vanilla "10 lines". The API you propose was an aha-erlebnis, although it took a while to sink in. Thank you, Wouter. Maybe we'll meet next time at the Laundromat ;-) 

Wouter Beek

unread,
Sep 3, 2016, 5:03:25 AM9/3/16
to Luc De Keyser, SWI-Prolog
Hi Luc,

I forgot to include two pointers to packages that may implement some of the BNF operators, but with different syntax:

  - dcg_util by Michael: http://eu.swi-prolog.org/pack/list?p=dcg_util
Cheers!,
Wouter.

On Sat, Sep 3, 2016 at 10:56 AM, Luc De Keyser <lucjde...@telenet.be> wrote:
I am just a "kitchen and home garden" (recognize the Dutch idiom?) prolog user. The BNF's of BNF I found also do not extend beyond the vanilla "10 lines". The API you propose was an aha-erlebnis, although it took a while to sink in. Thank you, Wouter. Maybe we'll meet next time at the Laundromat ;-) 

--

Carlo Capelli

unread,
Sep 10, 2016, 12:37:43 PM9/10/16
to Luc De Keyser, SWI-Prolog
Hi Luc

If you are still interested, I could try to help you with your (E)BNF to DCG,
maybe applying pack(dcg_util) into your working current source ( if you can share it :).

I haven't seen the (E)BNF of SNOMED CT (where to look for ?), so I could be plain wrong...

Mind storming: SNOMED CT seem a great place to Attempto something funny. We have an ACE engine available !

Thanks, Carlo


2016-09-03 10:56 GMT+02:00 Luc De Keyser <lucjde...@telenet.be>:
I am just a "kitchen and home garden" (recognize the Dutch idiom?) prolog user. The BNF's of BNF I found also do not extend beyond the vanilla "10 lines". The API you propose was an aha-erlebnis, although it took a while to sink in. Thank you, Wouter. Maybe we'll meet next time at the Laundromat ;-) 

--

Carlo Capelli

unread,
Sep 10, 2016, 12:44:48 PM9/10/16
to Luc De Keyser, SWI-Prolog
2016-09-10 18:37 GMT+02:00 Carlo Capelli <cc.car...@gmail.com>:
Hi Luc

If you are still interested, I could try to help you with your (E)BNF to DCG,
maybe applying pack(dcg_util) into your working current source ( if you can share it :).

I haven't seen the (E)BNF of SNOMED CT (where to look for ?),

never mind, I've found this...

Carlo Capelli

unread,
Sep 10, 2016, 12:57:31 PM9/10/16
to Luc De Keyser, SWI-Prolog
2016-09-10 18:44 GMT+02:00 Carlo Capelli <cc.car...@gmail.com>:


2016-09-10 18:37 GMT+02:00 Carlo Capelli <cc.car...@gmail.com>:
Hi Luc

If you are still interested, I could try to help you with your (E)BNF to DCG,
maybe applying pack(dcg_util) into your working current source ( if you can share it :).

I haven't seen the (E)BNF of SNOMED CT (where to look for ?),

never mind, I've found this...

and this...

Luc De Keyser

unread,
Sep 10, 2016, 3:33:18 PM9/10/16
to SWI-Prolog
Thank you Carlo,
You found an early version of the Snomed CT constraint language specification. The need for a BNF to DCG arose from the updates to be expected. My goal is to set up an environment to extract clinically meaningful views/extracts from this large but rather shallow controlled vocabulary (go to browser for a taste of it) . If there are elegant tools readily available the better. In the meantime I updated the DCG rules to the latest july 2016 update to the ABNF of the constraint language. So far, so good for the constructs that I use.
The next hurdle is finding a way not to use Protégé as Snomed CT is the poster child of description logic EL++.. .
Reply all
Reply to author
Forward
0 new messages