Семантика Turingol

Конструкция программы

Александр Шкотин,

ashkotin@acm.org

Абстракт

Обычно программа представляется как цепь слов. Именно цепь слов появляется на выходе лексического анализатора и подвергается синтаксическому анализу. В работе показывается, что синтаксически программа может быть представлена как ориентированное дерево слов - синтаксическое дерево программы. Причём слова программы располагаются как в узлах так и на стрелках дерева. Основное свойство дерева — стрелки исходящие из каждого узла помечены разными словами (включая пустое слово). В таком случае семантику можно задавать прямо на этом дереве — как требованиями так и дополнительными связями, а пополнение некоторых узлов дерева инструкциями даёт возможность задать выполнение программы, т.е. описать конструкцию программы "до конца".

Раздел 1 содержит краткое изложение подхода и пример текста программы и её синтаксического дерева. Для задания семейства синтаксических деревьев используется синтаксическая схема, описанная в разделе 2. В результате язык оказывается семейством деревьев, заданных схемой. К синтаксическому дереву программы предъявляются дополнительные требования, отражающие семантику языка программирования. Кроме того на синтаксическом дереве программы проводятся дополнительные стрелки — "семантические связи". Семантика зависит от языка программирования и будет рассмотрена на примере языка Turingol [SoCFL] в разделе 3. Конструкция внешних данных, существующих независимо от программы, требует отдельного рассмотрения. В разделе 4 данные описаны только для Turingol, программа которого работает с лентой. Программа в виде синтаксического дерева с семантическими связями должна быть инициализирована. Например к ней должны быть подсоединены внешние данные с которыми она будет работать. Кроме того в узлы соответствующие выполняемым операторам заносятся инструкции для Исполнителя. Инициализация описана в разделе 5, а исполнение в разделе 6.

В Приложении 1 описано как привести авторскую грамматику Turingol к форме дающей схему, а в Приложении 2 собраны необходимые средства работы с конечными помеченными графами.

Введение

На протяжении всей статьи мы будем рассматривать в качестве примера Turingol [SoCFL]. Это простой язык программирования для которого с самого его рождения была описана, причём автором, формальная семантика. Правда, при ближайшем рассмотрении оказывается, что описана трансляция программ Turingol'а в программы машин Тьюринга. Трансляция при которой проверяется правильность Turingol программы. О самом же языке автор говорит, что он и так понятен [SoCFL, p.138, lines 1-3.]. Таким образом требования к Turingol программе "скрыты" в трансляции. Впрочем пара требований упомянута явно [SoCFL, p.139]:

"...programs are malformed if the same identifier is used twice as a label or if a go to statement specifies an identifier which is not a statement label. "

Мы не будем рассматривать программы машин Тьюринга, а сосредоточимся на самих Turingol программах. Предполагается, что некий Исполнитель выполняет саму Turingol программу, работающую с лентой. Соответственно будет описана конструкция ленты.

Программа представляет собой граф слов, описание его свойств и правил использования и есть основная цель статьи. В основе графа программы лежит ориентированное дерево слов языка — синтаксическое дерево программы (или её части). Для задания семейства деревьев вводится "синтаксическая" схема, в определённом смысле аналогичная синтаксическим диаграммам Wirth [Wirth]. Но в то время как синтаксические диаграммы задают правила построения цепочки слов, схема задаёт правила построения деревьев, помеченных словами. Способов создания под-деревьев всего два: цепь узлов (связанных стрелками) и узел из которого выходит заданный схемой набор стрелок. То что конкретная схема, порождает деревья исходящие стрелки которых помечены по разному надо доказывать, что и будет сделано для Turingol.

То что программа сама по себе представляет дерево позволяет по новому взглянуть на описание её семантики. Конечно узлам дерева можно приписывать различные атрибуты, в том числе для компиляции [SoCFL].

