[ Государственное образовательное учреждение
высшего профессионального образования
Сургутский государственный университет
Ханты-Мансийского автономного округа – Югры
Факультет автоматики и телекоммуникаций
Кафедра автоматики и компьютерных систем
Гришмановский Павел Валерьевич,
кандидат технических наук, доцент
Теория языков программирования
и методы трансляции
Учебно-методическое пособие Сургут, 2010 Теория языков программирования и методы трансляции Содержание Введение
Тематический план дисциплины
Лабораторная работа № 1 Создание простейшего распознавателя
Лабораторная работа № 2 Распознаватель числовых констант
Лабораторная работа № 3 Алгоритм рекурсивного спуска
Лабораторная работа № 4 Генерация промежуточного кода
Лабораторная работа № 5 Оптимизация промежуточного кода
Список рекомендуемой литературы
© Кафедра АиКС, СурГУ, Теория языков программирования и методы трансляции Введение Целью изучения дисциплины «Теория языков программирования и методы трансляции» является формирование у студентов систематизированных знаний в области построения трансляторов языков высокого уровня и организации вычислительного процесса средствами вычислительной техники.
Задачи преподавания дисциплины:
– студент должен знать основные этапы процесса трансляции, способы задания и описания искусственных языков;
– студент должен иметь представление об основных методах и подходах решения задач, связанных с конкретными шагами принципиальной схемы трансляции, об основных классах языков и о допустимых преобразованиях, совершаемых над грамматиками языков;
– студент должен приобрести навыки по изучению конструкций искусственного языка и применению оптимальных методов для решения поставленной задачи.
Освоение дисциплины заключается в изучении теоретического материала в соответствии с планом, представленным в настоящем учебно-методическом пособии. При этом может использоваться литература, указанная в списке рекомендуемых источников.
Практическое освоение ряда разделов дисциплины осуществляется в результате выполнения комплекса лабораторных работ (лабораторного практикума).
Лабораторный практикум по дисциплине «Теория языков программирования и методы трансляции» направлен на изучение и практическое освоение основных алгоритмов грамматического разбора, методов их программной реализации и построения элементов трансляторов программ. Для выполнения каждой лабораторной работы необходимо изучение соответствующего раздела теоретической части курса.
Программную реализацию распознавателей и трансляторов, их отладку и тестирование необходимо выполнять с учетом всех методических рекомендаций, приведенных в описании каждой лабораторной работы. Для программной реализации может быть использована любая распространенная среда программирования. Для обеспечения возможности проверки результатов работы преподавателем, рекомендуется выполнять реализацию на языках C/C++ с использованием только стандартных библиотек и текстового интерфейса (тип приложения – консольное), что обеспечит хорошую переносимость на уровне исходного кода.
Так как программы, создаваемые в ходе выполнения лабораторных работ, выполняют преимущественно преобразование входного текста в выходной, рекомендуется имена входного и выходного файлов передавать в качестве параметров командной строки.
По каждой лабораторной работе оформляется отчет, который должен содержать следующие элементы:
1. Титульный лист.
2. Цель работы.
3. Задание на лабораторную работу.
4. Основная часть:
– формализованное описание решения задачи;
– другая информация (в соответствии с методическими рекомендациями по каждой лабораторной работе);
– описание принципов программной реализации (желательна иллюстрация блоксхемами алгоритмов, схемами и диаграммами, фрагментами листинга и т.п.).
5. Выводы (в соответствии с методическими рекомендациями по каждой лабораторной работе).
К отчету для проверки преподавателем прикладывается архив в формате RAR, ZIP или 7z, содержащий:
© Кафедра АиКС, СурГУ, – исходный код (или файлы проектов) разработанного приложения (распознавателя или транслятора) с подробными комментариями;
– входные файлы, использовавшиеся для тестирования, и соответствующие им выходные файлы;
– файл readme.txt с указанием среды разработки и, при необходимости, существенных особенностей настройки среды разработки, размещения файлов, компиляции и сборки проектов, использования параметров командной строки приложения и т.п.
© Кафедра АиКС, СурГУ, Тема 1. Введение.
Понятие языков и трансляторов. Группы языков и парадигмы программирования.
Свойства искусственных языков. Аспекты стандартизации языков программирования.
Понятие транслятора. Виды трансляторов. Структура транслятора и этапы трансляции. Методы трансляции. Интерпретация и компиляция.
Тема 2. Формальные языки и грамматики.
Формальный язык. Способы задания языка. Понятие формальной грамматики.
Способы задания грамматик.
Бэкусова нормальная форма (Нормальная форма Бэкуса–Наура). Грамматики Хомского. Иерархия грамматик Хомского и абстрактные машины.
Вывод и грамматический разбор. Стратегии синтаксического анализа. СУ-схемы.
Транслирующие грамматики. Атрибутные транслирующие грамматики.
Тема 3. Трансляция на основе польской инверсной записи.
Определение польской инверсной записи. Алгоритм трансляции выражений.
Алгоритм Дейкстры формирования польской инверсной записи. Трансляция выражений, содержащих переменные с индексом.
Трансляция операторов на основе польской инверсной записи. Оператор присваивания. Динамические деревья. Трансляция условных операторов.
Тема 4. Регулярные грамматики, языки и их свойства.
Преобразование контекстно-свободных и регулярных грамматик в автоматные.
Диаграмма состояния автоматной грамматики. Конечный автомат-распознаватель автоматных языков. Построение конечного автомата по автоматной грамматике.
Лексический анализ. Сканер. Блок лексического анализа.
Тема 5. Контекстно-свободные грамматики.
Типы контекстно-свободных грамматик. Редуцированные и приведенные грамматики. Допустимые преобразования. Устранение левой рекурсии, факторизация, удаление несущественных символов. Условия порождения бесконечных языков.
Распознаватель для контекстно-свободных языков. Нормальные формы Хомского и Грейбах.
Тема 6. Нисходящие стратегии синтаксического анализа.
Нисходящий распознаватель. Неформальное описание нисходящего анализа.
Алгоритм нисходящего анализа.
Тема 7. Методы детерминированного синтаксического анализа на основе восходящей стратегии.
Восходящий распознаватель. Неформальное описание восходящего анализа.
Алгоритм восходящего анализа. Отношения предшествования. Грамматики предшествования. Распознаватель для грамматик предшествования.
Построение отношений предшествования. Матрица предшествования. Построение функций предшествования с помощью алгоритма Флойда. Построение функций предшествования с помощью графа линеаризации. Метод простого предшествования.
Тема 8. LR(k)- и LL(k)-грамматики.
Особенности LR(k)- и LL(k)-грамматик и распознавателей. Правила подстановок Флойда-Эванса. Методы детерминированного синтаксического анализа на основе нисходящей стратегии. K-предсказывающий алгоритм разбора.
Тема 9. Контекстный анализ.
Атрибутная индукция. Генерация. Основные задачи процесса генерации.
Оптимизация.
© Кафедра АиКС, СурГУ, Активировать имеющиеся навыки программирования, приобрести навыки автоматного программирования, получить практический опыт построения простейших распознавателей (лексических анализаторов).
Содержание работы Построение распознавателя комментариев языков C и C++ с использованием автоматной модели.
Построить детерминированный конечный автомат распознавателя многострочных комментариев языка C и выполнить его программную реализацию.
Усовершенствовать распознаватель для корректного удаления комментариев языков C (многострочных) и C++ (однострочных).
Методические рекомендации к заданию В соответствии с п.1 Задания, распознаватель должен, проведя лексический анализ входного файла, содержащего текст программы на языке C, сформировать выходной (новый) файл, содержащий тот же текст, но с удаленными из него комментариями вида /*...*/. Рассматриваются только комментарии языка C и не производится анализ какихлибо иных лексем. Следует учесть, что такие комментарии не могут быть вложенными.
Конечный автомат распознавателя проще всего представить в виде традиционного графа (диаграммы) состояний, в котором состояния представлены узлами, а переходы – дугами. Условием перехода из одного состояния в другое (событием, входным сигналом) является значение одного очередного символа, считанного из входного потока. При любом переходе из одного состояния в другое может производиться запись в выходной поток как последнего считанного символа, так и произвольного символа или любой цепочки символов. Таким образом, каждая дуга в графе должна быть маркирована и входным символом a, и выходной цепочкой символов, т.е. записью вида «a / ». При этом для компактной и наглядной записи выражений допускается:
– указывать допустимые символы входной цепочки в виде множества, например, запись «{a, b, c, 0..9} / …» будет означать принадлежность считанного символа указанному множеству, т.е. его равенство одному из элементов этого множества;
– использовать некоторое обозначение или метасимвол для входного символа в записи условия, например, запись «c {0..9} / …» будет означать, что считанный символ не является десятичной цифрой (является любым другим возможным символом);
– использовать некоторое обозначение для особых (типичных) ситуаций, например «else», «default» и т.п. для обозначения всех остальных случаев, т.е. образованных исключением из алфавита языка (полного множества возможных входных символов) всех тех символов, которые указаны в условиях перехода всех остальных дуг, исходящих из этого же состояния;
– использовать квантор, если переход осуществляется при чтении любого возможного символа (немаркированная дуга означает безусловный переход из одного состояния в другое, при котором чтение очередного символа не производится);
– использовать некоторое обозначение или метасимвол для обозначения конца входной цепочки (при реализации программы – конца файла), например «EOF», «» и т.п.;
© Кафедра АиКС, СурГУ, – использовать некоторое обозначение или метасимвол для обозначения множества пустых символов – символов-разделителей, – таких как пробел, перевод строки, возврат каретки, табуляция и т.п., например «B», «blank», « » и т.п.;
– не указывать выходную цепочку вместе с символом «/» или указывать «… / », если при данном переходе ничего не выводится в выходной поток;
– использовать некоторое обозначение для входного символа при его выводе в выходной поток, например: «c {0..9} / c» – символы входного потока, являющиеся цифрами, дублируются в выходной поток; «c / c» – дублирование любого считанного символа в выходной поток.
Для построения распознавателя необходим детерминированный и полностью определенный конечный автомат. Это означает, что в каждом состоянии для каждого возможного входного символа должен быть определен ровно один переход. Конечный автомат распознавателя будет являться недетерминированным, если хотя бы в одном состоянии некоторый считанный символ приводит к одновременному выбору двух или более направлений перехода, что невозможно реализовать без использования параллельных процессов, рекурсии и/или последующего обратного движения по входной цепочке (возврата). Конечный автомат распознавателя будет являться определенным не полностью или недоопределенным, если хотя бы в одном состоянии существует хотя бы один входной символ из множества возможных, для которого не задан переход, что приведет к неразрешимой ситуации при реализации распознавателя. По этой причине необходимо ввести конец файла как входной символ.
После реализации простейшего лексического анализатора в соответствии с п. Задания необходимо оценить его адекватность. При выполнении п.2 Задания в первую очередь следует уточнить диаграмму состояний распознавателя для многострочных и однострочных комментариев. При этом необходимо учесть все особенности комментариев и некоторых других лексем языка C++, в частности:
– многострочные комментарии не могут быть вложенными;
– многострочный комментарий может использоваться вместо символа-разделителя и его удаление не должно приводить к «склеиванию» лексем и их неправильной интерпретации транслятором;
– окончанию «*/» многострочного комментария может предшествовать символ «*» в любом количестве;
– комментарии не могут являться частью строковой или символьной константы (начинаться или заканчиваться внутри нее – комментарии не должны распознаваться внутри строковых и символьных констант, а строковые и символьные константы не должны распознаваться внутри комментариев);
– строковые и символьные константы могут включать в себя как символы одинарную и двойную кавычки в виде последовательностей «\'» и «\"», которые не являются завершением записи константы, а также любые управляющие последовательности, запись которых начинается с символа «\»);
– строковая константа может занимать несколько строк в исходном тексте программы;
– любой из символов перевода строки или возврата каретки («\r» или «\n») завершают однострочный комментарий, при этом они являются равнозначными и сохраняются в выходной поток.
Общий вид автомата, соответствующего этим требованиям, будет следующим (конечное состояние, соответствующее концу входного потока, и ведущие в него дуги не изображены):
© Кафедра АиКС, СурГУ, На данной диаграмме видно, что переход между состояниями, которые находятся в частях автомата, соответствующих распознаванию комментариев, строковых и символьных констант, невозможен, т.е. эти конструкции не могут перекрываться или быть вложенными друг в друга.
При реализации необходимо обеспечить корректное завершение программы (запись символов, закрытие файлов и т.п.) при обнаружении конца входного файла в любом состоянии автомата.
Фрагмент возможной реализации (упрощенный) лексического анализатора на языке С с использованием стандартных библиотек показан ниже.
typedef enum States { Normal, Slash, Comment,... } States;
int main(int argc, char ** argv) FILE * fi, * fo; /* входной и выходной файл */ States State = Normal; /* текущее состояние */ fi = fopen(argv[1], "rb");
if (!fi) fprintf(stderr, "Input file \"%s\" open error.\n", argv[1]);
fo = fopen(argv[2], "wb");
if (!fo) fclose(fi);
fprintf(stderr, "Output file \"%s\" open error.\n", argv[2]);
while ((c=fgetc(fi)) != EOF) /* считываем символ и проверяем, */ switch (State) /* обрабатываем считанный символ в */ State = Slash; /* то перешли в соответствующее состояние */ else if (с ==...) /* если еще что-то, то аналогично */ © Кафедра АиКС, СурГУ,... /* и т.д. обрабатываем все состояния автомата */ fclose(fi); /* не забывайте закрывать файлы! */ fclose(fo); /* особенно выходной, т.к. он был открыт для записи */ return 0;
В отчете по лабораторной работе должны быть полностью отражены оба варианта распознавателя (по каждому пункту задания). Основная часть должна содержать графы состояний разработанных конечных автоматов и протоколы работы лексических анализаторов. В выводах по работе необходимо привести оценку адекватности разработанных лексических анализаторов.
© Кафедра АиКС, СурГУ, Получить практический опыт использования нормальной формы Бэкуса-Наура для формального описания регулярных языков и построения лексических анализаторов на основе порождающих грамматик, закрепить навыки автоматного программирования.
Содержание работы Построение распознавателя числовых констант языков C и C++ с использованием нормальной формы Бэкуса–Наура и детерминированных конечных автоматов, используя в качестве основы распознаватель комментариев, созданный в лабораторной работе № 1.
Определить грамматику, порождающую цепочки, соответствующие записи числовых констант языков C/C++, используя нормальную форму Бэкуса–Наура.
Построить конечный автомат лексического анализатора этих цепочек.
Реализовать синтаксический анализатор на основе разработанного конечного автомата.
Методические рекомендации В первую очередь необходимо формализовать предметную область с использованием естественного языка, т.е. определить множество типов данных в соответствии с вариантом индивидуального задания и возможные способы записи констант этих типов. При этом можно также использовать метасимволы, регулярные выражения, синтаксические диаграммы Вирта и другие нотации для наглядного представления синтаксиса. Необходимо учесть, что могут существовать различные способы записи констант для одних и тех же значений, и возможное наличие символовмодификаторов, уточняющих тип константы. Особое внимание следует обратить на необязательные части в записи константы (например, знак числа, дробная часть, символмодификатор и др.).
В соответствии с формализованным описанием необходимо построить грамматику, порождающую заданные константы, в нормальной форме Бэкуса–Наура. Учитывая, что язык заданных лексем является регулярным, желательно также использовать регулярную (лево- или праволинейную) грамматику, или даже привести ее к виду автоматной грамматики, что упростит в дальнейшем построение конечного автомата и реализацию лексического анализатора. В записи правил грамматики можно использовать метасимвол «|» для компактной записи правых частей правил, но не допускается использование других метасимволов расширений нотации Бэкуса–Наура и регулярных выражений.
Построенная грамматика (с целью упрощения) не должна порождать комментарии, символьные константы и строковые литералы, а также числовые константы, не принадлежащие группе типов данных, заданной вариантом индивидуального задания.
В соответствии с построенной грамматикой необходимо определить конечный автомат, который должен идентифицировать успешное распознавание цепочки, ошибки распознавания и пропуск непринятых цепочек. Автомат не должен принимать числовые константы тех типов, которые не соответствуют варианту индивидуального задания – в этих случаях должна идентифицироваться ошибка распознавания или осуществляться пропуск цепочек (их игнорирование без попытки начать распознавание). Например, считав из входного потока цепочку «123.», распознаватель вещественных констант продолжит чтение и анализ символов, а распознаватель целочисленных – выдаст ошибку © Кафедра АиКС, СурГУ, (символ «точка» не может присутствовать в записи этих констант) и перейдет в некоторое исходное состояние, ожидая начала следующей подходящей цепочки во входном потоке.
Цепочка «123», если за ней следует не алфавитно-цифровой символ (например, пробел), будет принята как константа типа int и не будет принята распознавателем вещественных констант, так как лексема закончилась, но она не содержит признаков константы вещественного типа (десятичной точки или символа «e»). Цепочка «a123» будет просто проигнорирована обоими автоматами, т.к. никакая числовая константа не может начинаться с буквы (эта лексема – идентификатор) Для корректного распознавания числовых констант необходимо также распознавать комментарии, символьные константы и строковые литералы, т.к. числовые константы как лексемы не могут находиться внутри них. Допустим, автомат в лабораторной работе № распознавал цепочки некоторого языка L' – комбинация цепочек (любых допустимых и в любом порядке) языков комментариев LR, символьных констант LC и строковых литералов LS. Иными словами, L' = LR LC LS. Грамматика, построенная в данной работе, задает язык числовых констант LN и, следовательно, автомат будет являться лексическим анализатором для некоторого языка L = LN L' = LN LR LC LS.
Таким образом, в качестве основы следует взять конечный автомат из лабораторной работы № 1 и дополнить его новыми состояниями (и соответствующими переходами):
Здесь множество A содержит символы, которые могут являться первыми в записи распознаваемых констант. Начиная с этого символа и далее, в области «Распознавание числовых констант», входная цепочка должна дублироваться в выходной поток и завершаться либо типом данных константы (цепочка принята), либо сообщением об ошибке (цепочка не принята). Множество B – символы, с которых могут начинаться лексемы, внутри которых распознавание констант невозможно (например, идентификаторы и ключевые слова). Таким образом, состояние Z играет роль состояния, блокирующего распознавание констант. Автомат находится в таком состоянии, пока поступают «запрещающие» символы множества C (например, буквы, цифры и др.).
Следует отметить, что множества C и B могут отличаться. Вновь распознавание константы может начаться только после «разрешающего» символа из множества D (например, символ операции, скобка и т.п.) или разделителя (например, пробел и т.п.).
Распознаватель, реализованный в соответствии с построенным автоматом, должен в результате лексического анализа входного файла (текст программы на языках C/C++) сформировать файл отчета, содержащий все числовые константы из входного файла в том порядке, в каком они были найдены, с указанием типа этих констант. При отсутствии в записи константы модификаторов (суффиксов, уточняющих тип), полагать, что константа имеет базовый тип вне зависимости от ее значения. Если цепочка не была принята, то необходимо вывести соответствующий результат и показать символ, приведший к ошибке © Кафедра АиКС, СурГУ, распознавания. Например, отчет распознавателя целочисленных констант может иметь следующий вид:
...
Основная часть отчета по лабораторной работе должна содержать:
формализованное описание правил записи лексем на естественном языке;
запись грамматики в нотации Бэкуса–Наура;
граф состояний конечного автомата для представленной грамматики, включающий распознавание комментариев, символьных констант и строковых литералов;
– протоколы работы лексического анализатора, включая специально внесенные ошибки и случаи, не подлежащие распознаванию (запись чисел внутри строк и комментариев, цифры в идентификаторах и т.п.).
В выводах по работе необходимо привести оценку адекватности разработанного лексического анализатора, в т.ч. в тех случаях, когда невозможно однозначно определить границы лексем при помощи регулярной грамматики (т.е. задача должна решаться при помощи контекстно-свободных грамматик).
Варианты индивидуальных заданий Вариант индивидуального задания выбирается по общим правилам:
Целочисленные константы: 8-я, 10-я и 16-я системы счисления; все возможные целочисленные типы (кроме char) с учетом модификаторов (суффиксов) в записи константы, тип по умолчанию – int.
Вещественные константы (с плавающей точкой): запись в виде десятичной дроби, показательной формы и их сочетания; все возможные типы с учетом модификаторов (суффиксов) в записи константы, тип по умолчанию – double.
© Кафедра АиКС, СурГУ, Изучение LL-методов грамматического разбора для контекстно-свободных грамматик и их практическое освоение на примере метода рекурсивного спуска.
Содержание работы Построение транслятора для языка, заданного контекстно-свободной грамматикой, с использованием метода рекурсивного спуска.
1. Записать грамматику, заданную вариантом индивидуального задания, включая полные множества правил, терминальных и нетерминальных символов.
2. Выполнить преобразование записанной грамматики к виду грамматики рекурсивного спуска (при необходимости).
3. Построить транслятор (интерпретатор) программ заданного языка, реализующий алгоритм рекурсивного спуска.
Методические рекомендации Заданная грамматика G порождает язык L(G), каждая возможная цепочка которого представляет собой один оператор присваивания переменной (левый операнд) значения некоторого выражения (правый операнд), причем, при первом использовании в качестве левого операнда, переменная определяется, а при использовании ее в выражении правого операнда – должна быть определена ранее. Последовательность таких операторов, которые могут быть отделены друг от друга пустыми символами (в любом количестве, в т.ч. 0), представляет собой программу на языке L'. Таким образом, L' = ( L(G) )*, где – множество пустых (непечатаемых) символов, выполняющих роль разделителей (в данном случае – между операторами).
Тип данных, значениями которого оперирует программа на языке, порождаемом заданной грамматикой, определяется записью констант этого языка (разделы IV и VI грамматики).
Следует отметить, что правила грамматики, записанные в табл. 3.2, не предполагают наличия разделителей (пустых символов) между лексемами в одном операторе, в то время, как для большинства языков программирования это является нормой. Это сделано для упрощения записи правил грамматики. Например, запись правила SI=E; из раздела I,а табл. 3.2 с учетом наличия пустых символов будет иметь вид S1I2=3E4;, где i * и это так же, с формальной точки зрения, должно быть раскрыто при помощи правил грамматики. Очевидно, что ввод разделителей в явном виде излишне усложняет запись грамматики, поэтому их наличие должно быть учтено во время реализации интерпретатора. При выполнении лабораторной работы необходимо самостоятельно определить либо возможность, либо обязательное отсутствие таких символов, как пробел, табуляция и т.п., между терминальными и нетерминальными символами в правых частях правил разделов I и II грамматики, т.е. между отдельными лексемами внутри операторов.
Прежде, чем приступать к построению транслятора, необходимо убедиться, что грамматика, заданная в соответствии с вариантом индивидуального задания, является грамматикой рекурсивного спуска или привести ее к такому виду. Грамматикой рекурсивного спуска называется такая грамматика, в которой для любого нетерминального символа A VN существует либо единственное правило A, где © Кафедра АиКС, СурГУ, V*, либо только правила вида A a11 | a22 | … | ann, где a1,a2,…,an VT, 1,2,…,n V* причем ai aj, при i j, т.е. правые части этих правил начинаются с различных терминальных символов. Следовательно, по первому символу каждой цепочки, выводимой из некоторого нетерминального символа A, можно однозначно установить соответствующее правило, сравнивая этот символ с первыми символами правых частей правил, левые части которых представлены символом А.
Построение распознавателя для языков, заданных грамматикой рекурсивного спуска, выполняется по следующим правилам:
1. Для каждого нетерминального символа A VN строится своя процедура разбора, например ProcA, выполняющая распознавание всех цепочек, выводимых из символа A.
2. Первый символ входного потока, анализируемый каждой процедурой разбора (т.е.
первый символ строки, выводимой из соответствующего нетерминального символа), считывается до ее вызова.
3. При завершении процедуры разбора, ею должен быть считан один символ входного потока, следующий за распознанной цепочкой (т.е. выводимой из соответствующего нетерминального символа).
4. Алгоритм каждой процедуры разбора строится в соответствии с правой частью выбранного правила для соответствующего нетерминального символа:
– если очередной символ правой части правила является терминальным, то он должен быть равен текущему считанному символу входного потока (на первом шаге – производится выбор правила), иначе цепочка не принимается (выводится сообщение об ошибке); при успешном сравнении считывается следующий символ входного потока и происходит переход к анализу следующего символа правой части выбранного правила;
– если очередной символ правой части правила является нетерминальным, то вызывается соответствующая ему процедура разбора (текущий считанный символ будет первым анализируемым символом в этой процедуре – правило 2, а после завершения вызванной процедуры текущий символ уже будет считан из входного Каждая процедура, как правило, выполняет некоторые действия в соответствии с распознанной цепочкой и возвращает некоторое значение. Например, в случае интерпретации выражений, процедура распознавания константы «собирает» символы константы, вычисляет и возвращает ее значение, а процедура распознавания выражения с операцией «+» вызывает процедуры для операндов, суммирует возвращенные ими значения и возвращает полученный результат. Очевидно, что операндом может являться как константа, так и другое выражение, в т.ч. содержащее ту же операцию. Таким образом, возможна рекурсия (отсюда и название метода), но единственное ограничение – рекурсия не должна быть левой (как прямой, так и непрямой).
Расширить применение метода рекурсивного спуска можно за счет:
– приведения исходной грамматики к требуемому виду посредством выполнения левой факторизации, устранения левой рекурсии, преобразования к нормальной форме Грейбах и т.п.;
– построения конечных автоматов для распознавания лексем, записи правил в регулярных выражениях, привлечения эвристического анализа, модификации базового алгоритма процедуры разбора и др.
Контекстные зависимости, присущие заданному описанным образом языку (например, идентификаторы, которые определенные в предшествующих операторах, зарезервированные слова и т.п.) реализуются посредством семантического анализатора.
Семантический анализатор представляет собой некоторую структуру данных (таблицу идентификаторов), хранящую информацию о текущем контексте, и обслуживающих ее алгоритмов (поиск, извлечение, добавление и т.п.). Выбранный способ программной реализации таблицы идентификаторов не должен вносить существенных ограничений на © Кафедра АиКС, СурГУ, количество идентификаторов, используемых в программе, и их длину, если это не обусловлено исходной грамматикой.
Транслятор должен после интерпретации каждого оператора программы выводить его порядковый номер, имя переменной и значение, присвоенное ей в этом операторе, а после интерпретации всей программы – список всех переменных и их значений. В случае ошибки необходимо выводить развернутое сообщение о ее причинах. Ниже приведены примеры протоколов в трех случаях: успешная интерпретация, ошибка в написании идентификатора (имени переменной), обработка пустого файла:
Begin parsing.
Operator 1: a = Operator 2: k34 = Operator 3: c= Operator 4: c = Operator 5: x0 = Operator 6: a = - Operator 7: sum = End parsing.
5 variables defined:
a = - k34 = c = x0 = sum = Begin parsing.
Operator 1: a = Operator 2:
Error 107: Identifier missing.
Abort parsing.
Begin parsing.
End parsing.
No variables defined.
Основная часть отчета по лабораторной работе должна содержать:
– запись исходной грамматики (по табл. 3.1 и 3.2) в нотации Бэкуса–Наура;
– описание языка, порождаемого заданной грамматикой (на естественном языке с примерами порождаемых конструкций);
– вывод о том, принадлежит или нет заданная грамматика классу грамматик рекурсивного спуска;
– описание преобразований грамматики (в случае необходимости) и полученную в результате грамматику рекурсивного спуска;
– описание алгоритмов процедур разбора (по одной для каждого раздела грамматики);
– протоколы работы лексического анализатора, включая как интерпретацию правильных программ языка, так и случаи идентификации специально внесенных ошибок.
Варианты индивидуальных заданий В соответствии с номером варианта индивидуального задания (от 1 до 20) из табл. 3.1 выбираются варианты 6-ти разделов грамматики G(VT, VN, P, S). Затем, в соответствии с вариантами разделов, из табл. 3.2 выписываются правила, образующие полное множество правил P грамматики. На основе полученного множества правил P строится алфавит грамматики V = VN VT. Нетерминальный символ S является целевым (начальным) во всех полученных грамматиках.
© Кафедра АиКС, СурГУ, Соответствие вариантов разделов грамматики варианту индивидуального задания Вариант Варианты разделов грамматики Вариант Варианты разделов грамматики
«