Часть 3: Извлечение данных

В этой статье мы построим парсер для уже описанного нами ранее формата конфигурационных файлов. Также мы реализуем небольшой DSL для упрощенного доступа к элементам полученного дерева. Еще из этой статьи вы узнаете о типах правил, действиях парсера, а так же о «темной материи» Parboiled — стеке значений.

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Стек значений (Value Stack)

Прежде чем извлекать какие-либо данные при помощи правил, следует немного рассказать про одну из концепций, которая реализована в Parboiled. Она называется Value Stack и ее можно не совсем корректно перевести как «стек значений». Представляет он собой, действительно, стек, который модифицируется действиями парсера (parser actions), в него помещаются и из него извлекаются результаты парсинга правил. Именно этому стеку мы должны дать подсказку при объявлении рекурсивных правил. Для того, чтобы элементы были помещены на стек, их необходимо явно захватить, что отразится на виде ваших правил. Типы правил также отражают количество захваченных элементов и их тип. Элементы стека могут иметь разный тип, а типизация стека значений проверяется на этапе компиляции.

Типы правил

В Parboiled2 существуют следующие типы правил:

• Rule0 — просто отвечает на вопрос "Сопоставилось ли?", не изменяя содержимое стека.
• Rule1 — помещает один объект в стек значений.
• Rule2 — помещает два объекта в стек значений.
• RuleN — помещает N объектов в стек значений, используя семантику библиотеки Shapeless. Для работы с Parboiled2 знать Shapeless не нужно (хотя и будет полезно).
• PopRule — извлекает значения со стека, не помещая туда новых значений.

При желании можно объявить свои псевдонимы для типов, как это было в Parboiled1. Так, например, в коде Parboiled2 реализуется Rule2:

type Rule2[+A, +B] = RuleN[A :: B :: HNil]

В Parboiled1 для каждого количества аргументов от 0 до 7 существовал отдельный тип, что создавало так называемую «проблему Rule7»: класса Rule8 уже нет и положить восемь элементов в стек значений не получится, даже если очень хочется. Существуют различные пути для обхода этой проблемы, и про один из них я расскажу в следующей статье.

Действия парсера (parser actions)

Действия парсера стоило бы назвать действиями над стеком, так как они позволяют извлекать данные из сопоставившихся правил, преобразовывать их, а при условии высокой степени вашей испорченности — производить с ними сайд-эффекты (что может в некоторых случах быть действительно необходимым, например, если размер и количество извлекаемых данных заранее не известны). С помощью действий можно формировать абстрактные синтаксические деревья (AST), их можно использовать для вычисления «на месте», как это сделано в примере с калькулятором.

Захватывающие истории

Чтобы совершить какое-то полезное дейстие над данными, нам надо их сначала захватить. Для этого существует функция capture: она сопоставляет данные с правилом и в случае успеха помещает их на стек значений.

Предположим у нас есть правило типа Rule0, из которого мы хотим хоть что-то вытащить:

def User: Rule0 = rule { FirstName ~ Separator ~ LastName }

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

def User: Rule2[String, String] = rule {
  capture(FirstName) ~ Separator ~ capture(LastName)
}

С этого момента наше правило уже не Rule0, а Rule2, так как оно захватывает и оправляет в стек значений две строки. Впрочем, тип можно и не указывать, компилятор все поймет сам.

Оператор действия ~>

… или оператор, которым вам придется пользоваться чаще всего. В качестве правого параметра принимает лямбду, на вход которой отправляет захваченные со стека объекты — тем самым позволяя лямбде с этими объектами работать. Потом, при желании, значения можно отправить обратно в стек, или же создать из них узел для вашего AST — выберите по своему вкусу. В любом случае, для того, чтобы действие осуществилось, нужно предварительно выполнить захват данных на стек при помощи функции capture. В зависимости от типа возвращаемого значения используются различные формы оператора ~>, что делает использование данного оператора простым и интуитивным.

