Tôi đang tạo thư viện cho các ngữ pháp sẽ có 2 cách giải thích khác nhau: 1) phân tích chuỗi dựa trên ngữ pháp 2) tạo chuỗi theo ngôn ngữ được định nghĩa bởi ngữ pháp.Sử dụng cây tùy ý với Monads miễn phí trong Scala + Cats
Thư viện sử dụng mèo để tạo AST ngữ pháp làm đơn vị miễn phí. Tuy nhiên, có vẻ như nó có thể không hoàn toàn phù hợp bởi vì các monads tự do tạo ra một biểu diễn giống như danh sách AST của tôi, tốt cho danh sách các câu lệnh, nhưng ngữ pháp không nằm trong danh sách tuyên bố và gần gũi hơn với cấu trúc cây tùy ý.
Tôi đã quản lý để triển khai cây của mình bằng cách sử dụng toán tử ~ để biểu thị 2 ngữ pháp được ghép nối. AST sau đó là danh sách các ngữ pháp mà chính chúng là các AST tùy ý.
Câu hỏi của tôi là: Cách tốt để recurse các subtrees của một AST trong một đơn nguyên miễn phí là gì?
thực hiện hiện tại của tôi 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
}
})
}
}
Lưu ý đặc biệt, đó là trường hợp Multi sử dụng đệ quy không an toàn (ví dụ: không đuôi đệ quy) để đệ quy giải thích các cây con. Có cách nào tốt hơn để làm điều này?
Please click here for the source code.