По специализированным журналам прокатилась очередная волна сравнений различных языков программирования. Что лучше: Perl, C++, Prolog, Oberon, Lisp, Ada, Java, TCL, Phyton? Добавь и посоли по вкусу. Не будем складывать лампочки и апельсины. Неужели любую задачу мы обязаны решать одним инструментом? Может быть, для каждой задачи вообще лучше использовать свой собственный? Перегибаешь, скажете вы. Ну, может быть, слегка. Хотя, если присмотреться к продуктам из семейства GNU, то окажется, что создание своих «языков» для различных задач достаточно популярно. В данном случае «язык» взят в кавычки неспроста.

Речь обычно идет не о полноценном языке программирования, а просто о средстве для облегчения написания совершенно конкретных кусков кода. При этом часто часть кода написана на том языке, который выбран в качестве языка реализации (например, на С). В принципе, конечно, это можно назвать препроцессированием с языка на язык (мне встречались такие решения и для Паскаля, Фортрана 77, Ассемблера и т.д.). Алгоритмы подобного «препроцессирования» по сравнению с обычными макроподстановками могут быть достаточно сложными. Рассмотрим несколько примеров.

Симуляторы и симулянты

Рассмотрим задачу создания симулятора для какого-либо процессора. Как правило, первые симуляторы появляются раньше, чем процессор находит свое воплощение в кремнии. Что представляет собой симулятор? В простейшем варианте это программа, которая имитирует выполнение команд процессора, выполнение им операций с памятью и т.п. Более сложные симуляторы позволяют учесть влияние кэша, точно проверить производительность, сымитировать внешнее устройство или прерывание и т.д. Условно простой вариант можно представить в виде цикла:

   Цикл пока есть повод что-то делать
    Выбрать команду из памяти
    Декодировать команду
    Выполнить команду
   Конец цикла

На предложении «Декодировать команду» остановимся. Можно, конечно, попытаться поступить совсем просто. Берем список команд и записываем каждую команду в виде некоторой маски, которая позволяет отбросить параметры операции и того кода, который остается после отбрасывания параметров. Кроме того, надо учесть возможность ограничения на биты, которые задают параметры. Иногда «запрещенные» комбинации параметров для некоторой операции используются для введения новых операций. Бывают еще всякие префиксы и модификаторы. Правда, «запрещенные» комбинации и модификаторы используются в CISC-архитектур. Для случая RISC алгоритм с маской вполне проходит, хотя, конечно, декодер, обильно наполненный строками наподобие

If((code&MaskAdd)=
=OpAdd)ExecuteAdd();

не будет обладать достаточной эффективностью.

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

Switch((code&OpMask)
>>OpOffset){
...
Case OpAdd: ExecuteAdd(); break;
...
default: IllegalOp();
}

Все это хорошо, но у нас может появиться желание отрабатывать особенности различных вариантов архитектуры (команда может быть в наличии или нет, поведение конкретной команды может варьироваться и т.д.). При этом схема, хорошо работавшая для одного варианта процессора, начинает сбоить для нового варианта. Да и вообще, по поводу изменения схемы разбора может появиться масса желаний. Как быть? У каждого, кому приходилось писать программы подобного рода, наверняка рано или поздно возникало желание в некоем файле в некотором формате описать сам набор команд с дополнительными характеристиками, а затем попросить специальный кодогенератор по этому непроцедурному формату сгенерировать все, что необходимо. Атрибутов у команды, заметим, может быть достаточно много: доступность для конкретной версии процессора, имя команды для ассемблера или дизассемблера, основная часть симуляции команды. Если бы имелось описание, где вся информация о команде была сконцентрирована в одном месте, а не размазана по разным файлам, то в случае любого изменения не пришлось скакать по файлам, отлавливая все несогласованности. Достаточно изменить единый главный источник — описание команд.

Что должен сделать кодогенератор для нашего «языка»? Он может породить серию файлов: таблица кодов команд для ассемблера, таблица разбора для дизассемблера, таблица разбора для симулятора, подпрограммы для выполнения кода команд симулятора. Самое интересное: хотя и кажется, что код, который породит автомат, будет не оптимален по сравнению с ручным вариантом, на практике оказывается, что при минимальных затратах на создание кодогенератора за счет оптимизатора основного языка код может оказаться очень качественным по занимаемому им месту и производительности. Как правило, написание кодогенератора полностью оправдывается благодаря получению перечисленных выгод.