Полученное дерево должно удовлетворять некоторым требованиям, которые дадут "well-formed Turingol program" [SoCFL,p.138]. Для простоты мы будем предполагать, что существует отдельная фаза проверки этих требований. Хотя безусловно все проверки могут выполняться по мере построения дерева.

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

Чтобы до конца понять программу надо определить способ выполнения. Для этого аналогично [PostM] предполагается наличие абстрактного Исполнителя перемещающегося по графу программы и выполняющего инструкции в узлах соответствующих операторам. Этот подход соответствуют тому как мыслит свою программу программист. Размещение инструкций в узлах отнесено к фазе инициализации программы. Также к ней отнесено соединение программы с внешними данными, что в случае Turingol состоит в присоединении к ней ленты.

Исполнитель выполняет программу перемещаясь по некоторым её узлам и выполняя указанные в них инструкции (в том числе действия с лентой). Это именно то что имел в виду программист создавая программу. И тезис состоит в том, что программист в принципе может выполнить свою программу и сам, не обращаясь к машине (например машине Тьюринга). Более того, именно это понимание программистом выполнения "исходного текста" программы неким Исполнителем обязывает этот Исполнитель (aka debugger) взаимодействовать с программистом как-будто он (Исполнитель) исполняет "исходный текст" программы.

Пример программы — текст

Рассмотрим программу 4.1 [SoCFL] p.137. Для простоты некоторые словосочетания записаны через тире что делает их лексически одним сложным словом. Соответственно тире нужно добавить в алфавит языка.

tape-alphabet is blank, one, zero, point;

print "point";

go to carry;

test: if the-tape-symbol is "one" then

{print "zero"; carry: move left one-square; go to test};

print "one";

realign: move right one square;

if the-tape-symbol is "zero" then go to realign.

Синтаксическое дерево программы

Каждое слово программы (включая специальные слова такие как ';', ',') попадает в одну конкретную метку (узла или стрелки). Метка стрелки, а в общем случае и метка узла может быть пустым словом.

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

Отметим цепи узлов с разделителем, размещённым на стрелках:

- в первом ряду: 'blank' ',' 'one' ',' 'zero' ',' 'point'

- в пятом ряду: 'print' ';' 'move' ';' 'go'

- вертикально: 'print' ';' 'go' ';' 'if' ';' 'print' ';' 'move' ';' 'if'.

При этом первая цепь являются однородной — её члены имеют одинаковое строение. В данном случае это просто слово. Вторая и третья цепь являются разнородными, т.к. составляющие их операторы имеют различное строение дерева.

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

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

Схема. Задание семейств деревьев

Синтаксическая схема используется для задания семейств помеченных деревьев.

Для задания допустимого значения слова в узле или на стрелке дерева используются регулярные выражения (РВ). Впрочем обычно допустимо лишь какое-то конкретное слово. Для Turingol нам понадобятся всего лишь два РВ: left|right и [a-z]+, последнее для задания слова над алфавитом малых английских букв.

Далее в тексте определений в квадратных скобках пишется поясняющий комментарий, формально в определение не входящий.

Пусть PLA и MLA два не пересекающихся алфавита.

PLA – алфавит языка программирования, MLA – алфавит "метазыка".

Определения

Синтаксическое дерево (сокращённо - сид) есть ориентированное помеченное дерево, такое что метка узла и стрелки это слово из PLA*.

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

[Термин "умеченное" выбран по аналогии с термином "упорядоченное дерево", у которого стрелки исходящие из каждого узла упорядочены.]

Сентенциальное дерево (сед) это ориентированное помеченное дерево, такое что:

- Метка узла это слово из PLA* или из MLA+.

- Метка стрелки это слово из PLA*.

Узлы помеченные словом из MLA+ называются вспомогательные и играют роль аналогичную нетерминалам в КСГ.

Синтаксическая схема есть ориентированный помеченный граф с 2-мя видами стрелок (и-стрелка и или-стрелка) при этом и-стрелки делятся на два подвида (обязательная, необязательная).

