Если ваше образование окончилось после второго класса, если словарный запас ограничен, а речь невнятна, если вы попросту тупы, не знаете этих непонятных латинских букв, но всё равно хотите стать программистом, вам поможет наш быдлоязык Йоба. Йоба — язык для риальных пацанов!
Ну а если серьёзно, как-то раз у нас на работе кто-то в шутку предложил написать гоп-язык, чтобы программистом мог себя почувствовать себя любой. Начинать конструкции со слова «чо» и всё такое. Тут надо заметить, что, не встретив на своём жизненном пути образования в области computer science, я пропустил все те интересные курсы по построению компиляторов, формальным грамматикам и прочим вкусностям, которые вкушают нормальные студенты на втором-третьем курсе. Книга Вирта по построению компиляторов хотя и добавила мне знания всяких умных терминов типа БНФ, но практической пользы не принесла — ни одного компилятора я так и не написал. Поэтому задача оказалась для меня довольно интересной.
Если вы старше 18 лет, адекватно воспринимаете обсценную лексику нашего родного языка и вам интересно, с чего начать, добро пожаловать под кат.
Из всех средств для работы с грамматикой я встречал упоминания всего нескольких. Во-первых, это конечно же lex, flex, yacc, bison и antlr, которые используются преимущественно для компиляторов на C/C++. Во-вторых, это ocamllex и ocamlyacc — которые предназначены для разработки компилятора, как несложно догадаться, на окамле. И в-третьих, это fslexx и fsyacc — то же самое, только для языка F#, который скопирован с ocaml чуть менее, чем полностью, зато впоследствии оброс немаленьким количеством плюшек. F# я отмёл, как отсутствующий в моей системе, а все плюсовые средства — по причине их многочисленности. Да, иногда богатый выбор — это тоже плохо, я побоялся запутаться во всех этих лексерах и парсерах.
Кстати, это было довольно странным и неприятным для меня открытием, что оказывается, разбор любого языка состоит из двух отдельных этапов, которые выполняются разными тулзами, мне казалось, что почему бы не сделать всё в одном. Но увы.
Не буду врать, я не сразу продумал всю архитектуру языка и допиливал фичи постепенно. Но для сокращения размера материала (и чтобы быстро пройти тот путь, который у меня занял шесть прекрасных утренних воскресных часов) мы сделаем вид, будто всё было спланировано заранее. Каждая инструкция нашего языка является, скажем так, объектом. В C++ его можно было бы представить в виде одного из потомков некого базового класса Instruction, или в виде сложной структуры, или вообще в виде union. К счастью, окамл позволяет нам всё сделать максимально просто. Первый наш файл, yobaType.ml, который описывает все возможные виды инструкций, устроен максимально просто:
Каждая конструкция языка будет приводиться к одному из этих типов. DoNothing — это просто оператор NOP, он не делает ровным счётом ничего. Create создаёт переменную (у нас они всегда целочисленны), Decrement и Increment соответственно уменьшают и увеличивают заданную переменную на какое-то число. Кроме этого есть Stats для вывода статистики по всем созданным переменным и Conditional — наша реализация if, которая умеет проверять, есть ли в заданной переменной требуемая величина (или большая). В самом конце я добавил AddFunction и CallFunction — возможность создавать и вызывать собственные функции, которые на самом деле очень даже процедуры.
Следующим этапом мы опишем грамматику, те конструкции нашего языка, которые будут превращаться в инструкции одного из видов.
Перед показом кода я расскажу, как устроен наш язык. Любая конструкция, кроме запроса статистики (это у нас как бы служебная команда) и создания функции начинается и заканчивается ключевыми словами. Благодаря этому мы можем смело расставлять как угодно переносы строк и отступы. Кроме этого (мы же работаем с русским языком) я специально создал по паре инструкций для случаев, когда надо передавать и переменную, и значение. Позже увидите, зачем это было нужно. Итак, наш файл yobaParser.mly:
Первым делом мы вставляем заголовок — открытие модуля YobaType, который содержит наш тип action, описанный в самом начале. Для чисел и строк, не являющихся ключевыми словами языка (переменных) мы объявляем два специальных типа, которым указываем, что именно они в себе содержат. Для каждого из ключевых слов с помощью директивы %token мы создаём тоже свой тип, который будет идентифицировать это слово в грамматике. Можно было бы указать их все хоть в одну строчку, просто такая запись группирует всё по видам инструкций. Имейте в виду, что все созданные нами токены — это именно подстановочные типы, по которым парсер грамматики определяет, что ему делать. Обозвать их можно как угодно, то, как они будут выглядеть в самом языке, мы опишем позже. Указываем, что входной точкой для грамматики является main, и что возвращать он всегда должен объект типа action — инструкцию для интерпретатора. Наконец, после двух знаков %% мы описываем саму грамматику:
В фигурных скобках мы указываем, что делать при совпадении строки с данным вариантом, при этом $N обозначает N-ный член конструкции. Например, если мы встречаем «CALL ID» (ID — это строка, не забываем), то мы создаём инструкцию CallFunction, которой в качестве параметра передаём $2 (как раз ID) — имя вызываемой функции.
Мы дошли одновременно до практически самой простой и самой муторной части. Простая она, потому что всего лишь описывает превращение слов языка в наши токены. А муторная, потому что лексеры (а может, только окамловский лексер) плохо рассчитаны на работу с русским языком, поэтому работать с русскими символами можно только как со строками. Так как я хотел сделать ключевые слова языка регистро-независимыми, это добавило кучу геморроя — вместо простого написания «дай» надо было расписывать вариант написания каждой буквы. В общем, смотрите сами, файл yobaLexer.mll:
Я только отмечу, что этот код нельзя показывать детям и людям с хрупкой душевной организацией, потому что вся обсценная лексика языка описана именно здесь. Кроме того, в начале мы открываем модуль нашего парсера, в котором определены все типы (STATS, GIVE, TAKE и т.п.) и создаём исключение, которое будет кидаться, когда ввод закончится. Обратите внимание на 11-ую строку, в ней указывается, что пробелы и прочий мусор нужно игноировать, при этом она специально идёт после тех инструкций, которые содержат в себе пробелы. 12-ая и 25-28-ая строки обрабатывают числа и названия переменных, а 29-ая кидает то самое исключение, обозначающее конец файла.
Осталась последняя часть — сам интерпретатор, который обрабатывает наши конструкции языка. Сначала код, потом объяснение:
Первым делом мы создадим две хэштаблицы — для переменных и для функций. Начальный размер 10 взят от фонаря, у нас же тренировочный язык, зачем нам сразу много функций.
Затем объявим две небольших функции: одна — для вывода статистики, вторая — для инкремента/декремента переменных.
Дальше идёт группа из сразу трёх функций: cond обрабатывает условные конструкции (наш if), callfun отвечает за вызов функций, а process_action отвечает за обработку пришедшей на вход инструкции как таковой. Надеюсь, почему все три функции зависят друг от друга, объяснять не надо.
Обратите внимание, все варианты в process_action не выполняют действие, а всего лишь возвращают функцию, которая его выполнит. Изначально это было не так, но именно это маленькое изменение позволило мне легко и непринужденно добавить в язык поддержку пользовательских функций.
Наконец, последняяя часть кода до посинения в цикле читает и обрабатывает результат работы парсера.
Добавим к этому Makefile и можно играться:
А теперь внимание, зачем я делал поддержку разного порядка значений и переменных? Дело в том, что язык получился очень, гм, натуральным, интерпретатор буквально разговаривает с вами. Поэтому я сам постоянно путал, в каком порядке что писать:
Из недостатков можно отметить то, что при вызове функций вылезают комментарии об успешно инкременте/декременте по числу оных операций.
Надеюсь, было интересно. Весь код интерпретатора можно скачать тут (2кб).
Если более опытные люди поделятся замечаниями по поводу кода, буду благодарен.
Ну а если серьёзно, как-то раз у нас на работе кто-то в шутку предложил написать гоп-язык, чтобы программистом мог себя почувствовать себя любой. Начинать конструкции со слова «чо» и всё такое. Тут надо заметить, что, не встретив на своём жизненном пути образования в области 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кб).
Если более опытные люди поделятся замечаниями по поводу кода, буду благодарен.
