torkve 28 мар 2011 в 01:13

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

14 мин

43K

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

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

{ open YobaParser exception Eof } rule token = parse ("и"|"И") ("д"|"Д") ("и"|"И") (' ')+ ("н"|"Н") ("а"|"А") ("х"|"Х") ("у"|"У") ("й"|"Й") { FUCKOFF } | ("б"|"Б") ("а"|"А") ("л"|"Л") ("а"|"А") ("н"|"Н") ("с"|"С") (' ')+ ("н"|"Н") ("а"|"А") ("х"|"Х") { STATS } | [' ' '\t' '\n' '\r'] { token lexbuf } | ['0'-'9']+ { INT(int_of_string(Lexing.lexeme lexbuf)) } | ("д"|"Д") ("а"|"А") ("й"|"Й") { GIVE } | ("н"|"Н") ("а"|"А") { TAKE } | ("ч"|"Ч") ("о"|"О") { WASSUP } | ("й"|"Й") ("о"|"О") ("б"|"Б") ("а"|"А") { DAMN } | ("л"|"Л") ("ю"|"Ю") ("б"|"Б") ("л"|"Л") ("ю"|"Ю") { RULEZ } | ("е"|"Е") ("с"|"С") ("т"|"Т") ("ь"|"Ь") { CONTAINS } | ("т"|"Т") ("а"|"А") ("д"|"Д") ("а"|"А") { THEN } | ("и"|"И") ("л"|"Л") ("и"|"И") { ELSE } | ("у"|"У") ("с"|"С") ("е"|"Е") ("к"|"К") ("и"|"И") { MEMORIZE } | ("э"|"Э") ("т"|"Т") ("о"|"О") { IS } | ("х"|"Х") ("у"|"У") ("й"|"Й") ("н"|"Н") ("и"|"И") { CALL } | ("а"|"б"|"в"|"г"|"д"|"е"|"ё"|"ж" |"з"|"и"|"й"|"к"|"л"|"м"|"н"|"о" |"п"|"р"|"с"|"т"|"у"|"ф"|"х"|"ц" |"ч"|"ш"|"щ"|"ъ"|"ы"|"ь"|"э"|"ю"|"я")+ { ID(Lexing.lexeme lexbuf) } | eof { raise Eof }

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

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

Осталась последняя часть — сам интерпретатор, который обрабатывает наши конструкции языка. Сначала код, потом объяснение:

open YobaType let identifiers = Hashtbl.create 10;; let funcs = Hashtbl.create 10;; let print_stats () = let print_item id amount = Printf.printf ">> Йо! У тебя есть %s: %d" id amount; print_newline (); flush stdout in Hashtbl.iter print_item identifiers;; let arithm id op value () = try Hashtbl.replace identifiers id (op (Hashtbl.find identifiers id) value); Printf.printf ">> Гавно вопрос\n"; flush stdout with Not_found -> Printf.printf ">> Х@#на, ты %s не любишь\n" id; flush stdout;; let rec cond amount id act1 act2 () = try if Hashtbl.find identifiers id >= amount then process_action act1 () else process_action act2 () with Not_found -> Printf.printf ">> Човаще?!\n"; flush stdout and process_action = function | Create(id) -> (function () -> Hashtbl.add identifiers id 0) | Decrement(amount, id) -> arithm id (-) amount | Increment(amount, id) -> arithm id (+) amount | Conditional(amount, id, act1, act2) -> cond amount id act1 act2 | DoNothing -> (function () -> ()) | Stats -> print_stats | AddFunction(id, funclist) -> (function () -> Hashtbl.add funcs id funclist) | CallFunction(id) -> callfun id and callfun id () = let f: YobaType.action list = Hashtbl.find funcs id in List.iter (function x -> process_action x ()) f ;; while true do try let lexbuf = Lexing.from_channel stdin in process_action (YobaParser.main YobaLexer.token lexbuf) () with YobaLexer.Eof -> print_stats (); exit 0 | Parsing.Parse_error -> Printf.printf ">> Ни@#я не понял б@#!\n"; flush stdout | Failure(_) -> Printf.printf ">> Ни@#я не понял б@#!\n"; flush stdout 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кб).
Если более опытные люди поделятся замечаниями по поводу кода, буду благодарен.

Теги:

Хабы:

Компиляторы

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

Типы языка

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

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

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

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

Публикации

Истории

Ближайшие события