Рассмотрим в качестве примера архитектуру MIPS. Заглянув в каталог симулятора gdb (sim/mips), можно обнаружить в нем группу файлов с расширением igen. Например, в файле mips.igen содержится описание инструкций. Простенький пример:

000000,5.RS,5.RT,5.RD,00000,
100000:SPECIAL:32::ADD
"add r, r,
 r"
*mipsI,mipsII,mipsIII,mipsIV:
*vr4100:
*vr5000:
*r3900:
{
TRACE_ALU_INPUT2 (GPR[RS], GPR[RT]);
{
ALU32_BEGIN (GPR[RS]);
ALU32_ADD (GPR[RT]);
ALU32_END (GPR[RD]);
}
TRACE_ALU_RESULT (GPR[RD]);
}

Как видим, здесь задана и битовая маска команды, и распределение в ней полей, и формат выдачи на экран, и типы процессоров, и, наконец, код, позволяющий симулировать данную инструкцию. Обработка данного файла программой igen приводит к порождению группы файлов для выполнения различных функций. Для симулятора генерируется код с использованием макросов — для кодогенераторов это достаточно стандартное решение. Набор макросов и упрощает код, и обеспечивает поддержку. Этот пример, конечно, далек от программирования на «настоящем» языке, однако вполне работоспособен.

Компилируем

Если проанализировать аналогичные решения в рамках компилятора gcc, то там таких генераторов окажется очень много. Задачи достаточно узкие — вот и нет повода создавать сложные конструкции. Рассмотрим несколько примеров. Продолжая пример с архитектурой MIPS, возьмем, скажем, файл gcc/config/mips/mips.md. Этот файл содержит массу информации по генерации кода MIPS. Разберем, например, операции сложения:

(define_insn "addsi3_internal"
[(set (match_operand:SI 0 
"register_operand" "=d")
(plus:SI (match_operand:SI 1 
"reg_or_0_operand" "dJ")
(match_operand:SI 2 
"arith_operand" "dI")))]
"! TARGET_MIPS16
&& (TARGET_GAS
|| GET_CODE (operands[2]) != CONST_INT
|| INTVAL (operands[2]) != -32768)"
"addu	%0,%z1,%2"
[(set_attr "type"	"arith")
(set_attr "mode" "SI")])

Это достаточно короткий, но любопытный пример. В нем можно обнаружить шаблон для внутреннего представления кода, ограничения на тип операндов, условия применимости с учетом типа кода, типа Ассемблера, который будет далее использоваться, шаблон генерируемого кода и значения атрибутов. Это только одна из форм записей, которые есть в md-файле. Есть здесь формы и для генератора внутреннего кода, и для преобразований кода, оптимизации, установка атрибутов для учета времени выполнения инструкций и т. д. Однако синтаксис приблизительно такой же — «лиспоподобный» с вставками на C. Этот «язык» уже существенно более развит по сравнению с тем, что мы рассматривали ранее. И опять же имеет место переход к декларативному варианту написания программы. Есть, конечно, в gcc и более стандартный для компилятора код, который делается при помощи средств лексического и синтаксического анализа; он порождается средствами lex/flex и yacc/bison.

Супербизоны

Не будем углубляться в суровую теорию лексического и синтаксического анализа (любопытствующим можно порекомендовать, например, [1]). Иногда такой анализ может стать достаточно нетривиальной задачей. Достаточно хорошо известен случай, когда замена одного символа на другой имела фатальные последствия. К сожалению, мне не удалось найти точной ссылки (дело былое), но связано это было с фортрановской конструкцией DO. С точки зрения анализа кода DO1I=1.5 означает присваивание переменной значения, а DO1I=1,5 — поскольку пробелы не являются существенными — эквивалентно «DO 1 I = 1 , 5», что указывает на начало цикла. Замена запятой на точку привела к краху космического проекта. Подчеркнем, ошибки этого рода не отлавливаются компилятором.

