Re: Semantics, opt in Semantics

Kaz Kylheku <kaz@kylheku.com> wrote:
> On 2015-01-15, Seima Rao <seimarao@gmail.com> 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

Return to the comp.compilers page.
Search the comp.compilers archives again.