Пользователь
0,0
рейтинг
28 марта 2011 в 01:13

Разработка → Интерпретатор из подворотен

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

Ну а если серьёзно, как-то раз у нас на работе кто-то в шутку предложил написать гоп-язык, чтобы программистом мог себя почувствовать себя любой. Начинать конструкции со слова «чо» и всё такое. Тут надо заметить, что, не встретив на своём жизненном пути образования в области 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кб).
Если более опытные люди поделятся замечаниями по поводу кода, буду благодарен.
Всеволод @torkve
карма
216,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (28)

  • +15
    а где воркеры? ну т.е. «лохи»?
  • +60
    Можно добавить пару операторов?

    «if» — «Есть чё?»
    «else» — «А если найду?»
    • +14
      «А если найду?» — это elif
      • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      «while» — «хоп, давай-давай!»
  • +1
    Очень!
  • +67
    «try» — «кинул пацана?»
    «catch» — «по #балу на!»
    • +1
      try = зацени

      catch = опа!

      finally = палюбому
  • +2
    Сразу вспомнился йобибайт. Если компилятор обработает такое количество информации — снимаю шляпу!
  • +31
    Надо срочно двигать в массы! У меня тут под окнами периодически очень перспективные программисты собираются!
    • +26
      Так сказать, придадим альтернативный смысл термину быдлокодер!
      • 0
        быдлокодер, в хорошем смысле этого слова
  • +2
    Чо пацан, ANTLR позволяет лексер и парсер в одном файле делать, вообще удобный парсер
    А ваще — зачОт!
  • +38
    Даёшь SCM для риальных пацанов!

    $ сука замути ; init
    $ сука взял код.йоба ; add
    $ сука понял ; commit
    $ сука сныкал на районе ; push
    $ сука чё нового; pull
    $ сука чё там ; diff
    $ сука чёзакаракули ; gui
  • +16
    — Микрософт приняла решение переписать Windows N на языке Йоба#. Для это были наняты четкие пацанчики из Подмосковья, во главе с профессиональным кодером Сявой. Как сообщает пресс-центр Микрософта это будет первая система по понятиям.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +14
    Я бы выдал премию «золотой велосипед»! :)
    Практической пользы — ровно ноль. Но, БЛИН!, как же это чертовски интересно! Вот ради таких вещей можно надо было уходить в программисты в своё время. Это же творчество в чистом виде!
  • +3
    Забавно получилось! Предлагаю ещё пару команд ввода-вывода

    «Отвечаешь?» — input
    «Нан#х» — print
  • +80
    Почему еще никто не запостил это:
    #define подъёбку setlocale
    #define чуть_чуть 7
    #define так_себе 12
    #define пошло_оно_всё 120
    #define срака double
    #define волосатая unsigned long
    #define фигню фигня
    #define кидай cin >> 
    #define кончил }
    #define начал {
    #define конкретно *
    #define ну )
    #define в_общем (
    #define кагбэ [ 
    #define ХУЙ 0
    #define да ] 
    #define какая_то int
    #define какой_то int
    #define какое_то int
    #define какие_то int
    #define давай void
    #define туды_сюды for
    #define Слышь_это cout <<
    #define эээ <<
    #define и_ещё_больше ++
    #define хуякс /
    #define Подрыхнуть Sleep
    #define подвинь_жопу new
    #define бля endl
    #define шнягу шняга
    #define стал =
    #define стала =
    #define стало =
    #define стали =
    #define взад return
    #define ну_если_уж if
    #define убрать_нахуй delete
    #define Закрой_Пасть CloseHandle
    #define УЁБИЩЕ HANDLE
    #define стало_похоже_на ==
    #define говно NULL
    #define присобачить +=
    #define тогда /*WTF*/
    #define Жди_Хрен_Дождёшься WaitForSingleObject
    #define вантуз GetLastError
    #define ХУИТА main // sic!
    #define поехали CreateThread
    #define въёбывай LPTHREAD_START_ROUTINE
    #define почти <
    #define норма 1
    #define ДОХУЯ INFINITE
    #include <windows.h>
    #include <iostream>
    #pragma warning в_общем disable: 4244 ну 
    using namespace std;
     
    какая_то фигня;
    какие_то маленькое, ОГРОМНОЕ;
    какие_то Ленин, ЕБАНУТОСТЬ;
     
    давай поработай в_общем какая_то конкретно шняга ну 
    начал 
    	маленькое стало шняга кагбэ ХУЙ да;
    	какой_то козёл, говнистость;
    	туды_сюды в_общем козёл стал норма; козёл почти фигня; козёл и_ещё_больше ну 
    	 начал 
    		ну_если_уж в_общем шняга кагбэ козёл да почти маленькое ну 
    		 начал 
    			маленькое стало шняга кагбэ козёл да;
    			Ленин стал козёл;
    			Подрыхнуть в_общем так_себе ну;
    		 кончил 
    	 кончил 
     
    	Слышь_это "\n\nМинимальный элемент массива: " эээ маленькое эээ бля;
     
    	ОГРОМНОЕ стало шняга кагбэ ХУЙ да;
    	туды_сюды в_общем говнистость стало норма; говнистость почти фигня; говнистость и_ещё_больше ну 
    	 начал 
    		ну_если_уж в_общем шняга кагбэ говнистость да > ОГРОМНОЕ ну 
    		 начал 
    			ОГРОМНОЕ стало шняга кагбэ говнистость да;
    			ЕБАНУТОСТЬ стала говнистость;
    			Подрыхнуть в_общем пошло_оно_всё ну;
    		 кончил кончил 
     
    	Слышь_это "\n\nМаксимальный элемент массива: " эээ ОГРОМНОЕ эээ бля; кончил 
    	 какая_то ХУИТА в_общем ну начал подъёбку в_общем ХУЙ, ".1251" ну;
     
    	Слышь_это "\nВведите размерность массива: \n"; кидай фигню;
    	какая_то конкретно шняга стал подвинь_жопу какая_то кагбэ фигня да;
    	Слышь_это "\nВведите элементы массива: \n";
     
    	туды_сюды в_общем какой_то козёл стал говно; 
    	козёл почти фигня; козёл и_ещё_больше ну кидай шнягу кагбэ козёл да;
    	волосатая пизда;
     
    	УЁБИЩЕ быдло стало поехали в_общем говно, говно, в_общем въёбывай ну поработай, в_общем давай конкретно ну шняга, ХУЙ, &пизда ну;
     
    	ну_если_уж в_общем быдло стало_похоже_на говно ну тогда взад вантуз в_общем ну; // Если ошибка
     
    	// Находим среднее арифметическое
    	срака посередине стало шняга кагбэ ХУЙ да;
    	туды_сюды в_общем какая_то козёл стал норма; козёл почти фигня; козёл и_ещё_больше ну 
    	 начал 
    		посередине присобачить шнягу кагбэ козёл да;
    		Подрыхнуть в_общем чуть_чуть ну;
    	 кончил 
    	посередине стало посередине хуякс фигня;
    	Слышь_это "\n\nСреднее арифметическое элементов массива: " эээ посередине эээ бля;
     
    	Жди_Хрен_Дождёшься в_общем быдло, ДОХУЯ ну; // Ждём, пока поток поработай закончит работу
     
    	какая_то писька стала посередине; // Целая часть
    	шняга кагбэ Ленин да стал писька; // Замена минимума
    	шняга кагбэ ЕБАНУТОСТЬ да стала писька; // Замена максимума
     
    	Слышь_это "\nМассив с заменой минимума и максимума на целую часть среднего арифметического: \n" эээ бля;
    	туды_сюды в_общем какая_то какашка стала говно; какашка почти фигня; какашка и_ещё_больше ну 
    		начал Слышь_это шняга кагбэ какашка да эээ " "; кончил 
    	Слышь_это бля эээ бля;
    	Закрой_Пасть в_общем быдло ну; // Закрываем дескриптор потока
    	убрать_нахуй шнягу;
    	взад ХУЙ; кончил
    
    • +15
      Последняя строка очень красноречива )
    • +19
      Курсовую что ли так написать
    • 0
      Не хватает строчки:
      #define пижже_чем >
  • +4
    А как можно было забыть о таком замечательном языке, как LOLCODE, тем более что о нём знает даже Википедия?
  • +3
    Во времена пошли, гопники уже свои языки программирования пишут, на отнятом у очкозавра ноуте.
  • –1
    class РовныйПацан: Район {}

    public interface Понятия {}

    public interface Рамсы: Понятия {}

    public interface Берега: Рамсы {}
  • +1
    Надо срочно делать диалект SQL, чтобы гопники могли запрашивать семки, на пиво и позванить по чётким понятиям.
    • 0
      SELECT `мелочь`, `семки` from `лошара` =>`лошара`, `мелочь`, `семки` есть?
  • +3
    > кидает то самое исключение, обозначающее конец файла.

    Уже в середине вашего текста прочитал как «кидает то самое заключение, обозначающее конец фуфла».

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.