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



             

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


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

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

Алфавит пробел, единица, нуль, точка; печатать "точка"; перейти на выполнить; тест: если символ на ленте _единицаї, то {печатать "нуль"; (4.1) выполнить: сдвинуться влево на одну клетку; перейти на тест}; печатать "единица"; возврат: сдвинуться вправо на одну клетку; если символ на ленте "нуль", то перейти на возврат.

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

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

  • множества "состояний" Q,
  • множества "символов" ?
  • начального "состояния" q0
    Q
  • конечного "состояния" q1
    Q
  • и "функции переходов"
    , отображающей множество

(Q-{q?})x? в ?{-1, 0, +1}xQ. Если

(q, s) = (s', k', q'), то это означает, что если машина находится в состоянии q и обозревает символ s, то она печатает символ s', сдвигает читающее устройство на k клеток вправо (сдвигу на одну клетку влево соответствует случай k = 1) и переходит в состояние q'.


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