Работая над несколькими проектами в Delphi, автору пришлось сделать немало лексических и синтаксических анализаторов с помощью пакета TP Lex/Yacc. Оставив за рамками статьи обсуждение вопроса "Почему это не сделать на C (C++)?", попробую показать проблемы, с которыми пришлось столкнулся и решение, которое позволило мне преодолеть большую часть из них. Сразу скажу, что я описываю готовое решение, которое работает в нескольких проектах. Название ему - OLex и OYacc. Название дано по аналогии с реализацией пакета TP Lex&Yacc для Linux под Free Pascal. Там программы называются plex и pyacc соответственно. Приставка "O" означает объекты.

(Пред) История

Занимаясь разработкой трансляторов на Delphi, рано или поздно сталкиваешься с пакетом TP Lex and Yacc (автор Albert Graef). Пакет этот максимально повторяет оригинальные Lex и Yacc, генерирующие код на языке C. Этот факт при переходе на язык Pascal порождает ряд проблем, а точнее неудобств, которые связаны с различиями в трансляции и структуре языков C и Pascal. Оригинальный Yacc, равно как и TP Yacc, генерируют выходной файл, содержащий функцию yyparse. Тоже самое делает и Lex. И если в языке C полученный файл является самодостаточной синтаксической единицей, то в Pascal этот файл еще надо как-то "прикрутить" к проекту. Вариантов сделать это не так много. В Pascal объявление функции должно находиться в том же синтаксическом модуле, что и ее реализация, поэтому сгенерированный файл либо сам должен быть модулем, либо должен включаться в уже заготовленный модуль директивой {$I }.

В первом случае .y файл выглядит примерно так:

 %{
 unit <имя файла>;
 interface
 uses
   <список модулей>;
 function yyparse: Integer;
 implementation
 %}
   <Определения>
 %%
   <Продукции>
 %%
 end.


Во втором случае надо уже два (как минимум) файла:

файл модуля <parser.pas>

 unit <имя файла>;
 interface
 uses
   <список модулей>;
 function yyparse: Integer;
 implementation
 {$I <parser_y.pas>}
 end.


и файл parser_y.y (этот файл нельзя называть parser.y, что было бы вполне логичным, из-за конфликта имен).

Оставив в стороне споры о том, на каком языке делать генераторы и тот факт, что в C включение файлов является встроенной возможностью, рассмотрим более внимательно то, что имеем.

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

Проблемы

С этими сложностями можно было бы мириться, если бы не два НО.

1) Генерируемые анализаторы слабо вписываются в объектную модель Delphi.

Генератор создает функцию, которая в своей работе использует дополнительный модуль (LexLib и YaccLib для лексического и синтаксического анализаторов соответственно). Встраивание анализатора-функции в проект, собранный сплошь из объектов, является весьма нетривиальной проектной задачей.

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

Alexey Mahotkin в свое время предпринял попытку реализовать механизм потоков в Lex. Однако, на мой взгляд, этого недостаточно. Неудобства, описанные выше, все равно остаются.

2) Очень сложно сделать несколько анализаторов в одном проекте.

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

Решение

Проанализировав все имеющиеся реализованные автором анализаторы, были сделаны следующие наблюдения:

• модуль (unit) создается всегда;
• включаемые файлы не используются;
• для каждого анализатора создается класс-обертка или вызывающий метод класса;
• некоторые анализаторы используют консоль для ввода символов, некоторые - потоки, некоторые файлы типа Text;
• разные анализаторы используют один и тот же разделяемый код из библиотек LexLib и YaccLib.

Обобщение наблюдений привело к тому, что было решено произвести переделку генераторов таким образом, чтобы они генерировали модули, содержащий классы, соответствующие лексическому и синтаксическому анализаторам.

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

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

Были произведены следующие изменения.

Для того, чтобы отличать оригинальные библиотеки от измененных, имена файлов были изменены:

Было	Стало
LexLib.pas	OLexLib.pas
YaccLib.pas	OYaccLib.pas
yylex.cod	yyolex.cod
yyparse.cod	yyoparse.cod

В библиотеках OLexLib и OYaccLib были определены классы для сканера (TBaseScanner) и парсера (TBaseParser). Во вновь созданные классы были инкапсулированы все процедуры/функции и переменные соответствующих библиотек. Это дало возможность построить шаблоны так, что генераторы будут создавать анализаторы, являющиеся наследниками указанных классов. Инкапсуляция переменных и методов, используемых при разборе, внутри класса позволяет запускать несколько анализаторов одновременно.

