Interested Article - Расширенная форма Бэкуса — Наура

Расширенная форма Бэкуса — Наура ( расширенная Бэкус — Наурова форма ( РБНФ )) ( англ. Extended Backus–Naur Form ( EBNF )) — формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно-свободных формальных грамматик . Предложена Никлаусом Виртом . Является расширенной переработкой форм Бэкуса — Наура , отличается от БНФ более «ёмкими» конструкциями, позволяющими при той же выразительной способности упростить и сократить в объёме описание.

Тем не менее, используется множество различных вариантов РБНФ. Международная организация по стандартизации приняла стандарт РБНФ: ISO/IEC 14977 .

Описание

Терминалы и нетерминалы

Как и в БНФ, описание грамматики в РБНФ представляет собой набор правил, определяющих отношения между терминальными символами (терминалами) и нетерминальными символами (нетерминалами).

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

Правила

Правило в РБНФ имеет вид:

идентификатор = выражение.

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

Семантика правила РБНФ — нетерминальный символ, заданный идентификатором слева от знака «равно», представляет собой определяемую выражением комбинацию терминальных и нетерминальных символов.

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

Выражения

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

Конкатенация. Определяется символом "," (запятая). Правило вида A = B,C. обозначает, что нетерминал A состоит из двух символов — B и C. Элементы конкатенации называют ещё синтаксическими факторами, или просто факторами. В данном примере B и C — синтаксические факторы.
Выбор. Обозначается вертикальной чертой. Правило вида A = B|C|D. обозначает, что нетерминал A может состоять либо из B, либо из C, либо из D. Элементы выбора называют ещё синтаксическими термами, или просто термами. В данном примере B, C, D — синтаксические термы.
Условное вхождение. Квадратные скобки выделяют необязательный элемент выражения, который может присутствовать, а может и отсутствовать. Правило вида A = [B]. обозначает, что нетерминал A либо является пустым, либо состоит из символа B.
Повторение. Фигурные скобки обозначают конкатенацию любого числа (включая нуль) записанных в ней элементов. Правило вида A = {B}. обозначает, что A — либо пустой, либо представляет собой конкатенацию любого числа символов B (то есть A — это либо пустой элемент, либо B, либо BB, либо BBB и так далее). Если требуется, чтобы A представлял собой либо B, либо произвольное число B, но не мог быть пустым, используется запись A = B{B}.
Помимо основных операций, в РБНФ могут использоваться обычные круглые скобки. Они применяются для группировки элементов при формировании сложных выражений. Например, правило A = (B|C)(D|E). обозначает, что A состоит из двух символов, первым из которых является либо B, либо C, вторым — либо D, либо E, то есть A может быть одной из цепочек BD, BE, CD, CE.
не общепринято! Также иногда имеет смысл использовать отрицание. Например, A = (B|D)!C означает, что A может быть B или D, но не BC или DC. Такой вариант позволяет четко отличить A от G = (B|D)C и упростить процедуру разбора.
не общепринято! Определение цифры включает в себя 10 символов — от '0' до '9'. Вполне логично описать понятие «цифра» перечислением: Digit = '0' | '1' | '2' | ... | '9' . Также можно определить понятие «символ».

Или все вышеуказанное вкратце:

лексема «::=» её описание (или «=»)
'…' — текстовый элемент — символ или группа символов
A, B — элемент A, за которым следует элемент B (конкатенация)
A | B — либо элемент A либо B (выбор)
[A] — элемент A входит или не входит (условное вхождение)
{A} — ноль или более элементов A (повторение)
(A B) — группировка элементов

Варианты синтаксиса

В некоторых работах встречаются модифицированные варианты синтаксиса РБНФ.

Можно встретить использование в правилах символа « ::= » вместо « = » (по аналогии с БНФ).
Иногда конкатенация в выражениях обозначается не простым следованием символов друг за другом, а с помощью запятой. В таком случае несколько слов, написанных через пробелы, следует понимать как одно многословное имя нетерминального символа. Например:

  Условный оператор = "IF", Логическое выражение, "THEN",  
  Группа операторов,  
  {"ELSIF", Логическое выражение, "THEN", Группа операторов}, 
  ["ELSE", Группа операторов], 
  "ENDIF"

