Java /kotlin AST 构建相关，悬赏 200 求解，人已经麻了

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1010 天前的主题，其中的信息可能已经有所发展或是发生改变。

写在前面：给出的悬赏可能在各位眼里看起来比较可笑，但对我来说这是我两天的生活费了，网上的教程乱七八糟，目前的这个架构是在 chatGPT 设计的结构上魔改的，但出了严重的问题。如果能解决这个问题，我宁愿不吃不喝两天整提前谢谢各位了，这项目是自己玩整的，别的都好了，就卡在一个 ast 上，虽然是自己做着玩，但实在不想前功尽弃

这边的游戏需要设计一个可以将效果原子化和序列化的功能，由于 function 方法不可被原子化，且我这边无法使用 lua ，因此我设计了一个能输入和输出任意类型的抽象语法树，可以对其节点进行序列化和反序列化，从而使得整个树可以序列化。当前设计如下：有一个接口(astNode)，简称基类，有一个泛型 O ，有一个 operation 方法，输出类型是 O ，传参是 map<string ，object> 在基类第二层的是结构化节点：叶子节点和枝干节点，都继承自第一层。叶子节点只存储一个值，但不能存节点，有两个泛型，一个是记录存储属性类型的，一个是记录返回类型的。叶子节点就两种，一种记录常数(constant)，比如 2x+1 里的 2 和 1. 另一种记录未知数(param)，就是 2x+1 里的 x ，他会读取 operation 方法传过来的 map ，从里面找到对应的对象。枝干节点则里面可以存储叶子节点或枝干节点。他们有三种类型，单节点型，list 型和 pair 型，单节点的，比如提取目标怪兽的血量，里面就只需要记录一个指向怪兽的叶子节点。双节点最常见，加减乘除，operation 方法就是将两个节点 operation 的值进行运算。list 节点则是类似 in ，传入一个 list ，他从里面返回一个符合需求的值。然后第三层就是对运算目标的类型进行定义的层。比如 equals ，有针对数字的 equals ，有针对怪物实体的 equals ，等等，这一层将他们进行封装。第四层是封装层，这层会将所有泛型全部匹配，不会出现需要在外面输入泛型的情况。在最外侧，会有一个 tree 实体，这个实体可以访问根节点，并进行如深度搜索或者是查找节点，替换节点之类的行为。现在的问题是：我想要一个方式能将这个树序列化和反序列化，并通过读取用户输入将其转换为一个树。我最开始是打算从根节点向叶子节点进行构建，但我很快发现这个方法的不可操作性：因为我的树不是完全的二叉树，有常数和未知数两种没有子节点概念的树，他们只有一个 value ，而且由于我有三种不同类型的枝干节点，我无法使用一个统一的，写在基类里的 addNode 方法在节点生成后对子节点进行操作，我必须使用 if else 才行，这违背了泛型的初衷，也十分不灵活，所以我必须从最下方的叶子节点往上方构建。我的打算是，先筛选出所有的叶子节点，然后像搭金字塔一样，用 1 ，2 ，list 个节点将符号构建出来，然后在这个符号上再和其他符号或者节点一起搭符号，最后搭到根节点。但是这有个问题：当我在使用如 numberEqualsNode ，这种左右节点一个是 int ，另一个也是 int ，输出是 bool 的节点，我该如何判断输入的 node 的泛型是 int ？如果不判断，那么左右节点设置泛型的意义何在？由于 java 的泛型是在运行之后会被删掉的和注释一样的用于检查编译的东西，所以我不能直接 if node is node<int>，但那样我怎么检查这个节点？

备注：无法换语言，或者使用 lua ，但可以使用 kotlin 和 scala 。可以改变一些设计，但不能把整个底层都给刨了。

节点

泛型

叶子

枝干

13 条回复 2023-03-17 20:09:51 +08:00

iseki

2023-03-16 23:20:48 +08:00 via Android

代码呢，你用一大堆文字描述模型设计，不如直接把关键部分的代码拿出来

r1nice

2023-03-16 23:33:05 +08:00

@iseki 新人，没怎么用过 V2EX ，不清楚怎么 po 代码,这里先放个 github 链接:https://github.com/RiniceSiberia/Co2Dice/tree/master/src/main/java/org/co2dice/mirai/ast

以下是文字版代码

interface AstNode <
O
//输出
> {
val name : String

fun operation(param : Map<String,Any>):O
//这个节点的运算方式，计算这个节点的运算结果

fun vacancy() : Boolean
//用来检查能否被插入一个新节点

abstract fun getChild() : List<AstNode<*>>
//获取所有子节点

fun dfs(find : () -> Boolean) : AstNode<*>? {
if (find()) {
return this
}
for (child in getChild()) {
val result = child.dfs(find)
if (result != null) {
return result
}
}
return null
}

}

abstract class LeafNode<O,V>() : AstNode<O> {
abstract var value : V

override fun vacancy(): Boolean {
return false
}

override fun getChild(): List<AstNode<*>> {
return emptyList()
}
}
abstract class BranchNode<T>() : AstNode<T> {

}

