Definite Clause Grammars (DCGs)

Prolog has a built-in grammar mechanism, Definite Clause Grammars (DCGs). A DCG describes a sequence, and allows us to conveniently reason about sequences manifested as lists. DCGs are a very versatile mechanism, and one of Prolog's greatest attractions. We use them for parsing, describing output, passing arguments implicitly, reading from files, and several other applications. More information: www.metalevel.at/prolog/dcg

[@ngruhn]

Excellent video as usual. Especially the later stuff on semicontext notation was completely new to me. Very interesting.

[@wowzers1237____]

Yesss finally! Thanks Markus!

[@papagvasexy]

Recently got really interested in DCG’s, luckily, your video just came out. Great work as usual

[@thulsadum]

Really well explanation on DCGs. Thank you.

[@mikeamy4649]

Highly enlightening. I'm grateful because I was having trouble writing a VM bytecode analyser, but now I realise that I can write it more easily and powerfully using DCGs. Luckily I didn't get too far into it.
Oops, I mean 'describe' the bytecode.

[@SylvainSoliman]

I think that thanks to this video I actually finally understood what I _don't_ like about DCGs (sorry). As pointed out, DCGs are very imperative!
They are sensitive to they execution strategy, they allow for the direct translation of imperative algorithms… You can think of this as positive features, but… I guess that's why they don't feel natural to me in Prolog ^^

[@audunstolpe7408]

Very interesting. Hard to find elsewhere. New book badly needed.

[@froreyfire]

That's a nice creek in 46:30, but I wonder if it was intended? 🙂

[@GianMarcoLeone]

wow

[@eignnx_1738]

What would it mean to use arbitrary length lists in the semicontext position? Could that be analogous to tracking "multiple worlds" of state?

[@k9-guardian785]

I was wondering about why seq//1 leaves behind a choice point. In SWI-prolog, the equivalent is string//1.
string([]) -->
[].
string([H|T]) -->
[H],
string(T).
Logically there's no reason for these queries to leave choice points.
4 ?- phrase(string(S), "").
S = [] ;
false.
5 ?- phrase(string(S), "a").
S = [a] ;
false.
6 ?- phrase(string(S), "ab").
S = [a, b] ;
false.
So I was wondering if there's a way to redefine seq//1 such that it's deterministic.

[@bertrandduguesclin826]

I could not understand the call//1 predicate at 1:00:33. In fact what bugs me down the most is the definition of the output chars(Cs0,Cs). I did not know this could be defined in terms of list difference. I could not find any documentation about it.

[@theloniusbuddha2776]

What is the editor he is using to visualize the trees?

[@froreyfire]

36:53 Say you wanted the grammar to parse the + unambiguously as left-associative. What would you change?

[@k9-guardian785]

expr(1) --> "1".
expr(E+1) --> expr(E), "+", "1".
Would be left associative I believe. Even though it's left recursive it doesn't require tabling as long as you wrap your phrase call in once/1.

[@JoeTaber]

My `tags//1` definition for the viewer exercise at 25:00
tags([]) --> [].
tags([element(Tag,_,Children)|Siblings]) --> [Tag],tags(Children),tags(Siblings).

[@bertrandduguesclin826]

tags([]) --> [].
tags([element(Tag,_,Children)|Siblings]) --> [Tag],tags(Children),tags(Siblings),{!}.
tags([String|Siblings]) --> [String],tags(Siblings).

[@davidemontani9252]

why if i write phrase(xy, "XXX") it says list expected? if i put a variable he write me a list of the character accepted in ascii code

[@leswine1582]

im using swipl and am trying some of the string examples you showed but it aint working. Maybe I didnt import a library or something

[@leswine1582]

it works in scryer-prolog though. Maybe its dcg/basics for swipl?

[@ThePowerOfProlog]

@@leswine1582 Yes, I highly recommend using Scryer Prolog or one of the other modern Prolog systems which all handle the shown cases excellently!

[@valcron-1000]

12:50 In Haskell: f n = replicateM n ['X', 'Y']