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



         

Простой язык программирования - часть 2


Формально программа машины Тьюринга определяет вычисление для ленты с "любым начальным содержимым", то есть для любой бесконечной в обе стороны последовательности

...,a-3, a-2, a-1, a0, a1, a2, a3,...

Пример 4.2.

(html, txt)

элементов алфавита ? следующим образом. В произвольный момент вычисления существует "текущее состояние" q

Q и целочисленная величина "положение читающего устройства" p. Вначале q = q0 и p = 0. Если q
q? и если
(q, ap) = (s', k', q'), то следующим шагом вычисления будет замена значения p на p + k, q на q' и ap на s'. Если q = q?, вычисление заканчивается. (Вычисление может не закончиться; для программы (4.1) это произойдeт тогда и только тогда, когда aj="единица" для всех j < 0.)

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

(1) Семантическое правило " включить х в B ", связанное с синтаксическим правилом, означает, что x должен стать элементом множества B, где B - атрибут аксиомы S грамматики. Значением B будет множество всех x, для которых существует такое семантическое правило, связанное с каждым применением соответствующего синтаксического правила в дереве вывода. (Это правило можно рассматривать как сокращeнную запись семантического правила

B(&X_{p0})=\bigcup \limits_{j=1}^{n_p} B(X_{pj}) \cup \qquad \qquad \qquad\qquad \qquad \qquad\let \leqno \relax (4.3) \\ &\cup \; \{x \mid \text{"\textbf{включить} \; $x$ в $B$ "связано с $p$ -м правилом} \},

связанного с каждым синтаксическим правилом. Здесь B - синтезированный атрибут, имеющийся у всех нетерминальных символов. Для терминальных символов B(x) пусто. Ясно, что эти правила позволяют получить нужное B(S).)

(2) Семантическое правило "определить f(x) = y", связанное с синтаксическим правилом, означает, что значение функции f в точке x будет равно y; здесь f - атрибут аксиомы S грамматики. Если встречается два правила, задающих значение f(x) для одного и того же значения x, то возникает ситуация ошибки, а дерево вывода, в котором она возникла, называется неправильным.


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