Elixir: Готовим парсинг правильно — yecc и leex

Лексический анализ (токенизация) и парсинг — одни из наиболее важных концепцпий в информатике и программировании. Эти концепции базируются на огромном количестве теоретических знаний, но сегодня мы о них не будем говорить, потому что их действительно много. Кроме того, подход к парсингу через "науку" может вызвать жёсткое отвращение и напугать. Между тем, практическое применение очень простое и прямолинейное. Если хотите знать больше о теории — идите в Википедию (лексический анализ и парсинг), или читайте восхитительную книгу дракона (рекомендовано к прочтению вообще всем программистам).

Обычный человек боится использовать лексеры и парсеры, а вместо них пишет велосипед на регулярных выражения. Мне кажется, что кажущаяся сложность является этому причиной. В этом посте я пострараюсь развенчать её!

Почему?

Для начала отметим, что лексеры и парсеры обычно используются вместе, но это вообще говоря не обязательно. Вы можете использовать лексер, токенизировать какую то строку в набор токенов. Или вы можете использовать парсер для понимания грамматики чего угодно.

Я говорил, что люди часто используют регулярки для "парсинга" и понимания текста. Несмотря на то, что это работает на простых задачах для парсинга, в большинстве случаев велосипед очень хрупкий и совсем не едет. Кроме того, регулярки весьма ограничены в грамматиках, которые вы пытаетесь ими описать (к примеру попробуйте парсить html регулярками) (переводчик: на самом деле — нет. Но на ассемблере тоже можно написать кластерное приложение. Масштаб проблемы приблизительно одинаковый). Поэтому иногда вам надо что-то помощнее.

Скажи привет leex и yecc

В erlang встроены два модуля, которые здорово упрощают парсинг: leex и yecc. Соответственное названию, leex — это лексер: он читает файл с определённым синтаксисом и генерирует erlang модуль (в виде *.erl файла), который можно потом компилировать и использовать для токенизирования. yecc в принципе ведёт себя так же, только генерирует не лексер, а парсер.

Так как модули доступны ввиде батареек к erlang (где то в группе Parsing tools), то по идее их можно здорово использовать во всех местах, где они могут решить проблему.

Маленький, хиленький и неправдоподобный пример

Каждая статья, которая что-то объясняет, требует примеров, поэтому давайте сделаем: будем токинизировать и парсить list языка Elixir, который может состоять только из чисел и атомов, который просто написан в строку. Финальная цель — из этой строки получить оригинальный список Elixir:

iex> ListParser.parse("[1, 2, [:foo, [:bar]]]")
[1, 2, [:foo, [:bar]]]

Так как это абсолютно бессмысленно — возьмём как отличный пример.

Итак: лексер

Первым делом нам нужно токенизировать строчку: токенизирование обозначает просто превращение строки в список токенов, которые по сути не сильно то и структурированы по сравнению с обычным списком символов (строкой).

Например, одним из токенов может быть число, например 4917: у числа 4917 чуть больше структуры, чем у списка символов [?4, ?9, ?1, ?7] потому что мы можем считать его как одно целое.

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

• скобки (левую [ и правую ]),
• запятые,
• числа,
• атомы.

Для простоты будем иметь дело только с простыми атомами, как например :foo или :foo_bar, а с жёсткими :'foo and bar' или "hello world" иметь дела не будем.

Можно очень просто и быстро сделать собственный токенайзер для такого простейшего синтаксиса, но leex здорово упростит нашу работу, позволя написать лексер с очень простым синтаксисом. Принципиально, мы задаём токены регулярками, и ассоциируем их с Erlang выражениями, которые представляют этот токен. Я упоминал, что регулярки — зло для такой работы: да, они плохи для парсинга из-за обычно рекурсивной структуры данных, но они отличны для разделения строк на одномерные структуры.

Синтаксис этих правил прост:

Regular expression: Erlang code.

Вот тут в Erlang code нужно возвращать {:token, value} кортеж, если мы хотим чтобы лексер генерировал для нас токен (на самом деле {token, Value} кортеж, если вы пишите на Erlang а не Elixir).

