Как указать диапазон повторений в комбинаторах парсера Scala? - PullRequest
Новая
       21

Как указать диапазон повторений в комбинаторах парсера Scala?

1 голос
/ 13 октября 2019

Комбинаторы парсера Scala позволяют задавать некоторые повторения как 0 или более (.*), 1 или более (.+) и т. Д. Можно ли указать диапазон? Например, rep(p, q)(parser), где анализатор запускается не менее p раз и до q раз.

1 Ответ

2 голосов
/ 13 октября 2019

Операции комбинатора в компиляторах синтаксического анализатора Scala примерно смоделированы после регулярных выражений . Регулярные выражения имеют только три операции Combinator:

При наличии двух регулярных выражений R и S,

  • RS - это регулярное выражение ( Объединение )
  • R | S - это регулярное выражение ( Чередование )
  • R* - это регулярное выражение ( Kleene Star )

Вот и все. Scala добавляет еще пару, особенно + и ?, но это на самом деле не увеличивает мощность, поскольку R+ на самом деле просто RR* и R? просто R | ε. То же самое относится к вашему предложенному rep комбинатору. Это на самом деле не увеличивает мощность, так как 

R{m, n}

на самом деле просто 

RRRRRRRRRRR(ε | R | RR | RRR | RRRR | RRRRR | RRRRRR | RRRRRRR | RRRRRRRR | RRRRRRRRR)
 ↑↑ m×R ↑↑                                                                ↑↑ (m-n)×R ↑↑

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

Было бы довольно легко построить его поверх | и repN, я полагаю.

Что-то вроде: 

/** A parser generator for a number of repetitions within a range.
 *
 *  `repMN(m, n, p)` uses `p` between `m` and `n` time to parse the input
 *  (the result is a `List` of the consecutive results of `p`).
 *
 * @param p   a `Parser` that is to be applied successively to the input
 * @param min the minimum number of times `p` must succeed
 * @param max the maximum number of times `p` must succeed
 * @return    A parser that returns a list of results produced by repeatedly applying `p` to the input
 *        (and that only succeeds if `p` matches between `m` and `n` times).
 */
def repMN[T](min: Int, max: Int, p: ⇒ Parser[T]) = 
  (min to max).reverse map { repN(_, p) } reduce {_ | _}

Это выглядит достаточно полезным, что может даже иметь смысл подать как запрос на расширение.

...