Работа с генерируемым файлом была поделена на два этапа. Первый - это "честная" работа Lex (Yacc) по созданию генератора. Учитывая структуру шаблона, генераторы создают метод класса, yylex или yyparse, в зависимости от анализатора. Второй этап - это работа непосредственно с созданным файлом по его доводке. В шаблон встроены некоторые подстановочные символы, которые заменяются названием модуля, класса и т.д. (полный перечень приведен ниже). Для поддержки второго этапа были введены соответствующие изменения в генераторы.

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

Новые директивы OLex и OYacc

Ниже приведен список директив, реализующих нововведения.

Директивы OLex

%scannername <имя>

Директива задает имя сканера. Имя <имя> будет вставлено везде, где появляется название сканера; название сканера будет T<имя>Scanner. Например, если указать в коде .L файла %scannername Advanced, то любое упоминание названия сканера будет выглядеть как TAdvancedScanner.

%useslist <список имен>

Директива задает список используемых сканером библиотек. <список имен> представляет собой список идентификаторов через пробел. Например, если указать в коде .L файла %useslist LexLib Unit1 Unit2, то в результирующем файле появится строка uses LexLib, Unit1, Unit2;. Директива рассчитана на то, что хотя бы одна библиотека (OLexLib) в этом списке будет, а потому она обязательно должна присутствовать в .L файле.

Директивы OYacc

%parsername <имя>

Директива задает имя парсера. Имя <name> будет вставлено везде, где появляется название парсера; название парсера будет T<имя>Parser. Например, если указать в коде .Y файла %parsername Advanced, то любое упоминание названия парсера будет выглядеть как TAdvancedParser.

%scannername <имя>

Директива задает название сканера, сгенерированного программой OLex. В результирующем файле создается инфраструктура использования сгенерированного сканера и указывается его имя. Формат такой же, как и у директивы %scannername в OLex.

%noscanner

Предполагается, что парсер использует поток токенов, поступающих от сканера. Сканер может генерироваться программой OLex, а может быть написан разработчиком транслятора. И в том, и в другом случае обращение парсера за следующим токеном происходит посредством обращения к свойству yylex сгенерированного класса. То, в свою очередь, вызывает метод чтения Getyylex. Директива %noscanner определяет, как реализуется метод Getyylex. В случае, если директива в .Y файле отсутствует, то будет использоваться метод, который обращается ко встроенному сканеру (сгенерированному OLex-ом); в противном случае разработчик должен сам объявить и реализовать метод. Делается это посредством включения нижеуказанного кода в .Y файл:

 function T@@ParserName@@Parser.Getyylex: Integer;
 begin
   <Здесь должен быть код лексического анализатора>;
 end;


Код этот должен располагаться после второго разделителя %%. Назначение символов @@ раскрывается ниже.

%tokenfile <имя>

Если в исходном .Y файле определены токены через директиву %token, то в генерируемый файл добавляются конструкции вида const token_name=<число>. Кроме того, если у токенов определить тип, то кроме списка токенов в генерируемый файл вставляется также и определение типа YYSType. И то, и другое требуется знать лексическому анализатору, чтобы выдавать и токен, и его значение (посредством поля yylval). Однако, возникла циклическая зависимость модулей сканера и парсера. Обоим надо иметь определения констант и типа YYSType; созданием же этой информации занимается генератор парсера. Поэтому было принято решение о выносе констант и определения файлов в отдельный файл. Имя этого файла и задает директива %tokenfile. Если директиву не задать, то будет сгенерирован файл tokens.pas, иначе будет сформирован файл с названием <имя>.pas. Файл токенов строится на основе нового файла-шаблона yyotoken.cod.

%useslist <список имен>

Директива имеет тот же смысл, что и в .L файле.

Подстановки второго этапа

Новые директивы относятся к первому этапу обработки входного файла. Второй этап состоит в том, что генератор раскрывает подстановки вида @@<текст>@@. Здесь <текст> зависит от генератора.

Подстановки Lex

@@UNITNAME@@
Имя сгенерированного файла без расширения. Используется для записи имени модуля и берется из имени .L файла.

@@SCANNERNAME@@
Название сканера, задаваемое директивой %scannername. Заменяется на <имя>, указываемое после директивы.

@@USESLIST@@
Список библиотек, используемых сканером. Представляет собой строку вида "name1, name 2, name3". Здесь name1, name2, name3 - элементы списка "%useslist name1 name2 name3".

@@DATE@@
Текущая дата. Полезно для установки даты создания файла в шапке.

Подстановки Yacc

@@UNITNAME@@
Имя сгенерированного файла без расширения. Используется для записи имени модуля и берется из имени .Y файла.

@@PARSERNAME@@
Название парсера, задаваемое директивой %parsername. Заменяется на <имя>, указываемое после директивы.

