Построение транслятора и интерпретатора языка программирования 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.
Интересные материалы на сайте:
Описание алгоритмов для программного нажатия на клавиши. Пригодится системным администраторам и всем, кто увлекается системными утилитами.
Статья о поисковой интересности сайта. Возможно, часть материалов уже устарела за 10 лет, но на некоторые моменты стоит обратить внимание.
Свой взгляд на проблему обмена гипер ссылками между сайтом донором и сайтами получателями.
Еще один лайф-хак. Обыгрываем нечестных игроков в игру "Балда". Большая база слов, которая с легкостью может быть расширена.
