I'm experimenting with writing a DSL for AST matching (and hopefully also property extraction). I'm ...

# mathematics

[Curtis Ullerich]

I'm experimenting with writing a DSL for AST matching (and hopefully also property extraction). I'm curious if anyone knows of prior art.

[altavir]

Could you elaborate about what do you mean by AST matching? Generic tree comparison?

[Curtis Ullerich]

Matching of structure/properties of a tree made from a known kotlin node class.

[Curtis Ullerich]

I put together a toy example to explore possibilities. Here's a usage example:

val ast = ExponentNode(AdditionNode(VariableNode("x"), NumberNode(5)), NumberNode(2))
var name: String? = null
var value: Int? = null
val matcher =
  exp {
    parens() {
      optional()
      plus {
        variable { extract { name = it.name } }
        num { extract { value = it.value } }
      }
    }
    num { where { it.value == 2 } }
  }
val match = matcher.matches(ast)
println("$match $name $value")

[Curtis Ullerich]

the matching part seems straightforward and I'm pretty happy with the direction it's heading. I would like to find something better for the property extraction part. I was originally hoping to be able to write something like this:

val (name: String, value: Int) = matcher.extractFrom(ast) ?: return null

but I can't find a good way to implement it

[Curtis Ullerich]

I just realized there's a channel for DSLs. I'll ask that question about extract there but I'm still interested in any prior art for AST (math or otherwise) matchers.

[altavir]

We've developed a simple AST for maths called MST https://github.com/SciProgCentre/kmath/blob/master/kmath-core/src/commonMain/kotlin/space/kscience/kmath/expressions/MST.kt. But the whole idea in thins case is to avoid creating dedicated DSL for it. Instead the mathematical context ensures that regular mathematic expressions are converted to MST.

[altavir]

There is also a parser based on better-parse: https://github.com/SciProgCentre/kmath/blob/master/kmath-ast/src/commonMain/kotlin/space/kscience/kmath/ast/parser.kt