Понимание тильды в комбинаторах парсера Scala

Я новичок в Scala и читаю о комбинаторах парсеров (The Magic Behind Parser Combinators, Домен -Specific Languages в Scala) Я столкнулся с определениями методов следующим образом:

def classPrefix = "class" ~ ID ~ "(" ~ formals ~ ")"

Я читал API-документа scala.util.parsing.Parsers, который определяет метод с именем (tilde), но я до сих пор не понимаю его использования в приведенном выше примере. В этом примере (tilde) - это метод, который вызывается на java.lang.String, который не имеет этого метода и приводит к сбою компилятора. Я знаю, что (тильда) определяется как

case class ~ [+a, +b] (_1: a, _2: b)

но как это поможет в приведенном выше примере?

Я был бы рад, если бы кто-нибудь мог дать мне подсказку, чтобы понять, что происходит здесь. Большое вам спасибо заранее!

Jan

Ответ 1

Структура здесь немного сложна. Во-первых, обратите внимание, что вы всегда определяете эти вещи внутри подкласса некоторого парсера, например. class MyParser extends RegexParsers. Теперь вы можете отметить два неявных определения внутри RegexParsers:

implicit def literal (s: String): Parser[String]
implicit def regex (r: Regex): Parser[String]

Что они сделают, это взять любую строку или регулярное выражение и преобразовать их в парсер, соответствующий этой строке или регулярному выражению в качестве токена. Они неявные, поэтому они будут применяться в любое время, когда они понадобятся (например, если вы вызываете метод на Parser[String], который String (или Regex) не имеет).

Но что это за Parser вещь? Это внутренний класс, определенный внутри Parsers, supertrait для RegexParser:

class Parser [+T] extends (Input) ⇒ ParseResult[T]

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

Теперь мы можем просто найти способ ~:

def ~ [U] (q: ⇒ Parser[U]): Parser[~[T, U]]
  A parser combinator for sequential composition
  p ~ q' succeeds if p' succeeds and q' succeeds on the input left over by p'.

Итак, если мы увидим что-то вроде

def seaFacts = "fish" ~ "swim"

что происходит, во-первых, "fish" не имеет метода ~, поэтому он неявно преобразуется в Parser[String]. Метод ~ затем хочет аргумент типа Parser[U], и поэтому мы неявно конвертируем "swim" в Parser[String] (т.е. U == String). Теперь у нас есть что-то, что будет соответствовать входу "fish", и все, что осталось на входе, должно совпадать с "swim", и если это так, то seaFacts будет успешным в своем совпадении.

Ответ 2

Метод ~ в синтаксическом анализаторе объединяет два синтаксического анализатора в одном, который последовательно применяет два оригинальных анализатора и возвращает два результата. Это может быть просто (в Parser[T])

def ~[U](q: =>Parser[U]): Parser[(T,U)].

Если вы никогда не комбинировали более двух парсеров, это было бы нормально. Однако, если вы связали три из них, p1, p2, p3, с типами возврата T1, T2, T3, тогда p1 ~ p2 ~ p3, что означает, что p1.~(p2).~(p3) имеет тип Parser[((T1, T2), T3)]. И если вы соберете пять из них, как в вашем примере, это будет Parser[((((T1, T2), T3), T4), T5)]. Затем, когда вы сопоставляете шаблон с результатом, у вас также есть все эти скобки:

case ((((_, id), _), formals), _) => ...

Это довольно неудобно.

Затем появляется умный синтаксический трюк. Когда класс case имеет два параметра, он может отображаться в инфиксном, а не в префиксном положении в шаблоне. То есть, если у вас есть case class X(a: A, b: B), вы можете сопоставить образ с case X(a, b), но также с case a X b. (Это то, что сделано с шаблоном x::xs для соответствия непустому списку, :: - это класс case). Когда вы пишете регистр a ~ b ~ c, это означает case ~(~(a,b), c), но гораздо приятнее и приятнее, чем case ((a,b), c) тоже, что сложно сделать правильно.

Таким образом, метод ~ в Parser возвращает a Parser[~[T,U]] вместо Parser[(T,U)], поэтому вы можете легко сопоставлять шаблоны с результатом нескольких ~. Кроме того, ~[T,U] и (T,U) - это почти то же самое, что и изоморфно, как вы можете получить.

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

parser1 ~ parser2 ~ parser3 ^^ {case part1 ~ part2 ~ part3 => ...}

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

В последней точке есть вспомогательные операторы ~> и <~, которые отбрасывают результат одного из операндов, обычно константных частей в правиле, которые не содержат полезных данных. Поэтому лучше написать

"class" ~> ID <~ ")" ~ formals <~ ")"

и получить только значения ID и формалей в результате.

Ответ 3

Вы должны проверить Parsers.Parser. Scala иногда определяет класс метода и case с тем же именем, чтобы помочь совпадению шаблонов и т.д., и это немного запутывает, если вы читаете Scaladoc.

В частности, "class" ~ ID совпадает с "class".~(ID). ~ - это метод, который последовательно объединяет парсер с другим парсером.

Здесь неявное преобразование, определенное в RegexParsers, которое автоматически создает парсер из значения String. Таким образом, "class" автоматически становится экземпляром Parser[String].

val ID = """[a-zA-Z]([a-zA-Z0-9]|_[a-zA-Z0-9])*"""r

RegexParsers также определяет другое неявное преобразование, которое автоматически создает парсер из значения Regex. Таким образом, ID автоматически также становится экземпляром Parser[String].

Объединив два синтаксических анализатора, "class" ~ ID возвращает a Parser[String], который соответствует буквальному "классу", а затем регулярное выражение ID появляется последовательно. Существуют и другие методы, такие как | и |||. Для получения дополнительной информации прочитайте Программирование в Scala.