Апофеоз творения

Изучив, как превратить формальную грамматику в работающий парсер с помощью парсер-генератора racc…

И ознакомившись с тем, какой язык мы хотим получить…

Мы, наконец, можем приступить к написанию opus magnum.

Начнём с парсера и продолжим, в следующей лекции, реализацией «виртуальной машины».

Цель — добиться превращения вот такого кода:

1 + 2 * -3 ^ 4 <= x

Вот в такую префиксную форму AST:

[:program, [], [
  [:binary_operator, '<=',
    [:binary_operator, '+',
      [:literal, 1],
      [:binary_operator, '*',
        [:literal, 2],
        [:unary_operator, '-',
          [:binary_operator, '^',
            [:literal, 3],
            [:literal, 4]
          ]
        ]
      ]
    ],
    [:variable, 'x']
  ]
]]

Выглядит страшно, потому что сложно. Сложные вещи надо рассматривать по частям.

Вооружимся технологиями

Реализовывать будем с использованием парсер-генератора racc.

Можно, конечно, было бы воспользоваться комбинацией известных методов (кстати, некоторые компиляторы языка C, например, примерно так «вручную» и пишутся), но мы уже на предыдущих задачах заматерели и поняли, как оно «под капотом» устроено — поэтому можем с чистой совестью расслабиться и воспользоваться достижениями современных технологий.

Заготовка проекта

Установка Ruby

Нам понадобится Ruby не ниже версии 2.7.0 (на 2.6.х часть приведённых ниже примеров кода не будет работать), установить можно через RVM:

rvm install 2.7.0

Gemfile

Создадим Gemfile, где пропишем rake и racc:

# Gemfile
source "https://rubygems.org"

gem 'racc'
gem 'rake'

Наберём bundle install, установим гемы.

Лексер

Создадим директорию lib/.

В файл lib/lexer.rb положим следующий код:

