Конструирование транслятора для модельного языка
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.
Метод рекурсивного спуска
Метод рекурсивного спуска применим в том случае, если каждое правило грамматики имеет вид:
a)либо , где и это единственное правило вывода для этого нетерминала, где V- множество терминалов, N- множество нетерминалов;)либо , где для всех ; для ; , т. е. если для нетерминала правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть различными. Ясно, что если правила вывода имеют такой вид, то рекурсивный спуск может быть реализован по вышеизложенной схеме.
Естественно, возникает вопрос: если грамматика не удовлетворяет этим условиям, то существует ли эквивалентная КС-грамматика, для которой метод рекурсивного спуска применим? К сожалению, нет алгоритма, отвечающего на поставленный вопрос, т.е. это алгоритмически неразрешимая проблема.
Изложенные выше ограничения являются достаточными, но не необходимыми.
Попытаемся ослабить требования на вид правил грамматики:
1)при описании синтаксиса языков программирования часто встречаются правила, описывающие последовательность однотипных конструкций, отделенных друг от друга каким-либо знаком-разделителем (например, список идентификаторов при описании переменных, список параметров при вызове процедур и функций и т.п.).
Общий вид этих правил:
(либо в сокращенной форме ) Формально здесь не выполняются условия применимости метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Если принять решение, что в таких случаях будем выбирать самую длинную подцепочку (что и требуется при разборе реальных языков), то разбор становится детерминированным.
Тогда для метода рекурсивного спуска процедура будет такой:
Procedure L;
Begin if CH<>`a` then ER else ( CH=`,`) do L;
2)если грамматика не удовлетворяет требованиям применимости метода рекурсивного спуска, то можно попытаться преобразовать ее, т.е. получить эквивалентную грамматику, пригодную для анализа этим методом, например, т.е удалить левую рекурсию, провести левую факторизацию правил (см. лекцию).
3)если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, т.е. имеют вид
. . .
где ; ; , то можно заменить вхождения нетерминалов их правилами вывода в надежде, что правило нетерминала станет удовлетворять требованиям метода рекурсивного спуска:
Исходная грамматика модельного языка соответствует требованиям для реализации метода рекурсивного спуска, поэтому используя метод рекурсивного спуска, опишем некий алгоритм реализации синтаксического анализатора:
Алгоритм решения задачи
Входные данные СиА - файл лексем (построенный на этапе лексического анализа)
Выходные данные - заключение о синтаксической правильности программы или предупреждение об имеющихся ошибках. Сообщения об ошибках должны быть построены на основе правил грамматики.
Алгоритм:
1.для каждого нетерминала грамматики создаем рекурсивную процедуру. Самой первой процедурой синтаксического анализатора является процедура Рroc_P1, внутри нее расположены процедуры D2 и B, которые вызываются поочерёдно в зависимости от их расположения
2.открываем файл лексем, созданный на этапе лексического анализатора
.считываем очередную лексему с помощью процедуры Nextsymb, и рекурсивно проходим по каждой процедуре
.при несоответствии считанной лексемы терминалу выдается сообщение об ошибке
.при успешном распознавании цепочки выдается сообщение об отсутствии ошибок в синтаксисе программы
3.3 Семантический анализ
В ходе семантического анализа проверяются отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.
Рассмотрим пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:
) обработка описаний;
) анализ выражений;
) проверка правильности операторов.
В оптимизированном варианте СиА и СеА совмещены и осуществляются параллельно.
Обработка описаний
Задача обработки описаний - проверить, все ли переменные программы описаны правильно и только один раз. Эта задача решается следующим образом.
На этапе лексического анализа была создана таблица идентификаторов, обнаруженных в тексте исходной программы. На этапе семантического анализа создается множество S , в которое помещается все идентификатора описанные в объявлении переменных.
Анализ выражений
Задача анализа выражений - проверить описаны ли переменные, встречающиеся в выражениях, и соответствуют ли типы операндов друг другу и типу операции.
Эти задачи решаются следующим образом. На этапе семантического анализа создается множество S , в которое помещается все идентификаторы описанные в объявлении переменных. Если встречающийся идентификатор не находится в множестве S, то выводится сообщение об ошибке.
Проверка правильности операторов
Задачи проверки правильности операторов:
) выяснить, все ли переменные, встречающиеся в операторах, описаны;
) уста?/p>