В Parboiled1 захват выполнялся неявно, что я нахожу весьма неудобным.

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

Для примера попробуем извлечь у парсера хотя бы одно целое число:

def UnsignedInteger: Rule1[Int] = rule {
  capture(Digit.+) ~> (numStr => numStr.toInt)
}

В этой ситуации поощряется использование фирменного скаловского плейсхолдера:

def UnsignedInteger: Rule1[Int] = rule {
  capture(Digit.+) ~> (_.toInt)
}

Здесь наша лямбда имеет тип (String => Int), что обуславливает тип нашего правила — Rule1[Int]. Позволяется применять оператор ~> и к типизированному правилу, например, следующее правило сопоставляет целое число, но поместит в стек не его, а его удвоенное значение:

def TwoTimesLarger = rule { UnsignedInteger ~> (i => i * 2) }

Тип правила TwoTimesLarger так и останется Rule1[Int], только на стеке будет лежать другое значение.

Явное указание типа аргументов лямбда-функции не самая лучшая идея (по крайней мере, на момент написания статьи). В компиляторе Scala существует весьма неприятный баг, который не даст вашему коду нормально скомпилироваться.

С одним аргументом мы разобрались, но что делать, если их несколько? Как поведет себя лямбда? Просто и предсказуемо: первый параметр соответствует самому верхнему значению на стеке, второй параметр — второму сверху, и так далее. Так как процедура захвата подвыражений выполняется справа налево, то порядок аргументов лямбда-функции соответствует порядку записи операций захвата:

def UserWithLambda: Rule2[String, String] = rule {
  capture(FirstName) ~ Separator ~ capture(LastName) ~> ((firstName, lastName) => ...)
}

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

def UserName = rule {
  User ~> ((firstName, lastName) => s"$firstName $lastName")
}

В приведенном примере исходный тип правила User был Rule2[String, String], применив к нему лямбда-функцию мы создали новое правило UserFirstName с типом Rule1[String].

Лямбда не обязана принимать все параметры со стека, можно ограничиться последними N значениями (помним, что лямбда забирает аргументы с конца стека):

(foo: Rule2[Int, String]) ~> (_.toDouble)
// foo: Rule2[Int, Double].

Ничего не мешает нам попробовать скормить правилу лямбда-функцию, не имеющую аргументов, с предсказуемым результатом:

(foo: Rule0) ~> (() => 42)
// foo: Rule1[Int].

У Parboiled2 есть более мощные инструменты, например, возможность вернуть из лямбды на стек сразу группу значений:

(foo: Rule1[Event]) ~> (e => e::DateTime.now()::"localhost"::HNil)
// foo: RuleN[Event::DateTime::String::HNil]

Фактически мы конструируем фирменный шейплессовский HList. Тип результирующего правила будет RuleN[Event::DateTime::String::HNil].

Аналогично можно забирать значения со стека значений, ничего не отдавая взамен: для этого лямбда всего-навсего должна «возвращать» тип Unit. Типом получившегося правила, как вы наверное догадались, будет Rule0:

(foo: rule1[String]) ~> (println(_))
// foo: Rule0

Кроме того, оператор действия предлагает особо сладкий сахар для case-классов:

case class Person(name: String, age: Int)

(foo: Rule2[String, Int]) ~> Person
// foo: Rule1[Person]

Правда нужно отметить, что компилятор может и не переварить этот сахар, если для case-класса определен companion object. Тогда придется добавить лямбду, немного подчеркиваний и записать: ~> (Person(_, _)).

Сахар для case-классов идеально подходит для построения AST, опытные пользователи могут даже заметить, что в этом случае он работает совершенно аналогично оператору ~~> из Parboiled1. Существуют и другие способы применения ~>, но о них вы узнаете не от меня, а из документации. Отмечу только, что оператор ~> реализуется в коде Parboiled2 весьма нетривиальным образом, но как бы сложно не выглядело его определение, пользоваться им одно удовольствие. Пожалуй, самое лучшее техническое решение, принятое на этапе создания DSL.

