2. Формальные грамматики и языки

Назовем словарем любое непустое конечное множество символов, а цепочкой (над словарем) – конечную последовательность символов этого словаря. Если – некоторый словарь, то множество всех цепочек над этим словарем, включая пустую цепочку, будем обозначать ^*, а множество всех цепочек над словарем без пустой цепочки – ⁺.

Формальной грамматикой G называется четверка объектов G = < T, N, S, R >, где T – терминальный словарь, N – нетерминальный словарь, S – начальный символ грамматики, R – множество правил вывода.

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

Нетерминальный словарь N представляет собой конечное непустое множество вспомогательных символов (понятий языка), используемых для вывода предложений языка, T ∩ N = .

Терминальный и нетерминальный словари образуют V = T U N – полный словарь грамматики G.

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

Формальная грамматика G порождает язык L(G).

Пусть – правило грамматики G. Говорят, что цепочка = ₁₂ непосредственно выводима из цепочки = ₁₂ в грамматике G (записывается ), если цепочка может быть получена из цепочки путем применения правила .

Используя транзитивное замыкание отношения , можно получить нетривиальный вывод цепочки из цепочки в грамматике G (записывается + ). Говорят, что цепочка выводима из цепочки в грамматике G (записывается * ), если + или = . Последовательность цепочек =₀, ₁, …, _n=, которая образуется при выводе цепочки , называется выводом длины n цепочки из цепочки в грамматике G.

Множество всех цепочек над терминальным словарем, выводимых из начального символа грамматики, называется языком, порождаемым этой грамматикой, т. е. L(G) = { x S * x, x T^* }.

Для описания синтаксиса языков программирования наибольшее распространение получили контекстно-свободные грамматики (КС-грамматики). С их помощью можно определить синтаксис большинства конструкций языка программирования. В КС-грамматике правила вывода имеют вид: A , где A – нетерминал, а V^*.

КС-грамматики и БНФ, по существу, эквивалентны, различия касаются только обозначений. Так металингвистической связке “::=” из БНФ соответствует отношение “” в КС-грамматике, металингвистическим переменным из БНФ соответствуют в КС-грамматике нетерминальные символы, основным символам языка программирования из БНФ соответствуют терминальные символы КС-грамматики.

Вывод в КС-грамматике G называется левосторонним, если правила вывода на каждом шаге вывода применяются к самому левому нетерминалу цепочки.

Пример 1.1

Задана грамматика G₁ = < T, N, L, R >, где T = { a, b, c, +, , (, ) } ,

N = { E, T, P} , R = { E E + T, E T, T T P, T P, P ( E ), P a , P b, P c } .

Примером левостороннего вывода цепочки a + b c в грамматике G₁ является вывод:

E E + T T + T P + T a + T a + T P a + P P

a + b P a + b c

Представление вывода некоторой цепочки в КС-грамматике последовательностью цепочек, получаемых в процессе вывода, имеет ряд недостатков:

• приходится многократно выписывать повторяющиеся части цепочек (контекст, в котором применяются правила вывода);

• цепочки, получаемые в процессе вывода, не содержат никакой информации о синтаксической структуре выводимой цепочки.

Другим, более наглядным, способом представления вывода непустой цепочки в КС-грамматике является синтаксическое дерево (дерево вывода).

Синтаксическое дерево – это дерево, обладающее следующими свойствами:

• все вершины дерева помечены символами полного словаря V грамматики G: корень дерева помечен начальным символом грамматики, заключительные вершины – терминальными символами, а промежуточные вершины – нетерминалами;

• если вершина дерева помечена нетерминалом А, а ее прямые потомки – символами X₁, X₂, …, X_n, то А X₁X₂ …X_n – правило вывода КС-грамматики.

Алгоритм построения синтаксического дерева рассмотрим на примере построения дерева вывода цепочки a + b c в грамматике G₁ (см. пример 1.1). Построение синтаксического дерева начинается с корня, который отмечается начальным символом грамматики E. Выбираем правило вывода E E + T и для каждого символа, входящего в правую часть этого правила, строим вершину, отметив ее соответствующим символом, и соединяем ее дугой с корнем дерева. Все построенные вершины должны располагаться в дереве на одном уровне таким образом, чтобы самая левая вершина соответствовала самому левому вхождению символа в правую часть правила, вторая слева вершина – второму слева вхождению символа и т. д. На втором шаге построения дерева найдем вершину, отмеченную нетерминалом, к которому должно применяться правило вывода (вершина Е), и повторим для нее действия, описанные на первом шаге. Первый и второй шаги построения дерева повторяются до тех пор, пока в дереве имеются вершины, отмеченные нетерминалами. Синтаксическое дерево цепочки a + b c приведено на рисунке.

