Re: Semantics, opt in Semantics

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From	Kaz Kylheku <kaz@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: Semantics, opt in Semantics
Date	Fri, 16 Jan 2015 16:28:31 +0000 (UTC)
Organization	Aioe.org NNTP Server
Lines	55
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<15-01-021@comp.compilers> (permalink)
References	<15-01-013@comp.compilers>
NNTP-Posting-Host	news.iecc.com
X-Trace	miucha.iecc.com 1421478730 96689 2001:470:1f07:1126:0:676f:7373:6970 (17 Jan 2015 07:12:10 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Sat, 17 Jan 2015 07:12:10 +0000 (UTC)
Keywords	semantics
Posted-Date	17 Jan 2015 02:12:10 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:1478

Show key headers only | View raw

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]

Thread

Semantics, opt in Semantics Seima Rao <seimarao@gmail.com> - 2015-01-15 17:42 +0530
  Re: Semantics, opt in Semantics rpw3@rpw3.org (Rob Warnock) - 2015-01-16 16:11 +0000
  Re: Semantics, opt in Semantics Kaz Kylheku <kaz@kylheku.com> - 2015-01-16 16:28 +0000
    Re: Semantics, opt in Semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-01-17 18:42 +0000
  Re: Semantics, opt in Semantics Hans Aberg <haberg-news@telia.com> - 2015-01-16 18:20 +0100
  Re: Semantics, opt in Semantics wclodius@earthlink.net (William Clodius) - 2015-01-16 12:22 -0700
    Re: Semantics, opt in Semantics Stefan Monnier <monnier@iro.umontreal.ca> - 2015-01-18 10:03 -0500

csiph-web