Compilers
March 2011 28

Интерпретатор из подворотен

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

Ну а если серьёзно, как-то раз у нас на работе кто-то в шутку предложил написать гоп-язык, чтобы программистом мог себя почувствовать себя любой. Начинать конструкции со слова «чо» и всё такое. Тут надо заметить, что, не встретив на своём жизненном пути образования в области computer science, я пропустил все те интересные курсы по построению компиляторов, формальным грамматикам и прочим вкусностям, которые вкушают нормальные студенты на втором-третьем курсе. Книга Вирта по построению компиляторов хотя и добавила мне знания всяких умных терминов типа БНФ, но практической пользы не принесла ­— ни одного компилятора я так и не написал. Поэтому задача оказалась для меня довольно интересной.
Если вы старше 18 лет, адекватно воспринимаете обсценную лексику нашего родного языка и вам интересно, с чего начать, добро пожаловать под кат.

Из всех средств для работы с грамматикой я встречал упоминания всего нескольких. Во-первых, это конечно же lex, flex, yacc, bison и antlr, которые используются преимущественно для компиляторов на C/C++. Во-вторых, это ocamllex и ocamlyacc — которые предназначены для разработки компилятора, как несложно догадаться, на окамле. И в-третьих, это fslexx и fsyacc — то же самое, только для языка F#, который скопирован с ocaml чуть менее, чем полностью, зато впоследствии оброс немаленьким количеством плюшек. F# я отмёл, как отсутствующий в моей системе, а все плюсовые средства — по причине их многочисленности. Да, иногда богатый выбор — это тоже плохо, я побоялся запутаться во всех этих лексерах и парсерах.

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

Типы языка

Не буду врать, я не сразу продумал всю архитектуру языка и допиливал фичи постепенно. Но для сокращения размера материала (и чтобы быстро пройти тот путь, который у меня занял шесть прекрасных утренних воскресных часов) мы сделаем вид, будто всё было спланировано заранее. Каждая инструкция нашего языка является, скажем так, объектом. В C++ его можно было бы представить в виде одного из потомков некого базового класса Instruction, или в виде сложной структуры, или вообще в виде union. К счастью, окамл позволяет нам всё сделать максимально просто. Первый наш файл, yobaType.ml, который описывает все возможные виды инструкций, устроен максимально просто:
type action =
        DoNothing
      | AddFunction of string * action list
      | CallFunction of string
      | Stats
      | Create of string
      | Conditional of int * string * action * action
      | Decrement of int * string
      | Increment of int * string;;

Каждая конструкция языка будет приводиться к одному из этих типов. DoNothing — это просто оператор NOP, он не делает ровным счётом ничего. Create создаёт переменную (у нас они всегда целочисленны), Decrement и Increment соответственно уменьшают и увеличивают заданную переменную на какое-то число. Кроме этого есть Stats для вывода статистики по всем созданным переменным и Conditional — наша реализация if, которая умеет проверять, есть ли в заданной переменной требуемая величина (или большая). В самом конце я добавил AddFunction и CallFunction — возможность создавать и вызывать собственные функции, которые на самом деле очень даже процедуры.

Грамматика языка

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

Перед показом кода я расскажу, как устроен наш язык. Любая конструкция, кроме запроса статистики (это у нас как бы служебная команда) и создания функции начинается и заканчивается ключевыми словами. Благодаря этому мы можем смело расставлять как угодно переносы строк и отступы. Кроме этого (мы же работаем с русским языком) я специально создал по паре инструкций для случаев, когда надо передавать и переменную, и значение. Позже увидите, зачем это было нужно. Итак, наш файл yobaParser.mly:
%{
        open YobaType
%}

%token <string> ID
%token <int> INT

%token RULEZ
%token GIVE TAKE
%token WASSUP DAMN
%token CONTAINS THEN ELSE
%token FUCKOFF
%token STATS
%token MEMORIZE IS
%token CALL

