Os parser combinadores podem ser um tema bastante complicado a nível de programação, mas a nível de teoría é bastante simples. Existem muitos recursos sobre isto nomeadamente universidades como por exemplo aqui: Monadic Parser Combinators - University of Nottingham.
Monads
É muito importante perceber o que é um Monad e para isto tenho um exemplo no meu código:
typealias TextParser<T> = (String) -> Result<T>
Aqui, TextParser
é o nosso monad. Não tem necessáriamente que ser uma função. A teoría diz apenas que um monad é uma estrutura usada para envolver um valor e devolver um resultado no final da computação sendo possível usar o monad para cálculos intermédios onde os valores são utilizados no contexto de um monad.
Nós precisamos de este monad para o nosso exemplo. Neste caso o nosso monad é apenas uma função.
Simples parsers
No meu exemplo no GitHub hà vários parsers e todos têm uma função semelhante. Quando criamos parsers combinadores, devemos de criá-los com o objectivo de poder linkar-los ou associa-los com outros parsers de modo a que no final tenhamos apenas um parser que resolve todas as desejadas computações. Este é um exemplo disso:
fun charCountParser(expected: Char): TextParser<Char> = { input ->
val splits = input.split(expected)
val size = splits.size - 1
when (input.isNotEmpty() && size > 0) {
true -> Result(expected, size, splits.filter { it.isNotEmpty() })
else -> expected.emptyResult()
}
}
Este charCountParser
retorna uma função (não o valor), que conta o número de vezes que certo char
se contra em determinado texto. O texto é o argumento de entrada da função devolvida. Aqui temos um simples parser. No resto do project encontrarás outros parsers. Mas o importante é que todos estes parser retornam o mesmo típo e todos estes tipos são monads. No nosso caso todos recebem um String
e devolvem um Result
com um tipo arbitrário. Result
é implementado da seguinte forma por conveniência:
data class Result<T>(
val expected: T,
val count: Int,
val remainder: List<String>
)
Em expected
devolvemos o que esperamos encontrar. Nós podemos implementar isto como quisermos e até podemos chamar-lhe command. Não interessa muito o nome. É apenas a estrutura de dados que fornecemos como parametro. No nosso caso expected
representa o que queremos encontrar no texto. count
é o número de vezes que encontramos um match no nosso parser e remainder
é o texto ou resto. No nosso caso definimos remainder
como texto que não foi usado no parsing or vários motivos entre eles que não foi processado por não haver um match. Este remainder
é importante quando associamos diferentes parsers. Esá representado por uma lista de strings que representam os segmentos que resultam da separação do texto em duas strings pelo separador. Quando o texto não é separável, ou seja, o separador não existe, então esse texto torna-se o remainder
da operação.
Parsers combinadores
Agora que vimos uma forma de implentar parsers. Esá na altura de os combinar e no meu exemplo temos dois mas vamos ver apenas um para perceber como os podemos combinar. Parser combinadore podem ser implementados com operações infix
, operadores aritméticos out simples funçóes. Para perceber conceito básico vamos dar uma olhadela a uma implementação com funções, neste caso then
:
fun <T, R> TextParser<T>.then(textParser: TextParser<R>): TextParser<Pair<T, R>> = { input ->
this(input).let { (resultOfFirstParser, _, remainingOfFirstParser) ->
remainingOfFirstParser.map {
textParser(it).let { (resultOfSecondParser, countOfSecondParser, remainingOfSecondParser) ->
Result(Pair(resultOfFirstParser, resultOfSecondParser), countOfSecondParser, remainingOfSecondParser)
}
}
.takeIf { it.isNotEmpty() }
?.reduce { acc, pairResult ->
Result(
acc.expected,
acc.count + pairResult.count,
acc.remainder + pairResult.remainder
)
} ?: Pair(resultOfFirstParser, null as R).emptyResult()
}
}
Os pormenores da função then
são menos relevantes para esta resposta mas é importante entender um aspecto básico de como functiona. A combinação dos parsers significa que nós podemos implementar algo intermédio como uma funcionalidade extra que junta os dois parsers. then
, neste caso, utiliza o resultado do primeiro parser, o remaining
e chama a função do segundo parser com ele. Na nossa implementação, como os remainders são listas e não apenas uma string, nós temos que fazer a nossa implementação e tomar decisões. Para a minha implementação resolvir chamar o segund parser iterativamente e reduzir-lo com a operação reduce
para devolver uma única implementação. E aqui é importante salienter de que then
é uma implementação de uma função que retorna um monad, combinando dois monads.
Combinando
Quando temos os nosso parsers básicos e os combinadores implementados, nós podemos então finalmente criar os nossos combinadores customizáveis com os nossos objectivos. A implementação dos combinadores é, na minha opinião a parte mais complicada do desenvolvimento dos parsers combinadores.
Aqui temos um examplo nos meus testes unitários:
@Test
fun `should run combined parsers 3`() {
val woodCompanyInitialsParser = charCountParser('W')
.then(charCountOnStartParser('C'))
.then(charCountOnStartParser('M'))
val woodCompanyDescriptionTextParser: TextParser<String> = stringCountParser(" Cats Woodlands United")
val woodCompanyCombinedParser = woodCompanyDescriptionTextParser.then(woodCompanyInitialsParser)
val input = """
The WCM Cats Woodlands United association loves cats.
As a Wood Company Masters, they create beautiful scratch poles for cats.
If you have Cats you'll find that they particularly love these poles.
Maine Coon Cats Woodlands United helps cats around the world achieve their best version of themselves.
Come to WCM Cats Woodlands United
""".trimIndent()
val result = woodCompanyCombinedParser(input)
result.count shouldBe 2
result.remainder.shouldBeEmpty()
result.expected shouldBe (" Cats Woodlands United" to (('W' to 'C') to 'M'))
println(result)
}
Neste exemplo, o woodCompanyInitialsParser
é uma combinação de três parsers que procuram sequencialmente as siglas WCM. Primeiro aleatóriamente um W
e depois sequencialmente na primeria posição C
e M
. O woodCompanyDescriptionTextParser
é apenas um parser que procur o texto Cats Woodlands United
. No entanto, o parser combinado woodCompanyCombinedParser
vai procurar primeiro o texto e só depois as iniciais. Finalmente no resultado, ele encontra realmente 2 resultados e o expected
indica que os comandos executados e bem sucedidos corresponde à espectativa.
Conclusão
Este código tem bugs e a ideia não é prestar foco a isso. Isto é apenas um exemplo simplificado para perceber como os parser combinadores funcionam e uma forma de implementar-los.
A idea é perceber que temos parsers, combinadores e, outros parsers que resultam dessa combinação. O uso de parsers combinadores é muito interessante na perspectiva de criar um framework ou uma biblioteca. Os parsers combinadores são interessantes porque ajudam a criar software mais legível e fácil de usar, mas também têm problemas e são conhecidos por isso. Como podeste ver, os parser combinadores são complexos, difíceis de manter, exigem muito do programador comum, introduzem recursividade que pode ser problemática, a complexidade pode evoluir para um complexo backtracking, ou seja a procura exaustiva de todas as possíveis alternativas.
O exemplo completo pode ser acedido aqui: jesperancinha jeorg-kotlin-parser-combinators on GitHub.
Linguagens de programação
O meu exemplo é apresentado em Kotlin. Mas de nenhuma maneira está a teoria de parsers combinadores vinculada ao uso de Kotlin. Qualquer linguagem funcional ou que dê suporte a linguagem funcional como Lisp, Haskell, Scala, Kotlin, Javascript, Clojure, Python, Erlang, pode ser usada para a implementação de parsers combinadores. O exemplo é apenas uma ilustração
Saber mais
Aqui deixo links importantes para saber mais sobre esta teoria:
- Monadic Parser Combinators, Graham Hutton, University of Nottingham
- Monads for functional programming, Philip Wadler, University of Glasgow
- Categories and Functors, Bodo Pareigis, University of Munich, Germany