Про Parboiled (Часть 2)10.11.2015 04:33

Часть 2. Сопоставление текста

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

Для закрепления знаний мы напишем простой распознаватель для несложной грамматики. Именно распознаватель (recognizer), а не полноценный парсер, так как он будет только сопоставлять входной текст c описанными нами правилами (также называемыми продукциями), но не будет извлекать из сопоставленного текста какие-либо значения. Распознаватель может быть полезным и сам по себе, так как может работать в качестве валидатора: если вход оказался некорректным, распознаватель даст об этом знать и расскажет, что пошло не так и где. А совсем классным наш распознаватель станет тогда, когда мы узнаем, как извлекать разобранные значения и причем тут какой-то «value stack». Ну что, поехали?

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

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

Перед началом работы с библиотекой добавим её в classpath. В Maven, например, это делается так:

<dependency>
    <groupId>org.parboiled</groupId>
    <artifactId>parboiled_2.11</artifactId>
    <version>2.1.0</version>
</dependency>

Я использую Scala 2.11, однако существуют артефакты и для 2.10.
Вся функциональность Parboiled реализуется поверх синтаксиса языка Scala при помощи специализированного DSL. Поэтому описание парсера на самом деле есть ни что иное, как объявление класса, производного от org.parboiled.Parser. В качестве примера напишем парсер, который ничего не делает, что не мешает ему существовать и радоваться жизни:

import org.parboiled2._

class MyParser(val input: ParserInput) extends Parser {
  // Здесь описана ваша грамматика
}

Конструкции DSL и ряд полезных классов добавляются в зону видимости всего одной директивой импорта. Хочу отметить, что наличие параметра input в конструкторе является обязательным: это означает, что для каждого нового набора входных данных нужно создавать новый объект-парсер. Вначале меня это очень сильно пугало, но я перестал бояться, когда увидел, как быстро оно работает.

Правила для отдельных символов

Итак, когда никчёмный парсер у нас уже имеется, нужно добавить в него несколько правил, в соответствии с которыми он и будет обрабатывать данные. Если вы работали с Parboiled1, этот раздел можно просто пролистать, так как мои объяснения могут показаться вам излишне подробными.

Начнем с терминалов. Этот термин будет использоваться в дальнейшем, поэтому попробуем дать ему здесь определение (не совсем, впрочем, строгое):

Терминал — это простейшее атомарное правило, не требующие дополнительных определений

Давайте опишем два простейших правила: первое должно распознать некоторый наперёд известный символ, второе — строку:

def MyCharRule   = rule { ch('a') }
def MyStringRule = rule { str("string") }

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

def MyCharRule   = rule { 'a' }
def MyStringRule = rule { "string" }

Строки сопоставляются с точным учётом регистра символов. Тем не менее, существует множество языков, не чувствительных к регистру (например SQL). Для них существует правило ignoreCase, сопоставляющее входную строку независимо от ее регистра. Передаваемая в него строка обязательно должна быть в нижем регистре:

def StringWithCaseIgnored = rule { ignoreCase("string") }

Подробнее о правилах (или «продукциях», если вам так нравится больше) будет рассказано в следующей статье. Все приведенные выше (и ниже) правила имеют тип Rule0. Правила бывают разных типов, но сейчас нам необходимо знать лишь то, что Rule0 обозначает, что правило сопоставляет с собой входную строку и говорит, совпало или нет. Мы не указали тип потому, что механизм вывода типов языка пока легко справляется и сам. Однако, ничто не мешает нам указать тип явно:

def StringWithCaseIgnored: Rule0 = rule { ignoreCase("string") }

В Parboiled существуют особенные терминалы (они же синтаксические предикаты):

ANY — любой символ, кроме EOI.
EOI (End of Input) — виртуальный символ-маркер конца ввода, который вы обязательно захотите добавить в главное правило своего парсера. Определяется EOI так:
```
val EOI = '\uFFFF'
```

Несмотря на то, что символ U+FFFF зарезервирован для внутреннего использования стандартом Юникода, на практике он может запросто встретиться в пользовательском вводе и изменить поведение парсера. Поэтому будьте внимательны с текстом, который попадает на вход.

