Простейший метод написания парсера

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

Метод парсинга, который мы здесь разберём (recursive descent parsing), является самым простым при «ручном» написании парсеров.

Суть метода заключается в следующем: на каждый «нетерминал» создаётся функция, которая принимает список не считанных с входной ленты токенов и «распознает» данный нетерминал («съедая» соответствующие ему символы):

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

У метода рекурсивного нисходящего парсинга есть известные подводные камни:

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

Учебный пример: «язык массивов»

Рассмотрим следующую учебную BNF-грамматику, задающую массив чисел (с возможностью записывать вложенные массивы):

<array> ::=
  "[" <items> "]"
  | "[" "]"

<items> ::=
  <item> "," <items>
  | <item>

<item> ::=
  number
  | <array>

Требуется преобразовать подобную строку в массив на используемом языке программирования.

Примеры строк:

[1,2,3]
[1,2,[3,4,[5]]]
[[100,200],[100,200]]

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

Рассмотрим решение на Ruby.

Минималистичный лексер (игнорирующий, для удобства, пробелы и прочий мусор):

def lex(string)
  string.scan(/[\[\],]|\d+/)
end

Парсер: во-первых, создаём по отдельной функции на каждый нетерминал. Называть функции, для единообразия, будем как parse_<имя_нетерминала>.

# <array> ::=
#   "[" <items> "]"
#   | "[" "]"
def parse_array(tokens)
end

# <items> ::=
#   <item> "," <items>
#   | <item>
def parse_items(tokens)
end

# <item> ::=
#   number
#   | <array>
def parse_item(tokens)
end

# number ::= /\A\d+\z/
def parse_number(tokens)
end

Добавляем вспомогательную функцию shift(tokens, token), которая будет:

• убирать из массива tokens первый элемент и возвращать его, если он равен token;
• возвращать ошибку в ином случае.

def shift(tokens, token)
  if tokens.first == token
    tokens.shift
  else
    raise
  end
end

Смысл метода shift — проверить, что на ленте лежит тот символ, который мы ожидали там увидеть, и снять (удалить) его.

Парсинг нетерминалов

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

Начнём с метода parse_array:

# <array> ::=
#   "[" <items> "]"
#   | "[" "]"
def parse_array(tokens)
  shift(tokens, "[")

  if tokens.first == "]"
    shift(tokens, "]")
    return []
  end

  items = parse_items(tokens)
  shift(tokens, "]")

  items
end

Распознавая нетерминал <array> мы:

• в любом случае ожидаем, что в начале будет [ — снимаем её;
• дальше два варианта — либо <array> сразу и закончился ], либо идёт нетерминал <items>;
• если вторым символом идёт ], то <array> закончился — возвращаем пустой массив (извлечённый фрагмент AST);
• если вторым символом что-то другое, то вызываем парсинг <items>, запоминаем полученный результат, снимаем завершающую ], и возвращаем тот фрагмент AST, что вернул парсинг <items>.

Метод parse_items:

# <items> ::=
#   <item> "," <items>
#   | <item>
def parse_items(tokens)
  first_item = parse_item(tokens)

  begin
    shift(tokens, ",")
  rescue
    return [first_item]
  end

  next_items = parse_items(tokens)
  # Добавить first_item в начало массива next_items
  [first_item, *next_items]
end

Логика прямолинейная:

• снимаем хотя бы один <item>;
• если можем снять запятую, то снимаем и далее рекурсивно снимаем <items>;
• если запятой не оказалось, то возвращаем массив из одного <item>;
• если запятая была, то совмещаем результаты: добавляем первый <item> к остальным <items>.

Крайне важно нам самим с собой заранее договориться, где мы будем формировать результирующий массив: в parse_items или в parse_array. Потренировавши глазомер в этом деле (фактически, переводе “parse tree” в “AST tree”) мы далее с комфортом будем обращаться с системами автогенерации парсеров.

В данном случае мы любой не пустой массив формируем окончательно в parse_items.

Метод parse_item:

# <item> ::=
#   number
#   | <array>
def parse_item(tokens)
  begin
    parse_number(tokens)
  rescue
    parse_array(tokens)
  end
end

• Пытаемся считать number (первое правило вывода).
• Если не получилось, считываем <array> (второе правило вывода).

Метод parse_number:

# number ::= /\A\d+\z/
def parse_number(tokens)
  if tokens.first =~ /\A\d+\z/
    number = tokens.shift
    number.to_i
  else
    raise
  end
end

Этот метод в определённом смысле «внеграмматический», и работает без всякой магии: если первый токен в списке — число, то вернуть его. Иначе вернуть ошибку.

Проверка кода

К коллайдеру!

Допишем «вход» в наш парсер:

def parse(tokens)
  result = parse_array(tokens)

  unless tokens.empty?
    raise
  end

  result
end

Важно проверить, что во входной строке лежит массив, и больше ничего (иначе строки типа [1]]]] будут ошибочно считаться эквивалентами массива [1], т.к. метод parse_array «съест» первые три символа и, довольный результатом, выйдет).

Допишем в конец файла быстрый тест:

input = "[1,[2],3,[4,5,[6]]]"
pp parse(lex(input))

…и «входной» метод

Запустим, результат:

=> [1, [2], 3, [4, 5, [6]]]

Мы успешно превратили строку искусственного языка в Ruby-массив!

Можно переходить и к более сложным вещам.

Секреты и советы

Несколько советов новичкам, которые значительно облегчают жизнь, если им следовать заранее.

Декомпозируй грамматику

Источник картинки

С помощью немного разных вариантов BNF-правил можно записать один и тот же язык.

Например, наш «язык вложенных массивов» можно записать вот как, объединив <items> и <item>:

<array> ::=
  "[" items "]"
  | "[" "]"

<items> ::=
  number
  | array
  | number "," items
  | array "," items

На практике лучше правила «нарезать» как можно мельче.

Более длинная грамматика приводит к большей простоте написания кода. А более простой код проще написать и отладить.

Хорошая функция — жадная функция

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

<something> ::=
  <one_thing>
  | <one_thing> <another_thing>

…то не забывайте после «съедания» <one_thing> проверить, есть ли возможность съесть и <another_thing>.

Разметка кода формирования AST внутри BNF

Мы можем следующим образом разметить трансформации, которые производили с parse tree для превращения его в AST (и на каком уровне дерева парсинга мы их осуществляли):

<array> ::=
  "[" <items> "]"      ; { return $2 }
  | "[" "]"            ; { return [] }

<items> ::=
  <item> "," <items>   ; { return [$1, *$3] }
  | <item>             ; { return [$1] }

<item> ::=
  number               ; { return $1 }
  | <array>            ; { return $1 }

Значки $1, $2, … означают, соответственно, первый, второй и т. д. по порядку (слева направо) символ данной ветки правила вывода, который используется кодом, строящим фрагмент AST.

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