%start main
%type <YobaType.action> main

%%

main:
        expr                                          { $1 }
expr:
        fullcommand                                   { $1 }
      | MEMORIZE ID IS fullcommandlist DAMN           { AddFunction($2, $4) }
fullcommandlist:
        fullcommand                                   { $1 :: [] }
      | fullcommand fullcommandlist                   { $1 :: $2 }
fullcommand:
        WASSUP command DAMN                           { $2 }
      | STATS                                         { Stats }
command:
        FUCKOFF                                       { DoNothing }
      | GIVE ID INT                                   { Increment($3, $2) }
      | GIVE INT ID                                   { Increment($2, $3) }
      | TAKE ID INT                                   { Decrement($3, $2) }
      | TAKE INT ID                                   { Decrement($2, $3) }
      | RULEZ ID                                      { Create($2) }
      | CALL ID                                       { CallFunction($2) }
      | CONTAINS ID INT THEN command ELSE command     { Conditional($3, $2, $5, $7) }
      | CONTAINS INT ID THEN command ELSE command     { Conditional($2, $3, $5, $7) }
%%

Первым делом мы вставляем заголовок — открытие модуля YobaType, который содержит наш тип action, описанный в самом начале. Для чисел и строк, не являющихся ключевыми словами языка (переменных) мы объявляем два специальных типа, которым указываем, что именно они в себе содержат. Для каждого из ключевых слов с помощью директивы %token мы создаём тоже свой тип, который будет идентифицировать это слово в грамматике. Можно было бы указать их все хоть в одну строчку, просто такая запись группирует всё по видам инструкций. Имейте в виду, что все созданные нами токены — это именно подстановочные типы, по которым парсер грамматики определяет, что ему делать. Обозвать их можно как угодно, то, как они будут выглядеть в самом языке, мы опишем позже. Указываем, что входной точкой для грамматики является main, и что возвращать он всегда должен объект типа action — инструкцию для интерпретатора. Наконец, после двух знаков %% мы описываем саму грамматику:
  • Инструкция состоит либо из команды (fullcommand), либо из создания функции.
  • Функция, в свою очередь, состоит из списка команд (fullcommandlist).
  • Команда бывает либо служебной (STATS), либо обычной (command), в таком случае она должна быть обёрнута в ключевые слова.
  • С обычной командой всё просто, даже расписывать не буду.

В фигурных скобках мы указываем, что делать при совпадении строки с данным вариантом, при этом $N обозначает N-ный член конструкции. Например, если мы встречаем «CALL ID» (ID — это строка, не забываем), то мы создаём инструкцию CallFunction, которой в качестве параметра передаём $2 (как раз ID) — имя вызываемой функции.

Лексер — превращаем язык в ключевые слова