Если мы не собираемся для какой-то частной задачи заново реализовывать Фортран, то в «нормальной» жизни достаточно разбираться с простейшей формой записи синтаксических конструкций. Достаточно знать способы записи регулярных выражений для определения лексики и форму Бэкуса-Наура для определения синтаксиса. В качестве примера мы обратимся к возможности добавления новых команд в Ассемблере для архитектуры MIPS.

Ассемблер

Ассемблер проекта GNU (gas) особенно хорош для изучения принципов построения анализаторов различного типа: в нем имеется сразу несколько анализаторов, построенных по разным принципам. В частности, разбор выражений (а вам никто не мешает писать конструкции типа li $7,(7+5)*8, причем с использованием именованных констант) в gas выполняется «сверху вниз». А если обратиться к возможности добавления новых команд сопроцессоров (мы не отступаем от темы MIPS!), то налицо вообще специальный язык описания новых команд. В данном случае вопрос о симуляции не стоит (он решается отдельно); необходимо только задать мнемонику, допустимый набор операндов и генерируемый код. Это и проделывается за счет средств, описанных в файлах itbl-lex.l. Вот достаточно показательный фрагмент, позволяющий понять идеологию лексического анализа:

%{
#include 
...
%}
ALNUM	[A-Za-z0-9_]
...
HEX	[0-9A-Fa-f]
%%
"creg"|"CREG" {    return CREG;  }
...
{ALPHA}{ALNUM}* { yytext[yyleng] = 0;
 yylval.str = strdup (yytext);
    return ID; }
"p"{DIGIT} {    yytext[yyleng] = 0;
    yylval.processor = strtoul 
(yytext+1, 0, 0);    return PNUM;  }
"0x"{HEX}+ {    yytext[yyleng] = 0;
    yylval.num = strtoul (yytext, 0, 0);
    return NUM;  }
