Главная / ПрограммированиеСоздаём язык программирования → Лекция А4. Калькулятор с переменными (micro-LISP)

Микро-LISP-интерпретатор

Язык программирования Lisp знаменит «в народе» благодаря своей хорошо узнаваемой «скобочной структуре» (S-выражениям). Реализуем интерпретатор некоего минималистичного аналога Lisp-образного языка (micro-LISP интерпретатор).

Расширим грамматику префиксных выражений следующим образом:

<program> ::= "(" "program" <statements> ")"

<statements> ::=
  <statement>
  | <statement> <statements>

<statement> ::=
  "(" <operation> ")"
  | <identifier>

<operation> ::=
  <bin_op> <statement> <statement> ; бинарная операция
  | <un_op> <statement>            ; унарная операция
  | "=" var <statement>            ; присвоение значения переменной

<identifier> ::=
  var                              ; переменная
  | number                         ; число

<bin_op> ::= "+" | "-" | "*" | "/"
<un_op> ::= "-" | "+"

; var ::= /\A[a-z][a-zA-Z0-9_]*\z/
; number ::= /\A[0-9]+\z/

Будем считать «комментариями» всё, начиная с ; и до конца строки (не отображено формально в грамматике, чтобы не переусложнять запись).

Как можно видеть, целевая грамматика не является леворекурсивной, следовательно, для её разбора можно применить простой метод рекурсивного нисходящего разбора.

Программа на нашем диалекте micro-LISP будет выглядеть следующим образом:

(program
  (= x (* 2 2))  ; x = 2 * 2
  (= y (/ 10 2)) ; y = 10 / 2
  (+ x y)        ; x + y
)

А абстрактное синтаксическое дерево мы хотим получить вот какое:

[:program, [
  [:assignment,
    "x",
    [:binary, "*", [:number, 2], [:number, 2]]
  ],
  [:assignment,
    "y",
    [:binary, "/", [:number, 10], [:number, 2]]
  ],
  [:binary, "+", [:variable, "x"], [:variable, "y"]]
]]

Отдельно по каждому языковому элементу:

# число, например 5
[:number, 5]

# переменная, например my_var (в выражении, не в присвоении)
[:variable, "my_var"]

# бинарная операция, например (+ a b)
# (a и b будут представлены отдельными массивами)
[:binary, "+", a, b]

# унарная операция (- a)
# (a будет представлено отдельным массивом)
[:unary, "-", a]

# присвоение, например (= x a)
# (a будет представлено отдельным массивом)
[:assignment, "x", a]

# программа
[:program, [<массив инструкций>]]

Интерпретатор (реализуем на языке Ruby) должен выводить на экран результат выполнения последней команды:

; ./simple_program.micro_lisp

(program
  (= x (* 2 2))  ; x = 2 * 2
  (= y (/ 10 2)) ; y = 10 / 2
  (+ x y)        ; x + y
)
> ./interpreter.rb simple_program.micro_lisp
9

Как обычно, для создания интерпретатора требуется реализовать лексер, парсер и «виртуальную машину». В данной лекции акцент на последнем.

Лексер

Будем использовать простейший минималистичный лексер:

def lex(string)
  # Удаляем комментарии - всё, что после ; в строке
  string = string.gsub(/;.*$/, '')

  # Разбиваем на токены
  string.scan(/\d+|[-()*+\/=]|(?:[a-z][a-zA-Z0-9_]*)/)
end

На уровне лексера, кроме типовой задачи нарезания строки на токены, удаляем из исходного кода комментарии.

Парсер

Создание парсера предлагается читателю в качестве упражнения.

Owl

Как нарисовать сову — пошаговые инструкции.

Можно воспользоваться методом рекурсивного нисходящего парсинга из предыдущей лекции, можно методом автогенерации по грамматике из следующей.

В данном примере есть одна существенная особенность. Рассмотрим следующее правило вывода:

<operation> ::=
  <bin_op> <statement> <statement> ; бинарная операция
  | <un_op> <statement>            ; унарная операция
  | "=" var <statement>            ; присвоение значения переменной

Для того, чтобы отличить унарную операцию от бинарной, недостаточно заглянуть «на один символ вперёд».

Например, в выражении целевого языка (- (+ 3 5)) для того, чтобы понять, что минус унарный, а не бинарный, требуется полностью считать фрагмент (+ 3 5). Формально говоря, грамматика не относится к классу LL(1).

Для автоматических LR парсеров это не проблема, для ручного метода рекурсивного спуска требуется аккуратно «сохранить» и, при необходимости, «откатить» ленту.

Например, вот так можно реализовать метод парсинга нетерминала operation на Ruby:

# <operation> ::=
#   <bin_op> <statement> <statement> ; бинарная операция
#   | <un_op> <statement>            ; унарная операция
#   | "=" var <statement>            ; присвоение значения переменной
def parse_operation(tokens)
  # Сохраним "бекап" исходной входной ленты
  source_tokens = tokens
  tokens = source_tokens.dup

  # Первая ветка: <bin_op> <statement> <statement>
  begin
    op = parse_bin_op(tokens)
    left = parse_statement(tokens)
    right = parse_statement(tokens)

    # Успех! Возвращаем исходную ленту и результат.
    source_tokens.replace(tokens)

    return [:binary, op, left, right]
  rescue ParseError
  end

  # Неудача. Делаем другой клон входной ленты
  tokens = source_tokens.dup

  # Пробуем вторую ветку: <un_op> <statement>
  begin
    op = parse_un_op(tokens)
    left = parse_statement(tokens)

    # Успех! Возвращаем исходную ленту и результат.
    source_tokens.replace(tokens)

    return [:unary, op, left]
  rescue ParseError
  end

  # Неудача. Возвращаемся к работе с исходной лентой.
  tokens = source_tokens

  # Пробуем третий вариант (единственный оставшийся)
  shift(tokens, "=")
  left = parse_var(tokens)
  right = parse_statement(tokens)

  # left[1] - потому что parse_var вернёт [:variable, "x"], а нам здесь нужен этот "x"
  [:assignment, left[1], right]
end

Для дальнейшего изложения предположим, что интерпретатор реализован в виде класса MicroLisp::Parser, который находится по пути lib/parser.rb.

У данного класса будет:

  • конструктор, принимающий строку текста в качестве единственного аргумента;
  • метод parse без аргументов, возвращающий AST, соответствующий переданной ранее в конструктор строке.

Напишем вспомогательный файл main.rb

# main.rb

require_relative 'lib/parser'

input_file = ARGV.first || "./example.lisp"

unless input_file
  puts "Передайте имя файла первым аргументом"
  exit
end

input = File.read(input_file)
ast = MicroLisp::Parser.new(input).parse

Перед переходом к следующему пункту данный код должен работать.

Виртуальная машина

Спроектируем и разработаем «виртуальную машину» — часть интерпретатора, которая будет «перемалывать» AST в конечный результат.

Lisp machine

LISP-машина

По большому счёту, единственное принципиальное отличие от программной модели простой арифметической машины — наличие переменных.

Заготовка

Создадим заготовку класса «виртуальной машины» внутри lib/vm.rb:

module MicroLisp
  class InterpretError < StandardError; end

  class VM
    def initialize(ast)
      # ...
    end

    def run
      # ...
      # вернуть результат вычисления последней инструкции
      # или InterpretError
    end
  end
end

Допишем main.rb до финального вида:

require_relative 'lib/parser'
require_relative 'lib/vm'

input_file = ARGV.first || "./example.lisp"

unless input_file
  puts "Передайте имя файла первым аргументом"
  exit
end

input = File.read(input_file)
ast = MicroLisp::Parser.new(input).parse

pp ast

puts MicroLisp::VM.new(ast).run

В файл example.lisp (пробная программа для нашего интерпретатора) запишем следующий код:

(program
  (= x (* 2 5))
  (= y (+ 4 7))
  (+ x y)
)

Цель — сделать так, чтобы при запуске main.rb выводился правильный ответ (5 * 2 + (4 + 7) = 21):

> ruby main.rb
28

Формально, класс MicroLisp::VM должен реализовать два метода:

  • конструктор, в который единственным аргументом принимать AST (соответствующий ранее указанной спецификации);
  • метод run, который должен вернуть результат исполнения последней инструкции программы.

Переменные

Текущие значения переменных будем хранить в отдельном «регистре» машины:

@variables = {
  "x" => 1,
  "y" => 2,
  ...
}

Инициализируем @variables в конструкторе:

def initilaize(ast)
  @variables = {}
end

Программа = инструкция, инструкция, …

Для исполнения кода нам требуется исполнить каждую отдельную инструкцию:

def run
  @statements.each do |statement|
    execute(statement)
  end
end

Таким образом, заготовка класса со всеми методами получится вот какая:

# lib/vm.rb

module MicroLisp
  class InterpretError < StandardError; end

  class VM
    def initialize(ast)
      @statements = ast[1]
      @variables = {}
    end

    def run
      result = nil

      @statements.each do |statement|
        result = execute(statement)
      end

      # вернуть результат исполнения
      # последней инструкции
      result
    end

    private

    def execute(statement_ast)
      # исполнить отдельную инструкцию
    end
  end
end

Исполнение инструкций

Осталось дописать метод execute(statement_ast), который принимает на вход фрагмент ast, соответствующий отдельной инструкции, и выполняет её.

Используем в коде pattern matching.

def execute(statement_ast)
  case statement_ast
  in [:assignment, variable_name, expression]
    @variables[variable_name] = execute(expression)
  in [:binary, op, a, b]
    case op
    when '+'
      execute(a) + execute(b)
    when '-'
      execute(a) - execute(b)
    when '*'
      execute(a) * execute(b)
    when
      execute(a).to_f / execute(b)
    else
      raise InterpretError.new("Unknown operation: #{a.inspect}")
    end
  in [:unary, op, a]
    case op
    when '+'
      execute(a)
    when '-'
      -execute(a)
    else
      raise InterpretError.new("Unknown operation: #{a.inspect}")
    end
  in [:number, x]
    x
  in [:variable, variable_name]
    @variables[variable_name]
  else
    raise InterpretError.new("Unknown statement: #{statement_ast.inspect}")
  end
end

Выясняем, какой у инструкции тип (присвоение, бинарная операция, унарная операция, просто число, просто переменная, неведомое нечто) и выполняем её:

  • если число — просто вернуть его;
  • если переменная — вернуть её текущее значение из «регистра» @variables;
  • если присвоение — вычислить правую часть и «присвоить» результат переменной (сохранить новое значение переменной в @variables);
  • если бинарный оператор, то вычислить левую и правую часть и выполнить операцию;
  • если унарный оператор, то вычислить единственный операнд и выполнить операцию.

Заключение

Все отдельные кусочки знаний на месте, осталось сделать финальную сборку в двух последних лекциях основного трека цикла.

С этого момента вполне может на мгновение проскочить мысль о какой-то вещи, которая раньше воспринималась как данность, не обращала на себя внимания, хоть и была на самом виду.

Например, почему в Pascal-е if пишется так:

if <condition> then
  <statement>;
end;

…в C так:

if (<condition>)
  <statement>;

…или так:

if (<condition>) {
  <statement>;
};

…в Ruby так:

if <condition>
  <statement>
end

…в Python так:

if condition:
  statement

Проскочить, оставить после себя пару смутных фрагментов чего-то похожего на BNF, и иррациональное незаслуженное чувство близости к кому-то вроде Вирта, Ритчи, Матцумото или Гивдо ван Россума.