Кроме того, если вы не добавите EOI в конце главного правила и при сопоставлении возникнет ошибка, то о ней вы не узнаете, так как парсер будет считать, что входные данные ещё не закончились и будет ожидать поступления новых данных. Поэтому, что бы вы не подали на вход, на выходе вас ожидает бессмысленный Success.

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

def Digit      = rule { '0' - '9' }
def AlphaLower = rule { 'a' - 'z' }

Оба эти правила сопоставят за раз максимум один символ из диапазона (или не сопоставят ни одного). Хотя написать конкретно эти два правила в PB2 очень просто, делать это нет необходимости: они уже определены в объекте CharPredicate. Parboiled1, напротив, заставлял вручную создавать эти правила, практически каждый раз, когда вы пишете очередной парсер. Поэтому я носил свою библиотечку примитивов из проекта в проект (уверен, что не я один так делал). Теперь моя библиотечка заметно подыстощилась благодаря появлению CharPredicate. В него входят, например, следующие правила (думаю, что из названий будет понятно, каким категориям символов они соответствуют):

CharPredicate.All (работает почти так же, как ANY, но показывает худшую производительность на больших диапазонах символов);
CharPredicate.Digit;
CharPredicate.Digit19;
CharPredicate.HexDigit и много других правил.

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

CharPredicate from (_.isSpaceChar)

Кроме того, для символьных предикатов определены операторы except (--) и union (++), которых не было в PB1. Лично я от этого отсутствия очень страдал: приходилось замыкать правило «с другой стороны», перечисляя полностью черный или белый список символов в зависимости от ситуации. Правило -- можно так же назвать разностью, так как роль у него накая же, что и у разности двух множеств.

// Сопоставит любой печатный символ, если это не кавычка.
def AllButQuotes = rule { CharPredicate.Visible -- "\"" -- "'" }

// Неплохо подойдет для определения идентификатора. Обратите внимание, как
// AlphaNum объединяется с нижним подчеркиванием.
def ValidIdentifier = rule {
  CharPredicate.Alpha ~ zeroOrMore(CharPredicate.AlphaNum ++ "_") }

Полезно будет знать ещё о двух правилах: anyOf и noneOf. Они очень похожи на except и union, но работают на всём пространстве символов ANY. И самое главное: в этом пространстве они работают быстрее. Эти функции могут принимать на вход строку, состоящую из перечислений символов. Например:

// Определит, является ли символ одной из арифметических операций.
def ArithmeticOperation = rule { anyOf("+-*/^") }

// Сопоставит всё, кроме перечисленных пробельных символов и EOI.
def WhiteSpaceChar = rule { noneOf(" \t\n") }

Иногда возникает вопрос, что же выбрать: anyOf/noneOf или CharPredicate? Заранее предопределенный символьный предикат будет работать быстрее для 7-битных символов ASCII. «Заранее предопределенный» написано не просто так, и в разделе «Best Practices» части 4 будет рассказано, почему. Однако для очень больших символьных диапазонов CharPredicate ведёт себя откровенно плохо, и тогда на помощь должны прийти anyOf и noneOf.

Цепочки правил

N.times

Сопоставлять единичные символы не интересно, поэтому перейдем к более сложным правилам. Начнём с times, которое позволяет сопоставить одно правило несколько раз подряд. Количество повторений должно быть точным и заранее известным.

def BartLearningParboiled = rule {
  100 times "I will never write a parser again. "
}

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

def FutureOfCxx = rule { 'C' ~ (2 to 5).times('+') }

А в старом — существует правило nTimes, которое, требует указания точного числа повторений. В случае, если точное количество повторений заранее не известно, вам помогут следующая пара правил.

zeroOrMore

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

def Whitespace = rule { anyOf(" \n\t") }
def OptWs      = rule { zeroOrMore(Whitespace) }

oneOrMore

Правило, похожее на предыдущее. Оно делает почти то же самое, что и zeroOrMore, но требует, чтобы по крайней мере одно повторение присутствовало во входных данных. Идентично плюсу Клини для регулярных грамматик.

def UnsignedInteger = rule { oneOrMore(CharPredicate.Digit) }

Разделитель цепочек: separatedBy

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

def CommaSeparatedNumbers = rule { oneOrMore(UnsignedInteger).separatedBy(",") }

Однако, первая версия использует для этого менее элегантный синтаксис:

def CommaSeparatedNumbers = rule { oneOrMore(UnsignedInteger, separator = ",") }

Оператор последовательности (~)

