Если вам понравился Fact, если вы хотите не только использовать его, но и развивать его возможности, я буду рад любым предложениям, а чтобы облегчить ваш труд и избавить себя от лишних вопросов я написал это краткое введение в устройство моего интерпретатора Fact.

Присылайте ваши примеры

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

Все авторы буду упомянуты.

Желающим развивать Fact

Взгляд с высоты птичьего полёта

Fact написан на Python 2.4 (так же успешно протестирован на 2.5 и 2.6a0).

Программа обрабатывается в три шага:

token_list = TokenSeq() # 1. разбиение на токены
token_list = load(text) #    и отсечение комментариев
code=Prog()             # 2. компиляция во внутреннее
code=load(token_list)   #    представление (последовательность
                        #    классов операций)
code.execute(context)   # 3. выполнение программы в заданном
                        #    контексте

Метод load класса TokenSeq осуществляет синтаксический разбор. Метод load класса Prog — лексический.

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

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

Лексический анализатор анализирует LL(1) (Left to right, Leftmost derivation, 1 tokens of look-ahead; http://en.wikipedia.org/wiki/LL_parser) язык, грамматика языка такова, что становится возможным анализ в один линейный проход. Такое упрощение становится возможном благодаря двум обстоятельствам.

Синтаксис языка таков, что по первому токену в выражении всегда можно определить количество токенов в выражении.
Разбор идёт методом рекурсивного нисходящего синтаксического анализа (рекурсивный спуск), но токены, закрывающие блоки, обрабатываются на стороне вызываемого обработчика, а не вызывающего. Это позволяет отказаться от «забегания вперёд».

Кстати из этих двух правил следует невозможность использования закрывающих блок конструкций, состоящих из нескольких токенов. То есть, на пример, в рамках этих правил не возможны конструкции типа case или elseif. Это заметное ограничение, но я не считаю его фатальными. В конце концов, эту функциональность можно реализовать вложенными if.

Есть изменения, кажущиеся необходимыми, но на самом деле нежелательные.

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

Упрощение лексического анализатора возможно потому, что все «фразы» имеют определённую длину, однозначно определяемую по первому токену. Это накладывает существенные ограничения на возможные языковые конструкции, но пока я не вижу оснований переходить на более выразительную лексику и идти на усложнение анализатора.

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

Структура классов

Единицей Fact-программы является токен. Объекты класса Token хранят значение токена и строку в программе, где он находился. Большинство методов работают именно с токенами, а не с их значениями, получение значения токена происходит только в классе Context (см. ниже). Это позволяет практически на любом уровне генерировать исключения с указанием не только значения токена, но и строки программы в которой этот токен находится.

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

Текущая реализация такова, что после загрузки из файла, последовательность токенов может быть выдана только один раз. Эта «ущербность» может быть легко устранена, но пока я не вижу на то оснований, так как грамматическому анализатору последовательность токенов требуется только один раз.

Класс системы координат, Orts, хранит характеристики системы координат и умеет оперировать с ними. Он умеет делать только геометрические преобразования и никак не связан с остальным функционалом.

Этот класс умеет делать собственную копию. То есть создавать новый экземпляр, инициализируя его параметрами заданного экземпляра.

Класс Prog компилирует последовательность токенов (TokenSeq) в последовательность классов команд и умеет исполнять последовательность. Исполнение происходит линейно (команды выполняются одна за другой без ветвлений, переходов и прочего; однако, команда может содержать блок операторов).

Все классы команд (Ex*) Построены по единой схеме:

Они так или иначе наследуются от класса ExCommon, который содержит общий метод execute. Этот метод анализирует, не было прервано исполнение программы и вызывает метод action, который выполняет действия, специфичные для данной команды.
Универсальный конструктор (в классе ExCommon) вызывает два виртуальных метода: eat_args и eat_block. Первый загружает аргументы команды, второй — блок команд, относящихся к этой команде.
Все действия выполняются на уровне токенов. При выполнении команде передаётся контекст (класс Context), внутри которого и происходят разыменования токенов.

Классы, управляющие порядком выполнения программы (условные переходы, вызов подпрограмм, локализация контекста) хранят отдельные экземпляры класса Prog, кодирующие соответствующие действия.

Структура классов операций такова:

ExCommon . . . . . . . . базовый
|
+-- ExCommon1 . . . . .  операции с одним аргументом
|   |
|   +-- ExScale  . . . . масштабирование
|   +-- ExSetWidth  . .  установка толщины линии
|   +-- ExCallSub  . . . вызов подпрограммы
|
+-- ExCommon2 . . . . .  операции с двумя аргументами
|   |
|   +-- ExSetVar . . . . присвоение значения
|   +-- ExIncrVar . . .  прибавление
|   +-- ExMulVar . . . . домножение
|
+-- ExShift . . . . . .  сдвиг
|   |
|   +-- ExDraw . . . . . сдвиг с отрисовкой
|
+-- ExRotate  . . . . .  поворот
|   |
|   +-- ExRight  . . . . по часовой
|   +-- ExLeft  . . . .  против часовой
|
+-- ExSetColor . . . . . установка цвета
|   |
|   +-- ExSetBGColor  .  установка цвета фона
|
+-- ExCommonCode . . . . базовый для всех блочных операций
|   |
|   +-- ExLocal . . . .  локализация
|   +-- ExSave . . . . . локализация только переменных
|   +-- ExTransform . .  локализация только трансформаций
|   +-- ExDefSub . . . . определение подпрограммы
|   +-- ExRepeat  . . .  повторение в цикле
|
+-- ExCondition  . . . . условия
+-- ExDump  . . . . . .  остановка с дампом
+-- ExUpdateWindow . . . отрисовка промежуточного состояния

Контейнер контекста — класс Context — содержит контекст выполнения программы: функции, переменные, флаги, текущую систему координат.

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

Экземпляры класса Context могут использоваться как словари. Каждому токену (именно экземпляру класса Token, а не значению токена) ставится в соответствие его значение. Если имеется переменная с соответствующим именем, то возвращается её значение, если таковой нет, то значение самого токена приводится к типу float и возвращается. Исключения обрабатываются (см. ниже). Этот механизм используется для разыменования токенов.

Все вышеперечисленные классы имеют корректные методы __repr__, что существенно упрощает отладку.

Остальные классы не отвечают за выполнение программы.

Класс Window предназначен исключительно для инициализации окна.

Класс Conva отвечает за отображение элементов.

Класс Application отвечает за функционирование элементов пользовательского интерфейса.

Так же имеются классы исключений:

TokenException — не верный токен, обнаруженный в момент компиляции.
TokenRunTimeException(TokenException) — не верный токен, обнаруженный в момент исполнения (токен не удалось интерпретировать как число, и переменной с таким именем нет).
SubroutineException(TokenRunTimeException) — процедуры с таким именем нет.
InfoException — информационное прерывание: пользователю выводятся значения переменных.

Надеюсь, после этого краткого введения вам будет очень легко читать и развивать код.

TODO

Есть ряд изменений и «улучшений», которые я не сделал по двум причинам: либо я не уверен в их целесообразности, либо у меня возникли затруднения.

Если вы предложите улучшенную версию этих улучшений или сумеете разрешить вопросы с которыми я испытываю затруднения, я буду крайне признателен.

Улучшения, которые я не очень понимаю как сделать

Логику класса Orts наверно следует переписать с использованием комплексных чисел. У меня есть предположение, что это повысит производительность и добавит изящества.
Сейчас размер окна можно изменять только в меню. Это, конечно, не обычное поведение. Но я пробовал дать пользователю возможность произвольно изменять размер окна. Получается не красиво, так как получаются не квадратные окна. Сейчас поддержана и ширина и высота окна (они всегда равны).

В версии 2.3 я сделал окно изменяемым. Вроде получилось не плохо, но я оставил для скачивания обе версии: с изменяемым и не изменяемым окном.

Возможно из-за ошибки в библиотеке Tk, PostScript-файлы сохранятся с небольшими полями. Мне так и не удалось понять, является ли это моей ошибкой, ошибкой реализации Tk или ошибкой в gv.
Некоторые реализации Tk (например под Windows) не вычерчивают линию, если её толщина меньше одного пикселя. То есть логически линия существует, в PostScript она сохраняется корректно, но на экране не отображается. Решение «принудительно вычерчивать линии не тоньше одного пикселя» не годится, так как это приводит к заметным искажение рисунка в PostScript. Возможно надо ввести несколько режимов отображения или что-то в этом духе. У меня пока нет окончательного решения.

Неточности и небрежности

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