SoftHub关联区 - [golang][新语言]手把手教你使用ANTLR和Go实现一门DSL语言（第三部分）：建立和验证语义模型【zt】

您的位置：首页 >> SoftHub关联区 >> 主题: [golang][新语言]手把手教你使用ANTLR和Go实现一门DSL语言（第三部分）：建立和验证语义模型【zt】 [回主站] [分站链接]

您的位置：首页 >> SoftHub关联区 >> 主题: [golang][新语言]手把手教你使用ANTLR和Go实现一门DSL语言（第三部分）：建立和验证语义模型【zt】 [最新] [回主站]

[golang][新语言]手把手教你使用ANTLR和Go实现一门DSL语言（第三部分）：建立和验证语义模型【zt】

clq

浏览(121) - 2024-06-04 18:33:54 发表编辑

关键字:

[2024-06-04 18:34:27 最后更新]
[golang][新语言]手把手教你使用ANTLR和Go实现一门DSL语言（第三部分）：建立和验证语义模型【zt】

https://blog.csdn.net/bigwhite20xx/article/details/125013317

--------------------------------------------------------

Dump基于树的遍历，提供了以前序(preOrder)、中序(inOrder)和后序(postOrder)遍历方式输出Tree的各个Node的特性。树的遍历是树的基本操作，以前序遍历为例，看看遍历的实现：

    // pre order traverse
    func preOrderTraverse(t *Node, level int, enterF func(*Node, int), exitF func(*Node, int)) {
        if t == nil {
            return
        }

        if enterF != nil {
            enterF(t, level) // traverse this node
        }

        // traverse left children
        preOrderTraverse(t.l, level+1, enterF, exitF)

        // traverse right children
        preOrderTraverse(t.r, level+1, enterF, exitF)

        if exitF != nil {
            exitF(t, level) // traverse this node again
        }
    }

这里借鉴了ANTLR语法解析树的“思路”，在遍历每个Node时都提供enterF和exitF的回调，用于用户自定义遍历Node时的行为。了解了原理后，我们看看基于下面逆波兰表达式：

speed,50,<,temperature,1,+,4,<,and,salinity,roundDown,600,<=,ph,roundUp,8.0,>,or,or

构建的Tree的样子如下：

    [root]( "root")
     |---[binop](or "binop")
          |---[binop](and "binop")
               |---[binop](< "binop")
                    |---[variable](speed "variable")
                    |---[literal](50 "literal")
               |---[binop](< "binop")
                    |---[binop](+ "binop")
                         |---[variable](temperature "variable")
                         |---[literal](1 "literal")
                    |---[literal](4 "literal")
          |---[binop](or "binop")
               |---[binop](<= "binop")
                    |---[unaryop](roundDown "unaryop")
                         |---[variable](salinity "variable")
                    |---[literal](600 "literal")
               |---[binop](> "binop")
                    |---[unaryop](roundUp "unaryop")
                         |---[variable](ph "variable")
                    |---[literal](8 "literal")

一旦Tree构建完毕，我们就可以基于该Tree进行求值了。下面是求值函数Evaluate的实现：

    func Evaluate(t Tree, m map[string]interface{}) (result bool, err error) {
        var s Stack[Value]

        defer func() {
            // extract error from panic
            if x := recover(); x != nil {
                result, err = false, fmt.Errorf("eval error: %v", x)
                return
            }
        }()

        var exitF = func(n *Node, level int) {
            if n == nil {
                return
            }

            if n.p == nil {
                // root node
                return
            }

            v := n.GetValue()
            switch v.Type() {
            case "binop":
                rhs, lhs := s.Pop(), s.Pop()
                s.Push(evalBinaryOpExpr(v.Value().(string), lhs, rhs))
            case "unaryop":
                lhs := s.Pop()
                s.Push(evalUnaryOpExpr(v.Value().(string), lhs))
            case "literal":
                s.Push(v)
            case "variable":
                name := v.Value().(string)
                value, ok := m[name]
                if !ok {
                    panic(fmt.Sprintf("not found variable: %s", name))
                }

                // use the value in map to replace variable
                s.Push(&Literal{
                    Val: value,
                })
            }
        }

        preOrderTraverse(t.(*Node), 0, nil, exitF)
        result = s.Pop().Value().(bool)
        return
    }

虽然这里用的是preOrderTraverse，但我们是在exitF回调中做的计算，因此这里等价于一个标准的树的后序遍历。每当遇到操作数，就入栈；当操作数为variable时，在输入参数中map中查找该variable是否存在，如存在，则将值压入栈。每当遇到操作符，则将操作数弹栈计算后，再入栈。如此，最终栈内仅保存一个值，就是这个表达式树的计算结果。
三. 验证语义模型之表达式树