Для того чтобы указать последовательность правил используется оператор ~. В регулярных выражениях нет необходимости в подобном операторе, там этот факт записывается непосредственным образом, так же, как и в некоторых вариантах BNF. Для примера напишем (предельно упрощенное) правило которое сопоставляет дату определенного формата:

import CharPredicate.Digit

// Дата должна иметь следующий формат: "yyyy-mm-dd"
def SimplifiedRuleForDate = rule { Year ~ "-" ~ Month ~ "-" ~ Day }

def Year  = rule { Digit ~ Digit ~ Digit ~ Digit }
def Month = rule { Digit ~ Digit }
def Day   = rule { Digit ~ Digit }

Как видите, правило максимально упрощено, и я прекрасно отдаю отчет тому, что у нас может быть 99 дней и 99 месяцев. Не все проверки имеет смысл оставлять на уровне парсера: мы всё равно передадим сопоставленную строку на вход какому-нибудь классу для работы с датой и временем, который догадается выполнить валидацию, и вернет результат, обернутый в Option. А вот грамматику этим мы заметно упростим. Попытка заставить парсер выполнить все возможные и невозможные проверки часто приводит к подобным результатам.

«Необязательное» правило (optional)

Если бы существовало правило zeroOrOne, то это и был бы optional: либо есть одно вхождение, либо вхождений нет совсем. Давайте разберем следующий пример: в разных семейства операционных систем маркер конца строки кодируется по-разному. Например, в Unix-подобных операционных системах нужен только символ \n, тогда как в Windows исторически используется последовательность из двух символов: \r и \n. И если мы хотим обрабатывать текст, созданный в любой из этих систем, то можно использовать следующее правило для конца строки:

def Newline = rule { optional('\r') ~ '\n' }

Упорядоченный выбор (|)

Аналог оператора | в регулярных выражениях, неспроста называемый упорядоченным выбором (ordered choice). Предположим, что нам нужно распознать число, у которого может быть знак, а может, и не может. Знак, если он есть, может быть двух типов: положительный и отрицательный, разберемся сначала с ним:

def Signum = rule { '+' | '-' }

Знак может вовсе отсутствовать в записи положительного числа:

def MaybeSign = rule { optional(Signum) }

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

def Integer = rule { MaybeSign ~ UnsignedInteger }

Порядок перечисления вариантов в правиле Signum имеет значение: выбирается самый первый из подошедших вариантов, что исключает возможность появления неоднозначности у грамматики. И да, так работают все без исключения PEG-парсеры. Так что, если вам нужно разобрать выражение на языке C, начинать перечисление нужно с самых длинных операций, чтобы они сопоставились первыми, как и предписывает стандарт. Упрощённо правило может выглядеть, например, так:

def Operator = rule {
  "+=" | "-=" | "*=" | "/=" | "%=" | "&=" | "^=" | "|=" | "<<=" | ">>=" |
  "<<" | ">>" | "<=" | ">=" | "==" | "!=" |
  "||" | "&&" | "->" | "++" | "--" |
  "<"  | ">"  | "+"  | "-"  | "&"  | "|" | "." |
  "*"  | "/"  | "!"  | "~"  | "^"  | "=" | ","
}

Порядок перечисления может быть самым различным, но нужно обеспечить, чтобы в нём + всегда шёл после += и ++, а < — после <= и << (а <<, в свою очередь, после <<=). В противном случае может случиться, что составной оператор присваивания <<= распарсится в последовательность [<=, =], а то и вовсе [<, <, =].

Если правило выбора становится избыточно сложным и нам не хочется полагаться на порядок его элементов, стоит сгруппировать их по общим префиксам (факторизовать парсер):

def Operators = rule {
  ("+" ~ optional("=" | "+")) |
  ("<" ~ optional("=" | ("<" ~ optional("=")))) | ...
}

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

Немного сахара

Для optional, oneOrMore и zeroOrMore существует синтаксический сахар, позволяющий сделать определения ещё короче: .?, .+ и .*. Пожалуйста, используйте их мудро: при злоупотреблении ими, ваши правила будут читаться немногим лучше, чем регулярки. С помощью этих «ярлыков» мы можем сделать описание наших правил менее многословным:

import CharPredicate.Digit