Метки это РВ над алфавитом PLA. [В том числе слова из PLA*.]

Узел из которого нет исходящих стрелок называется атомарный (а-узел).

Узел из которого исходят только или-стрелки называется или-узел.

Узел из которого исходят только и-стрелки называется и-узел.

Каждому узлу схемы можно приписать уникальное имя (схемное имя) - слово из MLA+. Такая схема называется полностью поименованная схема.

конец определений

Turingol. Схема

В качестве примера рассмотрим полностью поименованную схему Turingol:

Узлы это прямоугольники. Овалы содержат схемные имена. Или-стрелки обозначены жирной линией. Необязательные стрелки обозначены прерывистой линией.

PLA - строчные латинские буквы, а также: |.,;:-{}"|, где "|" буква не встречающаяся в PLA.

MLA - прописные латинские буквы.

Большинство узлов и стрелок помечены конкретным словом PLA. Узлы DL, LD, I помечены РВ [a-z]+. Стрелка из SM в OS помечена РВ left|right. Узлы L, S, SE помечены пустым словом. Также пустым словом помечены стрелки P-DOT, SI-A, SP-STR.

Теперь опишем как синтаксическая схема задаёт семейство сид.

Построение сентенциального дерева от узла схемы: Пусть схема как-то полностью поименована и указан некоторый узел У0 схемы. Тогда, чтобы создать сентенциальное дерево от узла У0 надо:

Создать изолированный узел У1 (копию узла У0).

Провести из него копии всех обязательных исходящих и-стрелок и какие-то из необязательных узла У0, пометить копии стрелок словами допустимыми РВ их образцов в схеме. На конце каждой стрелки создать узел со схемным именем соответствующего узла схемы.

Если у узла У0 есть или-стрелки, то взять имя узла на конце одной из них и записать в У1 иначе пометить У1 словом заданным РВ узла У0.

Для или-узла инструкция существенно упрощается: Создать изолированный узел У1. Взять имя узла на конце одной из исходящих или-стрелок узла У0 и записать в У1.

Также проста инструкция и для атомарного узла: Создать изолированный узел У1. Пометить У1 словом заданным РВ узла У0.

Таким образом схема даёт возможность сопоставить каждому схемному имени узла совокупность сентенциальных деревьев. Фактически мы имеем в компактной форме КСГ деревьев, когда в левой части правила — изолированный узел помеченный каким-то схемным именем, а в правой части — сед или сид.

Например, от L порождаются два сед (из-за необязательной стрелки): одно - просто S, второе S со стрелкой ';' в L; от S - 12 сед: шесть изолированных узлов (SG, SI...) и шесть этих узлов со стрелкой ':' в LD.

Или-стрелки (в том числе одна как у L) дают возможность задавать сед у которых в корне — нетерминал.

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

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

Построение сид по схеме: Пусть схема полностью поименована. Чтобы получить начальный сед достаточно взять любой узел схемы и создать изолированный узел помеченный схемным именем этого узла схемы.

Пусть дан сед С1 в котором есть узел У1 помеченный каким-то схемным именем. Тогда можно создать сед С2 от узла схемы со схемным именем равным метке У1 и подставить С2 на место У1 в С1.

Если через несколько подстановок в С1 не найдётся узла помеченного словом из MLA+, то мы получили сид.

Свойства схемы: Легко видеть что:

- метка или-стрелки не используется;

- параллельные или-стрелки избыточны;

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

Таким образом без ограничения общности можно считать, что:

- метка или-стрелки, а также узла из которого есть или-стрелка есть пустое слово;

- на схеме нет параллельных или-стрелок.

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

Умеченные семейства

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

И-условие: регулярные множества РВ и-стрелок исходящих из каждого узла не пересекаются между собой.

И-условие легко проверить на схеме. Но его не достаточно, т.к. если из узла У1 есть и и-стрелки и или-стрелки, то к и-стрелкам У1 могут присоединяться и-стрелки из узлов на окончаниях или-стрелок и т.д. Например, по схеме Turingol и-стрелка ":" из S ("метка оператора") может распространиться по всем или-стрелкам на все операторы.

