Основы конструирования компиляторов

Преобразователи с магазинной памятью


Рассмотрим важный класс абстрактных устройств, называемых преобразователями с магазинной памятью. Эти преобразователи получаются из автоматов с магазинной памятью, если к ним добавить выход и позволить на каждом шаге выдавать выходную цепочку.

Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P = (Q, T,

,
, D, q0, Z0, F), где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением

того, что

- конечный выходной алфавит, а D - отображение множества QЧ(T
{e})Ч

в множество конечных подмножеств множества Q Ч

*Ч
*.

Определим конфигурацию преобразователя P как четверку (q, x, u, y), где q

Q - состояние, x
T* - цепочка на входной ленте, u
* - содержимое магазина, y
* - цепочка на выходной ленте, выданная вплоть до настоящего момента.

Если множество D(q, a, Z) содержит элемент (r, u, z), то будем писать (q, ax, Zw, y)

(r, x, uw, yz) для любых x
T*, w
* и y
*. Рефлексивно-транзитивное замыкание отношения
будем обозначать
*.

Цепочку y назовем

выходом для x, если (q0, x, Z0, e)

*(q, e, u, y) для некоторых q
F и u
*. Переводом (или трансляцией), определяемым МП-преобразователем P (обозначается
(P)), назовем множество

Будем говорить, что МП-преобразователь P является детерминированным (ДМП-преобразователем), если выполняются следующие условия:

  • для всех q
    Q, a
    T
    {e} и Z
    множество D(q, a, Z) содержит не более одного элемента,

  • если D(q, e, Z)
    ,

    то D(q, a, Z) =

    для всех a
    T.

    • Пример5.1. Рассмотрим перевод

    , отображающий каждую цепочку x
    {a, b}*$, в которой число вхождений символа a равно числу вхождений символа b, в цепочку y = (ab)n, где n - число вхождений a или b в цепочку x. Например,
    (abbaab$) = ababab.

    Этот перевод может быть реализован ДМП-преобразователем P = ({q0, qf}, {a, b, $}, {Z, a, b}, {a, b}, D, q0, Z, {qf}) c функцией переходов:

     

    D(q0, X, Z) = {(q0, XZ, e)}, X

    {a, b},

    D(q0, $, Z) = {(qf, Z, e)},

    D(q0, X, X) = {(q0, XX, e)}, X

    {a, b},

    D(q0, X, Y ) = {(q0, e, ab)}, X

    {a, b}, Y
    {a, b}, X
    Y .

     



    Содержание раздела