Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!samsung!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.misc Subject: Re: Complexity of syntax Message-ID: Date: 10 Jan 91 20:04:29 GMT References: <11883:Jan502:21:0191@kramden.acf.nyu.edu> <1991Jan5.044445.15116@agate.berkeley.edu> <13857:Jan506:12:5891@kramden.acf.nyu.edu> <1991Jan5.081755.23488@agate.berkeley.edu> <1991Jan8.173302.14624@maths.nott.ac.uk> Sender: cho@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 33 Nntp-Posting-Host: odin In-reply-to: anw@maths.nott.ac.uk's message of 8 Jan 91 17:33:02 GMT On 8 Jan 91 17:33:02 GMT, anw@maths.nott.ac.uk (Dr A. N. Walker) said: [ ... on whether invalid declarations can be forbidden on purely syntactive grounds, which it cannot be done with a context free grammar ... ] anw> As others have pointed out, this is easy with a two-level grammar. anw> For details, see the Revised Report, or [better!] "Grammars of anw> Programming Languages" by Cleaveland and Uzgalis (Elsevier, 1977). Ah, here you take out the book which is the nuclear weapon of context sensitive grammar debates. I agree with what you say, as far as it goes, but you omit to remind us that that book clearly demonstrates what the *semantics* of a language can easily be formalized with a two level grammar, which throws a spanner in the well oiled structure of this type of debate (Bernstein writes provocative, edgy but sensible things, everybody else stop chewing their sandwich and jumps on him with glee :->). Context sensitive grammar generators (they do exist!) can do pretty impressive things -- just consider that people have been using simple context free grammars to do, in favourable conditions, code generation! Two level or attribute grammars are strange beasts indeed, at least from the usual CS perspective under which grammars stop at context free. End of debate while a lot of people stop jumping on Bernstein and rush to the library (not the bookshop -- out of print for a long time) to get a copy of the book over which to finish munching their sandwich? :-) -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk