Разбор рекурсивных структур в Scala

Question

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

select id from users where name = "peter" and age = 30 order by lastname

Но теперь мне стало интересно, как анализировать вложенные и классы, т. е.

select name from users where name = "peter" and (age = 29 or age = 30)

Текущее производство моего комбинированного предиката выглядит следующим образом:

def combinedPredicate = predicate ~ ("and"|"or") ~ predicate ^^ {
  case l ~ "and" ~ r => And(l,r)
  case l ~ "or" ~ r => Or(l,r)
}

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

Кстати, я просто экспериментирую здесь ... не реализую всю спецификацию ansi-99;)

Answer 1

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

def combinedPredicate = predicate ~ rep( ("and" | "or" ) ~ predicate )
def predicate = "(" ~ combinedPredicate ~ ")" | simplePredicate
def simplePredicate = ...

Таким образом, он никогда не будет переполняться стеком, потому что, для повторения, он должен сначала принять символ. Это важная часть - если вы всегда гарантируете, что рекурсия не произойдет без предварительного принятия персонажа, вы никогда не попадете в бесконечную рекурсию. Если, конечно, у вас нет бесконечного ввода. : -)

Answer 2

Переполнение стека, которое вы испытываете, возможно, является результатом леворекурсивного языка:

def combinedPredicate = predicate ~ ...
def predicate = combinedPrediacate | ...

Комбинаторы парсеров в Scala 2.7 являются парсерами рекурсивного спуска. С ними сталкиваются парсеры рекурсивного спуска, потому что они понятия не имеют, каким является символ терминала, когда они впервые сталкиваются с ним. Другие виды синтаксических анализаторов, такие как пакетные парсин-комбинаторы Scala 2.8, не будут иметь проблем с этим, хотя вам нужно определить грамматику, используя lazy val s вместо методов, например так:

lazy val combinedPredicate = predicate ~ ...
lazy val predicate = combinedPrediacate | ...

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

def combinedPredicate = predicate ~ ...
def predicate = "(" ~> combinedPrediacate <~ ")" | ...

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

Answer 3

Прочитав о решениях для приоритетов операторов и придумав следующее:

  def clause:Parser[Clause] = (predicate|parens) * (
            "and" ^^^ { (a:Clause, b:Clause) => And(a,b) } |
            "or" ^^^ { (a:Clause, b:Clause) => Or(a,b) } )

  def parens:Parser[Clause] = "(" ~> clause  <~ ")"

Вероятно, это просто еще один способ написать то, что написал @Daniel;)