module ProceduralInterpreter
  module Lexer
    def self.lex(string)
      string = string.gsub(/\n+/, "\n")

      symbols =
        string.
          #         число           операторы    \n      переменная           строка     сравнения         <>
          scan(/(?:\d+(?:\.\d+)?)|[-()*+\/^&|!,]|\n|(?:[a-z][a-z_0-9]*\??)|(?:"[^"]*")|(?:[<>=](?!>)=?)|(?:<>)/).
          map { |x| x =~ /\A\d+(\.\d+)?\Z/ ? x.to_f : x }

      symbols.map do |s|
        case s
        when Numeric
          [:LITERAL, s]
        when /"/ # двойная кавычка - "
          [:LITERAL, s[1..-2]]
        when 'true', 'false'
          [:LITERAL, s == 'true']
        when '(', ')', '*', '/', '^',
             '&', '|', '!', '=', ',', '+', '-',
             '<', '>', '<=', '>=', '==', '<>', ','
          [s, s]
        when "\n"
          [:NEWLINE, "\n"]
        when 'end'
          [:END, 'end']
        when 'fn'
          [:FN, 'fn']
        when 'if'
          [:IF, 'if']
        when 'else'
          [:ELSE, 'else']
        when 'return'
          [:RETURN, 'return']
        when 'case'
          [:CASE, 'case']
        when 'when'
          [:WHEN, 'when']
        when 'while'
          [:WHILE, 'while']
        when /\A[a-z][a-z_0-9]*\??\z/
          [:VARIABLE, s]
        else
          raise "Unknown token #{s.inspect}"
        end
      end
    end
  end
end

Лексер является развитием подхода предыдущего упражнения с учётом требований racc и грамматики разрабатываемого языка.

Лексер реализован как единственный метод соответствующего класса (класс выделен в модуль/namespace ProceduralInterpreter, в котором будут лежать все разрабатываемые нами классы).

Парсер

Определение парсера будет лежать в lib/parser.y.

Заготовка данного racc-файла будет выглядеть следующим образом:

# lib/parser.y
class ProceduralInterpreter::Parser
prechigh
  right '^'
  right UNARY
  left '*' '/'
  left '+' '-'
  left '<' '<=' '>' '>='
  right '==' '<>'
  left '&'
  left '|'
preclow

token
  LITERAL VARIABLE
  FN
  IF ELSE
  CASE WHEN
  WHILE
  END
  RETURN
  NEWLINE

options no_result_var

rule
end

---- inner

def initialize(tokens)
  @tokens = tokens.dup
  super()
end

def parse
  do_parse
end

private

def next_token
  @tokens.shift
end

Заготовка стандартная, за исключением операторов. Чтобы не смущать пользователей нашего языка, приоритет операторов следует взять из какого-нибудь уже существующего языка. Например, из C++.

Токены перечислены (после ключевого слова token) в соответствии с теми названиями, которые мы им дали выше в лексере.

Компиляция парсера

Создадим в корне проекта Rakefile и пропишем в качестве задачи по умолчанию выполнение команды компиляции парсера:

# Rakefile
desc "Compile parser"
task :compile do
  `racc lib/parser.y -o lib/parser.rb`
end

task default: :compile

«Объявления» и «тело» программы

Подготовленный читатель, в качестве упражнения, может делать самостоятельные наброски содержания y-файла в соответствии с предлагаемым планом, прежде чем подсматривать в предлагаемый ответ.

Первый шаг. Выхватим глазами из нашего технического задания следующий абзац:

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

Из него мы делаем следующий вывод: в программе должно быть две части — начальная, в которой определяются все функции; и дальнейшая, в которой идут инструкции.

AST спроектируем следующим образом:

[:program, [<массив объявлений функций...>], [<массив инструкций...>]]

Так и запишем:

# lib/parser.y, между словами rule... end:

rule
  program:
    declarations body { return [:program, val[0], val[1]] }

  declarations:
    function_definitions
    | /* empty */        { return [] }

  body:
    statements
    | /* empty */ { return [] }
end

Нетерминалы function_definitions и statements набросаем далее.

Мы воспользовались стандартным приёмом “0 или 1” формулирования грамматик.

Стоит также оживить в памяти тот факт, что в присоединённый к ветке правила вывода блок Ruby-кода ({ ... }) будет передан массив val, в котором содержатся все токены данной ветки (уже обработанные) по порядку.

Объявления функций

Вызов функций в ТЗ выглядит вот так:

fn adult?(x)
  x >= 18
end

Запланируем получить следующий AST из этого фрагмента исходного кода:

# массив всех объявленных функций
[
  # конкретная функция
  [:function_definition, 'adult?', ['x'], [<массив инструкций>]]
]

Сверяясь с вышеприведённым кодом лексера (обозначениями типов токенов) раскрываем нетерминал function_definitions:

rule
  # ...
  function_definitions:
    function_definitions function_definition  { return val[0] << val[1] }
    | function_definition { return [val[0]] }

  function_definition:
    FN VARIABLE '(' optional_function_definition_arguments ')' NEWLINE
      statements
    END NEWLINE { return [:function_definition, val[1], val[3], val[6]] }

  optional_function_definition_arguments:
    function_definition_arguments
    | /* empty */                         { return [] }

  function_definition_arguments:
    function_definition_arguments ',' VARIABLE { return val[0] << val[2] }
    | VARIABLE                                 { return [val[0]] }

  statements:
    statements statement NEWLINE { return val[0] << val[1] }
    | statement NEWLINE          { return [val[0]] }
end

Центральный нетерминал — function_definition, который для удобства чтения разбит на несколько строк в y-файле (переводы строк не значимы в данном коде), чтобы слегка напоминать то, что мы видим в исходном коде целевого языка.

Промежуточный нетерминал optional_function_definition_arguments вводится как приём реализации правила “0 или более”.

NEWLINE — тип терминала из лексера, обозначающая простой перенос строки \n. Кстати, в грамматике языка Ruby используется в аналогичном месте вместо переноса строки нетерминал с условным названием TERM, который определяется как «перенос строки или ;» (TERM : ';' | '\n').

Поэтому в Ruby вы сможете написать так:

puts "строка 1"; puts "строка 2";

А в нашем учебном языке придётся писать так (скобки при вызове функции также обязательны):

output("строка 1")
output("строка 2")

Тело программы

Тело программы (body) — это инструкции или ничего:

body:
  statements
  | /* empty */ { return [] }

В AST мы желаем получить либо массив данных инструкций, либо пустой массив.

Инструкции

Наконец, дошли до ключевого места. Что такое «инструкции» (statements) и «инструкция» (statement).

«Инструкции» — это набор отдельных инструкций, разделённых переводом строки (обозначен как токен NEWLINE в лексере):

statements:
  statements statement NEWLINE { return val[0] << val[1] }
  | statement NEWLINE          { return [val[0]] }

В AST мы возвращаем массив отдельных инструкций.

Инструкция (единственное число) бывает трёх типов: выражение, присвоение или оператор возврата return:

statement:
  expression
  | assignment
  | while
  | return

Разница между инструкцией и выражением

Про языки вроде Ruby часто, в положительном ключе отмечая их особенности, говорят: every statement is expression, каждая инструкция является выражением.

Концептуально (на уровне общего смысла), выражение — это просто некая алгебраическая запись. Выражение ничего не делает, если только внутри него не вызывается функция с побочными эффектами (например, выводом на экран или записью в файл и т. п.).

Например, 1 + 2 * 3 — если мы напишем это выражение на отдельной строке, то программа, вычислив результирующую 7, сразу же выкинет этот результат, поскольку он нигде далее не используется и не может использоваться.

Другое дело, если мы сохраним этот результат в переменную: x = 1 + 2 * 3. Данная строка уже совершает некое действие, тем самым в целом являясь «инструкцией», а не выражением.

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

В языках типа Ruby, с чего мы начали-то, инструкции типа условных операторов являются на самом деле выражениями (имеют вычисляемое значение):

x = if a > b
  5
else
  3
end

В языке C, к примеру, такая запись невозможна.

if вернёт последнюю выполненную строку (из той ветки, по которой пошло выполнение).

При дизайне нашего языка мы решили отнести, как и в Ruby, условные операторы (if, case) к выражениям. Но, вопреки Ruby, циклы и присвоения мы отнесли к инструкциям, и их нельзя будет использовать в правой части присвоения:

# Валидный код на Ruby, но не на проектируемом учебном процедурном языке
x = while a > b
  a = a - 1
end

Однако, как и в Ruby, у нас каждое выражение одновременно является инструкцией, т. е. тело программы может состоять из одной строки «2 * 2».

В языке C, опять же, такое невозможно: требуется хотя бы использовать инструкцию return: return 2 * 2.

Основные типы инструкций

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

assignment: VARIABLE '=' expression { return [:assignment, val[0], val[2]] }

return:
  RETURN expression { return [:return, val[1]] }

while:
  WHILE expression NEWLINE
    statements
  END                      { return [:while, val[1], val[3]] }

В AST мы хотим получить:

• для присвоения — [:assigment, <название_переменной>, <присваиваемое_выражение>];
• для return — [:return, <возвращаемое_выражение>];
• для while — [:while, <условие>, <массив_инструкций>];

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

Выражение

Выражения в традиционных языках программирования в целом повторяют и расширяют наивную грамматику математических выражений:

/* НЕ БУДЕТ РАБОТАТЬ */

expression:
  LITERAL
  | VARIABLE
  | '(' expression ')'
  | expression binary_operator_expression
  | unary_operator expression
  | ... /* вызов функций, if, case, ... */

binary_operator: "+" | "-" | "*" | "/" | ...

Выражение — это либо буквальное значение (число или строка), либо переменная, либо выражение в скобках, либо бинарная операция, либо унарная операция.

Плюс все языковые конструкции, которые мы своим решением отнесли к выражениям, а не инструкциям. Но подвох не в них.

Мы снова натыкаемся на уже известные грабли неоднозначности сворачивания инфиксного выражения.

Как же так, ведь мы определили приоритет операций, который должен ликвидировать всякую неоднозначность?

Должен, но для использования таблицы приоритетов в парсере правила, которые будут разрешены на основе приоритетов, должны быть:

• в разных ветках одного и того же нетерминала (в нашем случае expression);
• буквально содержать те токены, которые указаны в таблице приоритетов.

Мы же попытались схитрить и вместо буквального указания токенов +, - и т. д. в правилах вывода expression заменили их общим binary_operator. Это не будет работать — парсер-генератор не настолько умный (отметим, что это скорее техническое ограничение конкретных парсер-генераторов, а не некая концептуальная проблема).

Правильно делать так (финальный код с блоками получения AST):

/* БУДЕТ РАБОТАТЬ */

expression:
  LITERAL                      { return [:literal, val[0]] }
  | VARIABLE                   { return [:variable, val[0]] }
  | '(' expression ')'         { return val[1] }
  | expression '^' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  | expression '*' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  | expression '/' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  | expression '+' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  | expression '-' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  /* ... ВСЕ бинарные операции - пропущено для краткости ... */
  | expression '&' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  | expression '|' expression  { return [:binary_operator, val[1], val[0], val[2]] }
  | unary_operator expression  { return [:unary_operator, val[0], val[1]] } =UNARY
  | function_call
  | if_else
  | case_when

unary_operator: '-' | '+' | '!'

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

Правила получения AST:

• для буквального значения — [:literal, <буквальное_значение>];
• для переменной — [:variable, <имя_переменной>];
• для выражения в скобках — «снять» скобки;
• для бинарной операции — [:binary_operator, <оператор>, <левая_часть>, <правая_часть>];
• для унарной операции — [:unary_operator, <оператор>, <правая_часть>].

Для вызова функции, управляющих конструкций if и case грамматика и правила получения AST задаются далее.

Вызов функции

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

# x - формальный аргумент
fn square(x)
  x * x
end

# 1 + 2 + 3 * 4 = 10 - актуальный (реальный) аргумент
square(1 + 2 + 3 * 4)

Выразим это в грамматике:

function_call:
  VARIABLE '(' optional_function_call_arguments ')' { return [:function_call, val[0], val[2]] }

optional_function_call_arguments:
  function_call_arguments
  | /* empty */                   { return [] }

function_call_arguments:
  function_call_arguments ',' expression { return val[0] << val[2] }
  | expression                           { return [val[0]] }

В AST получаем: [:function_call, <название>, <массив_аргументов>].

Условный переход if - else - end

Условный переход if содержит опциональную else-часть:

if_else:
  IF expression NEWLINE
    statements
  maybe_else
  END                   { return [:if_else, val[1], val[3], val[4]] }

maybe_else:
  ELSE NEWLINE
    statements  { return val[2] }
  | /* empty */ { return [] }

В AST для условного перехода получаем: [:if_else, <условие>, <массив_инструкций_if_части>, <массив_инструкций_else_части>].

Мы используем тот же нетерминал statements, который обсуждали несколькими тактами ранее, говоря о теле всей программы. Переиспользование нетерминалов делает наш язык последовательным, не содержащим странных «исключений»: гарантированно любая последовательность инструкций, допустимая в теле («корне») программы, допустима внутри условного оператора, тела функции и т. п. (и наоборот).

Оператор выбора case - when - end

Оператор case-when с опциональной else-частью и одним или более when запишем по накатанной:

case_when:
  CASE expression NEWLINE
  whens
  maybe_else
  END                     { return [:case_when, val[1], val[3], val[4]] }

whens:
  whens when { return val[0] << val[1] }
  | when     { return [val[0]] }

when:
  WHEN expression NEWLINE
    statements            { return [val[1], val[3]] }

На выходе (в AST) мы получим:

[:case_when, <оцениваемое_выражение>,
  [
    [<when_условие>, <массив_инструкций>],
    ...
  ],
  <else_инструкции>
]

Мы здесь не делаем никаких сложных преобразований, записываем AST «как есть». Можно было уже на уровне парсера преобразовать case - when к череде вложенных if - else, но мы не будем этого делать, реализуя самый простой и прямолинейный вариант.

Обратите внимание, что maybe_else у when тот же самый, что у if. Это ещё одна подсказка, что здесь мы двигаемся в верном направлении и язык получается целостный/однородный.

Создание виртуальной машины

Для удобства чтения, создание виртуальной машины описано в следующей лекции. Разрабатывая виртуальную машину нам надо держать под рукой те кусочки AST, что мы спроектировали выше (но синтаксис исходного кода уже не будет иметь значения, мы с ним напрямую больше нигде не столкнёмся).