Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1470 > unrolled thread

Semantics, opt in Semantics

Back to article view | Back to comp.compilers

Contents

  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

#1470 — Semantics, opt in Semantics

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 ?

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

[toc] | [next] | [standalone]

#1477

Seima Rao  <seimarao@gmail.com> wrote:
+---------------
| Also, what is the equivalent in semantics of BNF ?
|
| [Man, there's a can of worms. There's no semantic formalism that
|  matches real semantics as well as BNF matches real syntax. -John]
+---------------

Perhaps not quite as well, but Bell & Newell-style RTL [Register
Transfer Language], such as used in their book[1] to describe/define
various processors' ISPs, comes close.

One might also consider Verilog & VHDL to be "semantic formalisms" as
well.

-Rob

[1] Bell and Newell, "Computer Structures: Readings
    and Examples", 1971 (McGraw-Hill).

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403
[How does RTL express semantics like names have to be declared
before they're used? -John]

[toc] | [prev] | [next] | [standalone]

#1478

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]

[toc] | [prev] | [next] | [standalone]

#1482

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

[toc] | [prev] | [next] | [standalone]

#1479

On 2015/01/15 13:12, Seima Rao wrote:
>      Is there something similar for semantics i.e. is there something optional
>      in semantics.
...
> [Man, there's a can of worms. There's no semantic formalism that matches real
> semantics as well as BNF matches real syntax. -John]

There is denotational semantics, though. Dave Schmidt's 1986 book is now
available for free:

https://en.wikipedia.org/wiki/Denotational_semantics
http://people.cis.ksu.edu/~schmidt/text/densem.html

[toc] | [prev] | [next] | [standalone]

#1480

Seima Rao <seimarao@gmail.com> wrote:

>     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 ?
>
> Sincerely,
> Seima Rao.
> [Man, there's a can of worms. There's no semantic formalism that matches real
> semantics as well as BNF matches real syntax. -John]

This seems to combine three separate questions:

1. What notations are available for semantic descriptions?

2. What semantic concepts are considered optional?

3. How are those optional concepts expressed in the semantic notations?

As to the first question the complexity of semanticsx has resulted in a
large variety of notations: the van Wijngaarden two level grammar, the
Vienna Definition Language/Vienna Development Method, Denotational
semantics, attribute grammars,etc.

As to the second some obvious optional semantics include parallelism,
and side effects including exceptions and some forms of I/O.

I believe the latter reports on Algol68 included parallelism defined in
the van Wijngaarden two level grammar.

[toc] | [prev] | [next] | [standalone]

#1486

> As to the first question the complexity of semanticsx has resulted in a
> large variety of notations: the van Wijngaarden two level grammar, the
> Vienna Definition Language/Vienna Development Method, Denotational
> semantics, attribute grammars,etc.

The most commonly used formalism nowadays in the programming languages
community is operational semantics (either "small step" or "big
step").

While denotational semantics can be thought of as "compiling the
language to set-theory" (or to some kind of pure lambda calculus),
operational semantics looks more like an interpreter.

Its popularity is probably largely due to the fact that it's defined
in 2 steps: first define the "machine" you use to represent the
intermediate states, and then define the transition rules.  So you can
define the machine according to your needs.

As for "optional", I'm not sure what you (the OP) meant by that.
Already in the syntax case, it's not clear whether you meant "optional
syntax" to mean "syntax which the implementation can choose to support
or not" or "syntax which the user can decide to use or not".  In the
BNF usually you get the second rather than the first, but the
equivalent for semantics ("semantics which the user can choose to use
or not") is generally implicit (which is a common reason why compilers
can't perform particular optimizations or need sophisticated analyses
before they can).

        Stefan

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web