Analizando estructuras recursivas en scala.

Question

Estoy tratando de construir un analizador en scala que pueda analizar cadenas simples tipo SQL. Tengo los conceptos básicos funcionando y puedo analizar algo como:

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

Pero ahora me pregunto cómo analizar anidados y clases, es decir,

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

La producción actual de mi 'Redacción combinada' se ve así:

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

Intenté hacer referencia de forma recursiva a la producción combinada de Predicate dentro de sí misma, pero eso da como resultado un stackoverflow.

por cierto, estoy experimentando aquí ... no implementando la especificación ansi-99 completa;)

Answer 1

Bueno, la recursión tiene que ser delimitada de alguna manera. En este caso, podrías hacer esto:

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

Por lo tanto, nunca se acumulará el desbordamiento porque, para repetirse, primero tiene que aceptar un carácter. Esta es la parte importante: si siempre aseguras que la recursión no suceda sin aceptar primero un personaje, nunca tendrás una recursión infinita. A menos que, por supuesto, tengas una entrada infinita. :-)

Answer 2

El desbordamiento de pila que está experimentando es probablemente el resultado de un lenguaje recursivo a la izquierda:

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

Los combinadores de analizador en Scala 2.7 son analizadores de descendencia recursivos. Los analizadores de descenso recursivo tienen problemas con estos porque no tienen idea de cómo es el símbolo terminal cuando lo encuentran por primera vez. Otros tipos de analizadores como los combinadores de analizador packrat de Scala 2.8 no tendrán ningún problema con esto, aunque tendrá que definir la gramática utilizando lazy val s en lugar de métodos, como por ejemplo:

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

Alternativamente, puedes refactorizar el idioma para evitar la recursión a la izquierda. A partir del ejemplo que me está dando, el hecho de requerir paréntesis en este idioma podría resolver el problema de manera efectiva.

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

Ahora, cada nivel más profundo de recursión corresponde a otro paréntesis analizado. Usted sabe que no tiene que recurrir más profundamente cuando se queda sin paréntesis.

Answer 3

Después de leer acerca de las soluciones para la precedencia del operador y surgió lo siguiente:

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

Probablemente sea otra forma de escribir lo que escribió @Daniel;)