Подразделы

Другие разделы

Дата и время

18/08/2022 15:37:04

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

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

printСпособы описания синтаксиса

Для формального описания структуры входных данных, синтаксиса языков программирования используют несколько способов. Наиболее подходящими для компьютерной обработки являются синтаксические правила в форме Бэкуса-Наура (БНФ), которая применялась при описании языка Алгол. Аналогично 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 } ], ")" ;
Способ перевода из РБНФ в БНФ показан в таблице.
КонструкцияРБНФБНФ
Группировкаrule = part1, (part21 | part22), part3; <rule> ::= <part1> <grp_part2> <part3>
<grp_part2> ::= <part21> | <part22>
Опциональная частьrule = part1, [ part2 ], part3; <rule> ::= <part1> <opt_part2> <part3>
<opt_part2> ::= | <part2>
Повтор 0 или более разrule = part1, { part2 }, part3; <rule> ::= <part1> <rep0_part2> <part3>
<rep0_part2> ::= | <rep0_part2> <part2>
Повтор 1 или более разrule = part1, { part2 }-, part3; <rule> ::= <part1> <rep1_part2> <part3>
<rep1_part2> ::= <part2> | <rep1_part2> <part2>
Повтор `n` разrule = part1, 3*part2, part3; <rule> ::= <part1> <part2> <part2> <part2> <part3>
Очень наглядны описания синтаксиса в графической форме, использованные Виртом для языков Паскаль и Модула, но они не слишком удобны для ввода и обработки компьютером:
38288.png
loading