Разработка компиляторов и интерпретаторов

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

В отличии от RE синтаксические правила позволяют описывать более сложные зависимости, например, соответствие открывающихся и закрывающихся скобок:

<скобки> ::= | (<скобки>) | <скобки><скобки>

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

Затем была предложена расширенная БНФ (есть стандарт ISO/IEC 14997:1996), в которой определение нетерминального символа необходимо было заканчивать символом ;, все терминальные символы записывать в кавычках или апострофах, а последовательность символов записывать через запятую. Были добавлены метасимволы {} для повторения конструкции ноль или более раз, [] для опциональной части конструкции, () для группировки, * для повторения конструкции заданное количество раз (5*" " – 5 пробелов), - для исключения варианта, а вместо ::= предлагалось писать просто =:

digit = ?цифра от 0 до 9? ;
natural number = digit - "0", { digit } ;
integer = "0" | [ "-" ], natural number ;

РБНФ позволяет описать синтаксис языка более компактно по сравнению с БНФ. Если грамматика языка является LL(k), то можно сгенерировать программу для синтаксического разбора методом рекурсивного спуска с помощью COCO/R, JavaCC или ANTLR.

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

БНФ:
<function call> ::= <name>(<args>) | <name>()
<args> ::= <arg> | <args>, <arg>
РБНФ:
function call = name, "(", [ arg, { ",", arg } ], ")" ;

Способ перевода из РБНФ в БНФ показан в таблице.

Очень наглядны описания синтаксиса в графической форме, использованные Виртом для языков Паскаль и Модула, но они не слишком удобны для ввода и обработки компьютером: