МП-преобразователь для Т-грамматики

Активная цепочка может рассматриваться как программа управления работой МП-преобразователя. Прежде чем посмотреть, как это происходит, обратимся к методике пост­роения МП-преобразователя по транслирующей грамматике. Затем получим, преобразователь для Т-грамматики условного опе­ратора и проследим работу преобразователя.

Рассматриваемая входная грамматика условных операторов (см. табл. 5.2.1) относится к классу LL(1)-грамматик. Поэтому вполне есте­ственно вести здесь речь о построении преобразователя, подходяще­го для такого класса грамматик. Наш МП - преобразователь будет использовать нисходящую стратегию анализа, он будет также детер­минированным. Методика построения МП - распо­знавателя для LL(1)-грамматик была рассмотрена ранее. По­вторим здесь полностью все пункты указанной методики с учетом особенностей, которые привносит в нее Т-грамматика.

Прежде всего, сохраним, по возможности, обозначения под­программ в управляющей таблице преобразователя:

- 3 ( , ) - Замена символа в вершине магазина строкой и запись в выходную строку части перевода, соответствующей це­почке операционных символов.

- П - перемещение указателя входной строки на одну пози­цию вправо.

- И( ) - Исключение символа из вершины магазина и вывод в выходную строку части перевода, соответствующей цепочке операционных символов.

- О - Обнаружение Ошибки в программе и завершение ра­боты.

- В - Выход, нормальное завершение работы.

Если один из аргументов подпрограммы 3 отсутствует, со­храняем разделяющую запятую. При отсутствии единственного аргумента подпрограммы И пишем И(). Теперь дадим пункты ме­тодики построения ДМП-преобразователя М = (Q, , Г, , , q₀, Z₀, F) с одним состоянием по Т-грамматике G_T = (V_T, V_N, , R, S), входная грамматика G = (V_T, V_N, Р, S) которой обладает свой­ством LL(1)-грамматик.

1.Q={q};q₀= q;F=

2. =V_T {#}, # — концевой маркер входной строки.

3. Г= V_N {#} {t\ t V_T,(A -> t ) Р, V⁺, V*}

{r\r , (А- > ₁B ₂ r ₃) R, B V_N; _{1 2}, ₃ (V )*}, где

t - не головной символ в правой части правила;

r - операционный символ, слева от которого в правой части прави­ла имеется хотя бы один нетерминал;

# — маркер дна магазина.

4. Z₀ = S#, S располагается в вершине магазина.

5. Заготовить управляющую таблицу преобразователя со строками Z Г и столбцами а (одну, так как состояние одно).

6.Последовательно проанализировать правила Т-грамматики и заполнить позиции (Z, а) таблицы обозначениями подпрограмм преобразователя:

а) 3( ,fg),П—для правила вида Z->fag ,где Z V_N ,a V_T, f,g *; {V }* и h₁( ) V, т.е. головной символ строки не должен быть операционным;

б) 3( ,f)—для правила вида Z->f и всех a DS(Z, ), где f *;

=A ,Z,A V_N; {V }*, ;DS(Z, ) вычисляется по правилам входной грамматики G;

в) И(f)—для правил вида Z ->f и всех a DS(Z, ), где Z V_N;
f *, а ; DS(Z, ) вычисляется по грамматике G;

г) И(fg),П—для правил вида Z->fag, где Z V_N,а V_T;f, g *.

7. Завершение заполнения позиций (Z, д) таблицы обозначе­ниями подпрограмм преобразователя:

а) И(), П — для всех позиций Z = а, где Z,a V_T;

б) И — для всех позиций строки Z ;

в) В — для позиции Z = а = #;

г) О — для всех оставшихся пустыми позиций.

Теперь формируются заготовки текстов сообщений об ошиб­ках, и на этом разработка МП-преобразователя завершается.

ЗадачаПостроить МП-преобразователь по транслирую­щей грамматике условных операторов

Решение

1. Q= {q};q₀=q;F= 2. ={if,then,else,z,p,;,#}

3. Г= {U,K,H,M,O,#,;,[x₃]} 4. Z₀= U#

5. Управляющая таблица представлена в табл. 5.2.2

6. Пояснения к заполнению табл. 5.2.2:

а) правило 1 — помещаем 3(К,),П в позицию (U, if);
правило 2 — помещаем 3(Н,[х₀]),П в позицию (K, р);
правило 3 — помещаем З((ОМ[х₃];),[х₁]), в позицию (H, then);
правило 4 — помещаем З(О,[х₂]),П в позицию (М, else);

б) правило 6 — помещаем 3(U,) в позицию (О, z);

в) правило 5 — помещаем И в позицию (М,;);

г) правило 7 — помещаем И([х₀]),П в позицию (О, z).

7. Пояснения к завершению заполнения табл. 5.2.2;

а) помещаем И( ),П в позицию (;,;);

б) помещаем И([x_з]) во все позиции строки [xз];

в) помещаем В в позицию (#, #);

г) помещаем О во все свободные позиции таблицы.

 

Таблица 5.2 Управляющая таблица

 

if

then

else

z

р

;

#

U

3(К,),П

О

О

О

О

О

0

K

О

О

О

О

3(О,[х2]),П

O

0

H

О

3((0М[х3]; [x1]),П

О

O

О

O

0

M

О

О

3(О,[х2]),П

О

О

И()

0

О

3(U,)

О

О

И[х0]),П

O

O

0

;

О

О

О

О

О

И(),П

0

[х3]

И([x3])

#

О

O

O

О

O

0

B

ЗадачаИспользуя МП - преобразователь из предыдущей задачи, вы­полнить перевод оператора ifp₁ then z₁ else z₂; в ОПЗ.

Прежде всего обратим внимание на то, что помимо магазина наш МП -преобразователь работает со стеком меток. Решение пред­ставим в табл. 5.2.3, предусмотрев в ней колонки для отображения номера шага преобразования, содержимого магазина, содержимого входной строки и записей в выходную строку преобразователя. Магазин изображается так, что его вершина расположена слева. Текущий символ входной строки также находится слева. Выход­ная строка формируется слева направо. Кроме того, для наглядности предусмотрены колонки для показа операционного символа, являющегося активным на текущем шаге перевода (колонка "операция"), и для представления стека меток (вершина стека слева).

На каждом шаге работы преобразователя выделяется пара (символ в магазине, текущий входной символ) и выполняются действия, определенные содержимым соответствующей позиции таблицы и активным операционным символом. На выходе пре­образователя получена строка р₁т₂УПЛz₁т₁БПт₁:z₂т₂:, котораяпредставляет собой ПОЛИЗ исходного оператора и может быть ис­пользована для генерации машинного кода или интерпретации.

 

Таблица 5.3 Перевод условного оператора в ОПЗ