Как обозначить семантику этого синтаксиса?

Question

Я пишу спецификацию языка, и мне нужно решить следующий элементарный вопрос. Предположим, у меня есть (по общему мнению, надуманный) абстрактный синтаксис:

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

Как выглядит денотационная семантика для этого языка? Нетерминалы заключены в "<" и ">", а терминалы - нет. Я хочу на карту 1... 6 в область натуральных чисел. Мне не совсем понятно, нужно ли мне предоставлять сопоставления для нетерминалов. Кажется, что мне не нужно, так как, например, <A> ::= <B> | <C> не имеет смысла; это просто немного структуры. Не обращайте внимания, на данный момент, что мы могли бы полностью устранить это правило.

Итак, в таком виде, как мне кажется, должно выглядеть полное денотационное определение, где правая часть (курсивом) представляет соответствующее значение из натуральных чисел:

[[1]] =один

[[2]] =два

[[3]] =три

[[4]] =четыре

[[5]] =5

[[6]] =шесть

Эстетически кажется странным не упоминать A, B, или же C вообще, но я предполагаю, что эти символы никогда не появятся в реальной программе (например: 4), так что, возможно, этого достаточно. Все материалы, которые у меня есть на эту тему, опускают этот очень простой, неотразимый аспект процесса определения языка в их обсуждениях.

Answer 1

Семантика применяется к программе, сгенерированной грамматикой. Когда вы генерируете программу из этой грамматики, вы не увидите нетерминалов, поэтому вам не нужно определять для них семантику.

Рассмотрим пример:

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

В этом примере необходимо определить семантику целого Num в каждом конкретном случае, но также важно определить семантику Expпотому что одно из произведений, хотя и не является терминальным (но у него есть некоторое понятие терминальности - + не собирается меняться) имеет какое-то особое значение для него - дополнение.

Итак, вы будете делать следующее:

[[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

Как вы можете видеть, когда вы определяете семантику, вы стремитесь придать смысл каждой возможной программе, которая может быть сгенерирована вашей грамматикой.

Вы можете думать об этом следующим образом: когда ваша продукция может быть применена рекурсивно, вам нужно определить семантику для нее - это относится к Exp + Exp, NumОднако, ведет прямо к терминалу, независимо от того, что вы пытаетесь сделать.

Sidenote: Стоит упомянуть, почему нам дана грамматика для определения семантики.

Грамматики являются наиболее удобными определениями языка для определения семантики. Это потому, что семантика может быть легко определена с помощью индукции по структуре нашего языка. Мы поставляем правила для базовых случаев - терминалов и нетривиального производства, как + в нашем примере.