www.gcmsite.ru

Новости Программы PHP-скрипты Статьи Числа
Услуги Резюме Игры Автомобили Поиск

СИСТЕМНОЕ И ВЕБ-ПРОГРАММИРОВАНИЕ
компьютерная техника, игры

Нужна программа, скрипт или сайт? Анализ сайта или оптимизация? Копирайт или рерайт текстов? Заявка на выполнение работ.

Построение транслятора и интерпретатора языка программирования 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.

Интересные материалы на сайте:

Рейтинг@Mail.ru     Автор, разработчик: Шаров Евгений   (gcmsite@yandex.ru)
(c) 2000-2017 GCM-Site - системное и веб-программирование
Цитирование материалов сайта возможно только при наличии гиперссылки