def SignedInteger   = rule { ("+" | "-").? ~ Digit.+ }
def Newline = rule { '\r'.? ~ '\n' }
def OptWs = rule { WhitespaceChar.* }

Запуск парсера

Для того, чтобы заставить написанный парсер сделать хоть что-то полезное, нужно вызвать метод run его главного (корневого) правила. Если вы пишете модульный-тест для парсера, то возможно, имеет смысл вызывать этот метод и для других правил. Скобочки после метода при этом обязательны.

Давайте заставим работать наш бесполезный парсер, умеющий сопоставлять только одну строковую константу. Итак наш парсер определён следующим образом (не забываем про EOI):

import org.parboiled2._

class MyParser(val input: ParserInput) extends Parser {
  def MyStringRule: Rule0 = rule { ignoreCase("match") ~ EOI }
}

Теперь где-нибудь в другом месте создадим несколько экземпляров парсеров и подадим им на вход разные данные:

val p1 = new MyParser("match")
val p2 = new MyParser("Match")
val p3 = new MyParser("much")

// по-умолчанию возвращают scala.util.Try
p1.MyStringRule.run()      // Success
p2.MyStringRule.run()      // Success
p3.MyStringRule.run()      // Failure

Прогон правил в Parboiled2 намного проще, чем в Parboiled1, для которого существует целый зоопарк раннеров (parser runners), которые приходится дополнительно вызывать. За более подробной информацией прошу в раздел «Отчеты об ошибках» части 4.

Вложенные структуры данных

Разбор рекурсивных структур — это то, что может Parboiled и не могут регулярные выражения. В Parboiled это получается естественно и непринужденно, что мы и продемонстрируем на последующих примерах. Единственное дополнительное усилие, которое от вас требуется — явно объявить тип правил, участвующих в рекурсии.

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

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

server.name = "webserver"
server {
  port    = "8080"
  address = "192.168.88.88"

  settings {
    greeting_message = "Hello!\n It's me!"
  }
}

Как видите, формат прост и незатейлив, хотя строки с экранированием (escaping) могут напугать тех, кто никогда не писал парсеры. Экранирование очень часто встречается при синтаксическом разборе, поэтому мы обязательно и в подробностях его рассмотрим.

Экранированные строки

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

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

Символы, открывающие и закрывающиие строку (в нашем случае это один и тот же символ — двойная кавычка).
Символ экранирования (в нашем случае это символ обратного слеша).
Набор символов-мнемоник для обозначения непечатных символов (мы будем поддерживать, как минимум, '\n', '\t' и '\v').

Сначала попробуем описать правило для квотированной строки без экранирования:

def OverlySimplifiedQuotedString = rule {
  '"' ~ zeroOrMore(AllowedChar) ~ '"'
}

Поскольку пустые строки тоже возможны, между кавычками мы используем правило zeroOrMore. Очевидно, что двойная кавычка в перечень допустимых символов не входит. Что же тогда разрешено? Всё, что не запрщено. Поэтому для нашего случая список разрешенных символов выглядит так:

def AllowedChar = rule { noneOf("\"") }

Без двойной кавычки жить можно, но сложно. Но что будет, если мы добавим кавычку внутрь строки? Встретив её, парсер подумает, что строка закончилась, и взорвётся сообщением об ошибке на следующем же символе.

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

def AllowedChar = rule {
  noneOf("\"\\") | EscapeSequence
}

// Поддерживаются последовательности: \", \\, \n, \a, \f, \v.
def EscapeSequence = rule {
  '\' ~ anyOf("\"\\nafv")
}

Разобравшись, как это работает, можно переходить к написанию финального варианта правил для экранирования. Для этого предлагаю создать выделенный трейт:

import org.parboiled2._

object QuotedStringSupport {
  val CharsToBeEscaped = "abfnrtv\\\""
  val Backslash = '\\'
  val AllowedChars = CharPredicate.Printable -- Backslash -- "\""
}

trait QuotedStringSupport { this: Parser =>
  import QuotedStringSupport._

  def QuotedString: Rule0 = rule {
    '"' ~ QuotedStringContent  ~ '"'
  }

  def QuotedStringContent: Rule0 = rule {
    oneOrMore(AllowedChars | DoubleQuotedStringEscapeSequence)
  }

  def DoubleQuotedStringEscapeSequence = rule {
    '\\' ~ anyOf(CharsToBeEscaped)
  }
}