Важнейшим свойством "интересных" схем является наличие на графе циклов. Цикл можно характеризовать типами узлов в него входящими.

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

В случае выполнения условия И-цикла срабатывает простой алгоритм распространения меток и-стрелок по схеме: образуем для каждой и-стрелки пару <схемное имя узла, метка стрелки> и поместим её в узел начала и-стрелки. Каждая такая пара продвигается вдоль всех или-стрелок и "оседает" на и-, а-узлах.

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

Схема Turingol удовлетворяет И-условию и условию И-цикла, т.к. на схеме есть только два цикла с или-стрелками: SC-L-S-SC, SI-S-SI и каждый содержит И-узел (SC, SI соответственно).

Алгоритм распространения даёт: Пары <L,';'>, <S,':'> прибудут в узлы на концах или-стрелок из S, но конфликтов не будет.

Таким образом достаточное условие выполнено и схема задаёт семейство умеченных деревьев.

Ясно, что произвольная схема может порождать экзотические деревья, в том числе бесконечные. В Приложении 1 рассматривается соотношение между схемой и КСГ. В том числе показывается к какому виду надо привести КСГ Turingol, чтобы получить схему.

Общий случай языка программирования

Следуя формулировке exercise 2.4.28, 2.4 Context-free languages [AU-1] имеем: в [Greibach-65] показано, что каждый КС язык порождается грамматикой, все правила которой имеют вид A:aBbC, A:aBb, A:aB, A:a. Если пустая строка принадлежит языку, то допускается правило S:e. Где заглавные буквы обозначают какие-то нетерминалы, строчные буквы (кроме "e") – какие-то терминалы, а "e" – пустую строку.

Легко видеть, что каждому виду правой части можно сопоставить сентенциальное дерево. Записывая граф тройками по количеству стрелок: <начало-стрелки метка-стрелки окончание-стрелки>, получим:

- для первого вида правила: <a '' B>, <a b C>. т.е. "a" – корень и из него идёт стрелка помеченная пустой строкой в "B" и стрелка помеченная "b" в "C".

- для второго: <a b- B>. Здесь "-" после "b" означает, что при линеаризации дерева b должно идти после линеаризации B. Без знака "-" ситуация как раз обратная.

- для третьего: a '' B.

- четвёртое и пятое правила дают атомарные узлы.

Приведённая выше форма КСГ называется стандартной операторной формой (СОФ). Таким образом если грамматику привести к СОФ, то можно будет "механически" перейти к умеченным деревьям. Можно сказать, что теоретически для каждого ЯП существует представление его программ умеченными деревьями. Ясно что таких представлений несколько и некоторые из них наверно будут наглядными, естественными. Лучше всего если о представлении в виде деревьев позаботится ещё Автор языка.

Turingol. Строение программы

К синтаксическому дереву программы существуют требования, описанные далее (ср. WFC в XML).

На хорошем (удовлетворяющем требованиям) синтаксическом дереве программы достраиваются:

- семантическая связь — is-declared-at;

- семантические связи управления — стрелки: next, yes, no;

превращающие сид в граф.

Обозначения: требования поименованы. Требование несоблюдение которого не критично для выполнения программы имеет в своём имени букву W (warning).

В Приложении 2 собраны некоторые способы работы с графами, которые нам понадобятся по ходу дела.

alphabet

Определение: узел объявления слова ленты (w-declaration-point) есть узел в цепи с головой 'tape-alphabet'+is.

Здесь 'tape-alphabet'+is есть "формула пути" (см. Приложение 2) и означает узел на конце стрелки помеченной "is" и исходящей из узла помеченного "tape-alphabet", т.е. предлагается пройти от узла помеченного 'tape-alphabet' по ходу (о чём говорит "+") стрелки помеченной "is".

