5.10. Перевод с одного языка на другой

Рассмотрим на простейшем примере перевод с одного языка на другой. Исходный язык задан грамматикой

Применяя грамматику получаем язык

Автомат, распознающий язык будет следующим:

Граф переходов автомата показан на рис. 5.19.

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

Рис. 5.19. Граф переходов автомата, распознающего язык

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

На автомат слева направо поступает очередной символ последовательности а

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

Состояние сопоставлено с некоторым действием, которое и выполняется. После этого все повторяется для следующего символа.

Введем единственное элементарное действие Соединить над последовательностями В результате выполнения этого действия получается новая последовательность Процесс перевода представим в виде таблицы (табл. 5.2). В первом столбце таблицы указывается очередной символ, поступающий на автомат, во втором столбце указано состояние, в которое

Таблица 5.2 (см. скан)

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

Вопросы и упражнения

(см. скан)