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

⇐ ПредыдущаяСтр 22 из 24Следующая ⇒

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

Рассматриваемая входная грамматика условных операторов (см. табл. 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; ₁ ₂, ₃ (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 Управляющая таблица

then

else

;

3(К, ), П

3(О, [х₂]), П

3((0М[х₃]; [x₁]), П

3(О, [х₂]), П

И()

3(U, )

И[х₀]), П

;

И(), П

[х₃]

И([x₃])

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

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

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

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

⇐ Предыдущая 15 16 17 18 19 20 212223 24 Следующая ⇒