Конструирование транслятора для модельного языка
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
µ>V1
3. Разработка алгоритма решения задачи
.1 Лексический анализатор
Лексический анализатор (ЛА) или сканер - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
Лексема (лексическая единица языка) - это структурная единица языка, которая состоит из элементарных символов языка и не содержит с своем составе других структурных единиц языка. Лексемами языков программирования являются идентификаторы, константы, ключевые слова языка, знаки операций и .т.п.
В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, разделителей и ключевых слов.
Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобно для последующей обработки.
Лексический анализатор имеет дело с такими объектами, как различного рода константы, идентификаторы, ключевые слова. Язык описания констант и идентификаторов в большинстве случаев является регулярным (автоматным), т.е. может быть описан с помощью автоматных грамматик. Распознавателями для автоматных языков являются конечные автоматы.
Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом характеристик каждой лексемы.
В процедурных языках лексемы делятся на классы:
- служебные слова;
- ограничители;
- числа;
- идентификаторы
и помещаются в таблицу лексем с соответствующими номерами.
Так, что лексема представляется парой чисел (n,k), где n - номер таблицы, k - номер лексемы в этой таблице.
Приведем один из алгоритмов реализации лексического анализатора:
Вход: таблица ограничителей, таблица служебных слов, текст транслируемой программы.
Выход: файл лексем, таблица идентификаторов, сообщение об ошибке.
Алгоритм:
1.открыть файл транслируемой программы и считать i-тую строку;
2.в исходной строке считываем символы в новую строку s до тех пор, пока не встретится пробел, либо ограничитель.
.проверяем, принадлежит ли полученная строка s таблице служебных слов, если да то к пункту 4, иначе к пункту 5.
.записываем в таблице лексем числа k1, k2, k3, где k1 - номер лексемы в таблице, где k2 - номер таблицы, k3 - номер строки в транслируемой программе.
.проверяем, является ли s идентификатором. Если да, то записываем информацию в файл лексем, согласно пункту 4, и записываем s в таблицу идентификаторов.
.если s[j] принадлежит таблице ограничителей, то проверяем, является ли следующий за ним символ ограничителем. Если да, то записываем в новую строку str символы s[j], пока они являются ограничителями. Далее сравниваем строку str с ограничителями, если находятся равные, то записываем в файл лексем согласно пункту 4. Иначе сравниваем символ s[j] с ограничителями, если находятся равные, то записываем в файл лексем согласно пункту
.4.
.если конец строки, то i:=i+1, к пункту 1.
.программа выполняется до тех пор, пока не достигнут конец файла транслируемой программы.
3.2 Синтаксический анализатор
Синтаксический анализатор (СиА) - программа, производящая синтаксический анализ на соответствие транслируемой программы правилам заданного языка.
Рассмотрим простейший пример программы на модельном языке:
Пример 1
Integer i,n;:=i+1;
Составим для примера1 цепочку вывода:
P1 D2B Integer i;B Integer D{,D};B Integer i{,B1};B Integer i,n;B Integer i,n; Begin S1 End Integer i,n; Begin D:=V1; End Integer i,n; Begin i:=V1; End Integer i,n; Begin i:=[ _ ]V; End Integer i,n; Begin i:=P{T1 P}; End Integer i,n; Begin i:=M{T1P}; End Integer i,n; Begin i:=D{T1 P}; End Integer i,n; Begin i:=i{T1 P}; End Integer i,n; Begin i:=i + P; End Integer i,n; Begin i:=i + M; End Integer i,n; Begin i:=i + K; End Integer i,n; Begin i:=i + 1; End
Построим дерево вывода для данного примера1 (рисунок 1).
Рисунок 1 - дерево разбора для примера1
Для синтаксического разбора используются КС-грамматика (контекстно-свободная грамматика).
Разбор по КС-грамматикам можно реализовать различными способами.
Одним из наиболее простых и потому одним из наиболее популярных методов нисходящего синтаксического анализа является метод рекурсивного спуска (recursive descent method) .
Метод рекурсивного спуска (РС-метод) реализует этот способ следующим образом:
-для каждого нетерминала грамматики создается своя процедура, носящая его имя;
-задача каждой такой процедуры - начиная с указанного места исходной цепочки найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибки, которая выдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор.
-Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова.
-Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочк?/p>