Я создаю библиотеку для грамматик, которая будет иметь 2 разные интерпретации: 1) разбор строк на основе грамматики 2) создание строк на языке, определенном грамматикой.
Библиотека использует кошек для создания AST грамматики в виде свободной монады. Однако кажется, что это может быть не идеальное соответствие, потому что бесплатные монады создают списочное представление моего AST, что хорошо для списков операторов, но грамматика далека от списка операторов и намного ближе к произвольной древовидной структуре.
Мне удалось реализовать свои деревья с помощью оператора ~ для обозначения двух объединенных грамматик. Таким образом, AST представляет собой список грамматик, которые сами по себе являются произвольными AST.
Мой вопрос: каков хороший способ рекурсии поддеревьев AST в свободной монаде?
Моя текущая реализация здесь:< /а>
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 используется небезопасная рекурсия (т. е. не хвостовая рекурсия) для рекурсивной интерпретации поддерева. Есть лучший способ это сделать?
