手把手教你使用ANTLR和Go实现一门DSL语言(第三部分):建立和验证语义模型

本文永久链接 – https://tonybai.com/2022/05/27/an-example-of-implement-dsl-using-antlr-and-go-part3

在前面的系列文章中,我们为气象学家们设计了一门名为Tdat的DSL,使用ANTLR的文法规则编写了Tdat的文法,基于该文法生成了Tdat的语法解析器代码并初步验证了文法的正确性,Tdat可以成功将我们编写的Tdat语法代码样例解析为一颗内存中的树结构。

此时此刻,我们编写的DSL语法代码还无法按预期工作,因为缺少执行语义。在这篇文章中,我们就来为这门DSL建立语义模型,并单独对这个语义模型进行验证。

让我们的语法示例能真正按预期run起来!

一. 什么是语义模型

通过前面的文章,我们了解到:文法只是形式化了DSL的语法结构,即在语法树中是如何表现的,而这一切与语义无关。而所谓语义,就是当用这个语法写的代码执行时,它会做什么

相同的语法,即便生成相同的语法树,那么由于对语法树的解释方法不同,语义就会不同。下面是Martin Fowler在其《领域特定语言》一书中的一个例子:

我们看到对同一语法写成的代码:5+3,如果语义模型不同,那么执行结果就不会相同:如果按加法语义解释语法树,我们得到的代码执行结果为8;如果按连接语义解释语法树,我们得到的代码执行结果为53。

那么语义模型究竟表现为何种形式呢?通常来说语义模型也是内存中的一个或一些特定的数据结构,这个数据结构存在的目的就是表述语义,对语句的执行逻辑进行制导

比如:《使用ANTLR和Go实现DSL入门》一文中的那个csv2map例子,其语义模型就存储在CSVMapListener这个结构体中的一个map结构(见下面的cm字段)和切片结构(见下面的headers)中了:

// github.com/bigwhite/experiments/tree/master/antlr/csv2map/csv_listener.go

type CSVMapListener struct {
    *parser.BaseCSVListener
    headers []string
    cm      []map[string]string
    fields  []string // a slice of fields in current row
}

csv2map通过遍历生成的语法树提取信息填充构造了cm和headers这两个字段,后续的代码执行都是基于这两个字段中存储的信息。

到这里有童鞋可能会问:是不是对所有DSL都要单独提取和组装一个语义模型出来呢?至少Martin Fowler建议这么做,这样做的最大好处就是将语法解析与语义执行这两个阶段解耦,然后语义模型可以单独拿出来测试与验证,无需依赖语法解析过程。

我个人觉得对于稍大一些的non-trivial的DSL来说,将语义模型分离出来还是很必要的,否则语义执行与语法解析的耦合会让DSL的实现难于理解、难于维护,同样也难于测试验证。

对于一些简单的DSL来说,其语法树自身就可以看作是一个语义模型,在这样的情况下,语法树的遍历过程将伴随着语句语义的执行,下面就是一个典型的以语法树为语义执行模型的例子(改编自这篇文章中的例子),例子文法如下:

// Calc.g4
grammar Calc;

// Rules
start : expression EOF;

expression
   : expression op=('*'|'/') expression # MulDiv
   | expression op=('+'|'-') expression # AddSub
   | NUMBER                             # Number
   ;

// Tokens
MUL: '*';
DIV: '/';
ADD: '+';
SUB: '-';
NUMBER: [0-9]+;
WHITESPACE: [ \r\n\t]+ -> skip;

基于该文法生成Parser代码后,我们实现一个语法树的Listener:

// calc/calc_listener_impl.go

type calcListener struct {
    *parser.BaseCalcListener
    stack []int
}

... ...

func (l *calcListener) ExitMulDiv(c *parser.MulDivContext) {
    right, left := l.pop(), l.pop()

    switch c.GetOp().GetTokenType() {
    case parser.CalcParserMUL:
        l.push(left * right)
    case parser.CalcParserDIV:
        l.push(left / right)
    default:
        panic(fmt.Sprintf("unexpected op: %s", c.GetOp().GetText()))
    }
}

