Re: Semantics, opt in Semantics

On 2015-01-15, Seima Rao <seimarao@gmail.com> wrote:
> Hi,
>
> The Backus Naur Form is a great mathematical model. It explains syntax
> quite succintly.
>
> In that form, the opt qualifier which stands for optional or
> epsilon is utilized extensively for optional syntax.
>
> Is there something similar for semantics i.e. is there something optional
> in semantics.
>
> 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.


A grammar has semantics: it specifies not only a set of strings, but
also denotes a procedure called a parser. The proof of this is that
parsers can be generated from grammars, and so grammars are used
directly as programming languages for writing parsers.


If we wish to denote arbitrary semantics (computations other than
parsers) we usually use some notation whose elements can be combined
to represent any recursive-primitive computation: in other words, a
Turing-complete computational language.


Roughly speaking, a Turing-complete language is to semantics, what a
grammar is to a set of strings.


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.


Relevant to compiler (see newsgroup name), there exist annotated "attribute
grammars" for expressing syntax directed translation.


http://en.wikipedia.org/wiki/Attribute_grammar


Attribute grammars are not intended to capture arbitrary semantics, but the
semantics of translation: converting the semantics of the input language
into another form.


> [Man, there's a can of worms. There's no semantic formalism that matches real
> semantics as well as BNF matches real syntax. -John]


Of course there is; the Universal Turing Machine, and all else that follows.


That is, if we are talking about semantics that can be computed.
[When I had in mind when I said "matching as well" is that languages
with grammars that humans can use tend to be similar ones that are
easy to describe in BNF. -John]

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