note000.txt

  Цель лабы. Написать прототип компилятора Рефал -> Си++. Ставится задача толь-
ко исследовать компиляцию функций на Рефале в код на Си++. При этом такие зада-
чи, как обеспечение продвинутой модульности, концептуальной целостности языка и 
др. не ставятся. Достаточно обеспечить модульность (модель компоновки) языка Си
(все имена функций должны быть объявлены перед первым использованием, функции из
других единиц компоновки должны быть объявлены как extern, локальные функции со-
ответствуют статическим функциям языка Си, глобальные -- нестатическим). Доста-
точно, чтобы язык поддерживал 3 вида атомов: ascii-символы, макроцифры (перепол-
нение для простоты не проверяется), имена функций. Т.к. все функции сначала дол-
жны быть объявлены, имена функций, которые используются только как флаги, должны
быть объявлены как empty (как в Рефале-2). При этом раз уж имена соответствуют
фунциям, пускай одноимённые локальные функции разных единиц трансляции при срав-
нении на равенство (использование одноимённых переменных) являются неравными
друг другу (в отличие от Рефала-2 и Рефала-7, в которых равенство двух имён оп-
ределяется их именами). Встроенных функций нет, все функции, которые используют-
ся в программе, или объявлены в текущей единице трансляции, или являются внешни-
ми. Таких полезных расширений как абстрактные типы данных, не будет. Используе-
мое подмножество Рефала -- базисный Рефал.
  Поскольку, несмотря на ограничения, язык будет достаточно продвинутым, будет
вестись разработка самокомпилятора. Поэтому сначала язык будет реализован как
препроцессор, переводящий этот Рефал (назовём его Simple Refal), в Модульный
Рефал, который будет написан конечно же на Модульнолм Рефале.
  В дальнейшем, в случае удачной разработки, сам Модульный Рефал может использо-
вать этот язык как back-end для получения готовых .exe-шников.

  Результаты.

  [1] В процессе лабы были разработаны следующие программы.

  * srprep -- препроцессор, переводящий код на Простом Рефале в код на Модуль-
ном Рефале. Написан на Модульном Рефале. Проблема несоответствия модульностей
Простого и Модульного Рефалов решалась также, как и в программе Refal5-to-
MRefal converter, использовавшейся для конверсии исходников Модульного Рефала
с Рефала 5 на Модульный Рефал. А именно, использовались особого вида коммен-
тарии перед директивами $EXTERN. Однако в отличие от уже упоминавшейся програм-
мы Refal5-to-MRefal converter, препроцессор осуществляет полексемное, а не по-
строчное препроцессирование. Как и в случае с переходом Рефал 5 -> Модульный
Рефал, эти же комментарии использовались и для использования в утилите make
(см. ниже).
  Препроцессор, в отличие от полноценного компилятора сам проверял только огра-
ниченный класс ошибок: требовал, чтобы описание имени предшествовало его испо-
льзованию. Более полная проверка не выполнялась, поскольку дальнейшую проверку
выполнял сам компилятор Модульного Рефала. Для того, чтобы сделать сообщения о
синтаксических ошибках, выдаваемых компилятором, более адекватными, препроцес-
сор лексемы в выходном файле располагал на тех же строчках, что и в исходном
файле.

  * srmake -- программа, облегчающая сборку проектов на Простом Рефале. Данная
программа для простоты не проверяла время последнего изменения входного и выход-
ного файлов. Как уже было сказано, программа пользовалась особыми комментариями
('//FROM ИмяФайла') для поиска зависимых файлов.

  * LexGen -- генератор лексического анализатора. На входе программа принимала
описание конечного преобразователя (автомата Мили, т.к. действия выполнялись
при переходе в новое состояние), на выходе создавался сам конечный автомат.
  Синтаксис лексического анализатора следующий:

   Description = Element* .
   Element = SetDescr | Sentence .

   SetDescr = SETNAME '=' Set* '.' .
   Set = LITERAL | SETNAME .

   Sentence = NAME '=' Alternative { '|' Alternative } '.' .
   Alternative = [Set] [Flush] [NAME] .
   Flush = '!-' | NAMEDFLUSH | ERRORFLUSH .

   SETNAME = ':' строчная-или-прописная-буква-или-цифра* ':' .
   LITERAL = "'" последовательность-символов-с-escape-последо-
   вательностями '"' .
   NAME = идентификатор-Рефада .
   NAMEDFLUSH = '!' идентификатор-Рефала .
   ERRORFLUSH = '!"' строка-сообщение '"' .

  Модель вычислений конечного преобразователя следующая. Конечный преобразова-
тель может находиться в одном из нескольких состояний. Кроме того преобразова-
тель содержит буфер символов, в конец которого он может добавить символ, сбро-
сить его содержимое в выходной поток или опустошить его. Находясь в некотором
состоянии конечный преобразователь считывает или не считывает очередной символ
из входного потока, если считывает, то обязательно добавляет в конец буфера,
производит действие над буфером (буфер может быть опустошён с выдачей или не-
выдачей содержимого в выходной поток) и переходит в другое состояние.
  В некоторых случаях преобразователь может ожидать конец ввода.
  Программа для конечного автомата состоит из набора предложений и описаний