Цепочка, которая получится, если выписать слева направо вершины дерева, отмеченные терминальными символами, называется кроной дерева.

Если G = < T, N, S, R > – КС-грамматика, то S* тогда и только тогда, когда в G существует дерево вывода с кроной [2].

КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка x L(G), которая является кроной двух или более деревьев вывода в грамматике G. В противном случае КС-грамматика G называется однозначной.

Желательно, чтобы грамматика, используемая для задания языка программирования, была однозначной. В противном случае программист и разработчик компилятора могут по-разному интерпретировать смысл некоторых программ; синтаксический анализ таких программ выполнить достаточно сложно.

В работе [2] доказано, что проблема однозначности для произвольной КС-грамматики алгоритмически не разрешима. Это означает, что нельзя составить алгоритм, который за конечное число шагов определял бы, однозначна КС-грамматика или нет. Однако для достаточно больших подклассов КС-грамматик известно, что они однозначны. Например, доказано [3], что все детерминированные КС-языки [4] определяются однозначными КС-грамматиками.

Описание синтаксиса языка программирования, выполненное с помощью БНФ или КС-грамматики, не всегда может быть использовано для конкретного метода синтаксического анализа. Часто разработчику языкового процессора приходится заново определять синтаксис входного языка, подбирая для описания КС-грамматику с определенными свойствами, требуемыми для выбранного метода синтаксического анализа, или использовать алгоритмы эквивалентного преобразования исходной грамматики [2], [4], [5], позволяющие получить КС-грамматику с нужными свойствами. Следующие эквивалентные преобразования КС-грамматик являются наиболее распространенными:

• исключение из КС-грамматики бесполезных символов [2], [4];

• преобразование КС-грамматики с ε-правилами в эквивалентную неукорачивающую КС-грамматику (НКС-грамматику) [2], [4];

• устранение из КС-грамматики цепных правил [2], [4];

• удаление из КС-грамматики произвольного одиночного правила [4];

• исключение из КС-грамматики правил с одинаковой правой частью [4];

• устранение из КС-грамматики левой рекурсии [2], [4];

• левая факторизация (вынесение общей части правых частей правил вывода) – используется для преобразования исходной КС-грамматики в эквивалентную LL(1)-грамматику [5];

• замена края (самого левого вхождения нетерминала в правую часть правила вывода) – используется для преобразования исходной КС-грамматики в эквивалентную LL(1)-грамматику [5];

• устранение конфликтов переноса – свертки (используется для приведения исходной грамматики к грамматике предшествования) [5].

Иногда оказывается более целесообразным не выполнять эквивалентные преобразования исходной КС-грамматики G, а разбить ее на n подграмматик G₁, G₂, …, G_n, которые вместе описывают исходный язык. В этом случае каждая подграмматика Gi (1 i n), которая также является КС-грамматикой, описывает одну или несколько конструкций языков программирования, таких, как арифметические выражения, раздел описаний типов, раздел описаний переменных, раздел операторов и т. п. При объединении подграмматик G₁, G₂, …, G_n в общую грамматику G начальные символы S₁, S₂, …, S_n подграмматик G₁, G₂, …, G_n интерпретируются в грамматике G как терминалы специального вида.

2. ВНУТРЕННИЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ

Математически перевод определяется как множество пар, причем первый элемент принадлежит множеству объектов, которые требуется перевести, а второй элемент – множеству объектов, являющихся результатом перевода.

Компилятор в целом определяет перевод исходной программы, представленной в виде цепочки символов на языке программирования, в объектный код. Если компиляцию рассматривать как многоэтапный процесс, то можно говорить о переводе, присущем каждому этапу компиляции. Например, в процессе лексического анализа исходная программа преобразуется из цепочки символов в цепочку лексических единиц (лексем), а на этапе синтаксического анализа цепочка лексем преобразуется в некоторую промежуточную форму, являющуюся линейной формой записи синтаксического дерева программы. Различные формы представления промежуточной программы различаются, в основном, способом соединения операторов и операндов. Общепринятыми промежуточными формами представления программы являются:

• польская инверсная запись;

• тетрады;

• триады;

• связные списочные структуры.