run

Особая версия оператора действия для любителей острых ощущений. Для программиста во многих отношениях run ведет себя точно так же, как и ~>, кроме того маленького неудобства, когда в случае с run компилятор не выводит типы автоматически и их приходится обозначать явно. Оператор является очень удобным средством для создания непроверяемых сайд-эффектов, например как здесь:

def RuleWithSideEffect = rule {
  capture(EmailAddress) ~ run { address: String => send(address, subj, message) } ~ EOI
}

Типом результирующего правила будет Rule0, а сопоставленная строка оказывается никому не нужна и ни в какой стек значений не попадет, что иногда бывает необходимо. Пользователи Parboiled1 наверное заметили, что в описанном выше контексте, run ведет себя так же, как оператор ~%.

Предупреждение: При использовании сайд-эффектов, не стоит заигрывать со стеком значений. Да, к нему можно получить прямой доступ, но по ряду причин этого лучше не делать.

push

Функция push помещает данные на стек значений в случае, если соответствующее ему правило сопоставилось. На практике мне не приходилось пользоваться им часто, так как большую часть работы может выполнить оператор ~>, но существует пример, в котором push просто блистает:

sealed trait Bool
case object True extends Bool
case object False extends Bool

def BoolMatch = rule { "true" ~ push(True) | "false" ~ push(False) }

Хоть это нигде и не отмечено, данное правило следует семантике call-by-name и вычисляется каждый раз, а значит и его аргумент вычисляется каждый раз. Обычно это пагубно сказывается на производительности, поэтому push лучше использовать с константами и только c константами.

Так же как в случае с run и ~>, тип значения, переданного в push, определяет содержимое стека и тип создаваемого правила.

Вложенные парсеры

В Parboiled2 существует поддежрка вложенных парсеров: захватывая текст и скармливая его оператору ~> мы получаем переменную строкового типа в качестве параметра лямбда функции. Проведя некоторые операции со сторокой мы можем скормить ее какому-нибудь подпарсеру и так далее. На практике применять не приходилось, но следует знать, что такая возможность есть.

Генерация AST

У нас есть все необходимые знания, чтобы написать свой парсер, генерирующий синтактическое дерево. Синтаксические деревья строятся из нод. Поэтому начнем с них, вернее с их описания:

sealed trait AstNode
case class KeyValueNode(key: String, value: String) extends AstNode
case class BlockNode(name: String, nodes: Seq[AstNode]) extends AstNode

Каждый из кейс классов соответствует определенному типу ноды, вроде бы все ясно и понятно. Тем не менее, давайте постараемся найти что-то общее среди приведенных выше узлов. У каждого есть имя, просто в случае с парой ключ-значение это ключ. Узлы между собой различать тоже как-то нужно.

sealed trait AstNode {
  def name: String
}

case class KeyValueNode
(override val name: String, value: String) extends AstNode

case class BlockNode
(override val name: String, nodes: Seq[AstNode]) extends AstNode

Начнем с узла для пар ключ-значение. Нам нужно захватить ключ, захватить значение и собрать это все в case class посредством оператора ~>. Захват мы будем делать «на месте» (в правилах для ключа и значения). И начнем мы с ключа:

// Можно довериться выводу типов и не указывать тип явно
def Key: Rule1[String] = rule { capture(oneOrMore(KeySymbol)) }

Просто добавляем capture и все — Parboiled думает о нас. Строка будет отправлена на стек. А вот с захватом значения ситуация сложнее. Если мы провернем операцию, аналогичную для ключа, нам придет строка с кавычками. Они нам нужны? Поэтому захват будем делать на территории строки:

def QuotedString: Rule1[String] = rule {
  '"' ~ capture(QuotedStringContent)  ~ '"'
}

