[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
本帖子属于以下条目()
NEWBT官方QQ群1: 276678893
可求档连环画,漫画;询问文本处理大师等软件使用技巧;求档softhub软件下载及使用技巧.
但不可"开车",严禁国家敏感话题,不可求档涉及版权的文档软件.
验证问题说明申请入群原因即可.