Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newspeer1.nac.net!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: glen herrmannsfeldt Newsgroups: comp.compilers Subject: Re: Semantics, opt in Semantics Date: Sat, 17 Jan 2015 18:42:26 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 64 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-01-025@comp.compilers> References: <15-01-013@comp.compilers> <15-01-021@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: miucha.iecc.com 1421524235 77084 2001:470:1f07:1126:0:676f:7373:6970 (17 Jan 2015 19:50:35 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 17 Jan 2015 19:50:35 +0000 (UTC) Keywords: semantics Posted-Date: 17 Jan 2015 14:50:35 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1482 Kaz Kylheku wrote: > On 2015-01-15, Seima Rao wrote: >> The Backus Naur Form is a great mathematical model. >> It explains syntax quite succintly. (snip) >> Also, what is the equivalent in semantics of BNF ? > A grammar is some combination of symbols which denote phrase structure > rules which in turn generate strings of symbols, or alternative, > determine which strings of symbols are well-formed. (snip) > This is why, for instance, under the most general-purpose > parser-generating tools, the phrase structures of a grammar are > associated with: arbitrary blocks of programming code that are invoked > in a syntax-directed way when their corresponding rule is reduced. Seems that the grammar describes the construction of statements, but not the way to combine them to a useful program. Similarly, English grammar describes sentences, but not how to put them together to make useful paragraphs and such. > Attribute grammars are not intended to capture arbitrary semantics, but the > semantics of translation: converting the semantics of the input language > into another form. BNF describes a simplified state machine that matches or doesn't match the syntax of a program. A compiler is a more complicated state machine that, among others, accepts a syntactically and semantically correct program. Seems to me that in theory, but only in theory, one could describe the full description of allowable programs, but it would not be understandable by humans. Even the BNF for a statement is often oversimplified. A declaration statement might allow one to declare one or more variables, but require each to be distinct. It is already too much work in BNF to write a description not allowing duplication of variable names. To consider an even simpler example, the PL/I DO statement allows for statements of the form: DO I=1 TO 10 BY 1; and DO I=1 BY 1 TO 10; In BNF, this is done allowing for either a TO or BY, and optionally followed by BY or TO, respectively. That isn't so hard to do. If a language allowed three different such subclauses, in any combination but without duplicates, the description is approximately 15 times as big as for one. The size increases worse than exponentially! Most BNF descriptions will allow for any number of subclauses, and note somewhere else not to duplicate them. (The PL/I OPEN statement, for example.) BNF is a nice compromise, giving reasonably useful, but not too large, descriptions of a language. -- glen