@@SCANNERNAME@@
Название сканера, задаваемое директивой %scannername. Заменяется на , указываемое после директивы.

@@USESLIST@@
Список библиотек, используемых парсером. Представляет собой строку вида "name1, name 2, name3" Здесь name1, name2, name3 - элементы списка "%useslist name1 name2 name3".

@@USESCANNERDEFINE@@ Заменяется на строку "{$DEFINE UseOLexScanner}", если директива %noscanner НЕ задана и на строку "{.$.DEFINE UseOLexScanner}", если директива %noscanner задана.

@@DATE@@
Текущая дата. Полезно для установки даты создания файла в шапке.

Работа с OLex и OYacc

Изменения коснулись и работы с кодом, включаемом в .L и .Y файлы. Ранее в исходном файле до первого разделителя %% можно было указывать директивы, определения и включаемый код (код вставлялся между скобок %{ %}). Теперь, в связи с тем, что генерируется класс, надо включать не исполняемый код, а некоторые определения, вставляемые в класс сканера (парсера) в раздел public.

После второго разделителя можно было включать исполняемый код уже безо всяких скобок. И сейчас можно вставлять без скобок, однако, учитывая, что создается класс, код должен писаться, учитывая этот факт. В качестве примера можно посмотреть на реализацию калькулятора expr из примеров TP Lex & Yacc посредством OYacc (см. папку example)

expr.y:
...
%{
 x : array [1..26] ofReal;
procedure Execute;
%}
%useslist OYaccLib ExprLex Tokens
...

%%
...
%%

procedure T@@ParserName@@Parser.Execute;
var
  i : Integer;

begin
  for i := 1 to 26 do x[i] := 0.0;
   if yyparse=0 then { done };
end;

Код для процедуры Execute полностью копируется в генерируемый файл, и на втором этапе работы @@ParserName@@ будет заменено названием, заданным директивой %parsername (или удалено, если директива не указана).

Список подключаемых модулей должен включать модуль Tokens или модуль, определенный директивой %tokenfile последним для того, чтобы была определен тип YYSType. Delphi берет определения из того модуля, который указан в uses последним.

Кроме того, в генерирумых файлах создаются функции, которые позволяют создать экземпляры анализаторов. Для лексического анализатора функция имеет название New@@ScannerName@@Scanner, для синтаксического анализатора - New@@ParserName@@Parser.

Функция New@@ScannerName@@Scanner получает на вход три параметра: указатели входной и выходной потоки и Boolean параметр _UseConsole. Третий параметр имеет значение по умолчанию False, так что на входе используются потоки. Иначе - потоки игнорируются и на входе используется консоль (процедура Readln).

Функция New@@ParserName@@Parser имеет два варианта - с параметрами или без. Какой вариант будет рабочим, определяет директива %noscanner. Если директива не указана, то функция имеет такие же параметры, как и New@@ScannerName@@Scanner (при создании парсера создается экземпляр сканера, название которого задается директивой %scannername в .Y файле, и конструктору сканера передаются параметры функции). Если же директива %noscanner указана, то парсер использует реализацию сканера, предоставленную разработчиком, а потому никаких параметров конструктору не передается.

Как и у анализаторов в TP Lex & Yacc, у анализаторов OLex и OYacc наблюдается странная особенность - они в упор отказываются работать, если не установлены опции компилятора Range checking и Overflow checking.

Работа по созданию "внутренностей" транслятора не отличается от работы с TP Lex & Yacc - можно обратиться к документации пакета для дальнейшего изучения.

Итог

Давно назревавшие изменения наконец-то были сделаны.

Изготовление лексических и синтаксических анализаторов теперь станет (на взгляд автора) несколько более удобным. Возможно, это изменит ситуацию, когда бытует мнение, что "компиляторы пишут только на C!" и можно будет теперь делать это на Delphi.

Автору будет очень приятно знать, что его работа кому-то оказалась полезной.

Дальнейшие планы

Дальнейших планов много.

• Расширить количество и качество примеров пакета.
• Создать нормальную документацию.
• "Научить" генераторы создавать тестовые *.dpr файлы для быстрой проверки анализаторов.
• Создать *.hrc-файл для Colorer'a для подсветки синтаксиса в .L и .Y файлах.
• Переписать код чтения символов из потока OLex для увеличения производительности (существующий код работает, но не очень эффективно).
• Портировать код под FreePascal (а там и под Linux).

Автор с благодарностью примет всякие нарекания, пожелания и сообщения об ошибках.

Выражаю благодарность Шилову Сергею за комментарии к статье.

Скачать архив: oLexYacc.rar (183 K)