func (l *calcListener) ExitAddSub(c *parser.AddSubContext) {
    right, left := l.pop(), l.pop()

    switch c.GetOp().GetTokenType() {
    case parser.CalcParserADD:
        l.push(left + right)
    case parser.CalcParserSUB:
        l.push(left - right)
    default:
        panic(fmt.Sprintf("unexpected op: %s", c.GetOp().GetText()))
    }
}

func (l *calcListener) ExitNumber(c *parser.NumberContext) {
    i, err := strconv.Atoi(c.GetText())
    if err != nil {
        panic(err.Error())
    }

    l.push(i)
}

这段代码直接将Parser建立的语法树当成了二叉表达式树(binary expression tree,叶子节点是操作数,其他节点为操作符)了,然后通过表达式树求值算法(借由一个stack)实现代码的求值语义,看下面驱动求值的main函数代码:

// calc/main.go

// calc takes a string expression and returns the evaluated result.
func calc(input string) int {
    // Setup the input
    is := antlr.NewInputStream(input)

    // Create the Lexer
    lexer := parser.NewCalcLexer(is)
    stream := antlr.NewCommonTokenStream(lexer, antlr.TokenDefaultChannel)

    // Create the Parser
    p := parser.NewCalcParser(stream)

    // Finally parse the expression (by walking the tree)
    var listener calcListener
    antlr.ParseTreeWalkerDefault.Walk(&listener, p.Start())

    return listener.pop()
}

func main() {
    println(calc("1 + 2 * 3"))  // 7
    println(calc("12 * 3 / 6")) // 6
}

通过上述代码,我们可以很清晰地看到这个例子直接将源码解析后建立的语法树作为语义模型了,这就让语义模型与解析后的语法树的结构产生了紧耦合,一旦语法变更,语法树结构发生变化,就会直接影响语义模型的执行,语义模型的实现也要随之变更。

针对我们自己的tdat DSL,我们将采用语义模型与语法树分离的方式。下面我们就来看看tdat的语义模型。

二. 语义模型之表达式树

在本系列的第一篇文章中,我们介绍了Tdat这门DSL的语义特性,我们的语义模型就是要实现这些语义特性。我们回顾一下tdat文法中的核心产生式规则ruleLine:

ruleLine
    : ruleID ':' enumerableFunc '{' windowsRange conditionExpr '}' '=>' result ';'
    ;

在这个产生式规则中,影响语义计算的主要规则包括:conditionExpr、windowRange、enumableFunc和result上,而最复杂的又在conditionExpr这个规则上。这个规则本质上就是一组一元、算术、比较和逻辑表达式的混合计算,

那么,我们能否像上面calc那个例子那样将语法树直接用作语义模型呢?实现层面上是可以的。我们以下面这个复杂一些的conditionExpr表达式为例:

(($speed < 5) and (($temperature + 1) < 10)) or ((roundDown($speed) <= 10.0) and (roundUp($salinity) >= 500.0))

我们来对比一下直接将语法树作为语义模型与使用表达式树结构作为语义模型的差别:

通过上图,我们看到,语法树是为了解析语法而构建的,并非为表达式树计算而构建,如果我们直接基于语法树去做语义计算,一来要多遍历一些无关的符号节点(非红圈里的节点),有额外开销,影响性能;二来这里的tdat使用的conditionExpr并非标准二叉表达式树,我们需要自己设计表达式求值的算法;最后就是Martin Fowler提到的语法解析与语义模型耦合在一起的弊端了。在语义模型不变的情况下,一旦语法结构发生变更,影响的不仅仅是语法树的结构,语义模型的求值行为也要一并改动。

