analizando estructuras recursivas en scala

Question

Estoy tratando de construir un analizador sintáctico en scala que pueda analizar cadenas sencillas similares a SQL. Tengo los conceptos básicos de trabajo y se puede analizar algo como:

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

Pero ahora me preguntaba cómo analizar y clases anidadas, es decir

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

La producción actual de mi 'combinedPredicate' se parece a esto :

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

Traté de hacer referencia de forma recursiva la producción combinedPredicate dentro de sí mismo, sino que se traduce en una stackoverflow.

por cierto, sólo estoy experimentando aquí ... no implementar toda la especificación ANSI-99;)

Answer 1

Bueno, recursividad tiene que ser delimitado de alguna manera. En este caso, usted puede hacer esto:

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

así que nunca desbordamiento de pila, ya que, a recursiva, primero tiene que aceptar un carácter. Esta es la parte importante: si siempre asegura que la recursión no ocurrirá sin antes aceptar un personaje, nunca tendrá una recursión infinita. A menos que, por supuesto, tengas una entrada infinita. :-)

Answer 2

Después de leer acerca de las soluciones para la precedencia de los operadores y se le ocurrió la 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 <~ ")" 

Wich es probablemente sólo otra manera de escribir lo que escribió @ Daniel;)

Answer 3

El desbordamiento de pila que' re experimentando es probablemente el resultado de un lenguaje de izquierda recursiva:

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

los combinadores de analizadores en Scala 2.7 son analizadores descendente recursivo. Los analizadores sintácticos 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 programas de análisis como de Scala 2.8 combinadores packrat analizador tendrán ningún problema con esto, sin embargo tendrá que definir la gramática utilizando lazy val s en lugar de métodos, así:

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

Como alternativa, puede refactorizar el lenguaje para evitar la recursividad a la izquierda. Por el ejemplo que me está dando, 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. Sabes que no tienes que recurrir más profundo cuando te quedas sin paréntesis.