Теперь, когда мы расквитались со строками и выделили соответствующую функциональность в отдельный трейт, перейдем к самому формату.

Вспомогательные терминалы

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

Начем описание со вспомогательных элементов, а именно, с пробелов. В нашем случае пробелами будут являться символы: ' ', '' и ''. Конечно же, пробельных символов в природе существует куда больше, но в примере мы ограничимся тремя. Разобраться с пробелами можно разными способами:

перечислить символы через оператор упорядоченного выбора;
объявить свой CharPredicate, содержащий эти три символа;
использовать anyOf.

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

val WhitespaceChars = "\n\t "
def WhiteSpace = rule { anyOf(WhitespaceChars) }
def OptWs      = rule { zeroOrMore(Whitespace) }

Правило, описывающее перевод строки мы объявляли ранее:

def Newline = rule { optional('\r') ~ '\n' }

Ключ и Имя блока представляют собой идентификатор, похожий на тот, что вы можете встретить в различных языках программирования. Идентификатор должен начинаться либо с буквы английского алфавита (регистр не имеет значения), либо с символа нижнего подчеркивания. В середине может содержать цифры а так же буквы английского алфавита (строчные и заглавные). Вхождение точки, в середине идентификатора тоже допустимо. Перед тем как объявлять ключ, объявим правило, описывающее идентификатор. (Аналогичные правила будут применяться для имени блока). Нам необходимо два символных предиката: для первого и последующих символов.

// Первый символ идентификатора
val IdentifierFirstChar = CharPredicate.Alpha ++ '_'

// Для последующих символов
val IdentifierChar      = CharPredicate.AlphaNum ++ '.' ++ '_'

Объявим также символы начала и конца блока:

val BlockBeginning  = '{'
val BlockEnding     = '}'

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

Пары ключ—значение

Теперь перейдём к синтаксису пар «ключ–значение». Потребуем, чтобы ключ представлял собой валидный идентификатор, как описанно выше, а значение было квотированной строкой, как тоже описано выше. Итак, начнем с определения идентификатора:

def Identifier = rule {
  IdentifierFirstChar ~ zeroOrMore(IdentifierChar)
}

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

def Key = rule { Identifier }

Для описания значения воспользуемся уже имеющимся правилом (для этого нам всего-то нужно подмешать написанный нами ранее трейт):

def Value = rule { DoubleQuotedString }

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

def KeyValuePair = rule { Key ~ OptWs ~ "=" ~ OptWs ~ Value }

Вложенные блоки

Блок ограничен фигурными скобками и может содержать внутри как пары «ключ—значение», так и другие блоки. Поэтому для начала нужно стереть различия между блоками и парами ключ—значение, обозвав и те, и другие узлами (nodes) синтаксического дерева. Это делается следующим кодом:

// Тип правила обязателен к указанию, иначе не взлетит!
def Node: Rule0 = rule { KeyValuePair | Block }

Так как и блок, и корневая структура состоят из списка узлов, нам нужно объявить правило для этого списка:

def Nodes = rule {
  OptWs ~ zeroOrMore(Node).separatedBy(Newline ~ OptWs) ~ OptWs
}

Опциональные пробелы могут быть и перед списоком нод, и после него, и между отдельными его элементами, поэтому у нас в правиле получилось так много вхождений MaybeWs. Теперь определим имя блока — это всё тот же идентификатор, что используется и в имени ключа:

def BlockName = rule { Identifier }

Наконец, всё необходимое для объявления блока целиком у нас есть, поэтому объявим блок:

def Block = rule { BlockName ~ "{" ~ Nodes ~ "}" }

Помните мы определяли BlockBeginning и BlockEnding? Используем их в объявлении:

def Block = rule { BlockName ~ BlockBeginning ~ Nodes ~ BlockEnding }

Заметьте, что Block ссылается на правило Nodes, которое будет ссылаться на правило Node. Node может ссылаться как на правило Block, из-за чего возникает цикл. Поэтому нам необходимо явно указать тип правила, успокоив Parboiled. Так как мы пишем распознаватель, тип правила всегда будет Rule0 (подробнее о типах правил будет в следующей статье).

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

def Root: Rule0 = rule { Nodes ~ EOI }

Вот мы и написали распознаватель. Ознакомиться с его полным исходным кодом вы можете здесь.

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