7
나는 두 가지 해석이 가능한 문법 라이브러리를 만들고있다 : 1) 문법에 따라 문자열 파싱 2) 문법에 정의 된 언어로 문자열 생성.Scala + Cats에서 Free Monads로 임의의 나무 사용하기
라이브러리는 고양이를 사용하여 문법의 AST를 무료 모나드로 만듭니다. 그러나 무료 모나드는 AST의 목록과 같은 표현을 생성하기 때문에 성립되지 않을 수도 있지만 문법은 문 목록과는 거리가 멀며 임의의 나무 구조에 훨씬 가깝습니다.
~ 연산자를 사용하여 연결된 2 개의 문법을 나타내는 것으로 트리를 구현할 수있었습니다. AST는 그 자체로 임의의 AST 인 문법 목록입니다.
제 질문은 : 무료 모나드에서 AST의 하위 트리를 재귀하는 좋은 방법은 무엇입니까?
내 현재 구현 is here:
def parserInterpreter: GrammarA ~> ParserInterpreterState =
new (GrammarA ~> ParserInterpreterState) {
def apply[A](fa: GrammarA[A]): ParserInterpreterState[A] =
fa match {
case Regx(regexp) => parseRegex(regexp)
case Optional(b) => parseOptional(b.foldMap(this))
case m @ Multi(g) =>
def x: State[String, A] =
State.apply(state => {
g.foldMap(this)
.run(state)
.map {
case (s, ParseSuccess(_)) => x.run(s).value
case r @ (s, ParseFailure()) => (s, ParseSuccess(s).asInstanceOf[A])
}
.value
})
x
case Choice(a, b) =>
State.apply(state => {
val runA = a.foldMap(this).run(state).value
if (runA._2.asInstanceOf[ParseResult[_]].isSuccess)
runA
else {
b.foldMap(this).run(state).value
}
})
}
}
주 특히 Multi 경우 재귀 서브 트리를 해석하기 위해 안전 재귀 (즉 꼬리없는 재귀)를 사용하는 것이다. 이 작업을 수행하는 더 좋은 방법이 있습니까?
Please click here for the source code.