Определение: узел использования слова ленты (w-usage-point) есть каждый узел print+" а также каждый узел if+''+is+".

Здесь print+" и if+''+is+" есть "формулы пути" (см. Приложение 2).

То что эти пути имеют смысл ("проходимы") легко видеть на схеме.

Требования AW1, AW2, AW3

(AW1) метки во всех w-declaration-point должны быть различны.

Содержательно: не следует объявлять слово ленты многократно. Это скорее всего говорит о небрежности или опечатке.

Алгоритмика. Вар-1 - классический. Проще всего иметь в первом узле накопительный атрибут - множество, заполнять проходом цепи и сообщать о том что очередной уже есть. Вар-2 - по простому. Попав в текущий узел проверять - нет ли его дальше по цепи! Тут ничего копить не надо, но конечно не эффективно... Вар-3 - многопроцессорный. Каждый узел высылает остальным своё имя. Каждое пришедшее имя сравнивает со своим и если найдёт совпадение - выдаёт сообщение.

(AW2) значение метки в каждой w-usage-point должно быть равно метке какой-то w-declaration-point.

Содержательно: каждое используемое программой слово ленты должно быть в ней объявлено.

(AW3) метка каждой w-declaration-point должна быть использована в какой-то w-usage-point.

Содержательно: не следует объявлять слово ленты и не использовать его.

Замечание-1. В примере 4.1 это не так и может быть поводом для warning.

Замечание-2. Требование AW3 порождает вопрос - что мы декларируем в фразе tape-alphabet: состав допустимых слов ленты или состав слов ленты используемых в программе.

is-declared-at для узла использования ленты

Выполнение требования (AW2) даёт возможность провести стрелку "is-declared-at" от w-usage-point к w-declaration-point.

Замечание: эти стрелки не нужны Исполнителю.

В других языках они нужны для дальнейшей обработки.

Метка

Определение: место задания метки (l-target-point) есть любой узел, в который входит стрелка ':'.

Определение: место использования метки (l-usage-point) есть любой узел, в который входит стрелка 'to'.

Требования L1, L2, LW1

(L1) - все метки в l-target-points должны быть различны.

Содержательно: метка должна однозначно идентифицировать свой узел.

(L2) - каждый l-usage-point должен иметь l-target-point с той же меткой.

Содержательно: должна быть возможность перейти к узлу с указанной меткой.

(LW1) - каждая l-target-point должна иметь l-usage-point.

Содержательно: каждая метка должна быть использована. Иначе она бесполезна.

Граф управления

Пусть дан сид.

Слово go, может оказаться ещё и меткой и словом ленты. Введём на сид простейшую классификацию:

Узел данных: это узел поддерева начинающегося с узла 'tape-alphabet'+is, а также узел на конце ":",to,'"'-стрелок.

S-узел: это не узел данных помеченный словом: go, if, print, move, "", "{".

Член L-цепи: в него входит стрелка ";".

Введём также простую классификацию S-узлов: операторы управления это: if, "{", go; остальные назовём - обычные. Это print, move, "".

Выполнив инструкцию в очередном S-узле Исполнитель должен знать куда идти дальше и так до тех пор пока не выполнит директиву Стоп. Для большинства узлов по которым перемещается Исполнитель следующий исполняемый узел один и только один. Из каждого мы проведём семантическую стрелку "next" в следующий исполняемый узел. Исключение составляют только if-узлы: из них будет проведено две стрелки управления: yes, no - аналогично ситуации описанной у Поста [PostM]:

"(B) Perform operation (e) and according as the answer is yes or no correspondingly

follow direction j_i' or j_i",".

Исполнитель начинает в узле alphabet-tape и синтаксически должен уйти по стрелке ";" к первому оператору. Это частая ситуация, когда стрелка управления (next, yes, no) параллельна синтаксической стрелке.

Построение: проведём стрелку next параллельно ";"-стрелке исходящей из узла "alphabet-tape".

