Построение транслятора и интерпретатора языка программирования GBasic
1 Постановка задачи.
Написать программы для трансляции и интерпретации языка программирования GBasic.
2 Теоретические сведения.
Процесс создания работы включает в себя два этапа:
1) написание транслятора с получением некоторого объектного кода входной программы, написанной на языке программирования Gbasic;
2) написание интерпретатора, выполняющего программу из объектного файла.
В процессе трансляции формулировки входного языка анализи-руются и переводятся в элементы промежуточного представления, содержащие информацию, достаточную для составления выходной программы (в нашем случае - объектного файла).
Режим интерпретации характеризуется тем, что процессор, обрабатывая промежуточное представление, почти одновременно с чтением промежуточных форм выполняет соответствующие им машинные операции; при этом не вырабатывается выходной программы, подлежащей дальнейшему исполнению.
3 Транслятор.
Режим трансляции является детерминированным, с прерыванием работы при обнаружении ошибки с выдачей соответствующего сообщения.
Трансляция делится на четыре последовательных этапа:
1) Лексический анализ, на котором выделяются лексемы, составляется таблица переменных, проверяется допустимость входного алфавита;
2) Синтаксический и семантический анализ, на котором конструируется некоторый образ памяти, проверяются типы переменных и выражений, дополняется таблица переменных, подсчитывается количество выражений;
3) Преобразование встреченных во входной программе выражений в обратную польскую запись, предложенную польским математиком Яном Лукашевичем;
4) Вывод образа памяти, преобразованных выражений и таблицы переменных в объектный файл.
Чтение отдельной лексемы происходит посредством процедуры GetSym. В результате получаем новую лексему в переменной Ident : string и ее тип в переменной Symbol:TypeWords.
Множество типов лексем содержится в определении типа TypeWords, который имеет вид:
TypeWords = (TAbs, TDelete, TInkeyS, TLength, TRnd, TSqr, TStr, TVal, TBeep, TCall, TCls, TFor, TIf, TInk, TInput, TLet, TNext, TPaper, TPause, TPrint, TRandomize, TStop, TTo, TThen, TEnd, TEndIf, TLocate, TElse, TProc, TReturn, TVar_, TEndVar, SymNum, SymStr, SymVar, SymConst, Tbreak, SymUnknown, Snone, sAny, SymIdent, SymNumber, SymDvoetoch, SymEq, SymAdd, SymSub, SymMul, SymDiv, SymBolshe, SymMenshe, SymBolsheEq, SymMensheEq, SymNotEq, SymOpenSk, SymCloseSk, SymOpenSkKvadr, SymCloseSkKvadr, SymZap, TString, TInteger, TArray);
Синтаксический и семантический анализ входной программы реализован посредством рекурсивных процедур Prog (начальная процедура), Statements (операторы), Statement (оператор), Pri1 (для оператора PRINT), Operator_Compare (сравнение двух выражений), Expression (получение типа выражения), ExpressionInSk (вычисляет тип выражения для индекса массива), Stat (операнд).
При успешной идентификации лексемы происходит компоновка образа программы добавлением в вписок ячеек памяти новых элементов. Этим занимается процедура AddMem с параметром x, где
х=1 - добавить зарезервированное слово; х=2 - добавить указатель на переменную; х=3 - добавить код разделителя (для условного оператора); х=4 - добавить указатель на выражение
По завершении работы С&С Анализаторов необходимо получить список выражений. Этим занимается процедура GetExpressions.
Когда список выражений составлен, необходимо преобразовать их в обратную польскую запись.
Для этого написаны специальные процедуры: - MorfologExpression - стартовая процедура - Morf - собственно процедура преобразования выражения Пример: 1+a*r[6] После преобразования, выражение будет иметь следующий вид $!$$0$+%A%%R%$6$^*+ Здесь используются следующие обозначения: $<Число>$ - обозначение числа %<Имя>% - обозначение имени переменной "<Строка>" - обозначение строковой константы Операция ^ означает, что идет обращение к элементу массива (i-2) с индексом (i-1)
После завершения преобразований выражений происходит запись образа программы и другой вспомогательной информации согласно формату объектного файла, описанного ниже.
4 Интерпретатор.
Режим интерпретации программы из объектного файла также является детерминированным, с прерыванием выполнения работы программы и выдачей сообщения об ошибке.
Образ памяти представляется в виде двунаправленного списка, состоящего из элементов rMem. Элементы rMem определяются так:
Record Num : integer; - номер ячейки памяти Code : integer; - код команды, переменной или разделителя XCode : integer; -номер ячейки для указателя на выражение Lvl : integer; - уровень вложенности команды Next,Pred : ^rMem; - указатели на следующую и предыдущую ячейки памяти End
Счетчик команд IP:integer получает новое значение исходя из выполнения текущей команды.
Для вычисления значений выражений, представленных в обратной польской записи используется процедура Solve, для которой определены два параметра: S_IN:string и S_OUT:string : соответственно вход и выход. При вычислении используется програмно-реализуемый стек (статический массив).
Определены две глобальные переменные, содержащие информацию об адресе стартовой команды (не обязательно равной 1), и об адресе команды завершения программы. Как только счетчик команд попадет в ячейку памяти с номером завершающей ячейки, работа интерпретатора может считаться выполненной и прекращается.
Выражения размещаются в памяти в виде однонаправленного списка, имеющего следующую структуру элементов:
RExpr=^exprType;
ExprType=Record
Stroka : itring;- само выражение
Num : integer; - порядковый номер выражения
TypeExpr : integer; - тип выражения
Next : rExpr - указатель на следующее выражение
End
Список зарезервированных типов слов аналогичен списку из раздела <<транслятор >>.
5 Описание языка Gbasic.
Данный язык является упрощенной версией языка программирования Basic for Spectrum48K. Отсутствует возможность работы с файлами, графикой, динамической памятью, строковыми массивами.
Типы переменных:
Integer - целое число в диапазоне от -32500 до 32500
String - строка диною не более 80 символов
Array - массив целых чисел
Операторы языка:
+ Abs - абсолютная величина значения выражения присваивается переменной
Abs <Выр1>:Int,<Имя>:Int
+ Beep - звуковой сигнал длительностью <Выр1> с частотой <Выр2>
Beep <Выр1>:Int,<Выр2>:Int
+ Call - вызов процедуры
Call <Имя процедуры>
+ Cls - заполнение текстового экрана цветом фона
Cls
+ Delete - удаляет часть строки, начиная с индекса <Выр1> длиною <Выр2>
Delete <Имя>:Str,<Выр1>:Int,<Выр2>:Int
+ For Next
переменная для цикла не должна являться элементом массива
For <Имя_ц>:Int=<Выр1>:Int to <Выр2>:Int:
<Тело цикла>:
Next <Имя_ц>
+ If Then Else EndIf
if <Выр1><Сравнение><Выр2>
then
<Тело then>
else
<Тело else>
endif
+ Ink - установка нового цвета текста (0..15)
Ink <Выр1>:Int
+ Input - ввод информации с клавиатуры
Input <Имя>
+ Lenght - длина строковой переменной
Length <Имя>:Str,<Имя>:Int
+ Let - присвоение переменной значения выражения
Let <Имя>=<Выр1>
+ Locate установка текстового курсора по координатам х=<Выр1>
у=<Выр2>
Locate <Выр1>:Int,<Выр2>:Int
+ Paper - установка нового фона для текста (0..7)
Paper <Выр1>:Int
+ Pause - задержка выполнения программы на <Выр1> мс
Pause <Выр1>:Int
+ Print - вывод на экран списка значений выражений
Print <Выр1>,<Выр2>,..,<ВырN>
+ Proc - процедура
Proc <Имя>:
<Тело процедуры>:
return
+ Randomize - инициализация генератора случайных чисел
Randomize
+ Rnd - получение случайного числа в диапазоне 0..<Выр1>
Rnd <Выр1>:Int,<Имя>:Int
+ Stop - насильственное завершение программы
Stop
+ Sqr - вычисляет квадрат выражения с присвоением результата переменной
Sqr <Выр1>:Int,<Имя>:Int
+ Str - преобразовывает результат числового выражения в строку
Str <Выр1>:Int,<Имя>:Str
+ Val - преобразовывает строку в число
Val <Выр1>:Str,<Имя>:Int
Функции:
В данной реализации языка функции отсутствуют.
Операция деления: Операция "/" производит целочисленное деление (аналог div в языке Turbo Pascal 7.0).
6 Формат объектного файла
GBasic OBJ-file [Program] N - Количество "ячеек памяти" [Start Point] N - Стартовый адрес программы [End Point] N - Адрес завершения программы [Memory] - блок представления памяти <1> <Имя команды> NN - код команды или переменной или выражения или операции сравнения MM - вспомогательный код KK - уровень вложенности <2> ... ... [Variables] - блок представления переменных N - Количество переменных <1> ZZ - Имя XX - тип <2> ... ... [Expressions] - блок представления выражений N - Количество выражений (В обратной польской записи) <1> WW - выражение EE - тип <2> ... ... [Arrays] - блок представления массивов ZZ - Количество массивов <1> WW - имя AA - левая граница BB - правая граница <2> ... ...
7 Инструкция по использованию.
Трансляция исходной программы с языка GBasic в объектный код: transl.exe <имя входного файла> (по умолчанию имя входного файла = "basic.in") Интерпретация объектного кода: interpr.exe <имя объектного файла> (по умолчанию имя объектного файла = "basic.obj") Работа с одномерными массивами (представлен только тип Integer); Запрещена вложенность массивов, т.е. let a[a[4]]=1 - это неправильно let i=a[4]: let a[i]=1 - это правильно.
8 Список литературы:
1) Н.Вирт "Алгоритмы+структуры данных=программы"
2) Ф.В.Вайнгартен "Трансляция языков программирования"
3) В.Н.Пинаев "Формальные методы описания языков програмирования и построение трансляторов"
9 Вместо заключения
Надеюсь, данная статья будет кому-нибудь полезной.
Delphi — это объектно-ориентированный язык программирования со строгой типизацией переменных. Он используется в основном для написания прикладных, пользовательских программ. Простота использования позволяет рекомендовать его в качестве языка для начального обучения программированию. Хотя, если смотреть на перспективу, работодатели мало интересуются работниками, программирующими на Delphi.
Интересные материалы на сайте:
Программа актуально против средств защиты, ограничивающих скачивание файлов из расшаренных ресурсов других компьютеров в локальной сети.
Рисуем прямо на рабочем столе поверх всех окон. Любое изображение, на что способна фантазия. как сохранить промежуточную версию нельзя, то рисунок будет уникальным, неповторимым.
Из большого текста формируется набор ключевых слов, которые должны содержаться на правильной странице правильного веб-сайта.
Теоретические навыки при создании простейшего сайта с нуля.