множеств. Предложение содержит слева от знака равенства имя текущего состояния,
слева -- набор альтернатив, что делает его внешне похожим на БНФ. Альтернатива
состоит из множества входных символов, которые можно считать, действия с буфе-
ром и нового состояния. Каждый из компонентов альтернативы может отсутствовать.
Если множество символов указано и текущий символ существует (т.е. не конец
ввода) попадает в это множество, то выполняется данная альтернатива и символ
считывается. Если же множество отсутствует, но присутствует следующее состояние,
то данная альтернатива также активизируется, при этом входной символ не считы-
вается -- входной поток не изменяется. При активации альтернативы если символ
считывается, то он добавляется в конец буфера. Действие может отсутствовать (в
этом случае с буфером ничего не происходит), может быть операцией безымянного
сброса (в этом случае буфер опустошается), может быть именованным сбросом (в
этом случае содержимое выбрасывается с данным именем -- формат выражения
(s.Name e.Content), где s.Name -- идентификатор -- имя сброса (в случае Просто-
го Рефала -- имя функции), e.Content -- содержимое буфера в данный момент,
включая считанный символ. Если действие -- сброс-сообщение об ошбике, то в
выходной поток выводится зарезервированная лексема TokenError.
  Альтернативы проверяются по очереди одна за другой. Если же ни одна альтерна-
тива не сработала, то срабатывают дефолтовые обработчики -- если не было конца
ввода, то выбрасывается неожиданный символ TokenUnexpected, перед ним содержимое
буфера как лексема TokenAccum, если же обнаружевается конец файла, то вместо
TokenUnexpected выбрасывается TokenUnexpectedEOF.
  Множество в начале альтернативы можно задать двумя способами -- как множество
явно перечисленных символов, так и как именованное множество. Объявление имено-
ванного множества состоит из имени множества, знака равенства и перечисления
входящих в него множеств. Объявление множества, как и предложение автомата,
завершается точкой. Содержимое множества представляет собой объединение мно-
жеств, перечисленных справа от знака равно. Поэтому допустима рекурсивная
зависимость множеств. Именованные множества позволяют не только сократить опи-
сания предложений, но и повысить ясность программы.
  Также есть особое именованное множество :Any:, которое включает в себя все
возможные символы.
  По соглашению, автомат начинает свою работу с состояния Root с пустым буфе-
ром.

  Описание автомата располагается внутри сишного комментария, который должен
начинаться с новой строки строкой '/*GEN:TOKENS' и завершается строкой (тоже
в отдельной строке) 'GEN:END*/'. Код автомата генерируется сразу же после
этого комментария и до конца файла. Если же между последней строчкой коммента-
рия и концом файла находился какой-либо текст, то этот текст удаляется.

  Не смотря на некоторую примитивность как синтаксиса, так и семантики автома-
та, его оказалось вполне достаточно для распознавания таких сложных конструк-
тов, как комментарии Си/Си++ и строки с escape-последовательностями. К недос-
таткам следует отнести то, что отсутствие любого члена альтернативы приводит
к сложностям как кода парсера автомата, так и собственно описания лексики.
Чтобы сделать заметным наличие/отсутствие элементов альтернатив, приходится
явно форматировать текст в виде таблицы (что я делать не люблю). Было бы удоб-
нее, если бы вместо отуствующих элементов использовались специальные символы
или ключевые слова.
  Другим недостатком является то, что сгенерированный код является достаточно
объёмным, т.к. результатом генерации являются функции Рефала, соответствующие
состояниям, каждое предложение которых соответствует переходу по некоторому
символу. Вероятно, код был бы компактнее, если бы вместо сравнения очередного
символа с явно заданным литералом осуществлялся бы поиск по открытой e-пере-
менной внутри отдельного множества. Относительно быстродействия трудно ска-
зать что-либо конкретное по поводу того или иного варианта. Как правило, апри-
ори (без профилирования) трудно определить оптимальность решения, особенно
для такого языка как Рефал.

  * srefc -- собственно, сам компилятор языка. О нём далее будет сказано доста-
точно подробно.

  [2] Было опробовано несколько методов лексического анализа.

  (2.1) Лексический анализ в препроцессоре.
  Можно подметить, что большинство лексем можно представить или как начинающиеся
с символа из некоторого множества (голова) и состоящих из некоторого (возможно,
нулевого) количества символов из другого множества (хвост), или как начинающего-
ся с символа из некоторого множества, для которого требуется особая обработка
хвоста. Например к первому типу относятся имена (начинаются с заглавной латин-
ской и состоят из букв, цифр, дефиса и подчёркивания), числа (головное и хвос-
товое множества совпадают и состоят из цифр), директивы (начинаются с $ и сос-
тоят из латинских букв), свободное пространство (начинаются и состоят из пробе-
лов, табуляций и новых строк). Ко второму типу относятся все остальные: перемен-
ные начинаются с букв 's', 'e', 't', знаки препинания хвоста не имеют, оба типа
комментариев начинаются с '/' (Простой Рефал не поддерживает старых рефальных
комментариев).
  Лексемы первого типа может потребовать после себя некоторой процедуры обработ-
ки (например, директива может провериться на корректность), лексемы второго типа
просто требуют определённой обработки. Поэтому в принципе можно построить табли-
цу лексем, которая будет затем интерпретироваться. Таблица в принципе будет со-
держать различные процедуры обработки. Приведу эту таблицу.

BaseTokens {
  = (EOF);

  e.Text =
    <SwBaseTokens
      ( <Default Number> ( <Types::Digits> ) <Types::Digits> )
      ( <Default Space> (' \n\t') ' \n\t' )
      ( <Default Punctuation> ('();{},=<>') )
      ( & FinishName
        (<Types::UpAlph>) <Types::UpAlph> <Types::LoAlph> <Types::Digits> '_-'
      )
      ( & FinishComment ('/') )
      ( & FinishLiteral ('\'') )
      ( & FinishDirective ('$') <Types::UpAlph> )
      ( & FinishVariable ('set') )
      ( e.Text )
    >;
}

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

  (2.2) Лексический анализ в генераторе автомата.
  Лексика описания автомата была сделана достаточно простой: из сложных конст-
рукций были только имена состояний, имена множеств, сбросы и литералы множеств
с escape-последовательностями. Имена состояний соответствовали правилам языка
Рефал для идентификаторов, имена множеств -- набор букв и цифр, окружённых с
обоих сторон двоеточиями, имена сбросов начинались с восклицательного знака, за
которым следовал идентификатор Рефала для именованного сброса, текст в двойных
кавычках для сообщения об ошибке или дефис для безымянного сброса. Лексический
анализатор в целом был построен по традиционной схеме с незначительным новшест-
вом. Дело в том, что для некоторых альтернатив после прочитанной части цепочки
выбор зависит от того, принадлежит ли следующий символ некоторому множеству. Эта
идея развилась в использование функции NextInSet, которая в случае принадлежнос-
ти сдедующего символа множеству вызывает один обработчик, в противном случае --
другой.

NextInSet {
  s.SuccessHandler s.FailHandler
  (e.Set-B s.Next e.Set-E) (e.Scanned) s.Next e.Text =
    <s.SuccessHandler (e.Scanned s.Next) e.Text>;

  s.SuccessHandler s.FailHandler (e.Set) (e.Scanned) e.Text =
    <s.FailHandler (e.Scanned) e.Text>;
}

  Обработчики s.SuccessHandler и s.FailHandler также могут вызывать функцию
NextInSet рекурсивно. Пример.

LoTokens {
  // ...
  '!' e.Text = <FlushName e.Text>;
  // ...
}

FlushName {
  '-' e.Text = (TFlush) <LoTokens e.Text>;

  '"' e.Text =
    <NextInSet
      ErrorFlush ErrorFlushFail
      (<NameTailSet> ' \t,.:;(){}[]*&')
      () e.Text
    >;

  e.Text =
    <NextInSet
      FlushNameTail FlushNameFail
      (<HiLetters>) () e.Text
    >;
}

ErrorFlush {
  (e.Scanned) e.Tail =
    <NextInSet
      ErrorFlush ErrorFlushFail
      (<NameTailSet> ' \t,.:;(){}[]*&')
      (e.Scanned) e.Tail
    >;
}

ErrorFlushFail {
  (e.Scanned) '"' e.Text =
    (TErrorFlush e.Scanned) <LoTokens e.Text>;

  (e.Scanned) s.Other e.Text =
    (TError 'Expected error text or "') <LoTokens e.Text>;
}

FlushNameFail {
  () e.Text = (TError 'expected flush name');
}

EndFlushName {
  (e.Scanned) e.Text = (TNamedFlush e.Scanned) <LoTokens e.Text>;
}

FlushNameTail {
  (e.Scanned) e.Tail =
    <NextInSet
      FlushNameTail EndFlushName
      ( <NameTailSet> ) (e.Scanned) e.Tail
    >;
}

  При обработке сброса-ошибки в случае s.SuccessHandler продолжает ввод симво-
лов, s.FailHandler проверяет, является ли следующий символ кавычками. Аналогич-
но функция FlushNameTail рекурсивно вызывает себя в случае успеха и завершает
ввод имени при неуспехе.

  (2.3) Использование генератора лексического анализатора.
  Третий способ применён в самом компиляторе Простого Рефала. Об устройстве ге-
нератора автомата я достаточно подробно написал выше. Основное отличие этого
способа от двух других в том, что пользователь пишет не сам код, а таблицу авто-
мата. Третий способ близок к первому, т.к. лексика задаётся средствами более вы-
сокого уровня, чем код.
  Не смотря на то, что дефолтовые обработчики в автомате предусмотрены (на слу-
чай, когда ни одна альтернатива не выполнима), я старался программировать авто-
мат так, чтобы до этих обработчиков дело не доходило.
  Однако, после распознавания лексики автоматом, проходила дополнительная вто-
ричная обработка лексем. В частности, автомат в поток лексем добавлял переводы
строки -- они нужны были только для добавления номеров строк в лексемы, на выход
они не попадали, все знаки пунктуации выбрасывались как (TkPunctuation s.Sign),
в дальнейшем они превращались в различные лексемы.

  (2.4) Лексический анализ Модульного Рефала (версия 0.1.953).
  Приведу для сравнения метод лексического анализа в самом Модульном Рефале.
В Модульном Рефале лексический анализ идёт по классической схеме без использова-
ния функций высших порядков. Модуль лексического анализа был написан довольно
давно, в те времена я обладал навыками программирования только в процедурных и
ОО-языках (в основном C++). Поэтому я реализовывал лексический анализатор по
схеме с использованием АТД: создаётся абстрактный тип сканера, который по сооб-
щению NextToken возвращает очередную лексему. Сам сканер, в свою очередь, для
получения исходного текста, создаёт и использует другой АТД -- символьный поток
(SymStream), инкапсулирующий в себе способ чтения данных из файла и подсчёт но-
меров строк.
  В целях упрощения работы с определёнными множествами символов (например, сим-
волы хвоста имени -- буквы, цифры, '-', '_', '?', '!'), класс потока символов
имеет методы для извлечения последовательности символов из некоторого множества.
  Сам класс потока символов содержит в себе дескриптор файла и читает файл пос-
трочно, по мере необходимости.
  Подобная архитектура (класс сканера по запросу читает лексемы, класс потока
символов по запросу читает очередные строчки файла), в отличие от первых трёх
методов, никогда не загружает файл или лексическую свёртку в память целиком.
За счёт этого Модульный Рефал может сравнительно безболезненно (т.е. не считая
потерянного времени) обработать модуль, содержащий 100 Мб пустых строк или 100
Мб пустых строк с точками с запятой (что является допустимой декларацией внутри
модуля) -- лишней памяти при этом не потребуется. Однако, эта архитектура слож-
нее, чем если бы весь исходный текст и/или вся лексическая свёртка загружались
бы в память.

  (2.5) Сравнение разных способов.
  Наиболее удобным мне показались первый и третий способы: первый способ соче-
тает достаточную наглядность с лаконичностью кода, третий способ более гибок и
высокоуровнев. К недостаткам первого способа можно отнести то, что он в какой-то
степени ориентирован на интерпретацию таблицы (для поиска символа требуется
двухуровневая итерация по открытым e-переменным), а значит, возможно, менее эф-
фективен. Недостатком третьего способа является то, что код, порождаемый в резу-
льтате, получается очень длинным. Число предложений в каждой функции-состоянии
линейно зависит от мощности объединения множеств в каждой из альтернатив. Сгене-
рированный код не содержит открытых e-переменных, по этому в принципе он мог бы
быть достаточно эффективным. Мог бы. Но поскольку генератор кода компилятора все
предложения функции обрабатывает независимо, приходится каждый раз распознавать
один и тот же формат типа (e.Accum) '3' e.Text. Если бы компилятор умел бы выво-
дить общий формат для нескольких соседних предложений и в случае образцов со
сходной структурой мог бы общий код "вынести за скобки", автомат был бы доста-
точно эффективен.
  Второй вариант тоже достаточно неплох, т.к. позволяет сократить исходный код,
вынося общий код поиска во множестве в отдельную функцию. Но метод не эффекти-
вен: как можно заметить по ряду функций, множества каждый раз необходимо загру-
жать заново, т.к. в функции-обработчики множества не передаются.
  Метод с генератором лексического анализатора можно скомбинировать методом лек-
сического анализа Модульного Рефала -- используя тот же формат описания таблицы
переходов, можно создавать код, читающий лексемы последовательно из файла. Таким
образом можно объединить достоинства обоих методов: высокоуровневое описание ле-
ксем и экономию памяти.

  [3] Особенности компилятора.
  В данной лабе при построении компилятора я опробовал для себя несколько новых
приёмов. В частности, использован трёхуровневый упрощённый алгоритм разбора и
независимая генерация различных элементов кода. Для генерации отдельных предло-
жений создавался абстрактный алгоритм (для каждого предложения) в виде последо-
вательности императивных команд. Затем этот алгоритм уже преобразовывался в
код, причём отдельные команды генерировались почти независимо друг от друга.
  Сам компилятор остался недоделанным для готового продукта, но для прототипа
он достаточно хорош. Из некоторых возможностей, которые надо было реализовать
или переделать: поддержка стандартных библиотечных каталогов -- в текущей вер-
сии все пути к файлам указываются или как абсолютные, или как относительные от
текущей папки; возможность выбора сишного компилятора -- в текущей версии про-
грамма вызывает программу call_cpp_compiler, который оказывается батником в те-
кущей папке; поддержка арифметики хотя бы на среднем уровне; поддержка escape-
последовательностей в сгенерированном коде (с hex-символами вида \xNN); провер-
ки на переполнение в целочисленных операциях и многое другое.

  (3.1) Краткий обзор языка.
  Данный диалект является практически подмножеством Базисного Рефала: все функ-
ции представляют собой пары предложений Образец = Результат, термами являются
только атомы и обычные скобочные структуры (т.е. абстрактных типов данных, ко-
торые суть именованные скобки, здесь нет). Множество атомов включает в себя
символы (characters), целые беззнаковые числа от 0 до 2**32-1 (макроцифрами они
не являются), функции и дескрипторы файлов, которые могут создаваться только
функцией FOpen.
  Коротко о числах. Целые числа не интерпретируются как макроцифры некоторого
неограниченно длинного числа, т.к. библиотечные функции Add и Sub имеют формат
<s.Func s.Num1 s.Num2> == s.Res, т.е. поддерживают только аргумент из двух ато-
мов (которые должны быть числами) и возвращают целочисленный результат в виде
одного символа. Если бы числа интерпретировались как макроцифры, то библиотечные
функции работали бы с цепочками чисел. Кстати вся арифметика в данном диалекте
ограничена только парой функций Add и Sub. Для преобразования число <---> стро-
ка используются отдельные примитивные функции. Ограничение связано с тем, что
Модульный Рефал также ограничен этой парой функций и в процессе работы над этой
лабой расширять его не хотелось.
  Функции упорядочевания двух символов также не было представлено, поэтому не
удалось реализовать корректную поддержку escape-последовательностей. Хотя для
прототипа это не так важно.
  Изображением функционального атома в программе является имя самой функции,
при чём это имя в программе должно быть определено. Локальных и лямбда функций
в языке нет, все функции должны быть описаны статически в глобальном простран-
стве имён. Все функции, которые присутствуют в единице трансляции (Модулей в
смысле Паскаля или Модулы в языке нет. Разделение программы на несколько различ-
ных файлов исходных текстов соответствует понятию единицы трансляции -- реликту,
впервые появившемуся в Фортране (язык поддерживал раздельную трансляцию, за счёт
чего на Фортране было написано много библиотек, некоторые из которых используют-
ся и по сей день) и затем сохранившемуся в Си и Си++.) делятся на два класса:
локальные и entry-фукции. Эти классы соответствуют функциям со статической и
внешней компоновкой языков Си/Си++.
  Для доступа к функциям из другой единицы трансляции используется директива
$EXTERN, которая соответствует одноимённому классу памяти в Си/Си++. В програм-
мировании на Рефале часто используются символические имена, имеющие смысл ско-
рее флагов, нежели функций, которые можно вызвать. Многие (кроме Рефала 2 и
Простого Рефала) имеется встроенная поддержка таких символических имён -- атомы
соответствующего типа называются идентификаторами или метками (в литературе
встречал разные названия). Простой Рефал не содержит подобного типа атомов. Для
их имитации используются функции. Очевидно, что если функция создана ради ис-
пользования только как имени, то тело этой функции никогда не будет (во всяком
случае не должно) вызываться. Такую функцию можно определить как пустую функцию,
т.к. пустая функция при любом аргументе вызывает дамп (что гарантирует останов-
ку программы в случае (случайного) запуска этой функции). Для скорописи подобных
функций в языке имеются директивы $ENUM и $EENUM. Обе функции принимают список
имён, разделённых запятыми. Указание имени функции в списке $ENUM эквивалентно
её объявлению как пустой локальной, указание в списке $EENUM -- как пустой ent-
ry-функции (eenum -- entry enum). Для объявления подобных функций я не стал ис-
пользовать директиву $EMPTY (по аналогии с Рефалом 2), т.к. слово enum больше
соответствует их предназачению -- представление символических имён -- как и
перечисления (enum) в таких языках как C++, C#, Visual Basic.
  Функции сравниваются (путём одноимённых переменных, а не в смысле функции упо-
рядочевания, которой нет) по адресам функций в смысле языка Си, а не по их име-
нам (в отличие от Рефала 2 и Рефала 7, в которых имена представляют функции и
функции сравниваются по строковому представлению их имени). Поэтому символичес-
кие имена, созданные в некоторой единице трансляции при помощи $EENUM, приходит-
ся импортировать при помощи директивы $EXTERN. Однако, атомы-функции, тем не ме-
нее содержат строковое представление имени -- это сделано в отладочных целях,
т.к. разобрать дамп поля зрения с шестнадцатиричными адресами функций крайне
сложно.
  Синтаксис схож с синтаксисом Рефала 5 с тем отличием, что допустимы пустые
функции (типа F { }) и существуют директивы $ENUM и $EENUM. Вот синтаксис в
РБНФ:

    TranslationUnit = Element* .

    Element =
      '$ENUM' NameList |
      '$EENUM' NameList |
      '$EXTERN' NameList |
      '$ENTRY' Function |
      Function .

    NameList = Name ',' NameList | Name ';' .
  
    Function =
      Name '{' Sentence* '}'

    Sentence = Pattern '=' Result ';' .

    Pattern = PatternTerm* .

    PatternTerm = Char | '(' Pattern ')' | Number | Name | Variable .

    Result = ResultTerm* .

    ResultTerm = PatternTerm | '<' Result '>' .

    Pattern = PatternTerm* .

  Лексику приводить не буду, т.к. её легко можно понять из таблицы автомата, по
которой создавался лексический анализатор.
  Некоторые особенности лексического разбора. Имена функций и индексы переменных
могли содержать дефис, который полностью эквивалентен подчёркиванию. Необходи-
мость замены '-' на '_' связана с тем, что в языке Си/Си++ недопустимы имена,
содержащие дефис, но исходные тексты на Рефале очень хорошо смотрятся с исполь-
зованием дефиса в именах. При считывании целочисленной переменной проверка на
переполнение не проводилась -- при превышении величины 2**32-1 результат оказы-
вался неопределённым.
  В языке как ни странно, не нашлось места для глобальных переменных: я уже при-
вык программировать на Рефале без них, поэтому усложнять компилятор ненужным
средством я не стал. Если вдруг нужда припечёт, могу написать на Си поддержку
копилки.

  (3.2) Несколько слов о стандартных функциях.
  Очевидно, что средствами самого Рефала (отождествление с образцом и построение
результата) ряд операций выполнить невозможно: это операции ввода вывода и опе-
рации с атомами. Конечно, арифметические функции теоретически можно описать вот
так:
  Add {
    0 0 = 0;
    0 1 = 1;
    1 0 = 1;
    ...
    234 456 = 690;
    ...
  }

но даже если такие функции написать (сгенерировав автоматически, например прог-
раммой на Си), то практически пользоваться ими будет сложно -- они крайне неэф-
фективны. Поэтому языку нужны примитивные функции, выполняющие примитивные опе-
рации.
  В данном компиляторе принята следующая модель. Вводить в язык встроенные функ-
ции мне идеологически противно, т.к. функции относятся к уровню пользовательских
определений, а выполняют действия уровня языка. К тому же для встроенных функций
выполняются особые правила, например, их не надо объявлять. Поэтому я примитив-
ные операции сделал как внешние -- по образцу языка Си -- в нём тоже нет встро-
енных функций. Поскольку примитивные операции (т.е. те, которые невозможно напи-
сать средствами Рефала) являются внешними, то точно также пользователь может на-
писать свои примитивные функции на Си++ и тоже они будут внешними.
  Из стандартных внешних функций даны следующие:

  Стандартные имена-метки: Success, Fails, True, False.
  Арифметика:
  Add, Sub -- арифметические команды.

  Ввод-вывод:
  <ReadLine> == e.Line -- считывает ввод с консоли,
  <WriteLine e.Line> == empty -- выводит на консоль,
  <FOpen s.Mode e.Name> == s.FileHandle -- открывает файл с заданным именем в
заданном режиме: 'r' -- для чтения, 'w' -- для записи.
  <FReadLine s.FileHandle> == s.FileHandle e.Line,
  <FWriteLine s.FileHandle e.Line> == s.FileHandle,
  <FClose s.FileHandle> -- закрывает файл.
  Функции файлового ввода-вывода сделаны по образцу соответствующих функций
модуля FileIO Модульного Рефала, т.к. для разработки препроцессора в качестве
примитивных операций я взял библиотечные функции Модульного Рефала.

  Преобразование типов:
  <StrFromInt s.Int> == e.Digits -- преобразует число в строку,
  <IntFromStr e.Text>
    == Success s.Number e.Rest
    == Fails e.Text

  Если e.Text начинается с цепочки цифр, то эта цепочка преобразуется в число
s.Number и возвращает остаток как e.Rest. Если же преобразование невозможно,
то функция возвращает Fails и свой аргумент.

  <Chr s.Num> == s.Char, <Ord s.Char> == s.Num -- очевидно.

  Средства операционной системы.
  <System e.Command> == empty -- вызывает данную командную строку,
  <Exit s.ReturnCode> -- завершает программу с выдачей кода возврата,
  <Arg s.Number> == e.Argument -- возвращает аргумент командной строки с задан-
ным номером,
  <ExistFile e.FileName> == True | False -- проверяет наличие файла.

  Также к компилятору прилагается стандартное расширение библиотеки LibraryEx,
которое целиком написано на Рефале и содержит такие полезные функции, как Map,
Reduce, MapReduce, LoadFile, SaveFile и ряд других. Приводить их описания не
буду, т.к. их семантику можно легко понять из исходного кода.

  (3.3) Особенности синтаксического анализа.
  Можно заметить, что если нетерминалы PatternTerm и ResultTerm описать следую-
щим образом (с потерей сбаллансированности скобок), то грамматика будет практи-
чески автоматной (не внешне, а легко преобразуема в автоматную).

    PatternTerm = Char | '(' | ')' | Number | Name | Variable .

    ResultTerm = PatternTerm | '<' | '>' .

  И подобный автомат описать будет гораздо легче (на Рефале удивительно легко
пишутся автоматные программы). После разбора разбора образца и результата можно
отдельно в них проверить сбаллансированность скобок. В программе я пошёл ещё
дальше: в отдельную процедуру я вынес также проверку переменных (в образце не
могут встречаться две переменные разного вида (s, t или e) с одинаковым индек-
сом, в результатном выражении не могут присутствовать необъявленные в образце
переменные).
  Данный автомат работал как преобразователь -- по прочтению отдельных элементов
(директивы $ENUM, $EENUM, $EXTERN, начало функции с фигурной скобкой, отдельное
предложение, закрывающая фигурная скобка) сразу же генерировался соответствующий
код (соответственно extern-объявление функции на Си, генерация пустых функций,
завершающихся неудачно, с разными классами памяти, начало непустой функции, код
обработки предложения, завершение функции). Отдельные элементы генерировались
полностью независимо друг от друга, что приходилось учитывать при создании выхо-
ных файлов. Исключение составляла только таблица символов, содержащая имена фун-
кций -- для проверки того факта, что все имена должы быть объявлены перед первым
использованием. О генерации будет подробно сказано позже.
  Как оказалось, данное разделение синтаксического анализа на три прохода (про-
ходы осуществлялись только по отдельным предложениям, а не по всей единице тран-
сляции) сильно упростило структуру самого компилятора. Такое сведение к автома-
ту стало возможно в связи с тем, что термы, из которых состоят левые и правые
части предложений, не могут содержать разделителей (соответственно, '=' и ';').
Если бы данный диалект мог бы поддерживать безымянные или локальные функции как
термы (которые внутри себя содержат предложения, разделяемые при помощи '=' и
';'), то подобное сведЕние контекстно-свободной грамматики к автоматной не было
бы возможно.
  В общем, как показала практика, разделить на два прохода проверку контекстно-
независимого синтаксиса и контекстных зависимостей очень полезно -- структура
компилятора становится проще. При проверке парности скобок можно не заботиться
о неожиданных лексемах, при проверке наличия переменных -- о парности скобок.
  В таком случае проверка контекстно-независимого синтаксиса, которая легко фор-
мализуется, может осуществляться автоматически -- можно написать генератор син-
таксического анализатора по БНФ, строящего синтаксическое дерево. В дальнейшем
это дерево можно обойти с проверкой контекстных зависимостей и построить абст-
рактное синтаксическое представление.

  (3.4) Реализация виртуальной Рефал-машины.
  Виртуальная Рефал-машина была реализована по классической схеме с использова-
нием поля зрения. Поле зрения представляет собой двусвязанный список узлов, каж-
дый из которых представляет собой либо атом, либо ту или иную скобку (одну из
(, ), <, >). Узлы содержат связи с соседними узлами, поле типа и поле информа-
ции, которое представляет собой объединение (union) нескольких полей различных
типов. Узлы-числа в поле информации содержат unsigned long, узлы-символы --
char, узлы-функции содержат указатель на функцию и указатель на const char, со-
держащий имя функции. Узлы, соответствующие структурным скобкам, содержат связи
на сопряжённые им скобки. Указатели на скобки конкретизации находятся в стеке
вызовов в том порядке, в котором они должны вызываться. Если вызов функции за-
мещается активным выражением с другими скобками конкретизации, то эти скобки
конкретизации помещаются на вершину стека в правильном порядке -- так осуществ-
ляется сохранение инварианта стека. Для реализации данного стека используется
поле информации в узлах скобок (как в Рефале 2).
  Функция на Си++, соответствующая функции на Рефале, при выполнении может либо
заменить свой вызов в поле зрения, вернув при этом refalrts::cSuccess, либо за-
вершиться неудачно вследствие невозможности сопоставления или отсутствия памяти,
возратив при этом соответственно refalrts::cRecognitionImpossible или refalrts::
cNoMemory. При этом, если функция завершилась неудачно, она не изменяет свой ар-
гумент.
  Внутренне функция состоит из обработчиков отдельных предложений, каждое из ко-
торых либо может завершить функцию успешно (выполнить return refalrts::cSuccess)
или сообщить о невозможности выделения памяти (выполнить return refalrts::cNoMe-
mory). Если обработчик не завершил функцию с выдачей одного из этих сообщений,
то управление передаётся следующему обработчику, в случае последнего обработчика
-- оператору return refalrts::cRecognitionImpossible; в конце функции.
  Выполнение обработчика предложения проходит через три фазы:
  1. Распознаётся аргумент. В процессе распознавания аргумент не меняется. Если
распознавание невозможно, то выполняется выход из обработчика.
  2. Копируются переменные и строятся элементы результата, заданные литералами,
включая структурные и функциональные скобки (готовые скобки и атомы из обазца не
используются -- это сделано в целях упрощения компилятора). На этой стадии функ-
ция может выработать сообщение refalrts::cNoMemory. Новые элементы строятся
внутри списка свободных блоков (см. ниже). Аргумент функции при аварийном завер-
шении никак не изменяется.
  3. Создаётся результат из переменных образца и элементов, построение результа-
та осуществляется при помощи операций над двусвязанными списками, не нарушающими
инвариант -- перенос части цепочки из одного места в другое с исключением из
исходного местаположения (splicing). После построения результата остатки образ-
ца переносятся в список свободных блоков. Все операции в этой фазе не могут за-
вершиться неуспешно -- данная фаза завершается выдачей refalrts::cSuccess.
  Для распределения памяти используется двусвязанный список свободных узлов. Все
операции, выделяющие память (копирующие переменные или создающие новые узлы),
создают свой аргумент внутри этого списка. В дальнейшем участки списка с вновь
созданными элементами переносятся в список поля зрения при построении результа-
та. Подобная стратегия обеспечивает непротиворечивость обоих списков при выдаче
сообщения refalrts::cNoMemory -- созданные элементы остаются в списке свободных
блоков, аргумент не изменяется.

  (3.5) Генерация предложений.
  Генерация предложений осуществляется в две стадии: сначала по промежуточному
представлению создаётся обработчик на абстрактном императивном языке (т.е. пред-
ложение преобразуется в последовательность команд обработки), а затем уже обра-
ботчик переводится с абстактного императивного представления переводится на
Си++, причём отдельные команды транслируются практически независимо друг от дру-
га. Операции двух последних фаз: выделение новой памяти и сборка результата реа-
лизуются сравнительно несложно, а вот распознавание образца довольно интересно.

  Приведу правила сопоставления с образцом так, как они описаны в руководстве
к Рефалу 5, а затем прокомментирую, как они реализованы в настоящем компиляторе.

    Общие требования к отображению P на E (сопоставлению E : P )

  1. Если узел N2 расположен в P правее узла N1, то проекция  N2 в E может либо
совпадать с проекцией  N1, либо располагаться справа от нее (линии проектирова-
ния не могут пересекаться).
  2. Скобки и символы должны совпадать со своими проекциями.
  3. Проекции переменных должны удовлетворять синтаксическим требованиям их зна-
чений; т.е., быть символами, термами или произвольными выражениями для s-, t- и
e-переменных соответственно. Различные вхождения одной переменной должны иметь
одинаковые проекции. 

    Правила отображения

  1. После того, как отображена скобка, следующей подлежит отображению парная ей
скобка.
  2. Если в результате предыдущих шагов оба конца вхождения некоторой e-перемен-
ной уже отображены, но эта переменная еще не имеет значения (ни одно другое ее
вхождение не было отображено), то эта переменная отображается следующей. Такие
вхождения называются закрытыми e-переменными. Две закрытые e-переменные могут
появиться одновременно; в этом случае та, что слева, отображается первой.
  3. Вхождение переменной, которая уже получила значение, является повторным.
Скобки, символы, s-переменные, t-переменные и повторные вхождения e-переменных в
P являются жесткими элементами. Если один из концов жесткого элемента отображен,
проекция второго конца определена однозначно. Если Правила 1 и 2 неприменимы, и
имеется несколько жестких элементов с одним спроектированным концом, то из них
выбирается самый левый. Если возможно отобразить этот элемент, не вступая в про-
тиворечие с общими требованиями  1-3, приведенными выше, тогда он отображается,
и процесс продолжается дальше. В противном случае объявляется тупиковая ситуация.
  4. Если Правила 1-3 неприменимы и имеются несколько e-переменных с отображен-
ным левым концом, то выбирается самая левая из них. Она называется открытой
e-переменной. Первоначально она получает пустое значение, т.е., ее правый конец
проектируется на тот же узел, что и левый. Другие значения могут присваиваться
открытым переменным через удлинение (см. Правило 6).
  5. Если все элементы Р отображены, это значит, что процесс сопоставления ус-
пешно завершен.
  6. В тупиковой ситуации процесс возвращается назад к последней открытой e-пе-
ременной (т.е., к той, что имеет максимальный номер проекции), и ее значение
удлиняется; т.е., проекция ее правого конца в Е подвигается на один терм вправо.
После этого процесс возобновляется. Если переменную нельзя удлинить (из-за Общих
требований 1-3), удлиняется предшествующая открытая переменная, и т.д. Если не
имеется подлежащих удлинению открытых переменных, процесс сопоставления не удал-
ся.

  Однако, очевидно, что порядок отображения жёстких элементов и закрытых e-пере-
менных несущественнен с точки зрения окончательного результата. Важен лишь поря-
док отображения открытых e-переменных. Поэтому в моём случае при создании алго-
ритма распознавания образца (промежуточное абстрактное императивное представле-
ние в коде называется алгоритмом) порядок отображения жёстких элементов несколь-
ко другой, чем в описанных выше Правилах.
  Алгоритм распознавания образца моделируется так. Рассмотрим метод для случая
"плоского" выражения -- выражения без структурных скобок, затем обобщим на иера-
рхический случай. В образец вводятся два указателя -- левый и правый (обозначим
их как [ и ]). Эти указатели могут располагаться между отдельными термами образ-
ца или непосредственно справа или слева вне образца (таково изначальное положе-
ние правого и левого указателей соответственно). Далее, итеративно выполняется
просмотр образца и перемещение указателей по следующим правилам:
  1) Если справа от [ находится жёсткий элемент, то создаётся команда распозна-
вания этого жёсткого элемента от левого конца выражения и указатель сдвигается
на один элемент вправо.
  2) Аналогично, если слева от ] находится жёсткий элемент, то создаётся коман-
