Разбор рекурсивных структур в Scala - PullRequest
Новая
       30

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

7 голосов
/ 26 ноября 2009

Я пытаюсь создать синтаксический анализатор в 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;)

Ответы [ 3 ]

11 голосов
/ 26 ноября 2009

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

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

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

7 голосов
/ 27 ноября 2009

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

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 <~ ")" | ...

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

0 голосов
/ 26 ноября 2009

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

  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;)

...