Hello Compiler Experts!

Ah! I found the answer to the question:

What is the semantics of a language?

Section 3.4 of the Bison specification [1] has the answer:

3.4 Defining Language Semantics

The grammar rules for a language determine only the syntax. The
semantics are determined by the semantic values associated with
various tokens and groupings, and by the actions taken when various
groupings are recognized.

Niklaus Wirth agrees with the Bison specification. In the introduction of his book, Compiler Construction, he says [2]:

The translation process is now guided by the structure of the analysed
text. The text is decomposed, parsed into its components according to
the given syntax. For the most elementary components, their semantics
is recognized, and the meaning (semantics) of the composite parts is
the result of the semantics of their components. Naturally, the
meaning of the source text must be preserved by the translation.

Do you agree that that is the definition of the semantics of a language?

/Roger

[1] Section 3.4 of the Bison specification: https://www.gnu.org/software/bison/manual/bison.html#Semantics

[2] See page 6, fourth paragraph in Compiler Construction by Niklaus Wirth: https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction1.pdf
[That's one definition. But I suspect we will hear it's far from the only one. -John]

On Friday, January 21, 2022 at 9:24:11 PM UTC-6, Roger L Costello wrote:
> What is the semantics of a language?
>
> Section 3.4 of the Bison specification [1] has the answer:
>
> 3.4 Defining Language Semantics
>
> The grammar rules for a language determine only the syntax. The
> semantics are determined by the semantic values associated with
> various tokens and groupings, and by the actions taken when various
> groupings are recognized.
>
> Niklaus Wirth agrees with the Bison specification. In the introduction of his book, Compiler Construction, he says [2]:
>
> The translation process is now guided by the structure of the analysed
> text. The text is decomposed, parsed into its components according to
> the given syntax. For the most elementary components, their semantics
> is recognized, and the meaning (semantics) of the composite parts is
> the result of the semantics of their components. Naturally, the
> meaning of the source text must be preserved by the translation.
>
> Do you agree that that is the definition of the semantics of a language?

I think those are both good. Another perspective is view syntax vs. semantics
as the purview of different tools. A parser generator will handle the syntax but
you have to provide the semantics in some other form. Adopting a common
backend will handle semantics but you have to provide your own syntax analysis.
So I'd say the syntax is directed by the grammar, but the semantics is directed
by the resulting structure from a successful application of that syntax.

What it looks like vs. What to do about it

On Friday, January 21, 2022 at 7:24:11 PM UTC-8, Roger L Costello wrote:

> Ah! I found the answer to the question:

> What is the semantics of a language?

> Section 3.4 of the Bison specification [1] has the answer:

> 3.4 Defining Language Semantics

> The grammar rules for a language determine only the syntax. The
> semantics are determined by the semantic values associated with
> various tokens and groupings, and by the actions taken when various
> groupings are recognized.

It seems to me that the distinction is less important than it used to be.

There is a story (possibly fictional) of a compiler with only one error message:

"SYNTAX ERROR" (You were lucky to get the line number.)

For most languages, there are many programs that satisfy the syntax
rules, but not the semantics. If, for example you have:

J = 1.2

and J has the wrong type, this is a semantic error, not a syntax error.
This used to be more important, as compilers generated the error messages
in a different way, and possibly at a different time. Syntax errors might be
generated line by line, but semantics errors not until the whole program has
been processed. When memories were small, tricks were used to fit compilers
into the available memory.

Reminds me, in the days of punched cards there were stories about
debugging compilers by feeding in cards from the recycling bin. Most
likely, that includes many statements that are almost correct, and
that one would like the compiler to properly report the error.
[The line between syntax and semantics is quite fuzzy. There have been languages
that put the types into the syntax so your example would have been a syntax
error. Experience has shown that's not a great idea since it's much harder
to produce useful error messages that way. -John]

On Sat, 22 Jan 2022 00:08:35 +0000, Roger L Costello
<costello@mitre.org> wrote:

>Hello Compiler Experts!
>
>Ah! I found the answer to the question:
>
> What is the semantics of a language?
>
>Section 3.4 of the Bison specification [1] has the answer:
>
>3.4 Defining Language Semantics
>
>The grammar rules for a language determine only the syntax. The
>semantics are determined by the semantic values associated with
>various tokens and groupings, ...

This part of the statement is an example of circular reasoning and is
absolutely meaningless.

>... and by the actions taken when various groupings are recognized.

This part is valid - there may be distinction necessary between
actions taken at compile time vs actions taken at run time, but in any
case actions DO define semantics.

>Niklaus Wirth agrees with the Bison specification. In the introduction of his book, Compiler Construction, he says [2]:
>
>The translation process is now guided by the structure of the analysed
>text. The text is decomposed, parsed into its components according to
>the given syntax. For the most elementary components, their semantics
>is recognized, and the meaning (semantics) of the composite parts is
>the result of the semantics of their components. Naturally, the
>meaning of the source text must be preserved by the translation.
>
>Do you agree that that is the definition of the semantics of a language?

I agree that Wirth's statement is very similar to what is in the Bison
manual.

Not having either the Bison manual or Wirth's book handy, I will
comment only on the quoted statements above. I will (perhaps naively)
assume that in both cases there is further explanation in the
respective texts.

