Простейший метод написания парсера
В качестве шутки: рекурсивный 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.
Тот или иной вариант подобным образом размеченной грамматики системы автогенерации парсеров могут использовать для того, чтобы автоматически за нас реализовать такой же парсер, который мы только что написали руками.