Определение языка. Синтаксис и семантика.

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

Формализм, или нотация, использованный при написании этих правил, называется Бэкуса–Наура формой (БНФ). синтаксические единицы <предложение>, <подлежащее> и <сказуемое> называются нетерминальными символами, слова "кошки", "собаки", "спят", "едят" – терминальными символами, а правила – порождающими правилами. Символы “::=”, “|”, а также скобки нетерминальных символов “<>” – это метасимволы языка БНФ (метасимволы не принадлежат описываемому языку, а относятся к языку описания. Семантика задает значение всем предложениям языка. Изменим пример про животных: <предложение>::=<подлежащее><сказуемое> <подлежащее> ::= люди | собаки <сказуемое> ::= говорят | спят Методы формального описания семантики разработаны недостаточно хорошо и в этих целях часто используется естественный язык. Для рассмотрения задачи спецификации синтаксиса дадим несколько определений. Алфавит – множество символов. Например: Русские буквы, Латинские буквы, цифры. Если A – алфавит, A* (замыкание A) обозначает множество всех строк (включая пустую строку), составленных из символов, входящих в A. A+ обозначает множество всех строк (исключая пустую строку), состоящих из символов, входящих в A. Пустая строка обычно обозначается с помощью ε (эпсилон). Синтаксис языка можно определить, пользуясь системой изображения множеств, например L = { 0n1n | n ≥ 0}. Данный язык включает строки, состоящие из одного или более нулей и того же числа последующих единиц, а также пустую строку.

Более сложный синтаксис языка лучше определять с помощью грамматики. В грамматику входит набор правил для получения предложений языка. Возьмем синтаксис L и воспользуемся следующими правилами: 1. S → 0S1 2. S → ε Чтобы вывести предложение этого языка, поступим следующим образом. Начнем с символа S и заменим его на 0S1 или ε. Если S опять появился в полученной строке, его опять можно заменить с помощью одного из этих правил, и т.д. Полученная таким образом любая строка, не содержащая S, является предложением этого языка. Например, S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111 Последовательность таких шагов называется выводом строки 000111, а символ ⇒ служит для разделения шагов вывода. Все предложения данного языка можно вывести, руководствуясь двумя правилами, любая строка, которую нельзя вывести с их помощью, не является предложением этого языка. Грамматику часто называют системой перезаписи. Грамматика определяется как четверка (Vt, Vn, P, S), где Vt – алфавит, символы которого называются терминальными (терминалами), из них строятся цепочки порождаемые грамматикой. Vn – алфавит, символы которого называется нетерминальными (нетерминалами), используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения. Vt и Vn не имеют общих символов, т.е. Vt ∩Vn = Ø, полный алфавит (словарь) грамматики V определяется как Vt ∪ Vn. P – набор порождающих правил, каждый элемент которых состоит из пары (α, β), где α находится в V+, а β в V*. α – левая часть правила, а β – правая, т.е. цепочки, построенные из символов алфавита V. Правило записывается α → β. S принадлежит Vn и называется начальным символом (аксиомой). Этот символ – отправная точка в получении любого предложения языка. Грамматикой, генерирующей язык L = { 0n1n | n ≥ 0} является G0 = ( {0,1}, {S}, P, S), где P = { S → 0S1, S → ε }.

Грамматикой, генерирующей язык L = { an bm | n, m ≥ 0} является G0 = ( { a, b}, {S, A, B}, P, S), где P = { S → AB, A → aA, A → ε, B → bB, B → ε } Начав с символа S и применяя последовательно по одному из правил замены нетерминала в выводимой строке можно, например, генерировать строку aaabb: S ⇒ AB ⇒ aAB ⇒ aaAB ⇒ aaaAB ⇒ aaaB ⇒ aaabB ⇒ aaabbB ⇒ aaabb Каждая строка, которую можно вывести из начального символа, называется сентенциальной формой. Предложение – сентенциальная форма, содержащая только терминалы. Терминалы будем обозначать строчными (маленькими) буквами, а нетерминалы – прописными (большими). Как правило, предложения языка можно генерировать с помощью более чем одной грамматики. Две грамматики, генерирующие один и тот же язык, называют эквивалентными. С точки зрения разработчика транслятора одна грамматика может быть гораздо удобней другой.