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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Описание[править | править вики-текст]

Терминалы и нетерминалы[править | править вики-текст]

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

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

Правила[править | править вики-текст]

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

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

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

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

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

Выражения[править | править вики-текст]

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

  • Конкатенация. Определяется символом "," (запятая). Правило вида 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".

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

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

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

РБНФ и БНФ[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

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

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

РБНФ и синтаксические диаграммы[править | править вики-текст]

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

Применение, достоинства и недостатки РБНФ[править | править вики-текст]

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

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

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

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

Примечания[править | править вики-текст]

  1. ISO/IEC 14977 (англ.). ISO/IEC (15 December 1996). Проверено 20 февраля 2015.
  2. Это сделано в английской версии этой статьи.

Ссылки[править | править вики-текст]