前面说过，语义模型与语法树分离后，我们可以对语义模型进行单独测试，下面就是一个简单的基于表驱动的对表达式树的单元测试[11]：

    // tdat/semantic/semantic_test.go

    func TestNewFrom(t *testing.T) {
     //($speed < 50) and (($temperature + 1) < 4) or ((roundDown($salinity) <= 600.0) or (roundUp($ph) > 8.0))
     // speed,50,<,temperature,1,+,4,<,and,salinity,roundDown,600,<=,ph,roundUp,8.0,>,or,or
     var reversePolishExpr []Value

     reversePolishExpr = append(reversePolishExpr, newVariable("speed"))
     reversePolishExpr = append(reversePolishExpr, newLiteral(50))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("<"))
     reversePolishExpr = append(reversePolishExpr, newVariable("temperature"))
     reversePolishExpr = append(reversePolishExpr, newLiteral(1))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("+"))
     reversePolishExpr = append(reversePolishExpr, newLiteral(4))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("<"))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("and"))
     reversePolishExpr = append(reversePolishExpr, newVariable("salinity"))
     reversePolishExpr = append(reversePolishExpr, newUnaryOperator("roundDown"))
     reversePolishExpr = append(reversePolishExpr, newLiteral(600.0))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("<="))
     reversePolishExpr = append(reversePolishExpr, newVariable("ph"))
     reversePolishExpr = append(reversePolishExpr, newUnaryOperator("roundUp"))
     reversePolishExpr = append(reversePolishExpr, newLiteral(8.0))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator(">"))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("or"))
     reversePolishExpr = append(reversePolishExpr, newBinaryOperator("or"))

     tree := NewFrom(reversePolishExpr)
     Dump(tree, "preorder")

     // test table
     var cases = []struct {
      id       string
      m        map[string]interface{}
      expected bool
     }{
      //($speed < 50) and (($temperature + 1) < 4) or ((roundDown($salinity) <= 600.0) or (roundUp($ph) > 8.0))
      {
       id: "0001",
       m: map[string]interface{}{
        "speed":       30,
        "temperature": 6,
        "salinity":    700.0,
        "ph":          7.0,
       },
       expected: false,
      },
      {
       id: "0002",
       m: map[string]interface{}{
        "speed":       30,
        "temperature": 1,
        "salinity":    500.0,
        "ph":          7.0,
       },
       expected: true,
      },
      {
       id: "0003",
       m: map[string]interface{}{
        "speed":       60,
        "temperature": 10,
        "salinity":    700.0,
        "ph":          9.0,
       },
       expected: true,
      },
      {
       id: "0004",
       m: map[string]interface{}{
        "speed":       30,
        "temperature": 1,
        "salinity":    700.0,
        "ph":          9.0,
       },
       expected: true,
      },
     }

     for _, caze := range cases {
      r, err := Evaluate(tree, caze.m)
      if err != nil {
       t.Errorf("[case %s]: want nil, actual %s", caze.id, err.Error())
      }
      if r != caze.expected {
       t.Errorf("[case %s]: want %v, actual %v", caze.id, caze.expected, r)
      }
     }
    }

上面是语义模型中最复杂的部分，但不是全部，还有windowRange、enumableFunc以及result，下面我们就来建立tdat的完整的语义模型。
四. 建立完整的语义模型

前面我们已经解决掉了语义模型中最复杂的部分：conditionExpr。下面我们就把完整的语义模型实现出来，我们定义一个Model结构体来表示语义模型：

    // tdat/semantic/semantic.go

    type WindowsRange struct {
        low int
        high int
    }

    type Model struct {
        // conditionExpr
        t Tree

        // windowsRange
        wr WindowsRange

        // enumerableFunc
        ef string

        // result
        result []string
    }

我们看到Model本质上就是conditionExpr、WindowsRange、enumerableFunc和result这几个影响执行结果的元素的聚合，因此Model的创建函数也比较简单：

    func NewModel(reversePolishExpr []Value, wr WindowsRange, ef string, result []string) *Model {
        m := &Model{
            t:      NewFrom(reversePolishExpr),
            wr:     wr,
            ef:     ef,
            result: result,
        }
        return m
    }

