1

I am writing a language specification, and I need the following rudimentary question resolved. Suppose I have the (admittedly contrived) abstract syntax:

<A> ::= <B> | <C>
<B> ::= 1 | 2 | 3
<C> ::= 4 | 5 | 6

What does the denotational semantics for this language look like? Non-terminals are enclosed in '<' and '>' and terminals are not. I want to map 1 ... 6 to the domain of natural numbers. The thing that is not at all clear to me is whether I need to provide mappings for non-terminals. It seems like I should not need to since, e.g., <A> ::= <B> | <C> has no meaning; it is simply a bit of structure. Ignore, for the moment that we could eliminate this rule entirely.

So, as it stands, this is what I think the complete denotational definition should look like, where the right-hand side (in italics) represents the corresponding value from the natural numbers:

[[1]] =one

[[2]] =two

[[3]] =three

[[4]] =four

[[5]] =five

[[6]] =six

Aesthetically, it seems odd not to mention A, B, or C at all, but I suppose that those symbols will never appear in an actual program (like: 4), so maybe this suffices. All of the materials I have on this subject omit this very simple, nuts and bolts, aspect of the language definition process from their discussions.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
Dan Barowy
  • 2,270
  • 24
  • 35

1 Answers1

2

Semantics is applied to program generated by grammar. When you generate program from this grammar you will not see non-terminals, so you don't need to define semantics for them.

Consider example:

Exp ::= Num | Exp + Exp
Num ::= 0,1,2,...

In this example it is necessary to define semantics of whole Num case by case, but it is also important to define semantics for Exp, because one of the productions even though is not terminal (but it has some notion of terminality - + is not going to change) has some special meaning assigned to it - addition.

So you will do as follows:

[[0]] = 0 // first 0 is just some string, the second is a number from N
[[1]] = 1 ...
[[Exp + Exp]] = [[Exp]] + [[Exp]] // first + sign is just string,
                                  // the second is addtion in N

As you can see, when you define semantics you are striving to give meaning to every possible program which can be generated by your grammar.

You can think of it as follows: when your production can be applied recursively you need to define semantics for it - that is the case for Exp + Exp. Num, however, leads straight to terminal no matter what you try to do.

Sidenote: It is worth mentioning why we are given grammar to define semantics.

Grammars are most handy definitions of language to define semantics. This is because semantics can be easily defined using induction over structure of our language. We supply rules for base cases - terminals, and non-trivial production, like + in our example.

Adrian
  • 1,166
  • 6
  • 15