Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14911

Difference between W-Grammars and DCG Transform (Was: From natural language processing to Prolog [Beijing, April 8, 2011])

Show all headers | View raw

Hi,

I didn't unlock the Metamorphoses Paper yet,
its still behind a paywall for me. But
a Paper about W-Grammars is available.

The Paper about W-Grammars is from
Alain Colmerauers website again.
While a W-Grammar rule of the form:

X |-> Y

Leads mathematically to a rewrite rule:

V,X,W ==> V,Y,W

A DCG Transform of the form:

P,Y --> X,P

Leads mathematically to a rewrite rule:

V,*,X,W ==> V,Y,*,W

Where * is a kind of replacement cursor.
So in DCG Transform there is no comming back
to match and replace a previous position again.

Thats why in my NetFish Transducer, I need
"cascading", basically repeatedly applying
the DCG Transforms by iteration,

until a kind of fixpoint is reached.

Bye

See also:

W-Grammar, Chastellier & Colmerauer (1968)
http://alain.colmerauer.free.fr/alcol/ArchivesPublications/Wgrammar/Wgrammar.pdf

Mild Shock schrieb:
> Hi,
> 
> I only rediscovered a little bit that DCG has
> also semi-context, and that when using non-terminals
> in semi-contexts, these act like what
> 
> was Meta-Grammars in W-Grammar, 1967–1968.
> W-Grammars with Meta-Grammars were basically
> Semi-Thue systems, but one needs to pay attention,
> 
> the todays DCG cannot directly implement them:
> 
>  From natural language processing to Prolog
> http://alain.colmerauer.free.fr/alcol/ArchivesTransparents/ChinaApril2011/NatLanguageProlog.pdf 
> 
> 
> What later came was Q-System, 1968–1970, French,
> 1971–1973, Prolog, 1973–1976 and Prolog II,
> 1977–1982. An early shift to CLP(X) was dif/2
> 
> which already appeared in Prolog II. That todays
> Prolog commmunity is clueless about the grammar
> and transform aspect is really sad.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Only morons waste time with regex when they have Prolog!
>> Its amazing, since Alain Colmerauer was already
>> juggling with a kind of transducers:
>>
>> "We present some very general grammars in which
>> each re-writing rule is of the type: replace such
>> and such sequence of trees by such and such another
>> sequence of trees."
>> https://www.researchgate.net/publication/225124810
>>
>> Still the Prolog community is to stupid to
>> transduce CR, CR LF and LF into LF. Thats quite a
>> feat. BTW, this should do using DCG semi-contexts:
>>
>> replace, [0'\n] --> [0'\r, 0'\n], replace.
>> replace, [0'\n] --> [0'\r], replace.
>> replace, [0'\n] --> [0'\n], replace.
>> replace, [X] --> [X], replace.
>> replace --> [].
>>
>> Works on my side:
>>
>> ?- replace("foo\rbar\r\nbaz", _L), atom_codes(A, _L).
>> A = 'foo\nbar\nbaz'
>>
>> Now optimize it to produce 0'\n as early as
>> possible and use a state machine, so that you
>> can implement it low level in your streams.
>>
>> Have Fun!
>>
>> Bye

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

ISO Prolog and yet another stinking pile of crap Julio Di Egidio <julio@diegidio.name> - 2025-10-10 23:33 +0200
  What about the <NEWLINE> ? (Was: ISO Prolog and yet another stinking pile of crap) Mild Shock <janburse@fastmail.fm> - 2025-10-11 10:35 +0200
    Re: What about the <NEWLINE> ? (Was: ISO Prolog and yet another stinking pile of crap) Julio Di Egidio <julio@diegidio.name> - 2025-10-11 13:08 +0200
      Metamorphosis Grammars by Alain Colmerauer (Was: What about the <NEWLINE> ?) Mild Shock <janburse@fastmail.fm> - 2025-10-12 00:35 +0200
        Compact DCG Transducer by Dogelog Player (Was: Metamorphosis Grammars by Alain Colmerauer) Mild Shock <janburse@fastmail.fm> - 2025-10-12 00:55 +0200
          Did Picat, Minizinc, etc.. dumb down Prolog? (Was: Compact DCG Transducer by Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-10-12 01:06 +0200
        Re: Metamorphosis Grammars by Alain Colmerauer (Was: What about the <NEWLINE> ?) Julio Di Egidio <julio@diegidio.name> - 2025-10-12 01:28 +0200
          Solve the Bootstrapping Problem: Self Hosting Systems (Was: Metamorphosis Grammars by Alain Colmerauer) Mild Shock <janburse@fastmail.fm> - 2025-10-12 04:28 +0200
        From natural language processing to Prolog [Beijing, April 8, 2011] (Re: Metamorphosis Grammars by Alain Colmerauer (Was: What about the <NEWLINE> ?) Mild Shock <janburse@fastmail.fm> - 2025-10-13 09:11 +0200
        From natural language processing to Prolog [Beijing, April 8, 2011] (Re: Metamorphosis Grammars by Alain Colmerauer (Was: What about the <NEWLINE> ?) Mild Shock <janburse@fastmail.fm> - 2025-10-13 09:11 +0200
          Difference between W-Grammars and DCG Transform (Was: From natural language processing to Prolog [Beijing, April 8, 2011]) Mild Shock <janburse@fastmail.fm> - 2025-10-13 09:23 +0200
            The Blunder: “constraint programming” companies in France 1984–1996 (Was: Difference between W-Grammars and DCG Transform) Mild Shock <janburse@fastmail.fm> - 2025-10-13 09:34 +0200
  Gradual Refinement: AI Memo 39 (Was: ISO Prolog and yet another stinking pile of crap) Mild Shock <janburse@fastmail.fm> - 2025-10-12 05:00 +0200

csiph-web