scala'daki özyinelemeli yapıları ayrıştırma

Question

Basit SQL benzeri dizeleri ayrıştırabilen bir scalada ayrıştırmaya çalışıyorum. Çalıştığım temellerini var ve böyle bir şey ayrıştırabilir:

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

Ama şimdi yani

benim 'combinedPredicate' mevcut üretim şöyle

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

, iç içe ve sınıfları ayrıştırmak merak :

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

ben yinelemeli kendi içinde combinedPredicate üretimini başvuran çalıştı ama bu bir stackoverflow sonuçlanır.

Answer 1

Eh, tekrarlama şekilde sınırlandırılmış olması gerekiyor);

btw, sadece tüm ansi-99 spec uygulayan değil ... Burada deniyorum. Bu durumda, bu yapabilirdi: Recurse, çünkü

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

yüzden taşma yığını asla öncelikle bir karakter kabul etmek vardır. Bu önemli bir parçadır - eğer her zaman bir karakteri kabul etmeden özyinelemenin gerçekleşmeyeceğini düşünüyorsanız, sonsuz bir tekrarlamaya asla girmeyeceksiniz. Tabii ki, sonsuz girdiniz yok. ;)

Answer 2

operatör önceliği çözümlerini hakkında okuduktan sonra ve Scala 2.7

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

ayrıştırıcı combinators özyinelemeli iniş ayrıştırıcısı vardır: yaşandığı yeniden bir sol özyinelemeli dilinin sonucu muhtemelen. Yinelemeli soy ayrıştırıcıları bunlarla ilgili problemlere sahiptir, çünkü terminal sembolünün ilk karşılaştıkları zaman nasıl olduğu hakkında hiçbir fikri yoktur.

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

Alternatif planı ayrı olabilir,: Bunu gibi lazy val s yerine yöntemler kullanılarak dilbilgisi tanımlamak gerekir gerçi Scala 2.8 en packrat ayrıştırıcı, bağdaştırıcılarla gibi ayrıştırıcıları Diğer türlü, bununla bir sorunum yok olacak sol özyineleme önlemek için dil. Bana verdiğiniz örnekte, bu dilde parantez gerektiren problemi etkin bir şekilde çözebilir.

Şimdi her bir daha derin özyineleme düzeyi, ayrıştırılan başka parantezlere karşılık gelir. Parantez bittiğinde daha derine inmek zorunda olmadığını biliyorsunuz.

Answer 3

yığın taşması size'

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 muhtemelen @Daniel yazdıklarını yazmaya sadece başka bir yoludur: Aşağıdaki ile geldi :-)