analisar estruturas recursivas em scala

Question

Eu estou tentando contruct um analisador em scala que pode analisar simples SQL-like cordas. Eu tenho o básico trabalhando e pode analisar algo como:

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

Mas agora eu me perguntava como analisar aninhada e aulas, i.

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

A produção atual de minha aparência 'combinedPredicate' assim:

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

Eu tentei de forma recursiva referenciando a produção combinedPredicate dentro de si, mas que resulta em um stackoverflow.

btw, estou apenas experimentando aqui ... não implementar toda a ansi-99 especificação;)

Answer 1

Bem, recursividade tem de ser delimitado de alguma forma. Neste caso, você poderia fazer isso:

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

Por isso, nunca vai estouro de pilha, porque, ao recurse, primeiro ele tem que aceitar um personagem. Esta é a parte mais importante - se você sempre garantir recursão não vai acontecer sem antes aceitar um personagem, você nunca vai entrar em uma recursão infinita. A menos, claro, você tem de entrada infinita. : -)

Answer 2

O estouro de pilha que você está enfrentando é provavelmente o resultado de uma linguagem de esquerda-recursiva:

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

Os combinadores analisador em Scala 2.7 são analisador sintático descendente recursivo. analisador sintático descendente recursivo tem problemas com estes porque eles não têm idéia de como o símbolo do terminal é quando eles encontrá-lo. Outros tipos de analisadores, como Scala 2,8 de combinadores analisador packrat não terá nenhum problema com isso, mas você vai precisar definir a gramática usando lazy vals em vez de métodos, assim:

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

Como alternativa, você poderia refatorar a língua para evitar recursão esquerda. A partir do exemplo que você está me dando, requerendo parênteses nesta língua poderia resolver o problema de forma eficaz.

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

Agora, cada nível mais profundo de corresponde recursão para outro parênteses analisado. Você sabe que você não tem que recurse mais profunda quando você correr para fora de parênteses.

Answer 3

Depois de ler sobre soluções para a precedência do operador e veio com o seguinte:

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

Wich é provavelmente apenas uma outra forma de escrita que @ Daniel escreveu;)