";"|"#" {    int c;
while ((c = input ()) !=  EOF)
{
if (c ==  '
')	{unput (c);	break;}
}
}
...
%%
#ifndef yywrap
int yywrap ()   {     return 1;   }
#endif

В начале фрагмента содержится определение символьного набора нашего «языка». Например, ALNUM — набор букв, цифр и символ подчеркивания. Введение такого обозначения позволяет легко описать понятие идентификатора. Обозначение HEX позволяет описать шестнадцатеричные числа, что и происходит чуть ниже. Отдельно вводится ключевое слово, скажем, creg (чаще введение ключевых слов делается иначе). Есть и кусочек для обработки комментариев, они должны начинаться с символа «#» или «;». Кроме возврата элемента, как видите, можно вернуть и значение его. В зависимости от типа элемента это может быть и число, и строка.

Разобравшись с отдельными словами (лексемами) языка, необходимо описать синтаксис построения конструкций (соответственно, файл itbl-parse.y):

%{
#include 
...
%}
%union
{
char *str; ...
int processor;...
}
%token	    DREG CREG GREG IMMED
 ADDR INSN NUM ID NL PNUM
%type	     value 
flags flagexpr
%type	     number 
NUM ftype regtype pnum PNUM
%type	     ID name
%start insntbl
%%
insntbl:	entrys
;
entrys:	entry entrys
|
;
entry:	pnum regtype name 
value NL { ... }
| pnum INSN name value range 
flags { ...} fieldspecs NL
| NL
| error NL
;
...
pnum:	PNUM	{$$ = $1;   }
;
regtype:	  DREG	{$$ = DREG;   }
| CREG	{$$ = CREG;   }
| GREG	{$$ = GREG;   }
;
name:	ID { $$ = $1;}
;
number: NUM { $$ = $1; }
;
flags:	'*' flagexpr	{$$ = $2;}
| 	{$$ = 0; }
;
...
%%
static int yyerror (const char *msg)
{  printf ("line %d: %s
", 
insntbl_line, msg);
return 0;}

Набор токенов определяется лексическим анализатором (это как раз и есть наши лексемы). Тип задает тип возвращаемого данной лексемой или конструкцией значения (соответственно $$ для возвращаемого значения или $1-... для элементов конструкции). Start указывает на верхний уровень синтаксического дерева (типа «весь программный файл»). А вот далее описывается синтаксис конструкций. Все они должны занимать одну строку (в конце NL). То, что мы видим в фигурных скобках, указывает на выполняемые в момент разбора действия.

Пример описания команды fuu для третьего сопроцессора (взят прямо из файла):

p3 dreg d3 3	; data register
 "d3" for COP3 has value 3
p3 creg c2 22	; control register 
"c2" for COP3 has value 22
p3 func fuu 0x01f00001 dreg:17-13
 creg:12-8
Пример использования:
fuu d3,c2
Генерируемый код:
31-26  25    24-20 19-18
      17-13 12-8        7-0
COPz   CO fun	dreg creg
010011 1     11111 00
     00011 10110 00000001
0x4ff07601

Конечно, все эти примеры взяты из области компилирования, сборки и симуляции команд. Тут, как говорится, пользоваться подобными способами вполне естественно, все-таки компиляторам — компиляторово. Однако использование lex/flex и yacc/bison значительно шире. Если в вашей системе установлено достаточно много источников, то файлы с расширениями l и у встречаются в ней на каждом шагу. Это и редактор emacs, и подсистема pam, и сетевой сканер nmap (www.insecure.org/nmap), и масса других источников, можно встретить ссылки даже среди драйверов (это, конечно, не сам драйвер, а, по всей видимости, подготовка загрузочного файла для контроллера).

Сам себе режиссер

Нужно ли для написания анализаторов и генерации кода использовать именно flex или bison (и, как следствие, C)? Совершенно не обязательно. Большинство интерпретаторов содержит средства для автоматической компиляции собственных конструкций. Вот только несколько примеров:

Shell
eval lastarg=$$#
Perl
$code = `while ...
...
$code .= '}';
eval $code;
TCL (eval, конечно, тоже есть,
 но так забавнее)
% set a {puts stdout $a}
% set b {puts stdout $b}
% if 1 $a else $b
puts stdout $a
...

Иногда аналогичными средствами можно «скомпилировать» выражения, ускорив выполнение программы. Например, такой способностью обладает Perl (пример взят из [2]):

my $match_func = eval 
«sub { local $_ =
shift if @_; $expr}»;

Проведенные «вычисления» на основе значения $expr приводят к появлению новой функции. Если «значение» expr оказывается «фиксированным», то вместо многократного eval в каждом необходимом месте делается только один. Далее же выполняется только вызов уже скомпилированной функции.

Аналогичной возможностью обладал и известный в свое время СНОБОЛ (функция code [3]).

В погоне за невозможным

С интерпретаторами разобрались. А как быть с анализом в общем случае? Для этого тоже существует достаточно много решений. Иногда те или иные минимальные возможности по анализу ввода добавляют в язык с рождения. Так, в Прологе имеется возможность определения операторов и их приоритетов в терминах самого языка. Действительно, язык сам по себе позволяет достаточно легко описать синтаксис разбираемых конструкций [4]. Как результат, появляется, например, возможность аналитической обработки выражений.

Как правило, использование дополнительного языка в проекте вполне оправдано. Типичное решение сегодня заключается в совместном использовании таких языков, как Perl/Java наряду с HTML/XML. При этом используются не только генерирующие возможности языков, но и возможности анализа. Например, во второй главе книги [5] приведено несколько ссылок на различные XML-анализаторы для среды Java. В пособии по Perl [5] можно найти ссылки на соответствующие модули для анализатора HTML под Perl.

Самая любопытная находка из этой области (ссылку я, увы, потерял, но, кажется, я набрел на нее в недрах www.linux.org.ru) — это реализация ассемблера средствами shell. Согласитесь, лучшего применения shell следовало бы поискать.

Литература
  1. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. В двух томах. М.: Мир, 1978
  2. Т. Кристиансен, Н.Торкингтон. Perl: Библиотека программиста. СПб: Питер, 2000
  3. Р. Грисуолд, Дж. Поудж, И. Полански. Язык программирования СНОБОЛ-4. М.: Мир, 1980
  4. Л. Стерлинг, Э. Шапиро. Искусство программирования на языке Пролог. М.: Мир, 1990
  5. М. Даконта, А. Саганич. XML и Java2. Библиотека программиста. СПб.: Питер, 2001

Игорь Облаков (oblakov@rapas.ru) — технический директор ЗАО «Рапас» (г. Москва).

Поделитесь материалом с коллегами и друзьями