Наш лексер выглядит очень просто:

Rules.

[0-9]+   : {token, {int,  TokenLine, TokenChars}}.
:[a-z_]+ : {token, {atom, TokenLine, TokenChars}}.
\[       : {token, {'[',  TokenLine}}.
\]       : {token, {']',  TokenLine}}.
,        : {token, {',',  TokenLine}}.

Мы возвращаем {:token, Value} чтобы указать leex что нам надо получать сопоставленые токены (поэтому первый элемент кортежа — :token), и мы хотим добавить это в результат работы лексического анализа.

TokenLine и TokenChars — это переменные, которые leex подставляет в выражения Erlang, которые следуют за мкаждой регуляркой. Эти переменные содержат строку сопоставленного токена и содержание сопоставленного токена в виде списка символов.

Будем использовать двух- или трёх-элементные кортежи в качестве значений токена, потому что этот формат потому будет нужен yecc. Иногда нас интересует значение токена, поэтому мы используем трёхэлементный кортеж. Но иногда, значение самого токена не важно (к примеру, если это запятая), поэтому достаточно двухэлементного кортежа. Такой вид токенов обязателен. В этом случае yecc может запросто выдать нам понятное сообщение об ошибке.

Нам вообще не обязательно сохранять все токены, которые вы нашли; можно их запросто отбросить. Для этого надо передать :skip_token в кортеж. Самое типичное применение — это исключение пробелов:

[\s\t\n\r]+ : skip_token.

Регулярки могут очень просто стать тошнотворными, но мы можем просто определить их с помощью формы

ALIAS = REGEX

Такие определения помещаются в начало файла, перед списком правил. Чтобы использовать их в определениях регулярок, можно завернуть их в {}:

Definitions.

INT        = [0-9]+
ATOM       = :[a-z_]+
WHITESPACE = [\s\t\n\r]

Rules.

{INT}         : {token, {int,  TokenLine, TokenChars}}.
{ATOM}        : {token, {atom, TokenLine, TokenChars}}.
\[            : {token, {'[',  TokenLine}}.
\]            : {token, {']',  TokenLine}}.
,             : {token, {',',  TokenLine}}.
{WHITESPACE}+ : skip_token.

Мы вполне готовы попробовать наш лексер. Для начала, нам нужно написать файл с расширением .xrl. Затем, мы превратим этот файл в erlang модуль в виде .erl файла с помощью :leex.file/1. Наконец, мы можем скомпилировать вновь сгенерированный Erlang модуль. Помните о том, что большинство erlang модулей принимает список символов вместо бинварных строк, поэтому заворачивать надо в одинарные а не двойные кавычки. (Примечание: Erlang использует одинарные кавычки для сложных атомов, таких как 'foo bar'. Эти атомы не могут быть представлены через регулярку, но вы же это помните?)

iex> :leex.file('list_lexer.xrl')
iex> c("list_lexer.erl")
iex> {:ok, tokens, _} = :list_lexer.string('[1, [:foo]]')
iex> tokens
{:"[", 1}, {:int, 1, '1'}, {:",", 1}, {:"[", 1}, {:atom, 1, ':foo'}, {:"]", 1}, {:"]", 1}]

Крутяк! leex так же предоставляет возможность опредлить код erlang, который будет ассоциирован с лексером. Это реализуется с помощью секции Erlang code. в самом конце .xrl файле. Мы можем использовать это преимущество чтобы преобразовывать токены атомов в непосредственно атомы.

...

{INT}  : {token, {int,  TokenLine, list_to_integer(TokenChars)}}.
{ATOM} : {token, {atom, TokenLine, to_atom(TokenChars)}}.

...

Erlang code.

to_atom([$:|Chars]) ->
  list_to_atom(Chars).

to_atom/1 просто откидывает первый символ токена атома (который представляет собой двоеточие, $: в мире Erlang), и преобразует всё остальное в атом. Так же используем list_to_integer/1 чтобы преобзовать токен число в непосредственно число.

Лексер полностью выглядит так:

Definitions.

INT        = [0-9]+
ATOM       = :[a-z_]+
WHITESPACE = [\s\t\n\r]

