Форма Бэкуса-Наура (БНФ)

Далее, для описания синтаксиса мы будем использовать контекстно-свободные грамматиками, задаваемые в форме Бэкуса-Наура (БНФ). Это существенно более мощный механизм, чем регулярные выражения. Поэтому из соображений наглядности его можно использовать и для описания лексики. Однако, регулярные языки допускают гораздо более эффективную реализацию.

Грамматика представляется в виде совокупности правил, каждое из которых даёт «толкование» некоторому определяемому понятию, называмому также нетерминалом. Для одного и того же нетерминала может быть несколько правил, и в этом случае они рассматриваются как альтернативы. Терминальными символами (или сокращённо терминалами) называются элементы, которые не требуют дальнейшего раскрытия. В случае описания лексики терминалами являются символы входного текста, а в случае синтаксиса – лексемы. В дальнейшем нетерминальные символы мы будем выделять курсивом, а терминальные – жирным подчёркнутым. Тогда каждое правило грамматики имеет вид

нетерминал::= последовательность терминалов и нетерминалов

Значок «::=» читается как «это». В таких обозначениях рассмотренное выше определение идентификатора может быть представлено следующей БНФ-грамматикой:

буква::= _

буква::= a

...[5]

буква::= z

цифра::= 0

…

цифра::= 9

букра::= буква

букра::= цифра

букры::=

букры::= букра букры

идент::= буква букры

Для сокращения записи грамматики используются регуляризованные БНФ (РБНФ), которые допускают в правой части правил нотацию, свойственную регулярным выражениям. Так, несколько правил, определяющих один и тот же нетерминал, можно заменить одним, разделив правые части вертикальной чертой "|". Так мы сможем записать

буква::= _ | a |…| z

Пару правил вида

можетбыть::=

можетбыть::= чтото

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

можетбыть::= [ чтото ]

Это позволит нам определить

букры::= [ букра букры ]

Повторение некоторой конструкции ноль или более раз задаётся в РБНФ с помощью итерации Клини *. То есть пара правил вида
несколько::=

несколько::= один несколько

может быть записана правилом:

несколько::= один*

Так мы можем определить букры как:

букры::= (букра)*

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

несколько::= один

несколько::= один несколько

может быть записана правилом:

несколько::= один⁺

Так, например,

букра (букра)* экививалентно (букра)⁺

(букра)* экививалентно [(букра)⁺]

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

Такие обозначения позволяют привести нашу грамматику к следующему виду:

буква::= _ | a |…| z

цифра::= 0 |…| 9

идент::= буква (буква | цифра)*

Переход от БНФ к РБНФ не привносит никакой содержательной информации и служит только для сокращения записи – любую РБНФ можно преобразовать обратно в БНФ.

В качестве примера будем использовать РБНФ для описания арифметических выражений, которые строятся над переменными и константами с помощью знаков операций и скобок:

выр ::= перем

| конст

| (+ | -) выр

| выр (= | < | <= | <> | + | - | * | /) выр

| ( выр )

Отметим, что переменные и константы в этой грамматике являются терминалами.

Задача состоит в том, чтобы выяснить, допускается ли цепочка лексем данной грамматикой. Будем говорить, что из некоторого нетерминала N можно вывести цепочку терминалов t₁,…,t_n, если существует последовательность цепочек s₁,...,s_k, состоящих как из нетерминальных, так и терминальных символов, где s₁ = N, s_k = t₁,...,t_n и каждая последующая цепочка получается из предыдущей заменой некоторого нетерминального символа на правую часть одного из соответствующих ему правил. Такая последовательность цепочек называется выводом. Например, начиная с нетерминала выр, мы можем получить следущий вывод:

Выр

выр + выр

x+ выр

x+ выр * выр

x+2* выр

x+2*y

Здесь предполагается, что x и y обозначают лексемы-переменные, а 2 - лексему-константу.

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

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

Для того, чтобы сохранить и отобразить процесс вывода, используют деревья вывода, называемые также деревьями разбора. Корнем этого дерева является начальный нетерминал, листьями – терминалы, а любая вершина, являющаяся нетерминалом, имеет ровно столько потомков и ровно в той последовательности, сколько встречается в одном из правил для этого нетерминала. Рассмотренный ранее вывод может быть представлен следующим деревом разбора:

выр

Искомая цепочка терминальных символов получается обходом всех листьев дерева слева направо.

Мы не будем вдаваться в подробности теории синтаксического анализа, основы которой можно найти в [Ахо,Ульман]. Отметим только, что эта задача с теоретической точки зрения в общем случае эффективно разрешима.

Поскольку дерево разбора задаёт синтаксическую структуру предложения, на основе которой далее определяется его смысл, то принципиальным является вопрос об однозначности: может ли оказаться, что для рассматриваемого предложения существует несколько деревьев разбора в данной грамматике? Несложно заметить, например, что x+2*y может быть разобрана и следующим образом:

выр

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

выр::= прост-выр [(= | < | <= | <>) прост-выр ]

прост-выр::= [ + | - ] слаг ((+ | -) слаг)*

слаг::= множ ((* | /) множ)*

множ::= (перем | конст | ( выр ))

В этой грамматике выражение x+2*y может быть разобрано единственным способом:

прост-выр

слаг

множ

выр

слаг

множ

Следует отметить, однако, что произведённые изменения в грамматике имеют и побочные эффекты. Например, стали недопустимы следующие выражения, которые допускались исходной грамматикой:

A < B + C < D

+ - + 2

X + - Y

В нашем случае можно считать, что мы ничего не потеряли, поскольку такие выражения были "неправильными" или "избыточными", однако, в общем случае придётся показать, что при изменении грамматики мы не повлияли на распознаваемый язык. Это поднимает вопросы об доказательстве эквивалентности и системах эквивалентных преобразований контекстно-свободных грамматик, но они выходят за рамки данного курса.

В некоторых случаях избавиться от неоднозначности путём преобразования грамматики не удаётся. Классическим примером является неоднозначность, связанная с условным оператором if в некоторых языках программирования. Рассмотрим, например, следующий оператор языка C:

if (x > 0)

if (x < 2)

x = x+1;

else

x = x-1;

Судя по расположению текста кажется, что внешний оператор if имеет две ветки – if(x<2)x=x+1; и x=x-1;. На самом деле это не так: внешний оператор if имеет только одну ветвь, а оператор x=x-1; относится к внутреннему, ближайшему if. Конечно, можно решить проблему, расставив скобки:

if (x > 0)

{

if (x < 2)

x = x+1;

}

else

x = x-1;

но её бы вообще не возникло, если бы условный оператор имел обязательный завершитель, как, например, в языке Modula-2:

IF x>0 THEN

IF x<2 THEN

x:= x+1

END IF