abstract class SingleChildNode<I,O> : BranchNode<O>() {
abstract var child : AstNode<I>

override fun vacancy(): Boolean {
return child !is PlaceholderNode
}

override fun getChild(): List<AstNode<I>> {
return listOf(child)
}

}
abstract class PairChildNode<LI,RI,O> : BranchNode<O>() {
abstract var left : AstNode<LI>
//左节点
abstract var right : AstNode<RI>
//右节点

override fun vacancy(): Boolean {
return (left is PlaceholderNode) || (right is PlaceholderNode)
}
override fun getChild(): List<AstNode<*>> {
return listOfNotNull(left,right)
}
abstract class ListChildNode<I,T>(
var childs: MutableList<AstNode<I>> = mutableListOf()
) : BranchNode<List<T>>() {

override fun getChild(): List<AstNode<I>> {
return childs
}

override fun vacancy(): Boolean {
return true
}

}
abstract class EqualsNode<T>(
override var left : AstNode<T>,
override var right : AstNode<T>,
) : PairChildNode<T, T, Boolean>() {

override fun operation(param : Map<String,Any>) : Boolean{
return left.operation(param) == right.operation(param)
}

override fun toString(): String {
return "=="
}
}
class NumberEqualsNode(
left : AstNode<Int> = NumberPlaceholderNode(),
right : AstNode<Int> = NumberPlaceholderNode(),
) : EqualsNode<Int>(left,right) {
override val name: String = Symbols.NUMBER_EQUALS.name
}

liuhan907

2023-03-17 00:53:00 +08:00

虽然写了很多，但是我还是没有搞清楚你的需求是什么。你解释了你的设计，但是没有说原始需求。令，不能更换语言的原因是技术上的还是非技术上的？

Leviathann

2023-03-17 01:11:22 +08:00

听起来有点像 GADT
Scala 3 的例子
https://gist.github.com/jsyeo/a4ba0f82cc2d658339f53c0ff3d84f8b
kotlin 一个可能的 work around
https://gist.github.com/elizarov/b5400f827616090811ebb348acd4c426

dif

2023-03-17 10:15:28 +08:00

用 github 的 gist 好一点吧，另外 v 站支持 md.

penguinWWY

2023-03-17 12:40:16 +08:00

所以你的问题是如何检查一个节点的类型？

r1nice

2023-03-17 13:20:29 +08:00

@liuhan907 需求:让一个游戏的玩家可以通过 json 或者 string 字符串类型的输入，来使用受限制的符号自定义一个 function ，并能将这个 function 序列化和反序列化塞进 mysql 里
不能更换语言的原因纯粹是我这边时间和精力不足以及成本太高，我只会 java 和 kotlin ，而且项目的代码除了 ast 外已经基本搞定了，如果要直接推倒重来成本完全不可接受，只能硬刚

Zakl21

2023-03-17 13:57:35 +08:00

怎么像是一个规则引擎的事情，用户通过输入规则，生成一个引擎，然后传入参数，通过这个引擎得到输出。。。

Zakl21

2023-03-17 14:22:43 +08:00

可以描述一下你想要的 ast 输入，以及参数输入，参数输出

wuych

2023-03-17 16:00:06 +08:00

所以你的需求类似于实现一个自创的编程语言，把用户提交上来的代码（类似.java ）解释成一颗 executable 的语法树，而且最好能把这棵语法树序列化存档（类似.class ），以便运行时直接反序列化成 AST 用于执行？
方案能不能简单一点？只把用户提交的数据编译成 AST ，不考虑 AST 的序列化和反序列化，存用户提交上来的数据，每次执行时进行编译？

r1nice

2023-03-17 16:51:30 +08:00

@wuych 不行，必须要进行序列化和反序列化，做到 ast 的永久化，否则这个系统搞不定任何事

r1nice

2023-03-17 17:02:27 +08:00

@Zakl21 两种输入:json 和字符串，我手敲一个好了
selectMonsterByName(StringConstant("zombie")).getAttribute(AttributeConstant("Dex")).plus(IntParam("test")).divide(Constant(3))
获取名称为 zombie 的僵尸，如果存在就获取其僵尸属性(否则就 throw)，返回(他的敏捷数值+输入的，key 为 test 的数值)/3 的数值
在 json 里的表达:

{
name : divide
left:{
name:plus
left:{
name:get_attribute
left:{
name:select_monster_by_name
left:{
name:string_constant
value:"zombie"
}
right:null
}
right:{
name:attribute_constant
value:Dex
}
}
right:{
name:int_param
value:"test"
}
}
right:{
name:int_constant
value:3
}
}

liuhan907

2023-03-17 20:09:51 +08:00

如果你不考虑安全问题，直接用 javac 把输入编译后加载直接跑，要是想要安全点就编译到 wasm 挂个 wasm rt 来跑