Теория и реализация языков программирования

         

S соответствует два состояния: начало


Отметим, что каждому оператору S соответствует два состояния: начало (S) - состояние, соответствующее первой команде, входящей в оператор (если таковая имеется), являющееся унаследованным атрибутом символа S, и следующее (S) - состояние, "следующее" за оператором, или состояние, в которое попадает машина после нормального выполнения оператора. В случае оператора перехода, однако, программа не попадeт в состояние следующее (S), поскольку действие оператора состоит в передаче управления в другое место; о состоянии следующее (S) можно сказать, что оно следует за оператором "статически" или "текстуально" , а не "динамически" в ходе выполнения программы.

В таблица 1 следующее (S) является синтезированным атрибутом; можно составить аналогичные семантические правила, в которых атрибут следующее (S) будет унаследованным. При этом, правда, программы, включающие пустые операторы, будут несколько менее эффективны (см. правило 4.4). Аналогично, оба атрибута начало (S) и следующее (S) могут быть сделаны синтезированными, но это будет стоить дополнительных инструкций в программе машины Тьюринга при реализации списка операторов.

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

Создаeтся впечатление, что такое определение Тьюрингола приближает нас к желанной цели: придать точный смысл тем понятиям, которые встречаются в неформальном руководстве по языку для программиста, причeм сделать это нужно совершенно формально и однозначно.Другими словами, это определение, возможно, отвечает нашему образу мышления при изучении языка. Определение 4.1 оператора печати, например, можно легко перевести на естественный язык, написав

Оператор может иметь вид: печатать "I"

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


Содержание  Назад  Вперед







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