— правило, задающее грамматику условного оператора языка Modula-2 , где «Условный оператор» и «Группа операторов» — нетерминальные символы с составными именами.

Стандарт BSI. Принятый в 1981 году Британским институтом стандартов (BSI) стандарт на EBNF отличается от варианта, предложенного Виртом, следующими особенностями:
- конкатенация обозначается запятой;
- конец определения правила обозначается точкой с запятой;
- пробелы в правиле, за исключением заключённых в кавычки, считаются незначимыми.

Примеры конструкций

Формальное самоопределение РБНФ

Общую форму грамматики РБНФ-описания можно описать в виде РБНФ следующим образом:

  Синтаксис     = { СинтОператор }.
  СинтОператор  = идентификатор "=" СинтВыражение ".".
  СинтВыражение = СинТерм {"|" СинТерм}.
  СинТерм       = СинтФактор { СинтФактор }.
  СинтФактор    = идентификатор | цепочка 
                | "(" СинтВыражение ")" | "[" СинтВыражение "]" 
                | "{" СинтВыражение "}".

В данном описании предполагается, что идентификатор и цепочка — предопределённые термы. При желании нетрудно записать и их определение в РБНФ, для этого потребуется лишь задать определённый алфавит и, если это необходимо, дополнительные ограничения на вид идентификатора.

Число и идентификатор в РБНФ

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

Число = ["+"|"-"]НатЧисло["."[НатЧисло]][("e"|"E")["+"|"-"]НатЧисло].
НатЧисло = Цифра{Цифра}.
Цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

Идент = Буква{Буква|Цифра|"_"}.

Определение нетерминала Буква здесь не приведено ввиду очевидности и громоздкости — он представляет собой выбор из принятого алфавита.

РБНФ и другие способы описания формальных грамматик

РБНФ и БНФ

Сходства и различия между БНФ и РБНФ очевидны из описания. Отличие состоит, по большому счёту, в двух основных моментах:

В РБНФ упрощён синтаксис записи правил: знак определения « ::= » заменён на « = » и упразднено использование угловых скобок для выделения нетерминалов. В результате исчезла возможность называть нетерминалы многословными идентификаторами, зато запись стала короче. В модификации синтаксиса РБНФ, в которой конкатенация обозначается запятой, многословные идентификаторы использовать можно.
В РБНФ введены два новых синтаксических элемента: условное вхождение (выражение в квадратных скобках) и повторение (выражение в фигурных скобках).

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

Главное преимущество РБНФ перед БНФ — возможность описывать простые повторяющиеся конструкции неопределённой длины (списки, строки, последовательности и так далее) без рекурсивных правил. Отсутствие в БНФ конструкции повторения приводит к тому, что любое повторение приходится определять путём введения дополнительных промежуточных нетерминальных символов и рекурсивных правил, из-за чего определение становится чрезмерно большим по объёму и малопонятным. Описание повторений в РБНФ оказывается одновременно и короче, и удобнее для восприятия человеком.

В качестве примера можно рассмотреть правила, определяющие нетерминал «список», представляющий собой набор от нуля до любого числа идентификаторов, перечисленных через запятую (предполагается, что символы «ПраваяСкобка», «ЛеваяСкобка», «Запятая» и «Идент» уже определены).

Определение в РБНФ включает всего одно правило:

  Список = ЛеваяСкобка [Идент {Запятая Идент}] ПраваяСкобка.

Определение в БНФ выглядит так:

  <Список> ::= <ЛеваяСкобка> <ПраваяСкобка> | <ЛеваяСкобка> <ИдентСпис> <ПраваяСкобка> 
  <ИдентСпис> ::= <Идент> | <Идент> <Запятая> <ИдентСпис>

Уже из этого примера видны отличия форм:

