Апофеоз творения
Изучив, как превратить формальную грамматику в работающий парсер с помощью парсер-генератора 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, что мы спроектировали выше (но синтаксис исходного кода уже не будет иметь значения, мы с ним напрямую больше нигде не столкнёмся).