스칼라의 재귀 구조를 구문 분석합니다

StackOverflow https://stackoverflow.com/questions/1802372

  •  05-07-2019
  •  | 
  •  

문제

나는 간단한 SQL 유사 문자열을 구문 분석 할 수있는 스칼라로 구문 분석기를 조언하려고합니다. 기본 사항이 작동하고 다음과 같은 것을 구문 분석 할 수 있습니다.

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

하지만 이제 나는 중첩과 수업을 구문 분석하는 방법이 궁금했습니다.

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

내 'combinedpredicate'의 현재 생산은 다음과 같습니다.

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

나는 자체적으로 결합 된 프레디 케이트 생산을 재귀 적으로 참조하려고 시도했지만 그 결과 스테이크 오버 플로우를 초래했다.

BTW, 나는 단지 여기서 실험하고 있습니다 ... 전체 ANSI-99 사양을 구현하지 않습니다;)

도움이 되었습니까?

해결책

글쎄, 재귀는 어떻게 든 구분되어야합니다. 이 경우 다음을 수행 할 수 있습니다.

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

따라서 재발하기 위해서는 먼저 캐릭터를 받아 들여야하기 때문에 오버플로를 쌓지 않습니다. 이것은 중요한 부분입니다. 만약 당신이 항상 캐릭터를 수용하지 않고 재귀가 일어나지 않도록한다면, 당신은 무한한 재귀에 빠지지 않을 것입니다. 물론, 당신은 무한한 입력이 없다면. :-)

다른 팁

당신이 겪고있는 스택 오버플로는 아마도 왼쪽 상환 언어의 결과 일 것입니다.

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

Scala 2.7의 Parser Combinator는 재귀 하강 파서입니다. 재귀 하강 파서는 터미널 기호가 처음 만났을 때 어떻게되는지 전혀 모르기 때문에 이것에 문제가 있습니다. Scala 2.8의 Packrat Parser Combinator와 같은 다른 종류의 파서는 이것에 아무런 문제가 없지만 문법을 사용하여 문법을 정의해야합니다. lazy valS와 같은 방법 대신 :

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

또는 왼쪽 재귀를 피하기 위해 언어를 리팩터링 할 수 있습니다. 이 언어로 괄호를 요구하는 예에서 나에게주는 예에서 문제를 효과적으로 해결할 수 있습니다.

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

이제 각각의 더 깊은 수준의 재귀는 구문 분석 된 다른 괄호에 해당합니다. 괄호가 떨어지면 더 깊이 되풀이 될 필요가 없다는 것을 알고 있습니다.

운영자 우선 순위 솔루션에 대해 읽은 후 다음을 생각해 냈습니다.

  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는 아마도 @daniel이 쓴 것을 쓰는 또 다른 방법 일 것입니다.)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top