В БНФ в правиле, определяющем Список, присутствует два варианта — для пустого списка и для любого другого. В РБНФ за счёт конструкции условного вхождения необходимость в явном описании двух вариантов исчезла.
В БНФ потребовалось ввести искусственное рекурсивное правило ИдентСпис, чтобы описать последовательность идентификаторов, разделённых запятыми. В РБНФ за счёт конструкции повторения данный фрагмент синтаксиса записан прямо в основном правиле, причём в более простом виде.
Поскольку РБНФ-правило одно, его длина меньше и оно не содержит вариантов и рекурсии, его гораздо легче понять. Чтобы восстановить форму списка по приведённым описаниям, в случае РБНФ-описания достаточно последовательно записать значения символов, а для БНФ-описания придётся определить порядок применения правил и построить списки для каждого варианта (а их по два в каждом правиле).

Естественно, что платой за преимущества РБНФ перед БНФ является бо́льшая сложность автоматической интерпретации РБНФ-описаний. Генераторы программ синтаксического разбора по формальным описаниям грамматики, использующие БНФ, проще тех, которые используют РБНФ.

РБНФ и синтаксические диаграммы

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

Применение, достоинства и недостатки РБНФ

РБНФ, как и её предшественница — БНФ, — чрезвычайно широко применяется как средство описания искусственных языков, прежде всего — языков программирования и родственных им систем обозначений. В частности, изобретатель РБНФ, Никлаус Вирт, использовал этот формализм в своих книгах для описания всех рассматриваемых там языков программирования.

Более высокая сложность РБНФ по сравнению с БНФ приводит к тому, что генераторов программ грамматического разбора, работающих на основе РБНФ, существенно меньше, чем тех, что основаны на БНФ. Тем не менее, они существуют и применяются. РБНФ является основой для генераторов программ грамматического анализа Spirit C++ Parser Framework, Coco/R, The SLK Parser Generator, а также ряда других. Для применения в таких системах синтаксис РБНФ расширяется в том же направлении, что синтаксис БНФ при использовании парсер-генераторов yacc или bison — в описание грамматики напрямую вставляется обрабатывающий её код, так или иначе организуется взаимодействие с лексическим анализатором. Могут накладываться дополнительные ограничения и на структуру правил — не все правила, которые можно описать на РБНФ, могут быть эффективно преобразованы в код.

К безусловным достоинствам РБНФ можно отнести простоту (сам язык РБНФ содержит всего 10 специальных знаков — три вида скобок, вертикальную черту, знак «равно» и кавычки, возможно, ещё запятую; его синтаксис определяется пятью правилами), достаточную мощность и наглядность, что делает его удобным для выполнения описаний, предназначенных не только для автоматической интерпретации, но и для чтения людьми. Близость конструкций РБНФ к синтаксическим диаграммам позволяет рисовать последние прямо по РБНФ-описанию.

К недостаткам РБНФ, как, впрочем, и БНФ, можно отнести тот факт, что они описывают грамматическую структуру формального языка без учёта контекстных зависимостей, а значит, при наличии таких зависимостей РБНФ-описание оказывается неполным, и некоторые правила синтаксиса описываемого языка приходится излагать в обычной текстовой форме. Это приводит к тому, что текст, точно соответствующий РБНФ-грамматике, может, тем не менее, оказаться синтаксически некорректным. Например, в РБНФ-грамматике невозможно естественным образом отобразить тот факт, что некоторая операция требует операндов одного и того же типа. Подобные проверки приходится проводить уже написанным вручную кодом грамматического анализатора. С другой стороны, системы описания грамматики, включающие определение контекстных зависимостей, например, грамматика ван Вейнгаардена , оказываются существенно сложнее, и использование их для автоматической генерации парсеров оказывается затруднительным.

Примечания

(англ.) . ISO / IEC (15 декабря 1996). Дата обращения: 20 февраля 2015. 11 марта 2007 года.

Ссылки

(англ.) . . University of Cambridge (15 декабря 1996). Дата обращения: 20 февраля 2015.
Андрей Бушман. . Локализация ISO/IEC 14977:1996(E) (Extended BNF) . Группы Google (21 июля 2013). Дата обращения: 20 февраля 2015.