Rules.

{INT}         : {token, {int,  TokenLine, list_to_integer(TokenChars)}}.
{ATOM}        : {token, {atom, TokenLine, to_atom(TokenChars)}}.
\[            : {token, {'[',  TokenLine}}.
\]            : {token, {']',  TokenLine}}.
,             : {token, {',',  TokenLine}}.
{WHITESPACE}+ : skip_token.

Erlang code.

to_atom([$:|Chars]) ->
    list_to_atom(Chars).

Работает всё так, как и ожидается:

iex> {:ok, tokens, _} = :list_lexer.string('[1, :foo]')
iex> tokens
[{:"[", 1}, {:int, 1, 1}, {:",", 1}, {:atom, 1, :foo}, {:"]", 1}]

Парсер

Теперь мы имеем одноуровневый список токен. Мы хотим придать им какую-то структуру, а потом превратить в Elixir список: нужно спарсить список токенов. Работа парсера базируется на грамматике, которая представляет собой список правил, которые описывают как токены должны структурироваться.

Мы, конечно, можем написать свой собственный парсер (хотя это и значительно сложнее, чем собственный лексер), проще воспользоваться yecc: он позволяет весьма декларативно описать правила грамматики, а кроме того его очень просто использовать с leex.

Небольшое отступление: на этом этапе вы можете думать, что имена парсера и лексера не имеют смысла. На самом деле это не так. Оби названы в честь двух очень известных программ: лексера lex и парсера yacc. Похоже, ребята из Erlang не такие психи?

Вернёмся к yecc. Основной элемент синтаксиса — правила, которые описываются в такой форме:

Left-hand side -> Right-hand side: Erlang expressions.

Слева находится категория токенов, справа — категория списка токенов. Категория токенов может быть двух видов — тупиковая и нетупиковая (terminal и non-terminal). Тупиковые — это такие токены, которые внутри себя ничего не содержат; нетупиковые — соответственно наоборот.

К примеру, :"[" или {atom, Atom} токен — тупиковые. Нетупиковый список может быть представлен через список тупиковых элементов:

list -> '[' ']'.
% or...
list -> '[' elems ']'.

% Вот тут, '%' используется для комментариев как и в Erlang.

Как вы можете видет, можно выбрать несколько условий для каждой категории: категория может принимать любые значения из перечисленных (думайте о них как о ИЛИ).

elems сам по себе нетупиковый. Мы можем его представить как единичный элемент, или элемент + запятая + список элементов:

elems -> elem.
elems -> elem ',' elems.

Соответственно elems могут быть elem, либо elem, elem и так далее.

elem сам по себе так же нетупиковый: он представляет число, атом или список. Заметьте, как элегантно мы может представить вложенность списка в список:

elem -> int.
elem -> atom.
elem -> list.

Красава!

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

Terminals '[' ']' ',' int atom.
Nonterminals list elems elem.

Можно так же определить корневой элемент, который будет являться стартовым нетупиковым элементом, который генерирует оригинальную грамматику. В нашем случае это — список:

Rootsymbol list.

Мы почти закончили! Осталось только превратить списки, которые только что были распарсены, в списки Elixir. Будем делать это в Erlang code, ассоциированным с каждым правилом парсинга. В этих выражениях, у нас есть парочка специальных атомов: $1, $2, $3 и так далее. yecc подставляет в них результат Erlang кода, который ассоциирован с категорией с тем же индексом, что и в правой части правила. Я вот прям слышу, как вы подумали "щито?" Вы правы, без примера не разберёшься:

list ->
  '[' ']' : []. % an empty list translate to, well, an empty list
list ->
  '[' elems ']' : '$2'. % the list is formed by its elements

elems ->
  elem : ['$1']. % single-element list (and base case for the recursion)
elems ->
  elem ',' elems : ['$1'|'$3']. % '$3' will be replaced recursively

elem -> int  : extract_token('$1').
elem -> atom : extract_token('$1').
elem -> list : '$1'.

% Точняк, тут тоже можно использовать код Erlang.
Erlang code.

extract_token({_Token, _Line, Value}) -> Value.