Останов программы есть специальное действие, которое в таком языке как Turingol лишь подразумевается, т.е. не имеет явного оператора. Для упрощения строения программы и следуя идеям Поста [PostM], введём специальный дополнительный узел, который будет называться Stop, и в котором на этапе инициализации программы (см. далее) будет размещена директива Стоп.

Построение: создать узел и пометить его словом "stop".

Узлы "tape-alphabet" и "{" имеют в подчинении цепь операторов; узел "if" – один оператор. Для обычного оператора если он последний в L-цепи или подчинён if, то какой оператор выполнять следующим указывается в подчиняющем. При условии, что он сам не является подчинённым. Тогда надо идти к его подчиняющему. Чтобы отразить отношение подчинения проведём вспомогательную стрелку "back".

Построение back-стрелок: В каждой L-цепи из последнего члена проводится стрелка "back" в узел подчиняющий цепь (т.е. в узел "tape-alphabet" или "{"). Из каждого узла подвешенного к "if" по стрелке "then" проводится стрелка "back" в этот "if".

Таким образом, по построению, для каждого S-узла выполнена одна и только одна из ситуаций:

- ситуация back: из него есть стрелка back;

- ситуация ";": из него есть стрелка ";", т.е. оператор есть не последний в L-цепи.

Построение: Перенаправим в узел Stop стрелку back входящую в узел alphabet-tape.

Ниже на рисунке представлен результат построения back-стрелок для примера 4.1.

Построение стрелок управления не зависящих от ситуации back or ";":

Для каждого if-узла параллельно then рисуется стрелка yes.

Для каждого "{"-узла параллельно "}" рисуется стрелка next.

Для каждого S-узла помеченного "go", используя его l-usage-point, рисуется стрелка next к последнему узлу до которого можно подняться по ':'-стрелкам от l-target-point с тем же значением метки что и метка l-usage-point.

Возможность последнего построения обеспечивается выполнением требований L1, L2.

Построение стрелок управления для ситуации ";": т.е. не последнего в L-цепи:

Для обычных операторов ("", print, move) создаётся стрелка next параллельная стрелке ";".

Для оператора if создаётся стрелка "no" параллельная стрелке ";".

Таким образом в ситуации ";" синтаксическая стрелка ";" не используется для построения стрелок next для узлов "go" и "{".

Построение управления для узлов имеющих исходящую стрелку back:

1. пометить все back-стрелки как необработанные.

2. если нет необработанных back-стрелок, то стоп.

3. выделить целиком (на всю длину) необработанную back-цепь. Она либо переходит в ";" (назовём это ситуация next и назовём эту ";"-стрелку - С1) либо завершается в узле Stop (назовём это ситуация Стоп).

Из каждого обычного узла back-цепи, имеющего исходящую стрелку back, рисуется стрелка next, а из узла if рисуется стрелка no. Эта стрелка:

если ситуация next, то рисуется туда же куда входит и С1;

если ситуация Стоп, то рисуется в узел Stop.

Все стрелки back-цепи помечаются как обработанные. Идти на 2.

Мы получили граф управления. Именно по нему перемещается Исполнитель, выполняя программу.

Граф управления построен на S-узлах, узле "alphabet-tape", который является стартовым узлом и узле Stop. Тем самым он построен на "синтаксических узлах" (плюс узел Stop) и по исходящим стрелкам устроен просто:

- из каждого S-узла (кроме if) и из узла "alphabet-tape" выходит одна и только одна стрелка next.

- из каждого if-узла выходит одна и только одна стрелка "yes" и одна и только одна стрелка "no".

На рисунке приведённом ниже, и соответствующем примеру 4.1, стрелки управления параллельные синтаксическим стрелкам не нарисованы, но соответствующие синтаксические стрелки нарисованы жирными. Метку соответствующей стрелки управления легко восстановить. Так стрелке ";" из "if" в 4-ой строке конечно соответствует "no".

