MiniML

English README

MiniML - это небольшой учебный проект на OCaml: интерпретатор компактного ML-подобного языка со своим AST, лексером, парсером, вычислителем и CLI.

Сейчас в проекте есть:

• целые числа и булевы значения
• арифметические, логические и сравнительные операции
• if ... then ... else
• let и let rec
• анонимные функции и применение функций
• REPL и запуск программы из файла

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

Ниже приведена BNF-грамматика MiniML, строго соответствующая текущей реализации парсера из lib/parser.ml:

<program> ::= <expr>

<expr> ::= <if-expr>

<if-expr> ::= <if-form>
            | <let-expr>

<if-form> ::= "if" <expr> "then" <expr> "else" <expr>

<let-expr> ::= <let-form>
             | <fun-expr>

<let-form> ::= "let" <let-binding>

<let-binding> ::= <ident> "=" <expr> "in" <expr>
                | "rec" <ident> "=" <expr> "in" <expr>
                | "rec" <ident> <ident> "=" <expr> "in" <expr>

<fun-expr> ::= <fun-form>
             | <or-expr>

<fun-form> ::= "fun" <ident> "->" <expr>

<or-expr> ::= <and-expr>
            | <and-expr> "||" <or-expr>

<and-expr> ::= <rel-expr>
             | <rel-expr> "&&" <and-expr>

<rel-expr> ::= <add-expr>
             | <add-expr> "=" <add-expr>
             | <add-expr> "<>" <add-expr>
             | <add-expr> "<" <add-expr>
             | <add-expr> "<=" <add-expr>
             | <add-expr> ">" <add-expr>
             | <add-expr> ">=" <add-expr>

<add-expr> ::= <mul-expr> <add-tail>

<add-tail> ::= "+" <mul-expr> <add-tail>
             | "-" <mul-expr> <add-tail>
             | ε

<mul-expr> ::= <unary-expr> <mul-tail>

<mul-tail> ::= "*" <unary-expr> <mul-tail>
             | "/" <unary-expr> <mul-tail>
             | ε

<unary-expr> ::= "-" <unary-expr>
               | "not" <unary-expr>
               | <app-expr>

<app-expr> ::= <atom> <app-tail>

<app-tail> ::= <app-arg> <app-tail>
             | ε

<app-arg> ::= <atom>
            | <fun-form>
            | <if-form>
            | <let-form>

<atom> ::= <int>
         | "true"
         | "false"
         | <ident>
         | "(" <expr> ")"

Лексические элементы:

<ident> ::= <ident-start> { <ident-char> }
<ident-start> ::= letter | "_"
<ident-char> ::= letter | digit | "_"
<int> ::= digit { digit }

Приоритет операций, от более высокого к более низкому:

• применение функции
• унарные - и not
• * и /
• + и -
• операции сравнения
• &&
• ||

Пример использования

Пример программы:

let rec fact n =
  if n = 0 then 1 else n * fact (n - 1)
in
fact 5

Результат:

120

Пример в REPL:

> let add = fun x -> fun y -> x + y in add 3 4;;
7

Сборка и запуск

Требования:

• OCaml
• Dune
• opam

Сборка:

dune build

Запуск REPL:

dune exec MiniML

Запуск программы из файла:

dune exec MiniML -- path/to/program.ml

Запуск тестов:

dune runtest

Покрытие кода

Для запуска тестов с покрытием через bisect_ppx:

find . -name '*.coverage' -delete
dune runtest --instrument-with bisect_ppx --force
bisect-ppx-report summary
bisect-ppx-report html

После этого HTML-отчёт будет доступен в _coverage/index.html.

Как помочь проекту

Если хочешь помочь проекту, можно:

• открыть issue с описанием бага или идеи
• прислать pull request с небольшим сфокусированным изменением
• добавить тесты и улучшить документацию

Лицензия

Проект распространяется под лицензией Apache License 2.0.

Инструменты

Для Continuous Integration используется GitHub Actions. Форматирование проверяется через ocamlformat.