44. Способы определения языков

Описание языков программирования во многом опирается на теорию формальных языков. Эта теория является фундаментом для организации синтаксического анализа и перевода.

Существует два основных способа определения языков:

• механизм порождения или генератор;
• механизм распознавания или распознаватель.

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

Неформально язык L - это множество цепочек конечной длины в алфавите T. Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой. Цепочки (предложения) языка строятся в соответствии с этими правилами. Достоинство определения языка с помощью грамматик в том, что операции, производимые в ходе синтаксического анализа и перевода, можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик.

Механизм распознавания использует алгоритм, который для произвольной входной цепочки остановится и ответит "да" после конечного числа шагов, если эта цепочка принадлежит языку. Если цепочка не принадлежит языку, алгоритм ответит "нет". Распознаватели используются непосредственно при построении синтаксических анализаторов и являются как бы их формальной моделью. Распознаватели строятся на основе теорий конечных автоматов и автоматов с магазинной памятью.

Формальные грамматики

Грамматикой называется четверка G = (N, T, P, S), где N - конечное множество нетерминальных символов (нетерминалов), T - множество терминалов (не пересекающихся с N), S - символ из N, называемый начальным, Р - конечное подмножество множества:

(N È T)^* N (N È T)^* x (N È T)^*,

называемое множеством правил. Множество правил Р описывает процесс порождения цепочек языка. Элемент p_i = (a, b) множества Р называется правилом (продукцией) и записывается в виде a Þ b. Здесь a и b - цепочки, состоящие из терминалов и нетерминалов. Данная запись может читаться одним из следующих способов:

·         цепочка a порождает цепочку b;

·         из цепочки a выводится цепочка b.

Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую. То есть правило p_i - это двойка (p _i1, p_i2), где p _i1 = (N È T)^* N (N È T)^* - цепочка, содержащая хотя бы один нетерминал, p_i2 = (N È T)^* - произвольная, возможно пустая цепочка (e - цепочка).

Если цепочка a содержит p_i1, то, в соответствии с правилом p_i, можно образовать новую цепочку b, заменив одно вхождение p_i1 на p_i2. Говорят также, что цепочка b выводится из a в данной грамматике.

Для описания абстрактных языков в определениях и примерах будем пользоваться следующими обозначениями:

·         терминалы обозначим буквами a, b, c, d или цифрами 0, 1, ..., 9;

• нетерминалы будем обозначать буквами A, B, C, D, S (причем нетерминал S - начальный символ грамматики);
• буквы U, V, ..., Z используем для обозначения отдельных терминалов или нетерминалов;
• через a, b, g... обозначим цепочки терминалов и нетерминалов;
• u, v, w, x, y, z - цепочки терминалов;
• для обозначения пустой цепочки (не содержащей ни одного символа) будем использовать знак e;
• знак “®” будет отделять левую часть правила от правой и читаться как “порождает” или “есть по определению”. Например, A®cd, читается как “A порождает cd”.

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

Пример грамматики G1:

G1 = ({A, S}, {0, 1}, P, S),

где P:

1. S ® 0A1;

1. 0A ® 00A1;
2. A ® e.

Выводимая цепочка грамматики G, не содержащая нетерминалов, называется терминальной цепочкой, порождаемой грамматикой G.

Язык L(G), порождаемый грамматикой G, - это множество терминальных цепочек, порождаемых грамматикой G.

Введем отношение Þ_G непосредственного вывода на множестве (N È T)*, которое будем записывать следующим образом:

j Þ_G y.

Данная запись читается: y непосредственно выводима из j для грамматики G = (N, T, P, S) и означает: если abg - цепочка из множества (N È T)* и b ® d - правило из Р то abg Þ_G adg.

Через Þ_G⁺ обозначим транзитивное замыкание (нетривиальный вывод за один и более шагов). Тогда j Þ_G⁺ y читается как: y выводима из j нетривиальным образом.

Через Þ_G^* - обозначим рефлексивное и транзитивное замыкание (вывод за ноль и более шагов). Тогда j Þ_G^* y означает: y выводима из j .

Пусть Þ^k k - я степень отношения Þ. То есть, если a Þ^k b, то существует последовательность a₀a₁a₂a₃ ... a_k из к+1 цепочек

a = a₀, a₁, ... a_{i -1} Þ a_i, 1 ≤ i ≤ k и a_k = b.

Пример выводов для грамматики G1:

S Þ 0A1 Þ 00A11 Þ 0011;

S Þ¹ 0A1; S Þ² 00A11; S Þ³ 0011;

S Þ⁺ 0A1; S Þ⁺ 00A11; S Þ⁺ 0011;

S Þ^* S; S Þ^* 0A1; S Þ^* 00A11; S Þ^* 0011;

где 0011 Ì L(G1).