да распознавания этого жёсткого элемента от правого конца и указатель сдвигает-
ся на один элемент вправо.
  При этом, если при выполнении правил 1) или 2) распознаётся переменная, то
она запоминается как распознанная и в дальнейшем отождествляется как повторная.
  3) Если между указателями оказывается нераспознанная e-переменная: [e.Index],
то создаётся команда отождествления остатка выражения с данной e-переменной. При
этом процесс распознавания выражения завершается.
  4) Если указатели [ и ] встречаются, то создаётся команда проверки оставшегося
выражения на пустоту.
  5) Если справа от указателя [ и слева от указателя ] оказываются нераспознан-
ные e-переменные, то создаётся команда-маркер открытой e-переменной и указатель
[ сдвигается вправо на один эемент. В дальнейшем все команды между этим марке-
ром и до конца помещаются во вложенный цикл, в котором открытая переменная за
каждую итерацию увеличиватеся на терм и пробуется выполнение оставшихся команд.

  Пример.
    s.X 'a' 2 e.Y s.Z
    [ s.X 'a' 2 e.Y s.Z ] => svar_left(s.X),   s.X [ 'a' 2 e.Y s.Z ]
    s.X [ 'a' 2 e.Y s.Z ] => char_left('a'),   s.X 'a' [ 2 e.Y s.Z ]
    s.X 'a' [ 2 e.Y s.Z ] => numb_left( 2 ),   s.X 'a' 2 [ e.Y s.Z ]
    s.X 'a' 2 [ e.Y s.Z ] => svar_right(s.Z),  s.X 'a' 2 [ e.Y ] s.Z
    s.Z 'a' 2 [ e.Y ] s.Z => rest_evar(e.Y),   конец распознавания
  
    s.X 5 t.Z
    [ s.X 5 t.Z ]         => svar_left(s.X),   s.X [ 5 t.Z ]
    s.X [ 5 t.Z ]         => numb_left( 5 ),   s.X 5 [ t.Z ]
    s.X 5 [ t.Z ]         => tvar_left(t.Z),   s.X 5 t.Z [ ]
    s.X 5 t.Z [ ]         => rest_empty,       конец распознавания

    1 e.X 2 e.Y 3
    [ 1 e.X 2 e.Y 3 ]     => numb_left( 1 ),   1 [ e.X 2 e.Y 3 ]
    1 [ e.X 2 e.Y 3 ]     => numb_right( 3 ),  1 [ e.X 2 e.Y ] 3
    1 [ e.X 2 e.Y ] 3     => E_CYCLE( e.X ),   1 e.X [ 2 e.Y ] 3
    1 e.X [ 2 e.Y ] 3     => numb_left( 2 ),   1 e.X 2 [ e.Y ] 3
    1 e.X 2 [ e.Y ] 3     => rest_evar(e.Y),   конец распознавания

  Этот метод легко расширяется на случай скобочной структуры: указатели вводятся
не только для всего образца, но и для каждой отдельной пары скобок. Чтобы разли-
чать выражения в различных скобках, каждой паре скобок можно присвоить индивиду-
альный целочисленный индекс начиная с 1. Точно также получают свой индивидуаль-
ный индекс и указатели, при этом полный образец получает указатели с индексом 0.
Механизм распознавания для такого случая описывается псевдокодом на Рефале:

    PatternMatching {
      // Распознавание слева

      //1
      e.Left [_N t.Атом e.Right =
        atom_left( t.Atom, выражение N )
        <PatternMatchign e.Left t.Атом [_N e.Right>;

      //2
      e.Left [_N t.ПовторнаяПеременная e.Right =
        repeatedvar_left( t.ПовторнаяПеременная, выражение N )
        <PatternMatching e.Left t.ПовторнаяПеременная [_N e.Right>;

      //3
      e.Left [_N t.st-переменная e.Right =
        stvar_left( t.st-переменная, выражение N )
        Запомнить t.st-переменную как распознанную
        <PatternMathcing e.Left t.st-переменная [_N e.Right>;

      //4
      e.Left [_N (_M e.Inner )_M e.Right =
        инициализировать выражение M
        bracket_left( выражение M, выражение N )
        <PatternMatching
          e.Left (_M [_M e.Inner ]_M )_M [_N e.Right
        >;

      // Распознавание справа

      //5
      e.Left t.Атом ]_N e.Right =
        atom_right( t.Атом, выражение N )
        <PatternMatching e.Left ]_N t.Атом e.Right>;

      //6
      e.Left t.ПовторнаяПеременная ]_N e.Right =
        repeated_right( t.ПовторнаяПеременная, выражение N )
        <PatternMatching e.Left ]_N t.ПовторнаяПеременная e.Right>;

      //7
      e.Left t.st-переменная ]_N e.Right =
        stvar_right( t.st-переменная, выражение N )
        <PatternMatching e.Left ]_N t.st-переменная e.Right>;

      //8
      e.Left (_M e.Inner )_M ]_N e.Right =
        инициализировать выражение M
        brackets_right( выражение M, выражение N )
        <PatternMatching
          e.Left ]_N (_M [_M e.Inner ]_M )_M e.Right
        >;

      // Аннигиляция указателей и открытые e-переменные

      //9
      e.Left [_N t.Закрытая-e-переменная ]_N e.Right =
        closed_e( t.Закрытая-e-переменная, выражение N )
        Запомнить t.Закрытую-e-переменную как распознанную
        <PatternMatching e.Left t.Закрытая-e-переменная e.Right>;

      //10
      e.Left [_N ]_N e.Right =
        empty_expression( выражение N )
        <PatternMatching e.Left e.Right>;

      //11
      e.Left [_N t.Нераспознанная-e-переменная-1 e.Inner
      t.Нераспознанная-e-переменная-2 ]_N e.Right =
        E-CYCLE( t.Нераспознанная-e-переменная-1, выражение N )
        Запомнить t.Нераспознанную-e-переменную-1 как распознанную
        <PatternMatching
          e.Left t.Нераспознанная-e-переменная-1
          [_N e.Inner t.Нераспознанная-e-переменная-2 ]_N e.Right
        >;

      // Завершение цикла -- указателей не осталось

      //12
      e.Pattern = ;
    }

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

    Инициализировать выражение 0 аргументом
    <PatternMatching [_0 e.Pattern ]_0>;

  В псевдокоде обозначения [_N, ]_N, (_N, )_N обозначали соответственно пронуме-
рованные указатели и структурные скобки. С точностью до порядка отображения жёс-
тких элементов, данный алгоритм порождает порядок отображения, порождаемый Пра-
вилами 1-6. Покажем это.
  Правило 1 автоматически выполняется, если примитивные команды распознавания,
из которых строится алгоритм, распознают две скобоки одновременно. В настоящем
компиляторе так оно и есть. Предложения 4 и 8 как раз и порождают абстрактные
команды, выполняющие эту функцию.
  Для общности рассуждений будем считать, что аргумент, подлежащий распознава-
нию, погружён в пару скобок с номером 0: (_0 e.Pattern )_0. Это упростит описа-
ние, т.к. не надо будет явно выделять случаи расположения элементов непосредст-
венно рядом с краем. Таким образом, в начале обработки образец имеет вид (_0,
[_0 e.Pattern ]_0 )_0.
  Можно убедиться, что указатели разбивают каждое подвыражение на три части:
справа и слева находятся уже спроектированные элементы, непосредственно рядом
с указателями находятся элементы с одним спроектированным концом, а между ними
элементы со свободными концами. Если имеются жёсткие элементы со спроектирован-
ным левым концом, то предложения 1-4 создадут команды их распознавания. Анало-
гично, если есть жёсткие элементы со спроектированным правым концом, то они об-
рабатываются предложениями 5-8. Таким образом, с точностью до порядка распозна-
вания жёстких элементов, предложения 1-8 реализуют Правило 3.
  Если же имеется закрытая e-переменная, то она будет обработана предложением 9
-- реализация Правила 2.
  Правила 4 и 6 реализуются уже в самом сгенерированном коде -- все команды на-
чиная с команды-маркера E-CYCLE и до конца алгоритма построения выражения поме-
щаются во вложенный цикл (если после маркера E-CYCLE имеется другой маркер E-
CYCLE, то код между ним и концом помещается в другой вложенный цикл и т.д.).
Перед выполнением цикла сохраняются все указатели, которые могут измениться в
цикле, в начале каждой итерации указатели восстанавливаются, в конце каждой ите-
рации происходит удлинение открытой e-переменной на один терм. Если распознава-
ние образца возможно, то выполняются фазы 2 и 3, которые могут завершиться толь-
ко возвратом refalrts::cSuccess и refalrts::cNoMemory. Если же распознавание
при итерации по e-переменной невозможно, то запускается следующая итерация опе-
ратором continue языка C++. При неуспешном распознавании вне итерации происходит
выход из обработчика предложения и переход к следующему предложению или команде
return refalrts::cRecognitionImpossible.
  Каждый обработчик предложения находится внутри цикла do { ... } while(0);,
поэтому выйти из обработчика можно выполнив оператор break вне циклов по e-пере-
менным. Таким образом обработчик предложения выглядит примерно так:

  do {
    // ... Распознавание вне циклов по e-переменным
    if( на каком-то этапе распознавание невожможно )
      break;

    // итерация по открытой e-переменной
    // ... Сохранение нужных указателей
    for(
      инициализация цикла;
      пока удлинение возможно;
      удлинение на терм
    ) {
      // ... Восстановление нужных указателей

      // ... Распознавание внутри цикла
      if( на каком-то этапе распознавание невожможно )
        continue;

      // Образец разобран -- фаза 2 -- выделение памяти

      if( на каком-то этапе памяти не хватило )
        return refalrts::cNoMemory

      // ... Построение результата -- фаза 3
      return refalrts::cSuccess;
    }
  } while(0);

  Правило 5 реализуется за счёт выполнения предложения 12 -- если не осталось
указателей, которые находятся рядом с нераспознанными элементами (предшествующие
предложения обрабатывают все возможные случаи расположения указателей), то рас-
познавание завершается.

  Поддиапазоны аргумента и результата представляются парой итераторов двусвязно-
го списка (обычных указателей на узлы). При этом первый итератор указывает на
первый узел поддиапазона, второй итератор -- на последний. Пустая последователь-
ность представляется парой итераторов, установленных в NULL. В начале я пытался
использовать обозначение диапазонов в стиле STL -- указателями на первый элемент
и на элемент, следующий за последним. Однако, для правильного обращения с подоб-
ными поддиапазонами нужно более тщательно планировать последовательности команд
построения результата, т.к. в результате переноса (splicing) элементов, находя-
щихся непосредственно за рассматриваемым диапазонам, переместится и элемент, на
который указывает концевой итератор -- пара [first, last) больше не будет ука-
зывать на корректный диапазон. При использовании диапазонов [first, last] при
любых операциях с соседними диапазонами итераторы на текущий диапазон не изме-
нятся.
  Операции для распознавания жёстких элементов образца представлены элементарны-
ми функциями с суффиксами _left и _right (за исключением move_left и move_
right). Все они имеют примерно такой формат:
  bool ***_left( описание жёсткого элемента, Iter& first, Iter& last);
  bool ***_right( описание жёсткого элемента, Iter& first, Iter& last);
где *** -- тип жёсткого элемента (имя функции, число, символ, структурные скоб-
ки, повторная переменная, st-переменная). Описание жёсткого элемента представля-
ет собой набор параметров, характеризующих жёсткий элемент (значение для атомов,
ссылки на правый и левый конец подвыражения для структурных скобок, ссылку на
терм для s- и t-переменных, для повторных переменных -- описание образца (указа-
тель на терм для st-переменных, пара итераторов для e-переменных) и местораспо-
ложение самой переменной (ссылка на итератор для st- и на пару для e-перемен-
ных)). Сами функции возвращают true в случае успешного распознавания, перемещая
при этом итераторы first и last так, чтобы вновь созданный диапазон [first,
last] указывал на нераспознанную часть выражения. Пример:
  'abcdef' => { char_left } => 'bcdef'
  F G H => { function_right } => F G
  Если же распознать жёсткий элемент невозможно, то возвращается false, при этом
связанный список поля зрения не изменяется, не меняются значения переменных, пе-
реданных по ссылке.
  Предусловием для этих функций является правильное задание параметров описания
жёсткого элемента и правильное указание поддиапазона [first, last] (указывают на
концы, либо оба равны нулю).
  Постусловием является в случае правильно составленного алгоритма соблюдение
Общих требований 1-3.

  Для итерации используется простой цикл for по открытой e-переменной. Если на
некоторой итерации при некоторой длине e-переменной распознавание произошло ус-
пешно, то выполняется код выделения памяти и построения результата, который мо-
жет завершиться только выдачей сообщений refalrts::cNoMemory или refalrts::
cSuccess. В случае неудачного распознавания оставшихся элементов образца, ите-
рация завершается при помощи оператора continue и e-переменная удлиняется. Если
переменную уже удлинить нельзя, то происходит продвижение к концу обработчика
предложения: если этот цикл не вложен в другой цикл по e-переменной, то проис-
ходит переход к следующему предложению, иначе -- завершается также и итерация
внешнего цикла по e-переменной (элементарно -- из-за того, что мы достигли конца
тела цикла). Псевдокод:
  do {
    // распознавание до открытой e-переменной
    ...
    if( где-то распозавание не удалось )
      break;
    ...
    for(
      /* Инициализация */;
      /* Растяжение дальше возможно */;
      /* Удлинение переменной */;
    ) {
     ...
     if( где-то распознавание не удалось )
       continue;
     ...
      for(
        /* Инициализация */;
        /* Растяжение дальше возможно */;
        /* Удлинение переменной */;
      ) {
        ...
        //Выделение памяти
        ...
        if( нет памяти )
          return refalrts::cNoMemory;
        ...
        // Построение результата
        ...
        return refalrts::cSuccess;
      }
    }
  } while( 0 );

  При невозможности распознавания должна осуществляться возможность отката с
восстановлением предыдущего состояния (выполнения Правила 6), т.к. в процессе
распознавания изменяются переменные типа bb_N и be_N -- границы подвыражений
в скобках. Для восстановления значения используется следующее свойство языка C++
-- возможность объявлять переменные во вложенных блоках с тем же именем, что
и во внешнем блоке с сокрытием последних. Таким образом, в блоке инициализации
цикла for определяются переменные bb_N и be_N типа refalrts::Iter, которые ини-
циализированы значением одноимённых переменных во внешнем блоке. Таким образом,
для сохранения значения не приходится заводить переменные с новыми именами или
вложенным переменным давать другие имена (это бы пришлось делать при генерации
кода на Паскале). Но, поскольку результат инициализации refalrts::Iter bb_N =
bb_N; не определён, то приходится заводить промежуточную переменную:
    refalrts::Iter bb_N_stk = bb_N;
    refalrts::Iter be_N_stk = be_N;
    for(
      refalrts::Iter
        ...
        bb_N = bb_N_stk,
        be_N = be_N_stk,
        ...;
      ...;
      ...;
    ) {
      ...
    }
  К сожалению, здесь допущена ошибка. Данный механизм превосходно работает, но
сохраняется лишь значение границ того подвыражения, в котором находится откры-
тая e-переменная. Если внутри итерации модифицируются границы других подвыраже-
ний, то эти изменения сохраняются и дальнейшее распознавание происходит непра-
вильно. Например, при распознавании образца
  e.Begin (_1 e.Inner )_1 (_2 e.Any 'X' e.Inner )_2
модифицируются границы пары скобок №2, что приводит к невозможности сопоставле-
ния данного образца, например с выражением ('er') ('super') ('any' 'X' 'super').
  В принципе, эту ошибку легко устранить, сохраняя все распознанные к этому эта-
пу скобки (даже если они не модифицируются), но уже лень. Данный компилятор я не
собираюсь сопровождать (по крайней мере, в обозримом будущем).
  Также имело бы смысл сохранять ***_stk переменные не как указатели (refalrts::
Iter -- синоним (typedef) для указателей), а как ссылки на них (refalrts::Iter&)
-- согласно Стандарту ссылки определяются как просто другое имя переменной --
поэтому выделения памяти может для них даже и не происходить. Но я верю в силу
оптимизации современных компиляторов, которые способны устранить промежуточное
присваивание в цепочке b = a; c = b; если b больше нигде не используется и явля-
ется простым встроенным типом данных вроде указателя.
  Однако мне (не)повезло: компилятор успешно компилирует самого себя и нормально
работает не смотря на эту ошибку. Если бы эта ошибка приводила к неверным ре-
зультатам, то я бы её исправил и конечный результат имел бы на одну ошибку мень-
ше.

  (3.5) Ограничения исследовательского прототипа.
  Полученный результат является исключительно исследовательским прототипом, для
использования в реальной жизни он не предназначен. Поэтому я его оставил его не-
доделанным. Недостатки самого языка (необходимость предварительного объявления
функций, отсутствие модульности и модель компоновки в стиле C, поддержка только
базисного подмножества и др.) недоделками я не считаю, т.к. это недостатки имен-
но языка, а не компилятора. Вот список недоделок.
  (1) Все исходные файлы должны быть перечислены в командной строке по их абсо-
лютным или относительным путям. Такой замечательной возможности, как указание
каталога для поиска библиотек, нет.
  (2) Отстуствуют какие бы то ни было средства конфигурирования. Для компиляции
вызывается (функцией System) программа call_cpp_compiler, которая реализована
как батник, собственно и вызывающий компилятор.
  (3) Есть неисправленыые ошибки, такие как ошибка сохранения состояния при от-
катах в открытых e-переменных (см. выше).
  (4) Код генерируется довольно прямолинейно: отдельные команды абстрактного им-
перативного языка (алгоритма) генерируются независимо друг от друга. Часто пере-
менные дублируют друг друга (например, при наличии закрытых e-переменных внутри
скобок можно было бы избежать использования итераторов bb_N и be_N).
  (5) При более тщательной проработке алгоритма можно было бы использовать ука-
зания диапазонов в стиле STL. При этом можно было бы не использовать переменные
eVarName_e для указания конца e-переменных -- конец в таком случае ограничивал-
ся следующей за ней переменной.
  (6) Можно было бы повторно использовать литеральные элементы образца (атомы и
скобки) вместо выделения их из списка свободных блоков. Также можно повторно
использовать неиспльзуемые литеральные элементы и st-переменные, переинициализи-
руя их.
  (7) Если заглянуть в реализацию RTS, то можно заметить, что код распознавания
отдельных атомов, пар скобок, повторных переменных во многом похож, функции
***_left и ***_right похожи как близнецы-братья. В принципе, компилятор вместо
вставки кода для вызова функций мог бы вставлять операторы, представляющие собой
тело функции. Хотя это привело бы к резкому возрастанию объёма сгенерированного
кода.
  (8) Не производится никакой оптимизации. Из-за того, что отдельные предложения
генерируются независимо друг от друга, одни и те же операции (в случае, если
функция имеет определённый формат аргумента -- а так почти всегда) выполняются
многократно. В неэффективности этого можно убедиться, если посмотреть на код ав-
томата лексического анализатора в файлах Lexer.sref и Lexer.cpp. Надежды на то,
что одинаковые вычисления будут объединены компилятором C++ мало -- в ходе рас-
познавания вызываются внешние функции (см. п. 7), которые потенциально могут
иметь побочный эффект. Хотя, если бы предложения обрабатывались бы совместно,
линейное перечисление обработчиков можно было бы заменить деревом. Т.е. вместо

  /*
    Все три предложения имеют общий формат.
    Также первые два предложения имеют много общего в образце.
  */

  do {
    // распознавание первого предложения
    if( неудача распознавания )
      break;
    // построение результата
    return refalrts::cNoMemory;
    return refalrts::cSuccess;
  } while(0);

  do {
    // распознавание второго предложения
    if( неудача распознавания )
      break;
    // построение результата
    return refalrts::cNoMemory;
    return refalrts::cSuccess;
  } while(0);

  do {
    // распознавание третьего предложения
    if( неудача распознавания )
      break;
    // построение результата
    return refalrts::cNoMemory;
    return refalrts::cSuccess;
  } while(0);

  return refalrts::cRecognitionImpossible;

можно было бы написать

  do {
    // распознавание общего для трёх предложений формата
    if( неудача распознавания )
      break;

    do {
      // распознавание общих элементов для первых двух предложений.
      if( неудача распознавания )
        break;

      do {
        // распознавание первого выражения
        if( неудача распознавания )
          break;
        // построение результата
        return refalrts::cNoMemory;
        return refalrts::cSuccess;
      } while(0)

      do {
        // распознавание второго выражения
        if( неудача распознавания )
          break;
        // построение результата
        return refalrts::cNoMemory;
        return refalrts::cSuccess;
      } while(0)

    } while(0);

    do {
      // распознавание второго выражения
      if( неудача распознавания )
        break;
      // построение результата
      return refalrts::cNoMemory;
      return refalrts::cSuccess;
    } while(0);

  } while(0);

  return refalrts::cRecognitionImpossible;

  В этом случае после неудачи распознавания первого предложения во втором при-
дётся выполнить минимум вычислений для распознавания, т.к. часть выражения уже
распознана.
  (9) Скудная библиотека стандартных внешних ("встроенных") функций. Этот недос-
таток при желании легко устраним.

  Выводы.

  [1] Компилятор, транслирующий Рефал в Си++, написал. О результатах исследова-
ния трансляции Рефал->C++ можно прочитать в разделе Результаты настоящего файла.
Те возможности языка, которые планировались в Цели лабы, были реализованы.
  Полученный компилятор работает, хотя и не без недостатков (см. выше).
  [2] Был написан самокомпилятор, а это значит, что языком можно пользоваться
для написания достаточно нетривиальных приложений (таких, как компилятор), а не
только Hello, World и Fibonacci программировать.
  [3] При исправлении некоторых ошибок и недоделок язык можно использовать и как
C++-back-end для Модульного Рефала (разумеется, адоптировав его под другой уро-
вень модульности). Причём можно использовать двояко: (1) генерация файлов на
Простом Рефале, а затем запуск компилятора Простого Рефала -- также как осущест-
вляется компиляция в back-end'е Рефала 5 и (2) интеграция кода самого компилято-
ра Простого Рефала в компилятор Модульного Рефала. Второй вариант облегчается
тем, что у нас имеется препроцессор, транслирующий Простой в Модульный Рефал.
  [4] Имеет смысл разработать генераторы лексического и синтаксического анализа-
торов. Это действительно удобно.
  [5] Если (когда) будет разрабатываться front-end для Модульного Рефала. порож-
дающий код на императивном языке, то целесообразно будет использовать границы
в стиле STL и более тщательное планирование сгенерированного алгоритма.