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

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

21 голосов
/ 25 июля 2011

Я довольно новичок в Scala и, читая о комбинаторах синтаксических анализаторов ( Волшебство за комбинаторами синтаксических анализаторов , Специфичные для домена языки в Scala ), я натолкнулся на определения методов, подобные этим: 

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

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

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

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

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

Jan

Ответы [ 3 ]

30 голосов
/ 25 июля 2011

Структура здесь немного хитрая. Во-первых, обратите внимание, что вы всегда определяете эти вещи внутри подкласса некоторого синтаксического анализатора, например 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, супертрейт для 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 будет успешно соответствовать.

13 голосов
/ 25 июля 2011

Метод ~ в анализаторе объединяет два анализатора в одном, который последовательно применяет два исходных анализатора и возвращает два результата.Это может быть просто (в 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 возвращает Parser[~[T,U]] вместо Parser[(T,U)], так что вы можете легко сопоставить шаблон с результатом нескольких ~.Кроме того, ~[T,U] и (T,U) - это почти одно и то же, настолько изоморфное, насколько это возможно.

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

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

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

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

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

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

3 голосов
/ 25 июля 2011

Вы должны оформить заказ 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 возвращает Parser[String], который соответствует литеральному «классу», а затем регулярное выражение ID, появляющееся последовательно. Есть и другие методы, такие как | и |||. Для получения дополнительной информации читайте Программирование в Scala .

...