22) Трансляция процедур
23) Самотранслятор
Процедура трансляции может быть параметризована значением формальных параметров: синтаксисом входного языка и его семантикой, записанной в терминах выходного языка. Назначением этой процедуры является анализ и выделение конструкции входного языка. Использование только процедуры анализа ( анализатора) имеет место и в случае перевода на промежуточный язык, состоящий из последовательности структур, для которых формирование информации производится программами вне тела этой процедуры. Настройка на синтаксис входного языка при сохранении программной части процедуры трансляции определяет наименование процедуры ( и соответствующих трансляторов) как синтаксически управляемой. Если же в трансляторах эти процедуры не применяются, то они носят не очень удачное название блочные.
24) Много- и однопроходные трансляторы
Синтаксический анализ, особенно в случае неоднозначных грамматик, - хорошее приложение для логического программирования, и для Пролога в частности. (Собственно, Пролог как раз и создавался для этой цели). Правила синтаксиса можно прямо выразить как предложения логической программы, а механизм отката позволяет анализировать грамматики практически произвольного вида. Последнее не очень актуально для современных языков программирования. Их грамматики содержат существенные ограничения, позволяющие однозначно выбирать соответствующее правило грамматики на основе анализа одной лексемы. Но некоторые языки, такие как Кобол или Фортран, не говоря уж о естественных языках, требуют гораздо более глубокого анализа. Логические программы - один из наиболее гибких способов выполнения синтаксического анализа. Их главный недостаток сотсоит в том, что, если грамматика является в значительной степени неоднозначной, синтаксический анализатор оказаться чрезвычайно медленным. Но если неоднозначность ограничена малыми фрагментами данных, например предложениями естественного языка, эффективность будет вполне приемлемой.
25)Метод рекурсивного спуска (англ. Recursive descent parser) — алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов парсинга, подходящий для полностью ручной реализации.
Варианты реализации
Предсказывающий парсер
Для парсеров этого типа нужна подходящая КС-грамматика, конкретно LL(k) грамматика, позволяющая по очередному токену или токенам однозначно выбрать (предсказать) один из альтернативных вариантов раскрытия каждого нетерминала.
Такой парсер работает за линейное время.
Вариантом является LL-парсер — реализация предсказывающего парсера с автоматическим построением «таблицы предсказания», определяющей по заданному нетерминалу и очередному токену подходящее правило для раскрытия нетерминала.
Парсер с возвратом
Вместо предсказания парсер просто пытается применить все альтернативные варианты правил по порядку, пока одна из попыток не увенчается успехом.
Такой парсер может потребовать экспоненциального времени работы, и не всегда гарантирует завершение, в зависимости от грамматики. Уязвим для левой рекурсии.