Всё готово! Вот как выглядит финальный вариант нашего парсера:

Nonterminals list elems elem.
Terminals '[' ']' ',' int atom.
Rootsymbol list.

list -> '[' ']'       : [].
list -> '[' elems ']' : '$2'.

elems -> elem           : ['$1'].
elems -> elem ',' elems : ['$1'|'$3'].

elem -> int  : extract_token('$1').
elem -> atom : extract_token('$1').
elem -> list : '$1'.

Erlang code.

extract_token({_Token, _Line, Value}) -> Value.

Сейчас мы можем создать Erlang файл из yecc файла (которые имеет расширение .yrl), точно так же как мы делали с leex:

iex> :yecc.file('list_parser.yrl')
iex> c("list_parser.erl")
iex> :list_parser.parse([{:"[", 1}, {:atom, 1, :foo}, {:"]", 1}])
{:ok, [:foo]}

Работает!

Клеим танчик

Мы может выкинуть результат работы лексера сразу в парсер и-ии:

iex> source = "[:foo, [1], [:bar, [2, 3]]]"
iex> {:ok, tokens, _} = source |> String.to_char_list |> :list_lexer.string
iex> :list_parser.parse(tokens)
{:ok, [:foo, [1], [:bar, [2, 3]]]}

Восхитительно!

Я не понял, а где Elixir?

Вручную генерировать файлы Erlang из .xrl и .yrl фалов, а потом компилирование уже этих файлов очень быстро надоедает. К сачстью, Mix может сделать всё за нас!

Mix поддерживает концепцию "компиляторов": они делают как раз то, что можно предположить — компилируют. Mix предоставляет компиляторы для Erlang (просто компилируют .erl файлы через установленный Erlang), ещё один компилятор — для Elixir, но так же есть компиляторы для leex и yecc. Они вообще-то даже включены по умолчанию, это можно проверить, вызвав функцию Mix.compilers/0 внутри Mix проекта (переводчик: и не только. Кстати, действительно по умолчанию, проверьте прямо сейчас!):

iex> Mix.compilers()
[:yecc, :leex, :erlang, :elixir, :app]

Последнюю вещь, которую стоит сделать для того, чтобы это всё отлично работало в Mix проекте — положить файлы .xrl и .yrl в директорию src/ проекта, и вуаля — модули видны в вашем коде после компиляции.

mix new list_parser
mkdir list_parser/src
mv ./list_parser.yrl ./list_lexer.xrl ./list_parser/src/

И допишем небольшую обёртку:

# ./list_parser/lib/list_parser.ex

defmodule ListParser do
  @spec parse(binary) :: list
  def parse(str) do
    {:ok, tokens, _} = str |> to_char_list |> :list_lexer.string
    {:ok, list}      = :list_parser.parse(tokens)
    list
  end
end

Таки где тут гешэфт?

Всё вышеизложенное может выглядеть весьма абстрактно, но я уверен что leex и yecc имеют миллиард путей применения. К примеру, я недавно написал парсер для PO файлов в рамках разработки биндинга GNU gettext для Elixir. Я использовал yecc чтобы описать парсер: всё это вылилось в очень декларативную, чистую и простую для понимания грамматику (вот тут посмотри), и вообще я суперщаслив и рад. Мы не использовали leex, главным образом потому что он нам показался слишком мощным инструментом для такой простой задачи, и мы написали собственный лексер (как я говорил, так тоже можно).

Ещё пример? Ну, есть такой: вы где-нибудь хоть краем глаза слышали о языке Elixir? Язык весьм наплохой, построен наверху Erlang VM, сфокусирован на параллельном программировании, устойчивости к пад… Да, он парсится yecc :)

Резюмируем

Мы запросто сделали лексер и парсер для преобразования строк-дампов списков Elixir в реальные списки Elixir. Мы испольщовали leex для генерации лексера и yecc для генерации парсера.

Мы рассмотрели только самые элементарные возможности этих инструментов: они могут сложнее (yecc генерирует LALR парсеры, если вы знаете, что это). Но для этого — добро пожаловать в документацию.