Файл: Мясников, В. А. Программное управление оборудованием.pdf

управлением к другому производить лишь замену описаний син­ таксиса входного языка и связи между входным и выходными языками.

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

1) изменился входной язык транслятора (т. е. выходной язык процессора) и не изменился его выходной язык (входной язык конкретного программного устройства);

2)не изменился входной язык и изменился выходной язык;

3)изменились оба языка.

При использовании обычного транслятора во всех трех случаях требуется разработать три разные согласующие программы (транс­ ляторы), в то время как при использовании синтаксического транс­ лятора необходимо произвести лишь следующие замены: в первом случае заменить описание грамматики входного языка, во втором и третьем случаях заменить описание связи между входным и вы­ ходным языками.

Метаязык /?-грамматик В [8, 9] для описания грамматик предложен так называемый метаязык ^-грамматик. Это чрезвычайно удобный, простой и на­

глядный способ описания синтаксиса языка.

Обычно грамматика выходных языков процессоров систем программного управления оборудованием чрезвычайно проста. Поэтому задача разработки постпроцессора сводится к описанию выходного языка процессора на метаязыке /^-грамматик и привне­ сению семантики в это описание (т. е. заданию связи между вход­ ным и выходным языками постпроцессора).

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

Пусть под магазин в памяти ЭВМ отведено k подряд идущих

ячеек 1, 2, . . ., &. Имеется еще одна ячейка — счетчик, распо­ ложенная в любом месте памяти и указывающая адрес первой свободной ячейки магазина. Полагают, что запись и считывание в магазин может быть осуществлено только через его верхушку. Таким образом, в каждый момент времени может быть считан только тот символ, который был записан последним (рис. 99). Если в магазин мы записывали символы в такой последователь­ ности: М, А, Г, А, 3, И, Н, то из магазина мы считываем их в обрат­ ной последовательности: Н, И, 3, А, Г, А, М.

Формальное описание /^-грамматик приведено в работе [8]; здесь мы приведем только основные понятия, которые необходимы для понимания методики построения постпроцессоров.

Грамматика в /^-метаязыке задается некоторым множеством правил, объединенных в комплексы.

Эти правила имеют вид:

r - ^ . a — i r < Л >

170

где г, — имя комплекса правил, который записан после двоеточия; г — имя комплекса правил-преемников, т. е. правил, к которым

следует обратиться после данного комплекса.

Среди всех комплексов правил выделяется комплекс г0, кото­ рый называется начальным или аксиомой, с него всегда должен начинаться процесс распознавания пли порождения. Другим вы­ деленным комплексом правил является комплекс г0, который

называется пустым или конечным. Этим правилом должно закан­ чиваться распознавание правильной (для данного языка) входной фразы, этим же правилом заканчивается процесс распознавания.

Символ а принадлежит входному алфавиту (вернее, алфавиту

синтермов).

Поясним сказанное выше примером. Пусть необходимо скон­ струировать грамматику, которая распознавала бы слова КОНТУР

будет сказано ниже), /^-грамматика для этого случая будет иметь следующий вид:

Процесс распознавания ведется следующим образом. Вводится первый символ К и происходит обращение к комплексу г0. Если

входной символ совпадает с символом,записанным слева от стрелки, то это означает, что символ распознан. Вводится следующий символ и осуществляется переход к правилу-преемнику, записан­ ному справа от стрелки (в данном случае к правилу г2). Аналогично анализируется и символ О.

После распознавания символа Н осуществляется ввод следую­ щего символа (например, Т для слова КОНТУР) и происходит переход к правилу г3. Поскольку текущий входной символ Т не совпадает с символом Е, происходит переход ко второму пра­ вилу в комплексе г3. Процесс заканчивается, если правилом-

преемником оказывается пустое (конечное) правило г0 (естествен­

171

ное окончание) или же если для входного символа не находится в комплексе правил-преемников такого же символа слева от стрелки.

Считывание из м агази н а

Очевидно, что при конструировании ^-грамматики возможен некоторый произвол. Например, ту же грамматику, что и в пре­ дыдущем примере, можно представить следующим образом:

г4 : { К ^ г в, У ^ г в};

При интерпретации правил ^-грамматики производятся неко­ торые операции над магазинной памятью, определяемые много­ местным отношением Wm = Wm (a*, а 2, . . . . a j .

Если m = 0, то никаких операций над магазинами не про­

изводится.

Если /п = 1, то в л магазинов записываются слова: а х в ма­ газин № 1, а 3 в магазин № 2 и, наконец, ап в магазин № п.

172

Если т = 2, то в магазинах стираются слова при условии,

что слово в верхушке магазина совпадает с соответствующим сло­ вом в выражении Wm.

Таким образом, если транслятор должен перейти к комплексу правил rt\

при входном символе а и если в верхушке магазина № 2 записано не слово а 2, то выполнится второе подправило г , т. е. в магазин № 1 запишется слово а о и правилом-преемником будет правило г,..

означает, что правилом-преемником является комплекс правил, имя которого записано в магазине № k.

Например, если в магазине № 3 записано правило г8, то пра-

w'. 3 i *

вило а ----- >гыозначает, что если входной символ равен а, то необ­

ходимо ввести следующий символ и перейти к выполнению пра­ вила г8.

Для того чтобы осуществить перевод с одного языка на другой, необходимо с каждым правилом /^-грамматики сопоставить неко­ торое семантическое правило (или множество правил) А, заклю­

ченное в угловые скобки.

Поскольку /^-грамматика может быть как распознающей, так н порождающей, то А может обозначать как имя соответствую­

щей порождающей грамматики, записанной на /^-метаязыке, так и имена подпрограмм, которые вводят семантическое опре­ деление.

Порождение, записанное на языке /^-грамматики, происходит

следующим образом.При обращении к некоторому правилу я ----- >■г{

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

Таким образом, распознавание и порождение можно произво­ дить с помощью практически одинаковых программ.

Описание входного языка координатографа ЭМ-703 с помощью /^-грамматик

В словарь входного языка входят следующие символы: цифры (О, 1, 2, . . ., 9), признаки координаты. (X, У), признаки прира­ щения координат (АХ, АУ), признак минус, признак команды (К), признак конца кадра (КК), признак цикла (Ц) и признак границы

массива (ГМ).

Вся информация о рисунке ограничивается с двух сторон признаками ГМ. В пределах одного массива ввод информации

173