Проектирование компилятора для языка РЛИ. Правила Компиляции | MetodPro.ru

Реклама на сайте

Проектирование компилятора для языка РЛИ. Правила Компиляции


1 Общие положения о компиляции программ на языке РЛИ

 Чтобы описать компилятор рассмотрим каждое правильная выражение на языке РЛИ и построим соответствующий список команд на языке secd машины, обладающий СВОЙСТВОМ ЧИСТОГО РЕЗУЛЬТАТА.

Суть его заключается в том, что программа, скомпилированная для правильного выражения такова, что после ввода в регистр управления secd машины и выполнения она оставляет значения в вершине стека s. При этом необходимо, чтобы вычислительная обстановка была представлена структурой, содержащей на соответствующих позициях значения свободных переменных выражения. Она (программа) оставляет стек без изменения за исключением извлечения и вталкивания значения выражения в вершину стека. Окружение и хранилище (e,d) имеют одни и те же значения до и после выполнения программы. Таким образом, если c – это программа, построенная для правильного выражения, e – это окружение, содержащее значение переменных оттого выражения, то для любого стека s  и хранилища d выполнение программы  приводит  к следующему состоянию secd машины:

secd - > (x.s)  e  nil d

x – значение, возвращаемое программой C. Таким образом, команда stop должна встречаться один раз в конце списка команд, чтобы после ее извлечения из списка управления он становился пустым. Вообще список управления C можно представить в виде последовательности c1,c2,..,cn (в виде последовательности подсписков), последовательное выполнение которых приводит к вталкиванию в стек соответствующих вычисленных значений и устранению этих программ из списка управления c.

При анализе каждого правильного выражения будет строится список переменных, объявленных в лямбда выражении (определении функции). Этот список будет конгруэнтен, то есть  равен по структуре,  в вычислительной обстановке, в текущей момент времени. Где бы не встретился новый блок или функция, перемене, объявленные в них будут добавлены к списку имен в качестве первого подсписка. По данному именному списку можно определить индексную пару для доступа к каждой переменной. Индексная пара вычисляется с помощью place(x,n), где x – рассматриваемая переменная, а n – список имен. Полученная индексная пара является аргументом команды ld

2 Правила компиляции выражения языка РЛИ

Если E – это правильное s-выражение, а σ – окружение, то запись Feσ используется для обозначения трансляции выражение E в окружении σ. Запись Feσ+ обозначает трансляцию выражения E в расширенном окружении. Если x – это переменная, то трансляция соответствует списку команд Fxσ

-> (LD(b m)) Где b номер подсписка в окружении σ, а m – номер значения переменной x в b-ом подсписке.

Образуется список из одной команды LD с аргументом b m, которая вводит требуемое значение в стек, причем (b m) = place (x,n).

Если S – это константа, то F(quote s)σ -> (LDC S)

Если OP – это бинарная операция, а e1 и e2 – это выражения ЯРЛИ, то общее правило трансляции имеет вид.

F(op e1 e2)σ= Fe1σ Fe2σ (OP)

Порядок следования аргументов таков, что сначала перед оператором располагается второй аргумент, а перед ним – первый. Согласно схеме трансляции сначала компилируется первый операнд, потом второй, а завершается операцией.

Исключение составляет команда cons, требующая свои аргументы в обратном порядке:

F(add e1 e2)σ= Fe1σ Fe2σ (ADD)

F(cons e1 e2)σ= Fe2σ Fe1σ (CONS)

Унарная операция.

Если OP – это унарная операция, то общее правило трансляции выражения имеет вид:

F(op e)σ= Feσ(OP)

Пример:

F(car e)σ= Feσ(car)

Рассмотрим пример:

e = (CONS (ADD (CAR X) (QUOTE 3))(CDR (QUOTE (A B C))))

σ = ((X Y))

=(CDR(QUOTE(A B C)))(ADD(CAR X)(QUOTE 3))(CONS)=

(CDR(QUOTE(A B C)))(CAR X)(QUOTE 3)(ADD CONS)=

(QUOTE(A B C))(CDR) X(CAR) LDC 3 (ADD CONS)   =

(LDC (A B C) CDR)(LD(0 0) CAR)( LDC 3 ADD CONS)        =

(LDC (A B C) CDR LD(0 0) CAR LDC 3 ADD CONS)

Условное выражение имеет 3 аргумента, каждый из которых жолжен быть вычислен:

(COND e1 e2 e3)        →       (SEL  (JOIN) (JOIN))

Схема трансляции сводится к тому, что сначала компилируется выражение e1, затем ставится команда SEL, следом помещается список из cтранслированного выражения e2, завершающегося командой JOIN, и, аналогичным образом, для выражения e3. Программы для выражений e2 и e3 вложены как операнды команды SEL, а программа для выражения e1 предшествует ей. Полученный список команд обладает свойством чистого результата.

Пример:

e=(COND(EQUAL(QUOTE 1)(QUOTE 3))(ADD(QUOTE 4)(QUOTE 3))

 (CAR(QUOTE (A B C))))

σ=NIL

=(EQUAL(QUOTE 1)(QUOTE 3))(SEL(ADD(QUOTE 4)(QUOTE 3)

(JOIN) (CAR(QUOTE(A B C)))(JOIN))=

(LDC 1 LDC 3 EQ SEL (LDC 4 LDC 3 ADD JOIN)

 (LDC (A B C)CAR JOIN))

Лямбда-выражение вводит новые переменные, которые оно использует в теле функции. Поэтому предварительно необходимо согласовать именной список, добавив в исходное окружение σ список связанных переменных, что дает расширенное окружение σ+. Тогда правило трансляции лямбда- выражения можно представить уравнением:

(LAMBDA (x1 … xk)  e)      →      (LDF   (RTN))                 

σ+  = (x1 … xk). σ

Теперь на переменные в исходном окружении σ будет осуществляться ссылка при помощи индексной пары, где первый индекс увеличен на единицу.

Схема трансляции заключается в компиляции тела функции относительно расширенного окружения σ+ и помещении его в вершину стека. Открывающая список команда LDF потребуется для создания замыкания в вершине стека. Ее аргументом является список, состоящий из скомпилированного тела функции и команды RTN, которая обеспечивает возможность возврата после каждого вызова функции для продолжения вычислений.

Рассмотрим пример:

e=(LAMBDA (X Y) (ADD X Y))

σ=((A Y))

= (LAMBDA (X Y)(ADD X Y))= (LDF (ADD X Y)(RTN)=

(LDF (LD (0 0) LD (0 1) ADD RTN))

Несмотря на то, что Y содержится в окружении и как локальная и как глобальная переменная, при трансляции она рассматривается как локальная (поиск в списке имен ведется с нулевого подсписка).



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем