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

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

Рассматриваемая входная грамматика условных операторов (см. табл. 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 D S(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 = а = #;

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

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

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