Мы дошли одновременно до практически самой простой и самой муторной части. Простая она, потому что всего лишь описывает превращение слов языка в наши токены. А муторная, потому что лексеры (а может, только окамловский лексер) плохо рассчитаны на работу с русским языком, поэтому работать с русскими символами можно только как со строками. Так как я хотел сделать ключевые слова языка регистро-независимыми, это добавило кучу геморроя — вместо простого написания «дай» надо было расписывать вариант написания каждой буквы. В общем, смотрите сами, файл yobaLexer.mll:
  1. {
  2.         open YobaParser
  3.         exception Eof
  4. }
  5. rule token = parse
  6.         ("и"|"И") ("д"|"Д") ("и"|"И") (' ')+
  7.         ("н"|"Н") ("а"|"А") ("х"|"Х") ("у"|"У") ("й"|"Й") { FUCKOFF }
  8.       | ("б"|"Б") ("а"|"А") ("л"|"Л") ("а"|"А")
  9.         ("н"|"Н") ("с"|"С") (' ')+
  10.         ("н"|"Н") ("а"|"А") ("х"|"Х")                     { STATS }
  11.       | [' ' '\t' '\n' '\r']                              { token lexbuf }
  12.       | ['0'-'9']+                                        { INT(int_of_string(Lexing.lexeme lexbuf)) }
  13.       | ("д"|"Д") ("а"|"А") ("й"|"Й")                     { GIVE }
  14.       | ("н"|"Н") ("а"|"А")                               { TAKE }
  15.       | ("ч"|"Ч") ("о"|"О")                               { WASSUP }
  16.       | ("й"|"Й") ("о"|"О") ("б"|"Б") ("а"|"А")           { DAMN }
  17.       | ("л"|"Л") ("ю"|"Ю") ("б"|"Б") ("л"|"Л") ("ю"|"Ю") { RULEZ }
  18.       | ("е"|"Е") ("с"|"С") ("т"|"Т") ("ь"|"Ь")           { CONTAINS }
  19.       | ("т"|"Т") ("а"|"А") ("д"|"Д") ("а"|"А")           { THEN }
  20.       | ("и"|"И") ("л"|"Л") ("и"|"И")                     { ELSE }
  21.       | ("у"|"У") ("с"|"С") ("е"|"Е") ("к"|"К") ("и"|"И") { MEMORIZE }
  22.       | ("э"|"Э") ("т"|"Т") ("о"|"О")                     { IS }
  23.       | ("х"|"Х") ("у"|"У") ("й"|"Й") ("н"|"Н") ("и"|"И") { CALL }
  24.       |
  25.       ("а"|"б"|"в"|"г"|"д"|"е"|"ё"|"ж"
  26.        |"з"|"и"|"й"|"к"|"л"|"м"|"н"|"о"
  27.        |"п"|"р"|"с"|"т"|"у"|"ф"|"х"|"ц"
  28.        |"ч"|"ш"|"щ"|"ъ"|"ы"|"ь"|"э"|"ю"|"я")+             { ID(Lexing.lexeme lexbuf) }
  29.       | eof                                               { raise Eof }

Я только отмечу, что этот код нельзя показывать детям и людям с хрупкой душевной организацией, потому что вся обсценная лексика языка описана именно здесь. Кроме того, в начале мы открываем модуль нашего парсера, в котором определены все типы (STATS, GIVE, TAKE и т.п.) и создаём исключение, которое будет кидаться, когда ввод закончится. Обратите внимание на 11-ую строку, в ней указывается, что пробелы и прочий мусор нужно игноировать, при этом она специально идёт после тех инструкций, которые содержат в себе пробелы. 12-ая и 25-28-ая строки обрабатывают числа и названия переменных, а 29-ая кидает то самое исключение, обозначающее конец файла.

Интерпретатор

Осталась последняя часть — сам интерпретатор, который обрабатывает наши конструкции языка. Сначала код, потом объяснение:
  1. open YobaType
  2.  
  3. let identifiers = Hashtbl.create 10;;
  4. let funcs = Hashtbl.create 10;;
  5.  
  6. let print_stats () =
  7.         let print_item id amount =
  8.                 Printf.printf ">> Йо! У тебя есть %s: %d" id amount;
  9.                 print_newline ();
  10.                 flush stdout in
  11.         Hashtbl.iter print_item identifiers;;
  12.  
  13. let arithm id op value () =
  14.         try
  15.                 Hashtbl.replace identifiers id (op (Hashtbl.find identifiers id) value);
  16.                 Printf.printf ">> Гавно вопрос\n"; flush stdout
  17.         with Not_found -> Printf.printf ">> Х@#на, ты %s не любишь\n" id; flush stdout;;
  18.  
  19. let rec cond amount id act1 act2 () =
  20.         try
  21.                 if Hashtbl.find identifiers id >= amount then process_action act1 () else process_action act2 ()
  22.         with Not_found ->
  23.                 Printf.printf ">> Човаще?!\n";
  24.                 flush stdout
  25. and process_action = function
  26.         | Create(id) -> (function () -> Hashtbl.add identifiers id 0)
  27.         | Decrement(amount, id) -> arithm id (-) amount
  28.         | Increment(amount, id) -> arithm id (+) amount
  29.         | Conditional(amount, id, act1, act2) -> cond amount id act1 act2
  30.         | DoNothing -> (function () -> ())
  31.         | Stats -> print_stats
  32.         | AddFunction(id, funclist) -> (function () -> Hashtbl.add funcs id funclist)
  33.         | CallFunction(id) -> callfun id
  34. and callfun id () =
  35.         let f: YobaType.action list = Hashtbl.find funcs id in
  36.         List.iter (function x -> process_action x ()) f
  37. ;;
  38.  
  39. while true do
  40.         try
  41.                 let lexbuf = Lexing.from_channel stdin in
  42.                 process_action (YobaParser.main YobaLexer.token lexbuf) ()
  43.         with
  44.                 YobaLexer.Eof ->
  45.                         print_stats ();
  46.                         exit 0
  47.               | Parsing.Parse_error ->
  48.                         Printf.printf ">> Ни@#я не понял б@#!\n";
  49.                         flush stdout
  50.               | Failure(_) ->
  51.                         Printf.printf ">> Ни@#я не понял б@#!\n";
  52.                         flush stdout
  53. done

