V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
r1nice
V2EX  ›  Kotlin

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

  •  
  •   r1nice · 2023-03-16 23:17:09 +08:00 · 2141 次点击
    这是一个创建于 377 天前的主题,其中的信息可能已经有所发展或是发生改变。

    写在前面: 给出的悬赏可能在各位眼里看起来比较可笑,但对我来说这是我两天的生活费了,网上的教程乱七八糟,目前的这个架构是在 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
        1
    iseki  
       2023-03-16 23:20:48 +08:00 via Android
    代码呢,你用一大堆文字描述模型设计,不如直接把关键部分的代码拿出来
    r1nice
        2
    r1nice  
    OP
       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
        3
    liuhan907  
       2023-03-17 00:53:00 +08:00
    虽然写了很多,但是我还是没有搞清楚你的需求是什么。你解释了你的设计,但是没有说原始需求。令,不能更换语言的原因是技术上的还是非技术上的?
    Leviathann
        4
    Leviathann  
       2023-03-17 01:11:22 +08:00
    dif
        5
    dif  
       2023-03-17 10:15:28 +08:00
    用 github 的 gist 好一点吧,另外 v 站支持 md.
    penguinWWY
        6
    penguinWWY  
       2023-03-17 12:40:16 +08:00
    所以你的问题是如何检查一个节点的类型?
    r1nice
        7
    r1nice  
    OP
       2023-03-17 13:20:29 +08:00
    @liuhan907 需求:让一个游戏的玩家可以通过 json 或者 string 字符串类型的输入,来使用受限制的符号自定义一个 function ,并能将这个 function 序列化和反序列化塞进 mysql 里
    不能更换语言的原因纯粹是我这边时间和精力不足以及成本太高,我只会 java 和 kotlin ,而且项目的代码除了 ast 外已经基本搞定了,如果要直接推倒重来成本完全不可接受,只能硬刚
    Zakl21
        8
    Zakl21  
       2023-03-17 13:57:35 +08:00
    怎么像是一个 规则引擎的事情,用户通过输入规则,生成一个引擎,然后传入参数,通过这个引擎得到输出。。。
    Zakl21
        9
    Zakl21  
       2023-03-17 14:22:43 +08:00
    可以描述一下你想要的 ast 输入,以及参数输入,参数输出
    wuych
        10
    wuych  
       2023-03-17 16:00:06 +08:00
    所以你的需求类似于实现一个自创的编程语言,把用户提交上来的代码(类似.java )解释成一颗 executable 的语法树,而且最好能把这棵语法树序列化存档(类似.class ),以便运行时直接反序列化成 AST 用于执行?
    方案能不能简单一点?只把用户提交的数据编译成 AST ,不考虑 AST 的序列化和反序列化,存用户提交上来的数据,每次执行时进行编译?
    r1nice
        11
    r1nice  
    OP
       2023-03-17 16:51:30 +08:00
    @wuych 不行,必须要进行序列化和反序列化,做到 ast 的永久化,否则这个系统搞不定任何事
    r1nice
        12
    r1nice  
    OP
       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
        13
    liuhan907  
       2023-03-17 20:09:51 +08:00
    如果你不考虑安全问题,直接用 javac 把输入编译后加载直接跑,要是想要安全点就编译到 wasm 挂个 wasm rt 来跑
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3354 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:22 · PVG 19:22 · LAX 04:22 · JFK 07:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.