因此这里我们直接将语义模型与语法树分离,我们采用上图中下方的二叉表达式树作为主要语义模型。这样我们就可以单独建立实现和测试该语义模型了。

像上图下方那样的一个典型的二叉表达式树可由一个逆波兰表达式(Reverse Polish notation)构建而成,构建算法可以参考《数据结构与算法分析:C语言描述(原书第2版》的4.2.2小节。

下面我就来简单说说这个表达式树的构建与求值实现。

我们先来建立一个二叉Tree数据结构:

// tdat/semantic/semantic.go

// semantic tree
type Tree interface {
    GetParent() Tree
    SetParent(Tree)
    GetValue() Value
    SetLeftChild(Tree) Tree
    GetLeftChild() Tree
    SetRightChild(Tree) Tree
    GetRightChild() Tree
}

type Value interface {
    Type() string
    Value() interface{}
}

// Node is an implementation of Tree
// and each node can be seen as a tree
type Node struct {
    V Value
    l *Node // left node
    r *Node // right node
    p *Node // parent node
}

我们建立了一个二叉树的接口类型,并提供了用于实现该接口类型的结构体类型Node。每个Node是Tree中的一个节点,它自身也可以被看成是一个Tree。树中每个Node都有一个Value,Value也是一个接口类型,它共有四种实现:

  • BinaryOperator

二元运算符,包括:二元算术运算符(+、-、*、/、%等)、关系运算符(>、<、>=、<=、==等)和二元逻辑运算符(and与or)。

  • UnaryOperator

一元运算符/内置函数,包括:roundUp、roundDown、abs等,可扩展。

  • Variable

用于表示数据指标,比如:speed、temperature等。

  • Literal

字面值,比如:10、3.1415、”hello”,通常做右值,或与Varible通过二元算术运算符构成表达式。

BinaryOperator和UnaryOperator都属于操作符,而Variable和Literal都属于操作数。这样,一个表达式树就是以操作数为叶子节点,以操作符为其他节点的树。由于树最多是二元操作符,所以表达式树正好是一个二叉树,一元运算符的操作数默认放置在左子节点处。

上面提到过,我们可以基于逆波兰表达式来构建出这样的一棵表达式树,下面就是基于逆波兰表达式构建这棵Tree的实现:

// semantic/semantic.go

// construct a tree based on a reversePolishExpr
func NewFrom(reversePolishExpr []Value) Tree {
    var s Stack[Tree]
    for _, v := range reversePolishExpr {
        switch v.Type() {
        case "literal", "variable":
            s.Push(&Node{
                V: v,
            })
        case "binop":
            rchild, lchild := s.Pop(), s.Pop()
            n := &Node{
                V: v,
            }
            n.SetLeftChild(lchild)
            n.SetRightChild(rchild)
            s.Push(n)
        case "unaryop":
            lchild := s.Pop()
            n := &Node{
                V: v,
            }
            n.SetLeftChild(lchild)
            s.Push(n)
        }

    }
    first := s.Pop()
    root := &Node{}
    root.SetLeftChild(first)
    return root
}

在这份实现中,我们借由一个stack缓存子树结点。我们从左向右逐一读取逆波兰表达式中的操作符或操作数:

  • 如果读出来的Value是操作数(literal或variable),则将该操作数打包成一个Node(可理解为子树),压到栈中;
  • 如果读出来的Value是一个二元操作符,则将从栈中出栈两个节点,分别作为二元操作符节点的左右节点,合并后的子树再压到栈中;
  • 如果读出来的Value是一个一元操作符,则从栈中弹出一个节点,作为一元操作符节点的左节点,合并后的子树再压到栈中。
  • 栈中最后存放的就是树的最顶层操作符节点,将该节点弹出后作为Root节点的左子节点,表达式树的构造就结束了。而这个Root节点与众不同的特征是其parent为nil(遍历树时会用到)。

构建后的这棵Tree究竟长啥样呢?我们可以通过Dump函数来查看:

func printPrefix(level int) {
    for i := 0; i < level; i++ {
        if i == level-1 {
            fmt.Printf(" |---")
        } else {
            fmt.Printf("     ")
        }
    }
}

func Dump(t Tree, order string) {
    var f = func(n *Node, level int) {
        if n == nil {
            return
        }

        printPrefix(level)

        if n.p == nil {
            // root node
            fmt.Printf("[root]()\n")
        } else {
            fmt.Printf("[%s](%v)\n", n.V.Type(), n.V.Value())
        }
    }

    switch order {
    default:
        // preorder
        preOrderTraverse(t.(*Node), 0, f, nil)
    case "inorder":
        inOrderTraverse(t.(*Node), 0, f, nil)
    case "postorder":
        postOrderTraverse(t.(*Node), 0, f, nil)
    }
}

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

一旦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是否存在,如存在,则将值压入栈。每当遇到操作符,则将操作数弹栈计算后,再入栈。如此,最终栈内仅保存一个值,就是这个表达式树的计算结果。

三. 验证语义模型之表达式树

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

// 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起来。

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


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

img{512x368}
img{512x368}

img{512x368}

我爱发短信:企业级短信平台定制开发专家 https://tonybai.com/。smspush : 可部署在企业内部的定制化短信平台,三网覆盖,不惧大并发接入,可定制扩展; 短信内容你来定,不再受约束, 接口丰富,支持长短信,签名可选。2020年4月8日,中国三大电信运营商联合发布《5G消息白皮书》,51短信平台也会全新升级到“51商用消息平台”,全面支持5G RCS消息。

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

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

我的联系方式:

  • 微博:https://weibo.com/bigwhite20xx
  • 微信公众号:iamtonybai
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • “Gopher部落”知识星球:https://public.zsxq.com/groups/51284458844544

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

手把手教你使用ANTLR和Go实现一门DSL语言(第二部分):文法验证

本文永久链接 – https://tonybai.com/2022/05/25/an-example-of-implement-dsl-using-antlr-and-go-part2

在本系列的第一篇文章《手把手教你使用ANTLR和Go实现一门DSL语言:设计DSL语法与文法》中,我们已经为气象学家们设计了一门DSL,建立了语法样例,并用ANTLR4文法将DSL定义了出来。按照外部DSL设计与实现的工作流,在这一篇中,我们将对上一篇设计的DSL文法进行验证,看看ANTLR基于我们设计的文法是否能成功生成解析器代码,并且基于生成的解析器是否可以成功处理我们编写的语法样例。

ANTLR文法验证可分为两个阶段,我们分别来看一下。

一. 验证ANTLR是否能解析我们定义的文法(Tdat.g4)

验证ANTLR是否能解析我们的文法Tdat.g4的过程也是通过antlr4尝试生成DSL语法解析器代码的过程,如果顺利生成目标代码,没有报错,则说明我们的Tdat.g4文法至少是符合ANTLR4对文法的要求的。一旦成功,ANTLR就会在特定目录下生成你期望的语法的解析器(parser)代码,比如下面命令将Tdat.g4文法生成目标代码为Go的解析器实现,生成的Go代码位于当前目录下的parser目录下。

$antlr4 -Dlanguage=Go -o parser Tdat.g4

在这个过程中,除了语法错误(比如没用分号结尾,缺少冒号等),我们常会遇到两类错误。

一类是Parser rule的间接左递归问题,比如下面这个例子:

// Demo2.g4
grammar Demo2;

expr1 : expr2;
expr2 : expr1 '+' expr3
      | '(' expr2 ')'
      ;
expr3 : INT;

INT: DIGIT+;

DIGIT: [0-9];

使用antlr基于上面Demo2.g4生成parser代码,我们会得到下面错误提示:

$antlr4 -Dlanguage=Go -o parser Demo2.g4
error(119): Demo2.g4::: The following sets of rules are mutually left-recursive [expr1, expr2]

以Demo2.g4为例,所谓“间接左递归”,就是expr1产生式中包含expr2,而expr2的产生式规则中又包含了expr1,这种情况Antlr是无法处理的。那么我们需要消除这种“间接左递归”,最直接的方法就是将文法改为“直接左递归”,如下面改后的文法:

grammar Demo2;

expr1 : expr1 '+' expr3
      | '(' expr1 ')'
      ;
expr3 : INT;

INT: DIGIT+;

DIGIT: [0-9];

这里把expr2这一中间rule去掉了!expr1的产生式中直接包含自己,这种直接左递归是antlr可以支持的。

另一类是词法规则生成式相同导致的归约歧义。这里antlr不会给出error,而会以warning形式提醒开发者。比如下面例子:

grammar Demo1;

prog: expr
    | expr1
    ;

expr: DIGIT AND DIGIT;

expr1: DIGIT MASK DIGIT;

AND : '&' ;

MASK : '&' ;

DIGIT: [0-9];

antlr处理这个文法时,会提示如下warning:

warning(184): Demo1.g4:14:0: One of the token MASK values unreachable. & is always overlapped by token AND

意思是MASK这个词法规则总是会被AND这个词法规则所遮蔽,或者说通过这个文法总是能识别到expr,而无法识别并归约到expr1这个规则。这个问题与具体文法设计相关,解决方法可参考ANTLR提供的词法规则说明

不过,即便基于你的文法成功生成Parser代码,也不代表你的文法没有逻辑错误。我们需要通过一些语法样例来验证生成的Parser是否能正确解析我们的语法样例。

二. 验证生成的Parser代码是否能正确解析我们的语法样例

第二阶段的验证有两种方法,最简单的就是使用antlr提供的工具grun。这里我将grun的相关命令打包到一个Makefile中:

// Makefile for debugging Tdat.g4
antlr4_exe = java -jar /usr/local/lib/antlr-4.10.1-complete.jar
grun_exe = java org.antlr.v4.gui.TestRig
target =

all:
    go build

gen:
    $(antlr4_exe) -Dlanguage=Go -o parser Tdat.g4

gen_visitor:
    $(antlr4_exe) -Dlanguage=Go -visitor -o parser Tdat.g4

gen_java:
    $(antlr4_exe) Tdat.g4

gui: gen_java
    javac *.java
    $(grun_exe) Tdat prog $(target) -gui

trace: gen_java
    javac *.java
    $(grun_exe) Tdat prog $(target) -trace

tokens: gen_java
    javac *.java
    $(grun_exe) Tdat prog $(target) -tokens

tree: gen_java
    javac *.java
    $(grun_exe) Tdat prog $(target) -tree

clean:
    rm -fr *.java *.class tdat

由于grun依赖于基于Tdat.g4生成的java parser代码,所以每个调试命令,如debug、trace、tokens等都需要依赖对应的Java的代码生成。

对于同归属于视觉动物的人类来说,我推荐你先使用图形化选项(gui)对语法样例的解析进行调试,我们以下面的最简单的samples/sample1.t为例:

// samples/sample1.t

r0001: Each { || $speed > 30 } => ("speed", "temperature", "salinity");

我们执行下面命令:

$make gui target=samples/sample1.t
java -jar /usr/local/lib/antlr-4.10.1-complete.jar Tdat.g4
javac *.java
java org.antlr.v4.gui.TestRig Tdat prog samples/sample1.t -gui
... ...

上述命令会打开一个新窗口,显示解析后的语法树:

很幸运!基于Tdat.g4文法生成的Parser可以正确解析sample1.t。

某些时候我们需要查看字符序列被解析为词法元素token的过程,以验证字符序列是否都被正确识别,我们可以通过make tokens来实现:

$make tokens target=samples/sample1.t
java -jar /usr/local/lib/antlr-4.10.1-complete.jar Tdat.g4
javac *.java
java org.antlr.v4.gui.TestRig Tdat prog samples/sample1.t -tokens
[@0,12:16='r0001',<ID>,3:0]
[@1,17:17=':',<':'>,3:5]
[@2,19:22='Each',<'Each'>,3:7]
[@3,24:24='{',<'{'>,3:12]
[@4,26:26='|',<'|'>,3:14]
[@5,27:27='|',<'|'>,3:15]
[@6,29:34='$speed',<METRIC>,3:17]
[@7,36:36='>',<'>'>,3:24]
[@8,38:39='30',<INT>,3:26]
[@9,41:41='}',<'}'>,3:29]
[@10,43:44='=>',<'=>'>,3:31]
[@11,46:46='(',<'('>,3:34]
[@12,47:53='"speed"',<STRING>,3:35]
[@13,54:54=',',<','>,3:42]
[@14,56:68='"temperature"',<STRING>,3:44]
[@15,69:69=',',<','>,3:57]
[@16,71:80='"salinity"',<STRING>,3:59]
[@17,81:81=')',<')'>,3:69]
[@18,82:82=';',<';'>,3:70]
[@19,84:83='<EOF>',<EOF>,4:0]

通过上述的每一行,我们都可以看到一个token被解析出来,匹配的是哪条词法规则。以第一行为例:”r0001″被解析出来,成功匹配ID这个token规则。

如果要结合parser规则一并查看匹配规则的步骤,可以用trace命令,通过这个命令的详细输出我们可以对parser规则匹配异常的情况进行诊断:

$make trace target=samples/sample1.t
java -jar /usr/local/lib/antlr-4.10.1-complete.jar Tdat.g4
javac *.java
java org.antlr.v4.gui.TestRig Tdat prog samples/sample1.t -trace
enter   prog, LT(1)=r0001
enter   ruleLine, LT(1)=r0001
enter   ruleID, LT(1)=r0001
consume [@0,12:16='r0001',<33>,3:0] rule ruleID
exit    ruleID, LT(1)=:
consume [@1,17:17=':',<1>,3:5] rule ruleLine
enter   enumerableFunc, LT(1)=Each
consume [@2,19:22='Each',<6>,3:7] rule enumerableFunc
exit    enumerableFunc, LT(1)={
consume [@3,24:24='{',<2>,3:12] rule ruleLine
enter   windowsRange, LT(1)=|
consume [@4,26:26='|',<9>,3:14] rule windowsRange
consume [@5,27:27='|',<9>,3:15] rule windowsRange
exit    windowsRange, LT(1)=$speed
enter   conditionExpr, LT(1)=$speed
enter   primaryExpr, LT(1)=$speed
consume [@6,29:34='$speed',<34>,3:17] rule primaryExpr
exit    primaryExpr, LT(1)=>
enter   comparisonOp, LT(1)=>
consume [@7,36:36='>',<24>,3:24] rule comparisonOp
exit    comparisonOp, LT(1)=30
enter   primaryExpr, LT(1)=30
enter   literal, LT(1)=30
consume [@8,38:39='30',<35>,3:26] rule literal
exit    literal, LT(1)=}
exit    primaryExpr, LT(1)=}
exit    conditionExpr, LT(1)=}
consume [@9,41:41='}',<3>,3:29] rule ruleLine
consume [@10,43:44='=>',<4>,3:31] rule ruleLine
enter   result, LT(1)=(
consume [@11,46:46='(',<11>,3:34] rule result
consume [@12,47:53='"speed"',<37>,3:35] rule result
consume [@13,54:54=',',<10>,3:42] rule result
consume [@14,56:68='"temperature"',<37>,3:44] rule result
consume [@15,69:69=',',<10>,3:57] rule result
consume [@16,71:80='"salinity"',<37>,3:59] rule result
consume [@17,81:81=')',<12>,3:69] rule result
exit    result, LT(1)=;
consume [@18,82:82=';',<5>,3:70] rule ruleLine
exit    ruleLine, LT(1)=<EOF>
exit    prog, LT(1)=<EOF>

上面这个r0001的逻辑比较简单,我们再来一个复杂的:

//samples/sample2.t

r0002: None { |,30| $temperature > 5 } => ("speed", "temperature", "salinity");
r0005: Each { |,| (($speed < 5) and (($temperature + 1) < 10)) or ((roundDown($speed) <= 10) and (roundUp($salinity) >= 500))} => ();

我们用gui形式输出语法树:

我们看到,虽然sample2.t中的源码逻辑变复杂了,但我们生成的Parser依旧可以成功将其解析为语法树。

如果你觉得grun提供的这些工具的输出都不符合你的胃口,那么好吧,你可以自己动手基于Listener方式自己写你的调试工具,最简单的逻辑:我们遍历一遍Parser生成的语法树,看看语法树每个节点是否符合我们的预期。

Antlr的Go runtime提供了一个TraceListener的结构,从名字上来看似乎是可以遍历语法树,对Node做trace的。但试用后发现总出panic,不知道是不是用法的问题。

不过自己写一个也不麻烦,我们建立一个trace_listener.go,这个listener将遍历语法树所有节点并按我们期望的格式输出相关信息:

package main

import (
    "fmt"
    "tdat/parser"

    "github.com/antlr/antlr4/runtime/Go/antlr"
)

type TraceListener struct {
    *parser.BaseTdatListener
    p *parser.TdatParser
    t antlr.Tree
}

func NewTraceListener(p *parser.TdatParser, t antlr.Tree) *TraceListener {
    return &TraceListener{
        p: p,
        t: t,
    }
}

func (l *TraceListener) EnterEveryRule(ctx antlr.ParserRuleContext) {
    printLevelPrefix(ctx)
    i := ctx.GetRuleIndex()
    ruleName := l.p.RuleNames[i]
    fmt.Printf("==> %s 《 %s 》\n", ruleName, ctx.GetText())
}

func (l *TraceListener) ExitEveryRule(ctx antlr.ParserRuleContext) {
    printLevelPrefix(ctx)
    i := ctx.GetRuleIndex()
    ruleName := l.p.RuleNames[i]
    fmt.Println("<==", ruleName)
}

antlr的listener默认对语法树进行前序遍历,antlr go runtime中的ParseTreeListener接口包含EnterEveryRule和ExitEveryRule两个方法:

type ParseTreeListener interface {
    VisitTerminal(node TerminalNode)
    VisitErrorNode(node ErrorNode)
    EnterEveryRule(ctx ParserRuleContext)
    ExitEveryRule(ctx ParserRuleContext)
}

在遍历过程中,这两个方法分别会在进入某节点以及结束遍历某节点时被调用,我们可以在我们的Listener接口实现中重写这两个方法来提取遍历的树的所有节点的信息。

现在我们提供一个main函数来驱动这个调试过程:

func main() {
    println("input file:", os.Args[1])
    input, err := antlr.NewFileStream(os.Args[1])
    if err != nil {
        panic(err)
    }

    lexer := parser.NewTdatLexer(input)
    stream := antlr.NewCommonTokenStream(lexer, 0)
    p := parser.NewTdatParser(stream)
    tree := p.Prog()
    antlr.ParseTreeWalkerDefault.Walk(NewTraceListener(p, tree), tree)
}

编译运行上面程序:

$make
go build

$./tdat samples/sample1.t 

input file: samples/sample1.t
==> prog 《 r0001:Each{||$speed>30}=>("speed","temperature","salinity"); 》
    ==> ruleLine 《 r0001:Each{||$speed>30}=>("speed","temperature","salinity"); 》
        ==> ruleID 《 r0001 》
        <== ruleID
        ==> enumerableFunc 《 Each 》
        <== enumerableFunc
        ==> windowsRange 《 || 》
        <== windowsRange
        ==> conditionExpr 《 $speed>30 》
            ==> primaryExpr 《 $speed 》
            <== primaryExpr
            ==> comparisonOp 《 > 》
            <== comparisonOp
            ==> primaryExpr 《 30 》
                ==> literal 《 30 》
                <== literal
            <== primaryExpr
        <== conditionExpr
        ==> result 《 ("speed","temperature","salinity") 》
        <== result
    <== ruleLine
<== prog

这里我用了一种带缩进的格式来查看整个遍历过程以及遍历的每个节点的信息,如果你有你期望输出的格式,可以修改上面的EnterEveryRule和ExitEveryRule方法的实现,总之,怎么方便怎么高效就怎么来!

一些童鞋会问,文法确定了,语法确定了,Parser也可以成功生成,那么还会有解析错误的情况么?这个肯定是有的,笔者在开发的过程中就遇到因词法规则顺序的问题导致语法规则匹配错误的情况,下面就是一个例子:

// Demo.g4
grammar Demo;

prog
    : prule1
    | prule2
    ;

prule1
    : 'repeat' INT
    ;

prule2
    : 'repeat' NONZEROINT
    ;

NONZEROINT
    : [1-9](DIGIT)*
    ;

INT
    : DIGIT+
    ;

fragment
DIGIT
    : [0-9]  // match single digit
    ;

LINE_COMMENT
    : '//' .*? '\r'? '\n' -> skip
    ;

COMMENT
    : '/*' .*? '*/' -> skip
    ;

WS
    : [ \t\r\n]+ -> skip
    ;

我们用下面语法测试基于上面Demo.g4生成的Parser:

//sample1.t
repeat 15

我们期望其匹配到的规则为prule1,但实际情况是:

grun -gui的输出结果是Parser匹配到了prule2!这是怎么回事呢?我们用grun -tokens再来看看词法规则匹配的情况:

 $grun Demo prog samples/sample1.t -tokens
[@0,1:6='repeat',<'repeat'>,2:0]
[@1,8:9='15',<NONZEROINT>,2:7]
[@2,11:10='<EOF>',<EOF>,3:0]

我们发现15这个数字匹配到了NONZEROINT这个词法规则,而不是INT。这是因为ANTLR默认优先匹配排在前面的词法规则。于是在parser规则层面匹配到prule2就不足为奇了。

这只是一个“故意制造”的例子,即便不用Parser,我们也能“肉眼”识别文法中的问题。但在真实的复杂的语法解析器验证时,这样的未按预期匹配的情况也是很常见的,而且是肉眼难于分辨的,我们需要利用grun提供的工具去仔细诊断。

三. 小结

在这一篇中,我们通过ANTLR提供的工具对编写的文法规则进行了验证,并进一步验证了基于该文法生成的Parser是否可以解析我们设计的所有语法样例。

好了,现在我们已经可以成功将语法样例解析并转换为内存中的一颗语法树了?那么有了这棵树后,我们怎么实现需求中的表达式求值、指标计算与输出呢?

在下一篇文章中,我将和大家一起学习如何从语法树中提取我们的语义模型,并对语义模型进行测试验证。

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


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

img{512x368}
img{512x368}

img{512x368}
img{512x368}

我爱发短信:企业级短信平台定制开发专家 https://tonybai.com/。smspush : 可部署在企业内部的定制化短信平台,三网覆盖,不惧大并发接入,可定制扩展; 短信内容你来定,不再受约束, 接口丰富,支持长短信,签名可选。2020年4月8日,中国三大电信运营商联合发布《5G消息白皮书》,51短信平台也会全新升级到“51商用消息平台”,全面支持5G RCS消息。

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

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

我的联系方式:

  • 微博:https://weibo.com/bigwhite20xx
  • 微信公众号:iamtonybai
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • “Gopher部落”知识星球:https://public.zsxq.com/groups/51284458844544

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

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats