home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / text / sgml / 904 < prev    next >
Encoding:
Text File  |  1992-07-21  |  3.3 KB  |  72 lines
  1. Newsgroups: comp.text.sgml
  2. Path: sparky!uunet!utcsri!torn!watserv1!watdragon.waterloo.edu!drraymon
  3. From: drraymon@watdragon.waterloo.edu (Darrell Raymond)
  4. Subject: Re: It's Not Just for Text Anymore
  5. Message-ID: <BrrEw0.MsA@watdragon.waterloo.edu>
  6. Organization: University of Waterloo
  7. References: <710783547snx@sgmlinc.com> <92202.164904U35395@uicvm.uic.edu>
  8. Date: Tue, 21 Jul 1992 22:09:35 GMT
  9. Lines: 61
  10.  
  11. In article <92202.164904U35395@uicvm.uic.edu>, C. M. Sperberg-McQueen <U35395@uicvm.uic.edu> writes:
  12.  
  13. >>   The argument is simple. Any system that restricts itself to context-free
  14. >> grammars is formally incapable of describing an infinite class of data,
  15. >> namely recursive languages.
  16. >
  17. >Seems to be a typo here.  Surely you don't mean that CFGs are incapable
  18. >of recursion, since their ability to allow recursion is notoriously what
  19. >distinguishes context-free languages from regular languages.  The example
  20. >you give in your second posting is indeed not context-free, but it is
  21. >also not recursive, that I see.
  22.  
  23.   Let me say "recursively enumerable", then, as I should have in the
  24. first place.  In other words, a language that requires a Turing machine
  25. as an acceptor.  Please excuse my sloppy use of terminology.
  26.  
  27. >1 SGML's competitors for practical use are markup languages like troff
  28. >and its cousins and derivatives, Scribe, Script, GML, TeX and LaTeX, and
  29. >possibly ODA.  
  30.  
  31.   The discussion here, however, was predicated on the idea that SGML "is 
  32. not just for text anymore".  It seemed natural to me, then, to conclude
  33. that SGML's competitors now include not only other markup languages, but 
  34. also any existing data models for these other domains.
  35.  
  36. >3 The fact that SGML is limited formally to context-free grammars does
  37. >not mean it cannot be useful for defining non-context-free languages.
  38.  
  39.   This is exactly what it does mean, I think.  How can you define a
  40. recursively enumerable language with a context-free grammar?  You
  41. can't.  You can only define the context-free parts of such a language. 
  42.  
  43. >The BNF used to define Algol and C, and the railroad track diagrams used
  44. >to define Pascal (and presumably Modula 2) cannot handle the
  45. >context-sensitive construct DR cited (viz. X**n Y**n) any more than SGML
  46. >can, but the grammars are still useful for those working with those
  47. >languages.
  48.  
  49.   This example doesn't work for several reasons.  First, the BNF of C 
  50. doesn't define C - that requires a lot of semantic information as well 
  51. (I haven't thought about it enough, but it may be that it even requires 
  52. Turing equivalence).  Second, the construct "X**n Y**n" is in fact 
  53. context-free.  Third, the construct "ww", which is the one I actually 
  54. mentioned, has no special semantics in C, or any other programming 
  55. language that I am aware of - it just means "do w and do w again".  So 
  56. recognizing it is not important.  Finally, are you confusing two 
  57. languages? - namely, the language consisting of the set of strings that 
  58. represent valid C programs (which is context free) and the language 
  59. accepted by any given C program (which, in general, is recursively 
  60. enumerable)?
  61.  
  62. >SGML's most serious problems as a practical tool seem to me
  63. >not its lack of non-CF power but the number of bells and whistles it has.
  64.      .
  65.      .
  66. >Darrell, what on earth are you up to now?
  67.  
  68.   Trying to establish formal arguments in favor of eliminating bells
  69. and whistles.  Question: could markup itself be one of them?
  70.  
  71. -Darrell. 
  72.