The problem with both statements is that neither defines what is meant
by "semantic value".

Bison assumes that the reader understands what is a token, what is the
"value" of a token, and what a token "value" means in context of a
given grouping of tokens.
[Of course, the developer /must/ know these things, but that statement
clearly was not written for a beginner.]

Wirth's statement makes an analogous mistake while also introducing a
distinction between "elementary" components whose semantics somehow
simply can be "recognized", and "composites" which somehow take their
semantics from some confluence of the semantics of their constituent
components (although that is not explicitly stated and so may be
unclear to the reader).

I learned addition in /elementary/ school - so is addition elementary?
Or is it composite? The reader has to know - or be told - that in the
context of compiling "2" should be considered elementary but "1 + 1"
should be considered composite.
[This leaves aside whether or not the the addition might be evaluated
at compile time and only the result inserted into the object code.]

For comparison, the Lisp manual explicitly defines what is literal
data and says that literal data is "self evaluating": e.g., "42" will
evaluate to the /integer/ value 42, and that the resulting value will
satisfy certain testing predicates such as integerp, rationalp, etc.
If, instead, you wanted a floating point value, you need to convert
the integer or write the literal in a different way.

Although somewhat blatantly obvious, Lisp makes clear that literals do
have semantics - ie. that they are self-evaluating, that the result of
evaluation is a value of a certain "type", and what it means to be a
value of a certain type.

Other languages also explicitly define these things in their manuals
and/or standards ... I'm simply picking on Lisp because, AFAIK, it was
the first to rigorously do so.

>/Roger
>
>[1] Section 3.4 of the Bison specification: https://www.gnu.org/software/bison/manual/bison.html#Semantics
>
>[2] See page 6, fourth paragraph in Compiler Construction by Niklaus Wirth: https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction1.pdf
>[That's one definition. But I suspect we will hear it's far from the only one. -John]

YMMV,
George

On Wednesday, January 26, 2022 at 11:48:28 AM UTC-8, George Neuner wrote:

(snip)

> I learned addition in /elementary/ school - so is addition elementary?
> Or is it composite? The reader has to know - or be told - that in the
> context of compiling "2" should be considered elementary but "1 + 1"
> should be considered composite.

For some reason, I have recently been answering questions (not here) about
which AP calculus class to take, and when.

I was reminded about the way some students think about math. That they
learn each subject (algebra, geometry, calculus), take the exam, check
it off the list of accomplishments, and then forget about it.

And my counterexample is that you still need the addition you learned
in first grade, even in calculus. (This is especially for students
hoping to finish calculus before college, so they don't have to think
about it any more.)

But as recent discussions here have noted, you can't completely
separate syntax and semantics. The line is fuzzy. A compiler class
might teach syntax for some lectures, and semantics later, try to
separate them to make it easier for students, but in the end you need
both of them.

This goes back to the way languages are defined. It goes into the way
compilers are written, which isn't always the same way as the language
definition. (And is more important when you try to get error messages
right.)

I remember so many years ago, learning about operator precedence
parsers, but that seems to be a lost art now.

On 1/21/2022 5:08 PM, Roger L Costello wrote:
> Hello Compiler Experts!
>
> Ah! I found the answer to the question:
>
> What is the semantics of a language?
>
> Section 3.4 of the Bison specification [1] has the answer:
>
> 3.4 Defining Language Semantics
>
> The grammar rules for a language determine only the syntax. The
> semantics are determined by the semantic values associated with
> various tokens and groupings, and by the actions taken when various
> groupings are recognized.
>
> Niklaus Wirth agrees with the Bison specification. In the introduction of his book, Compiler Construction, he says [2]:
>
> The translation process is now guided by the structure of the analysed
> text. The text is decomposed, parsed into its components according to
> the given syntax. For the most elementary components, their semantics
> is recognized, and the meaning (semantics) of the composite parts is
> the result of the semantics of their components. Naturally, the
> meaning of the source text must be preserved by the translation.
>
> Do you agree that that is the definition of the semantics of a language?
>
> /Roger
>
> [1] Section 3.4 of the Bison specification: https://www.gnu.org/software/bison/manual/bison.html#Semantics
>
> [2] See page 6, fourth paragraph in Compiler Construction by Niklaus Wirth: https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction1.pdf
> [That's one definition. But I suspect we will hear it's far from the only one. -John]

For what it's worth, the 1969 Burroughs B5500 Extended ALGOL Reference
Manual had sections like this:

===
EXPRESSIONS

GENERAL.

SYNTAX.

The syntax for <expression> is as follows:

    <expression> ::=
            <arithmetic expression> |
            <Boolean expression> |
            <designational expression> |
            <concatenate expression>

SEMANTICS

Expressions, which are basic to any algorithmic process, are rules to
obtain values of different kinds and types.

As mentioned on page 3-1 [GENERAL COMPONENTS], expressions are used to
define certain general components (subscripted variables and function
designators), and these quantities in turn are used to define
expressions. The definition of expressions is therefore necessarily
recursive.
===

It didn't make sense when I first read it some 50 years ago, and it
doesn't make sense now, but I learned not to let that bother me.

Louis