I.5. Синтаксис и семантика языка

 

В любом языке можно выделить синтаксис и семантику. Кроме того, трансляторы умеют делать с лексическими конструкциями (лексемами),которые задаются лексикой языка. Синтаксис языка – это любой набор правил, определяющий допустимые конструкции языка. Он определяет «форму» языка, т.е. задает набор цепочек символов, которые принадлежат языку. Чаще всего он задается в виде строго набора правил, но полностью это утверждение справедливо для чисто формальных языков.

Для большинства языков программирования набор заданной синтаксической конструкции нуждается в дополнительных пояснениях. Например строка 3+2 является арифметическим выражением,а тройка 32+ не является.

Семантика языка – это раздел языка, определяющий значения предложений языка. Она определяет содержание языка, т.е. задает смысл для всех допустимых цепочек языка. Для большинства языков она определяет неформальными методами отношение между знаками и тем, что они обозначают изучается семантикой. Чисто формальные языки лишены какого-либо смысла. Для записанного примера, используя семантику алгебры можно сказать, что строка 3+2 есть сумма чисел 3 и 2, а так же то, что 3+2=5 –это истинное выражение. Изложить синтаксис алгебры проще, чем ее семантику(хотя в случае алгебры семантику можно определить формально).

Лексика – совокупность слов, словарный запас языка. Слово или лексическая единица(лексема языка) это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Она может содержать только элементарные символы и не может содержать в себе других лексических единиц. Лексическими единицами (лексемами) для русского языка являются слова русского языка, а знаки препинания и пробелы – это разделители необразованных лексем. Лексическими единицами алгебры являются числа, знаки математических операций, обозначение функций неизвестных величин. В языках программные лексические единицы – это ключевые слова, идентификаторы, константы, метки, знаки препинания, разделители (скобки, точка запятой и др.)

 

I.6. Определение грамматики

Грамматика языка – это описание способа построения предложений некоторого языка, т.е. математическая система, определяющая язык. Она указывает правила порождения цепочек символов языка, т.е. является генератором символов цепочек языка. Она относится ко 2ому способу определения языков (т.е. порождению цепочек символов). Она описывается различными способами. Например: грамматика русского языка описывается набором правил, изученных в школе. Для синтаксических конструкций языков программирования используют формальные описания грамматик, построенных на основе системы правил (или продукций). Правила или продукция – это упорядочная пара цепочек символов α, β. В правилах связан порядок следования цепочек, поэтому их записывают α → β или α: = β. Такая запись читается: «α порождает β»,- или так: «β по определению есть α»

<< α … β>>, << β … α>>

Грамматика языка программирования содержит правила двух типов. Первые, определяющие синтаксические конструкции языка, они поддаются формальному описанию. Вторые, определяющие семантические ограничения языка. Они излагаются в неформальной форме. Поэтому любое описание или стандартный язык программирования состоит их 2ух частей. В первой части формально излагаются правила построения синтаксических конструкций, а потом на естественном языке дается описание семантических правил.

G L(G)

2 грамматики G и G’ называются эквивалентными, если они определяют один и тот же язык.

L(G)=L(G’)

Две грамматики называются почти эквивалентными, если заданные ими языки различаются не более, чем на пустую цепочку символов.

L(G)∪{ λ }=L(G’) ∪{ λ }

Формально G определяется

G(VT,VN,P,S), где

VT – это множество терминальных символов или алфавит терминальных символов

VN – это множество не терминальных символов или алфавит нетерминальных символов

P – множество правил (продукций грамматик)

Правило вида

α → β, где α ∈ (VN ∪VT)⁺, β ∈ (VN ∪VT)^*

S – целевой, начальный символ грамматики

S∈VT

VN ⋂ VT =

Алфавиты терминальных и нетерминальных символов не пересекаются. Это значит, что символ грамматики может быть терминальным, либо нетерминальным, но не может быть одновременно тем или другим. Целевой символ грамматики всегда терминальный (S).

Множество V=VN∪VT называют полным алфавитом грамматики G. Множество терминальных символов VT содержит символы, которые входят в алфавит языка порождаемой грамматикой. Как правило символы из этого множества встречаются только в цепочках в правых частях правил. Множество нетерминальных символов VN содержит символы, которые определяют слова,понятия, конструкции языка. Каждый символ этого множества может встречаться в цепочках как левой, так и правой частей правил грамматики, но он обязан хотя бы 1 раз быть в левой части хотя бы одного правила. Во множестве правил могут быть несколько правил, имеющие одинаковые левые части вот такого вида:

α → β₁, α → β₂, …, α → β_n.

Когда эти правила объединяют вместе, записывают в таком виде:

α → β₁ | β₂ |…| β_n.

Одной строке в такой записи соответствует n-правил. Такую запись правил грамматики называют правилом Бэкуса – Наура. Эта форма предусматривает, что нетерминальные символы берутся в угловые скобки.

 

I.7. Пример грамматики

Это грамматика G, которая определяет язык целых десятичных цифр со знаком

G=({0,l,2,3,…,9,-,+},{<число>,<чс>,<цифра>},Р,<число>)

Р:

<<число> → <чс> | +<чс> | —<чс>

<<чс> → <цифра> | <чс>|<цифра>

<<цифра> → 0 | 1 | 2 | …| 9

Составляющие элементы этой грамматики:

1) множество терминальных символов VT содержит двенадцать элементов: это десять

десятичных цифр и два знака;

2) множество нетерминальных символов VN содержит три символа: символы

<число> и <цифра>;

3) множество правил содержит 10 правил, которые записаны в три строки

Целевым символом является число. Символ <чс> бессмыслен.

В названии нетерминальных символов не обязательно быть осмысленным. Они применяются для удобства понимания символов грамматики. Их набор произволен. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой. В языках целых десятичных чисел со знаком, в котором нетерминальные символы обозначаются большими латинскими буквами.

G' =({ 0, 1, 2, 3, …, 9, -, +}, {S, T, F }, Р, S)

Р:

S → Т | +Т | —Т

Т → F | TF

F → 0 | l | 2 …| 9

Здесь изменилось лишь множество нетерминальных символов VN={STF}, а язык заданный грамматикой не изменился, поэтому грамматики G и G’ считаются эквивалентными.