parsing di strutture ricorsive in scala

Question

Sto provando a calcolare un parser in scala che può analizzare semplici stringhe simili a SQL. Ho le basi di lavoro e in grado di analizzare qualcosa come:

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

Ma ora mi chiedevo come analizzare e classi nidificate, cioè

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

La produzione attuale di mio 'combinedPredicate' si presenta così :

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

ho provato ricorsivamente riferimento alla produzione combinedPredicate in sé, ma che si traduce in una StackOverflow.

btw, sto solo sperimentando qui ... non attuare l'intero ANSI-99 spec;)

Answer 1

Beh, la ricorsione deve essere delimitato in qualche modo. In questo caso, si potrebbe fare questo:

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

in modo da mai impilare troppo pieno perché, per ricorsivamente, deve prima accettare un personaggio. Questa è la parte importante - se assicuri sempre che la ricorsione non accadrà senza prima accettare un personaggio, non entrerai mai in una ricorsione infinita. A meno che, naturalmente, tu non abbia input infiniti. :-)

Answer 2

Dopo aver letto su soluzioni per la precedenza degli operatori e si avvicinò con la seguente:

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

Quale è probabilmente solo un altro modo per iscritto ciò che ha scritto @ Daniel;)

Answer 3

Lo stack overflow di voi' re vivendo è probabilmente il risultato di un linguaggio di sinistra-recursive:

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

I combinatori parser in Scala 2.7 sono parser discesa ricorsiva. I parser di discesa ricorsivi hanno problemi con questi perché non hanno idea di come sia il simbolo del terminale quando lo incontrano per la prima volta. Altri tipi di parser come Scala 2.8 di combinatori packrat parser non avrà alcun problema con questo, anche se avrete bisogno di definire la grammatica utilizzando lazy val s invece di metodi, in questo modo:

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

In alternativa, si potrebbe refactoring la lingua per evitare la ricorsione a sinistra. Dall'esempio che mi stai dando, richiedere parentesi in questa lingua potrebbe risolvere il problema in modo efficace.

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

Ora ogni livello più profondo di ricorsione corrisponde a un'altra parentesi analizzata. Sai che non devi recidare più a fondo quando finisci le parentesi.