Предисловие переводчика
В статье Заметки о рекурсии 3 я упомянул о БНФ и РБНФ, а также об их значении для описания синтаксиса формальных языков. К сожалению, ограниченный объем статьи не позволил углубиться в эту тему, поэтому она была освещена весьма поверхностно.
После выхода статьи я начал получать письма с просьбами ответить на ряд вопросов, касающихся некоторых деталей данных нотаций. По возможности я стараюсь на них отвечать, но, во-первых, не всегда на подготовку продуманного ответа хватает времени, во-вторых, ответ на поставленный вопрос видит лишь автор вопроса и никто более, тогда как он мог бы быть интересен более широкой аудитории.
Учитывая чрезвычайную важность владения БНФ и РБНФ для профессионального программиста, я решил вернуться к этому вопросу снова.
Сейчас на ваш суд представляю перевод статьи BNF and EBNF: What are they and how do they work?, автор Lars Marius Garshol (сайт автора http://www.garshol.priv.no).
В упомянутой выше статье я использовал диалект РБНФ, широко используемый Н. Виртом в его работах (и по этой причине наиболее мне знакомый, поскольку мой научный руководитель придерживался школы Вирта). В данной статье описан другой диалект, на мой взгляд, не менее интересный и выразительный.
БНФ и РБНФ: что это такое и как это работает?
Введение
Что это такое?
Это - краткая статья, в которой я пытаюсь пояснить, что же такое БНФ, на основе сообщения
[email protected], отправленного в конференцию comp.text.sgml 16 июня 1998. Она представляет собой черновой набросок, поэтому, если вы получили ответы не на все интересующие вопросы, напишите мне, и я постараюсь объяснить, как смогу.
С тех пор она была существенно дополнена и изрядно прибавила в объеме. Впрочем, не тревожьтесь. По мере чтения статья становится все более детальной, поэтому, если вы не намереваетесь закапываться в эту тему глубоко, просто прервите чтение в момент, когда на все интересующие вас вопросы получен ответ и уже начинает становиться скучно.
Что такое БНФ?
Нотация Бэкуса-Наура (больше известная как БНФ или Форма Бэкуса-Наура) - формальный математический прием для описания языка, разработанный Джоном Бэкусом (а также, возможно, Питером Науром) для описания синтаксиса языка программирования Algol 60.
(Легенда гласит, что она была вначале разработана Джоном Бэкусом на основе более ранних работ математика Эмиля Поста, а затем заимствована и несколько улучшена Питером Науром для Algol 60, что принесло ей широкую известность. Поэтому Наур называет БНФ Нормальной Формой Бэкуса, тогда как все остальные называют ее Формой Бэкуса-Наура).
Она используется для формального определения грамматики языка таким образом, что не остается разногласий или неоднозначности касательно того, что является допустимым, а что нет. На самом деле БНФ настолько однозначна, что вокруг подобных грамматик было построено немало математических теорий, и в действительности можно механически построить парсер (модуль синтаксического разбора - прим. пер.) для языка, задав для него грамматику в виде БНФ. (Существуют некоторые виды грамматик, для которых это невозможно, однако обычно их можно вручную преобразовать к пригодному для этого виду).
Программы, которые делают это, обычно называются "компиляторами компиляторов". Наиболее известен среди них YACC, однако есть и немало других.
Как это работает
Основы
БНФ несколько напоминает математическую игру: вы начинаете с символа (называемого начальным символом и по соглашению обычно обозначаемого в примерах S), а затем вы получаете набор правил, указывающих, чем вы можете заменить этот символ. Язык, определяемый грамматикой БНФ, это всего лишь набор всех строк, которые вы можете получить, следуя этим правилам.
Правила называются правилами продукции и выглядят следующим образом:
Код:
символ := альтернатива1 | альтернатива2 ...
Правило продукции просто устанавливает, что символ слева от ":=" должен быть заменен одной из альтернатив в правой части. Альтернативы разделяются знаком "|". (В одном из вариантов используется знак "::=" вместо ":=", но смысл его тот же). Альтернативы обычно состоят из символов и так называемых терминалов. Терминалы это просто фрагменты конечной строки, не являющиеся символами. Они называются терминалами, потому что для них нет правил продукции: они завершают процесс построения строк. (Символы часто называют нетерминалами).
(Примечание переводчика. В отечественной литературе по теории формальных языков обычно используется подобная, но несколько другая терминология. Терминалы также называют терминальными символами, а нетерминалы нетерминальными символами. Таким образом, и те, и другие являются символами данной грамматики).
Еще одна вариация грамматики БНФ заключает терминалы в кавычки, чтобы отличать их от символов. Некоторые грамматики БНФ явно указывают, где допустимы пробелы, зарезервировав для этого специальный символ, тогда как другие грамматики предоставляют догадываться об этом самому читателю.
В БНФ имеется специальный символ "@", который означает, что символ может быть удален. Если вы заменяете символ на "@", вы просто удаляете символ. Это полезно, поскольку иногда трудно завершить процесс замещения, не используя этот трюк.
Таким образом, язык, описываемый грамматикой, представляет собой набор всех строк, которые вы можете вывести при помощи правил продукции. Если строка никоим образом не может быть выведена с использованием правил, строка не является допустимой в языке.
Реальный пример
Ниже представлена простая грамматика БНФ:
Код:
S := '-' FN | FN
FN := DL | DL '.' DL
DL := D | D DL
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Все символы здесь сокращения: S - начальный символ (start symbol), FN - число с дробной частью (fractional number), DL - список цифр (digit list), D - цифра (digit).
Допустимые предложения языка, описываемого данной грамматикой, - это все числа, возможно, дробные, возможно, отрицательные. Чтобы построить число, начинаем с начального символа:
Код:
S
Затем заменяем символ S одной из его продукций. Мы решили не ставить знак "-" перед числом, так что используем простую продукцию FN и заменяем S на FN:
Код:
FN
Следующий шаг - заменить символ FN на одну из его продукций. Мы хотим получить число с дробной частью, поэтому выбираем продукцию, которая создает две цепочки десятичных цифр с точкой между ними, а затем продолжаем выбирать замену символа на одну из его продукций по одной в строке (см. пример):
Код:
DL . DL
D . DL
3 . DL
3 . D DL
3 . D D
3 . 1 D
3 . 1 4
Здесь мы вывели дробное число 3.14. Как вывести число -5, оставим в качестве упражнения читателю. Чтобы убедиться, что вы поняли изложенное, изучите грамматику настолько, чтобы понять, что строка 3..14 не может быть выведена с использованием этих правил продукции.
РБНФ: Что это такое, и зачем нам это нужно?
Для описания DL мне пришлось использовать рекурсию (DL может произвести новые DL), чтобы выразить факт, что можно использовать любое количество D. Это не совсем удобно и делает БНФ не слишком удобной для чтения. Расширенная БНФ (разумеется, РБНФ) решает эту проблему добавлением трех операторов:
* ? означает, что символ (или группа символов в скобках) слева от оператора является необязательной (может встретиться 0 либо 1 раз);
* * означает, что нечто может повторяться произвольное число раз (а также может быть опущено);
* + означает, что нечто может встретиться 1 или более раз.
Пример грамматики РБНФ
С использованием РБНФ грамматика из предыдущего примера может быть записана следующим образом:
Код:
S := '-'? D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
что выглядит куда симпатичнее.
На заметку: РБНФ не мощнее, чем БНФ, в смысле языков, которые она может определить, а просто удобнее. Любая продукция РБНФ может быть преобразована в эквивалентный набор продукций БНФ.
Использование БНФ и РБНФ
Типичное применение
Большинство стандартов языков программирования используют какую-либо разновидность РБНФ для определения грамматики языка. Такой подход дает два преимущества: не может быть разногласий относительно того, что представляет собой синтаксис языка, и гораздо проще построить компилятор, поскольку парсер может быть сгенерирован автоматически компилятором компиляторов вроде YACC.
РБНФ используется также во многих других стандартах, таких как определение форматов протокола, форматов данных и языков разметки вроде XML и SGML. (HTML не определяется грамматикой, вместо этого он определен через SGML DTD, что представляет собой разновидность грамматики более высокого уровня).
Вы можете ознакомиться с собранием грамматик БНФ в BNF web club.
Как использовать формальную грамматику
Теперь вы знаете, что такое БНФ и РБНФ, для чего они используются, но, возможно не знаете, почему они столь полезны или как извлечь из них пользу.
Наиболее очевидный способ использования формальной грамматики уже был упомянут мимоходом: задав формальную грамматику для языка, вы полностью определяете его. Не может быть разногласий, что дозволено в языке, а что нет. Это весьма полезно, поскольку обычное словесное описание языка значительно многословнее и подвержено неоднозначной интерпретации.
Другое достоинство: формальные грамматики - математические конструкции и могут быть поняты компьютером. Имеется масса программ, которым можно задать не входе (Р)БНФ и автоматически получить код парсера для данной грамматики. На самом деле это самый обычный способ изготовления компилятора: использование так называемого компилятора компиляторов, который принимает грамматику на входе и производит код парсера на каком-то языке программирования.
Разумеется, компиляторы делают гораздо больше проверок, чем только проверка грамматики (например, проверку типов), и они также генерируют код. Эти аспекты не описываются грамматикой (Р)БНФ, поэтому компиляторы компиляторов обычно включают специальный синтаксис для связывания фрагментов кода (называемых действиями) с различными грамматическими конструкциями.
Наиболее известный компилятор компиляторов это YACC (Yet Another Compiler Compiler), который производит код на языке C, но существуют также и другие для C++, Java, Python и многих других языков.
Синтаксический разбор (парсинг)
Самый простой способ
Разбор сверху-вниз (LL)
Самый простой способ синтаксического разбора в соответствии с грамматикой, используемый в настоящее время, называется LL-парсингом (или разбором сверху-вниз). Он работает следующим образом: для каждой конструкции определяем, с каких нетерминалов может начинаться данная конструкция (они называются стартовым набором).
Затем при разборе мы начинаем с начального символа и сравниваем стартовые наборы различных продукций с первым элементом ввода, определяя, какая из продукций может быть использована. Разумеется, это не может быть сделано в том случае, если два или более стартовых набора для одного символа содержат один и тот же терминал. В этом случае нет возможности определить, какую продукцию выбрать, располагая первым терминалом на вводе.
LL-грамматики часто классифицируются по номерам: LL(1), LL(0) и т.д. Число в скобках указывает максимальное количество терминалов, которое вам требуется видеть одновременно, чтобы выбрать правильную продукцию в любом месте грамматики. Так, для LL(0) вам вообще не нужно просматривать терминалы, вы всегда можете выбрать правильную продукцию. Это возможно лишь в случае, если все символы имеют лишь одну продукцию, и если они имеют лишь одну продукцию, язык может включать лишь одну строку. Другими словами, грамматики LL(0) не представляют интереса.
Наиболее типичный (и полезный) класс LL-грамматик это LL(1), в которой вы всегда можете выбрать правильную продукцию, видя лишь первый терминал ввода в каждый момент времени. Для LL(2) вам необходимо видеть два символа, и т.д. Существуют грамматики, не являющиеся LL(k) для любого заданного значения k, и к сожалению, они довольно часто встречаются.
Пример LL-анализа
В качестве примера давайте проанализируем стартовый набор для грамматики, приведенной выше. Для символа D это просто: все продукции имеют одну цифру в качестве стартового набора, и стартовый набор символа D представляет все 10 цифр. Это значит, что наша грамматика в лучшем случае LL(1), т.к. в этом случае нам нужно просмотреть один терминал для выбора правильной продукции.
С DL натыкаемся на неприятность. Обе продукции начинаются с D, поэтому обе имеют один и тот же стартовый набор. Это значит, что, глядя лишь на первый терминал ввода, нельзя выбрать правильную продукцию. Впрочем, мы легко можем обойти эту проблему, применив небольшую хитрость: если второй терминал ввода не цифра, мы должны выбрать первую продукцию, а если оба они цифры, мы должны выбрать вторую. Другими словами, в лучшем случае это грамматика LL(2).
Фактически здесь я несколько упростил ситуацию. Продукция для DL сама по себе не говорит нам, какие терминалы допустимы после первого терминала в продукции D @, поскольку нам нужно знать, какие терминалы допустимы после символа DL. Этот набор терминалов называется последующим набором символа, и в нашем случае это "." и конец ввода.
Для символа FN все оказывается даже еще хуже, поскольку обе продукции имеют все цифры в качестве стартового набора. Просмотр второго терминала не помогает, поскольку нам нужно видеть первый терминал после последней цифры в списке цифр (DL), а мы не знаем, сколько в нем цифр, пока не считаем их все. И поскольку не задан предел возможного количества цифр, это не грамматика LL(k) для любого заданного k (какое бы k мы ни выбрали, все равно цифр может быть больше k).
Как это ни странно, символ S прост. Первая продукция имеет "-" в качестве стартового набора, вторая все цифры. Другими словами, когда вы начинаете разбор, вы начинаете с символа S и смотрите на ввод, чтобы решить, какой продукцией воспользоваться. Если первый терминал "-", вы знаете, что используется первая продукция. Если нет, используется вторая. (Здесь в оригинале ошибка - разумеется, вторая продукция может быть применена, лишь если на входе - одна из цифр - прим. перев.) Только продукции FN и DL вызывают проблемы.
Пример LL-преобразования
Впрочем, не стоит терять надежду. Большинство грамматик, не являющихся LL(k), могут быть довольно легко преобразованы к грамматикам LL(1). В нашем случае нам потребуется изменить два символа: FN и DL.
Проблема с FN заключается в том, что обе продукции начинаются с DL, однако вторую продолжает "." и еще один DL после первого DL. Это легко решается: заменим FN таким образом, чтобы он состоял из одной продукции, которая начинается с DL, за которой следует FP (fractional part), где FP либо пустая строка, либо ".", за которой следует DL:
Код:
FN := DL FP
FP := @ | '.' DL
Теперь у нас больше нет проблем с FN, поскольку имеется лишь одна продукция, и FP также не представляет проблем, поскольку две продукции имеют различные стартовые наборы, соответственно конец ввода и ".".
DL - более крепкий орешек, поскольку проблема состоит в рекурсии и обусловлена фактом, что нам нужен как минимум один D для получения DL. Решение - задать для DL единственную продукцию, D, за которым следует DR (digit rest). DR имеет две продукции: D DR или @. Стартовый набор первой продукции - набор всех цифр, второй - "." и конец ввода, так что проблема решена.
Вот полная LL(1)-грамматика, полученная в результате преобразования:
Код:
S := '-' FN | FN
FN := DL FP
FP := @ | '.' DL
DL := D DR
DR := D DR | @
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Немного более трудный способ
Разбор снизу-вверх (LR)
Более трудный способ синтаксического разбора известен как "редукция со сдвигом", или "разбор снизу-вверх". При этом подходе читается ввод до тех пор, пока не выяснится, что входную последовательность можно свести к символу. Возможно, это звучит сложновато, поэтому приведу пример для пояснения. Мы разберем строку 3.14 и увидим, как она может быть выведена из грамматики. Начинаем с чтения 3 из ввода:
Код:
3
а затем попробуем свести ее к символу, из которого она выведена. Это нетрудно, она выведена из символа D, которым мы заменяем 3. Затем мы замечаем, что можем вывести D из DL, и заменяем D на DL. (Грамматика неоднозначна, это значит, что мы можем свести сначала к FN, что будет неправильно. Для простоты мы опускаем здесь неверные шаги, но однозначная грамматика не позволила бы сделать неверный выбор). Затем мы считываем "." из ввода и пытаемся свести ее, но тщетно:
Код:
D
DL
DL .
Эта последовательность ни к чему не сводится, поэтому читаем очередной символ из ввода: 1. Затем сводим его к D и читаем следующую литеру 4. Она может быть сведена к D, затем к DL, затем последовательность D DL можно свести к DL:
Код:
DL .
DL . 1
DL . D
DL . D 4
DL . D D
DL . D DL
DL . DL
Взглянув на это грамматику, мы тут же замечаем, что из FN выводится эта самая последовательность "DL . DL", и выводим ее. Затем замечаем, что FN выводится из S, и сводим FN к S, завершая тем самым синтаксический разбор.
Код:
DL . DL
FN
S
Как вы уже, наверное, заметили, мы часто стоим перед выбором, произвести ли редукцию к символу немедленно или подождать, пока у нас появится больше символов, и тогда произвести редукцию. Есть более сложные разновидности этого алгоритма разбора со сдвигом-редукцией, в порядке возрастания сложности и мощности: LR(0), SLR, LALR и LR(1). LR(1) обычно требует непрактично больших таблиц разбора, поэтому алгоритм LALR используется наиболее часто, поскольку мощности SLR и LR(0) оказывается недостаточно для большинства языков программирования.
LALR и LR(1) слишком сложны, чтобы рассматривать их в этой статье, но основную идею вы поняли.
LL или LR?
На этот вопрос гораздо лучше меня уже ответил кто-то другой, поэтому я лишь полностью процитирую его сообщение в конференции:
Цитировать
Надеюсь, это не станет началом войны
Прежде всего Фрэнк, если ты читаешь это, не бей меня сильно. (Мой начальник Фрэнк ДеРемер, создатель LALR)
(Я позаимствовал эту сводку из Fischer&LeBlanc's "Crafting a Compiler")
Простота - LL
Общность - LALR
Действия - LL
Исправление ошибок - LL
Размер таблиц - LL
Скорость разбора сравнима (от меня: и зависит от инструмента)
Простота - LL впереди
Работа парсера LL гораздо проще. И если вам приходится отлаживать парсер, просмотр парсера с рекурсивным спуском (обычный способ программирования LL-парсера) гораздо проще, чем таблицы парсера LALR.
Общность - LALR впереди
Из-за простоты спецификации LALR легко побеждает. Большая разница между LL и LA(LR) состоит в том, что в LL-грамматике вы должны провести левую факторизацию правил и избавиться от левой рекурсии.
Левая факторизация необходима, поскольку LL-парсинг требует произвести выбор на основе ограниченного количества входных токенов.
Левая рекурсия проблематична, поскольку предпросмотр токена правила - это всегда предпросмотр токена того же самого правила. (Все, что содержится в множестве A, содержится в множестве A...) Это вынуждает правило рекурсивно обращаться к себе снова и снова...
Чтобы познакомиться со способами преобразования LALR-грамматик в LL-грамматики, посетите мою страницу: http://www.jguru.com/thetick/articles/lalrtoll.html
Для многих языков уже доступны LALR-грамматики, поэтому вам придется преобразовывать. Если для языка нет доступной грамматики, на мой взгляд, не столь сложно самостоятельно написать LL-грамматику. (Нужно только быть в правильном "LL" настроении, обычно для этого нужно часов 8 посмотреть Dr. Who перед тем, как усесться за написание грамматики... Если вы еще не знаете, я действительно предпочитаю LL...)
Действия - LL впереди
Для LL-парсера вы можете поместить действия где угодно, не вызывая конфликта.
Исправление ошибок - LL впереди
LL-парсеры имеют намного больше информации о контексте (поскольку они производят разбор сверху-вниз), и поэтому они могут быть намного полезнее для исправления ошибок, не говоря уже о сообщениях об ошибках.
Размеры таблиц - LL впереди
Если вы пишете таблично-управляемый LL-парсер, его таблицы будут приблизительно вдвое меньше. (Откровенно говоря, есть способы оптимизации таблиц LALR, чтобы сделать их меньше, и я считаю их убдительными...)
Скорость разбора - сравнима
От меня: и зависит от инструмента.
Scott Stanchfield, статья
[email protected] в конференции comp.lang.java.softwaretools Mon, 07 Jul 1997.
Дополнительная информация
John Aycock разработал замечательный и простой в использовании инструмент на языке Python под названием SPARK, описанный в этой очень легко читаемой статье.
Фундаментальный труд по синтаксическому разбору и компиляции 'The Dragon Book', or Compilers : Principles, Techniques, and Tools, by Aho, Sethi and Ullman. Впрочем, имейте в виду, что это довольно-таки глубокая книга, изобилующая математикой.
Бесплатная онлайн альтернатива, с виду неплохая, вот эта книга, однако не могу комментировать ее качество, поскольку сам еще не прочитал.
Frank Boumphrey написал еще одно руководство по РБНФ.
Henry Baker написал статью о парсинге на Common Lisp, который представляет простую, высокопроизводительную и весьма удобную среду для парсинга. Подход аналогичный применяемому в компиляторах компиляторов, но основывается на очень мощной системе макросов Common Lisp.
Один из вариантов синтаксиса грамматики БНФ можно найти в RFC 2234. Другой находится в стандарте ISO 14997.
Приложение
Благодарности
Приношу свои благодарности:
* Jelks Cabaniss за то, что подал мысль превратить заметку в новостях в статью, а также за очень полезную критику.
* C. M. Sperberg-McQueen за дополнительную историческую информацию относительно названия БНФ.
* Scott Stanchfield за то, что предоставил мне великолепное сравнение LALR и LL. Я запрашивал разрешения процитировать его, но, к сожалению, не получил ответа.
* James Huddleston за то, что поправил меня относительно имени Джона Бэкуса.
Last update 2003-07-21, by Lars M. Garshol.
Перевод: ©Alf, 17/10/2004