我们重点看一下Model的语义执行方法Exec：

    // tdat/semantic/semantic.go

    func (m *Model) Exec(metrics []map[string]interface{}) (map[string]interface{}, error) {
     var res []bool
     for i := m.wr.low - 1; i <= m.wr.high-1; i++ {
      r, err := Evaluate(m.t, metrics[i])
      if err != nil {
       return nil, err
      }
      res = append(res, r)
     }

     andRes := res[0]
     orRes := res[0]

     for i := 1; i < len(res); i++ {
      andRes = andRes && res[i]
      orRes = orRes || res[i]
     }

     switch m.ef {
     case "any":
      if orRes {
       return m.outputResult(metrics[0])
      }
      return nil, ErrNotMeetAny
     case "none":
      if andRes == false {
       return m.outputResult(metrics[0])
      }
      return nil, ErrNotMeetNone
     case "each":
      if andRes == true {
       return m.outputResult(metrics[0])
      }
      return nil, ErrNotMeetEach
     default:
      return nil, ErrNotSupportFunc
     }
    }

这里的实现并非“性能最优”，但逻辑清晰：Exec会使用表达式树对迭代窗口(从low到high)中的每个元素进行求值，求值结果放入一个切片，然后再针对这个切片，求所有元素的逻辑与(andRes)与逻辑或(orRes)，再结合enumerableFunc的类型综合判断出是否要输出最新的那条metric。

关于Model的验证与表达式树差不多，限于篇幅这里就不赘述了，大家可以参考semantic_test.go中的测试case demo。
五. 小结

在这一部分内容中，我们为DSL建立了语义模型，tdat语义模型的核心是表达式树，因此我们重点讲了基于逆波兰式创建表达式树的方法、表达式树的求值方法以及表达式树的验证。最后，我们建立了一个名为semantic.Model的完整模型。

在下一篇文章中，我们将讲解如何基于DSL的语法树提取逆波兰式，并组装语义模型，把DSL的前后端串起来，让我们的语法示例可以真正run起来。

本文中涉及的代码可以在这里[12]下载 - https://github.com/bigwhite/experiments/tree/master/antlr/tdat 。

“Gopher部落”知识星球[13]旨在打造一个精品Go学习和进阶社群！高品质首发Go技术文章，“三天”首发阅读权，每年两期Go语言发展现状分析，每天提前1小时阅读到新鲜的Gopher日报，网课、技术专栏、图书内容前瞻，六小时内必答保证等满足你关于Go语言生态的所有需求！2022年，Gopher部落全面改版，将持续分享Go语言与Go应用领域的知识、技巧与实践，并增加诸多互动形式。欢迎大家加入！

5db159640dd5d1285f487be724d89e50.png

2008581b5bf3a08dd5200fce7226add8.png

11425866e3956e3e78fb1d753a3fded4.png

8f0d3d4d97f54952882a2b7602b86bee.png

Gopher Daily(Gopher每日新闻)归档仓库 - https://github.com/bigwhite/gopherdaily

我的联系方式：

    微博：https://weibo.com/bigwhite20xx

    博客：tonybai.com

    github: https://github.com/bigwhite

8b57994d4352c2732b2ee4620f89ec6d.png

商务合作方式：撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。
参考资料

[1]

编写了Tdat的文法: https://tonybai.com/2022/05/24/an-example-of-implement-dsl-using-antlr-and-go-part1
[2]

初步验证了文法的正确性: https://tonybai.com/2022/05/25/an-example-of-implement-dsl-using-antlr-and-go-part2
[3]

《领域特定语言》: https://book.douban.com/subject/21964984
[4]

《使用ANTLR和Go实现DSL入门》: https://tonybai.com/2022/05/10/introduction-of-implement-dsl-using-antlr-and-go
[5]

csv2map: https://github.com/bigwhite/experiments/tree/master/antlr/csv2map
[6]

这篇文章: https://blog.gopheracademy.com/advent-2017/parsing-with-antlr4-and-go/
[7]

binary expression tree: http://en.wikipedia.org/wiki/Binary_expression_tree
[8]

第一篇文章: https://tonybai.com/2022/05/24/an-example-of-implement-dsl-using-antlr-and-go-part1
[9]

逆波兰表达式(Reverse Polish notation): http://en.wikipedia.org/wiki/Reverse_Polish_notation
[10]

《数据结构与算法分析：C语言描述（原书第2版》: https://book.douban.com/subject/33419792/
[11]

基于表驱动的对表达式树的单元测试: https://www.imooc.com/read/87/article/2437
[12]

这里: https://github.com/bigwhite/experiments/tree/master/antlr/tdat
[13]

“Gopher部落”知识星球: https://wx.zsxq.com/dweb2/index/group/51284458844544
————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/bigwhite20xx/article/details/125013317

总数：0　页次：1/0　首页尾页　　

所在合集/目录

新语言更多

发表评论:

本帖子属于以下条目()

NEWBT官方QQ群1: 276678893
可求档连环画,漫画;询问文本处理大师等软件使用技巧;求档softhub软件下载及使用技巧.
但不可"开车",严禁国家敏感话题,不可求档涉及版权的文档软件.
验证问题说明申请入群原因即可.