Первым делом мы создадим две хэштаблицы — для переменных и для функций. Начальный размер 10 взят от фонаря, у нас же тренировочный язык, зачем нам сразу много функций.
Затем объявим две небольших функции: одна — для вывода статистики, вторая — для инкремента/декремента переменных.

Дальше идёт группа из сразу трёх функций: cond обрабатывает условные конструкции (наш if), callfun отвечает за вызов функций, а process_action отвечает за обработку пришедшей на вход инструкции как таковой. Надеюсь, почему все три функции зависят друг от друга, объяснять не надо.

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

Наконец, последняяя часть кода до посинения в цикле читает и обрабатывает результат работы парсера.

Добавим к этому Makefile и можно играться:
all:
   ocamlc -c yobaType.ml
   ocamllex yobaLexer.mll
   ocamlyacc yobaParser.mly
   ocamlc -c yobaParser.mli
   ocamlc -c yobaLexer.ml
   ocamlc -c yobaParser.ml
   ocamlc -c yoba.ml
   ocamlc -o yoba yobaLexer.cmo yobaParser.cmo yoba.cmo

clean:
   rm -f *.cmo *.cmi *.mli yoba yobaLexer.ml yobaParser.ml

Проверка языка

А теперь внимание, зачем я делал поддержку разного порядка значений и переменных? Дело в том, что язык получился очень, гм, натуральным, интерпретатор буквально разговаривает с вами. Поэтому я сам постоянно путал, в каком порядке что писать:
$ ./yoba
чо люблю сэмки йоба
чо люблю пиво йоба
усеки сэмкораздача это
чо дай 3 сэмки йоба
чо дай 4 сэмки йоба
чо на пиво 2 йоба
йоба
чо х@#ни сэмкораздача йоба
>> Гавно вопрос
>> Гавно вопрос
>> Гавно вопрос
баланс нах
>> Йо! У тебя есть сэмки: 7
>> Йо! У тебя есть пиво: -2
чо есть 4 сэмки тада дай 1 пиво или иди на@#й йоба
>> Гавно вопрос
баланс нах
>> Йо! У тебя есть сэмки: 7
>> Йо! У тебя есть пиво: -1
чо есть 4 сэмки тада х@#ни сэмкораздача или х@#ни сэмкораздача йоба
>> Гавно вопрос
>> Гавно вопрос
>> Гавно вопрос
баланс нах
>> Йо! У тебя есть сэмки: 14
>> Йо! У тебя есть пиво: -3

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

Надеюсь, было интересно. Весь код интерпретатора можно скачать тут (2кб).
Если более опытные люди поделятся замечаниями по поводу кода, буду благодарен.
+152
33.2k 125
Comments 28