Требования CW1, C2

Идея управления порождает естественное требование:

(CW1) достижимость из "alphabet-tape" по графу управления любого S-узла программы.

Например: Если внутри L-цепи находится узел go, то узел на окончании исходящей из него ";"-стрелки должен иметь метку, иначе он недостижим. См., например, в 4.1 ";"-стрелку из go в третьей строке.

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

Требование (C2): next стрелки не должны образовывать цикл.

В том числе goto не должен указывать на самого себя. Заметим, что C2 не является следствием CW1, так в узел может входить несколько стрелок управления.

Заключение

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

Связи is-declared-at, back, next, yes, no, а также узел Stop нужны в большинстве языков программирования.

Нужны ли ещё какие-то связи есть предмет текущего исследования, в котором рассматривается Standard Pascal [SP]. Одна из кандидатов - связь "has-type" для языков с типами данных.

Граф управления проще "странслировать" в машину Поста чем машину Тьюринга.

Данные. Лента

Лента есть конечная цепь узлов помеченных словами. Стрелки помечены пустым словом.

Конечность ленты приводит к необходимости её достройки, если понадобится сделать шаг влево или вправо к узлу которого нет. Это делается по мере необходимости. Узел и стрелка при создании метятся пустым словом.

Замечание: конечно эта лента не является лентой машины Тьюринга, т.к.:

- содержит в ячейках слова, а не буквы;

- является конечной (см. [PostM] p.105, о возможных "улучшениях" ленты.).

Являясь "синтаксической" конструкцией семейство лент может быть описано формально в дополнение к грамматике языка:

T::=I| I T

где I - нетерминал для идентификатора (см. Приложение 1).

Фактически при описании языка должно быть два стартовых символа: для программы и для внешних данных.

Действия с лентой

Исполнитель будет:

- сравнивать метки некоторых узлов программы и узлов ленты;

- заносить метки некоторых узлов программы на узлы ленты;

- наращивать ленту.

Наращивание ленты основано на следующих ситуациях и действиях.

Пусть У1 именует корень ленты.

Тогда в результате выполнения директивы "Создать узел и стрелку из него в узел У1." (см. "Приложение 2") мы опять получим ленту. С новым корнем и стрелкой из него в старый корень.

Пусть У2 именует последний узел ленты ленты.

Тогда в результате выполнения директивы "Создать узел и стрелку в него из узла У1." (см. "Приложение 2") мы опять получим ленту. С новым последним узлом.

Заключение

Лента с которой работает программа Turingol является прообразом файла ЯП и техника представления в виде цепи может быть применена и к файлу.

Инициализация

На этапе инициализации:

- создаётся стрелка "tape" из узла "tape-alphabet" в некоторый узел ленты, с которой должна начать работать программа. Узел ленты в который входит стрелка tape называется текущим узлом ленты.

Обычно при написании программы предполагается, что "после открытия" текущий узел — первый узел ленты. Но, например, для программы примера 4.1 начальным текущим должен быть последний узел ленты.

Кроме того в некоторые узлы программы заносятся инструкции для Исполнителя. Расположение инструкций в узлах аналогично подходу Поста [PostM], правда у него программа состоит из нумерованных строк и есть переход по номеру, а у нас – из узлов и есть переход по стрелке.

Замечание: Эти инструкции можно приписывать узлам схемы как атрибут и копировать в сид ещё на стадии построения.

Инструкции в узлах

Далее даются инструкции для S-узлов с той или иной меткой, для начального узла "tape-alphabet" и узла Stop. У остальных узлов инструкций нет.

Для узлов с меткой "move" существуют два варианта инструкции.

Важно подчеркнуть, что по характеру операций выполняемых в инструкциях мы работаем с помеченными графами, меняя метки узлов, создавая узлы и стрелки, переназначая окончание стрелки tape. Если терминология не ясна интуитивно, она более точно описана в Приложении 2.

Узел "tape-alphabet"