Для правила Value ничего делать не нужно, оно автоматически будет иметь тип Rule1 (так как тело строки было захвачено ранее, со стека оно никуда не ушло).

Захват capture нужно делать один раз. И желательно, в том правиле, где он должен был произойти

Теперь соберем case class:

def KeyValuePair: Rule1[AstNode] = rule {
  Key ~ MayBeWS ~ "=" ~ MayBeWS ~ Value ~> KeyValueNode
}

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

// тип должен быть объявлен явно, даже если вы полагаетесь на компилятор
def Node: Rule1[AstNode] = rule { KeyValuePair | Block }

Так как каждая из нод захвачена, правило Nodes изменений не требует, разве что стоит указать тип значения, помещаемого на стек:

def Nodes: Rule1[Seq[AstNode]] = rule {
  MayBeWS ~ zeroOrMore(Node).separatedBy(NewLine ~ MayBeWS) ~ MayBeWS
}

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

def BlockName: Rule1[String] = rule { capture(oneOrMore(BlockNameSymbol.+)) }

Ноды уже были захвачены, поэтому просто соберем данные в case class:

def Block: Rule1[AstNode] = rule {
  BlockName ~ MayBeWS ~ BlockBeginning ~ Nodes ~ BlockEnding ~> BlockNode
}

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

def Root: Rule1[AstNode] = rule {
  Nodes ~ EOI ~> {nodes: Seq[AstNode] => BlockNode(RootNodeName, nodes)}
}

Какое имя выбрать? Мы можем дать блоку вполне осознанное имя, например root, но тогда нас могут ждать непредвиденные сюрпризы, если кто-то захочет выбрать имя root. Зная что BlockName является идентификатором, который не допускает ряд символов, можно попробовать имена вроде "$root", "!root!" или "%root%". Работать будет. Я предпочту пустую строку:

val RootNodeName = ""

Пустая строка:

• Удовлетворяет главному требованию — не является валидным именем блока или ключа;
• Отлично подойдет если мы захотим расширить грамматику. Как бы мы не мучили парсер, уж что-что, а пустую строку пользователь точно не создаст.

Теперь у нас есть захваченные данные. Остается только выполнить прогон из корня для подходящего текста.

DSL для работы с узлами

Получив на руки рабочий парсер, способный отдавать синтаксическое дерево, мы должны с этим деревом как-то работать. Создание небольшого DSL значительно упрощает эту задачу. Например, нам нужно перейти к следующей ноде по имени. Можно каждый раз писать один и тот же код, а можно сделать небольшой метод (продублированный перегруженным оператором), способный возвращать следующую ноду. Ниже приведены основные методы необходимые для работы с AstNode. На базе которых можно сделать много других (наиболее подходящих под ваши нужды). Если захотите, можно дать им символьные имена и любоваться красотой полученного DSL.

/**
 * Код имеющий крайне опосредованное отношение к parboiled
 */
trait NodeAccessDsl { this: AstNode =>

  def isRoot = this.name == BkvParser.RootNodeName

  lazy val isBlockNode = this match {
    case _: KeyValueNode => false
    case _ => true
  }

  /**
   * В случае блокового узла возвращает список вложенных пар
   * ключ-значение
   */
  def pairs: Seq[KeyValueNode] = this match {
    case BlockNode(_, nodes) =>
      nodes collect { case node: KeyValueNode => node }
    case _ => Seq.empty
  }

  /**
   * В случае блокового узла возвращает спосок вложенных
   * блоков
   */
  def blocks: Seq[BlockNode] = this match {
    case BlockNode(_, nodes) =>
      nodes collect { case node: BlockNode => node }
    case _ => Seq.empty
  }

  /**
   * Значение в случае пары "ключ-значение"
   */
  def getValue: Option[String] = this match {
    case KeyValueNode(_, value) => Some(value)
    case _ => None
  }
}

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

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

С кодом парсера вы можете ознакомиться здесь.