🚀 go-pugleaf

In article <92202.164904U35395@uicvm.uic.edu>, C. M. Sperberg-McQueen <U35395@uicvm.uic.edu> writes:

>>   The argument is simple. Any system that restricts itself to context-free
>> grammars is formally incapable of describing an infinite class of data,
>> namely recursive languages.
>
>Seems to be a typo here.  Surely you don't mean that CFGs are incapable
>of recursion, since their ability to allow recursion is notoriously what
>distinguishes context-free languages from regular languages.  The example
>you give in your second posting is indeed not context-free, but it is
>also not recursive, that I see.

  Let me say "recursively enumerable", then, as I should have in the
first place.  In other words, a language that requires a Turing machine
as an acceptor.  Please excuse my sloppy use of terminology.

>1 SGML's competitors for practical use are markup languages like troff
>and its cousins and derivatives, Scribe, Script, GML, TeX and LaTeX, and
>possibly ODA.  

  The discussion here, however, was predicated on the idea that SGML "is 
not just for text anymore".  It seemed natural to me, then, to conclude
that SGML's competitors now include not only other markup languages, but 
also any existing data models for these other domains.

>3 The fact that SGML is limited formally to context-free grammars does
>not mean it cannot be useful for defining non-context-free languages.

  This is exactly what it does mean, I think.  How can you define a
recursively enumerable language with a context-free grammar?  You
can't.  You can only define the context-free parts of such a language. 

>The BNF used to define Algol and C, and the railroad track diagrams used
>to define Pascal (and presumably Modula 2) cannot handle the
>context-sensitive construct DR cited (viz. X**n Y**n) any more than SGML
>can, but the grammars are still useful for those working with those
>languages.

  This example doesn't work for several reasons.  First, the BNF of C 
doesn't define C - that requires a lot of semantic information as well 
(I haven't thought about it enough, but it may be that it even requires 
Turing equivalence).  Second, the construct "X**n Y**n" is in fact 
context-free.  Third, the construct "ww", which is the one I actually 
mentioned, has no special semantics in C, or any other programming 
language that I am aware of - it just means "do w and do w again".  So 
recognizing it is not important.  Finally, are you confusing two 
languages? - namely, the language consisting of the set of strings that 
represent valid C programs (which is context free) and the language 
accepted by any given C program (which, in general, is recursively 
enumerable)?

>SGML's most serious problems as a practical tool seem to me
>not its lack of non-CF power but the number of bells and whistles it has.
 	.
 	.
>Darrell, what on earth are you up to now?

  Trying to establish formal arguments in favor of eliminating bells
and whistles.  Question: could markup itself be one of them?

-Darrell.