如何实现一个BNF语法树来解析GO中的输入？

Question

类型语言的语法如下:

TYPE ::= TYPEVAR | PRIMITIVE_TYPE | FUNCTYPE | LISTTYPE;
PRIMITIVE_TYPE ::= ‘int’ | ‘float’ | ‘long’ | ‘string’;
TYPEVAR ::= ‘`’ VARNAME; // Note, the character is a backwards apostrophe!
VARNAME ::= [a-zA-Z][a-zA-Z0-9]*; // Initial letter, then can have numbers
FUNCTYPE ::= ‘(‘ ARGLIST ‘)’ -> TYPE | ‘(‘ ‘)’ -> TYPE;
ARGLIST ::= TYPE ‘,’ ARGLIST | TYPE;
LISTTYPE ::= ‘[‘ TYPE ‘]’;

我的输入如下:TYPE

例如,如果我输入(int,int) - > float,这是有效的.如果我输入([int],int),则它是错误的类型并且无效.

我需要从键盘解析输入并确定它是否在此语法下有效(以后的类型推断).但是,我不知道如何使用go构建此语法以及如何解析每个字节的输入.是否有任何暗示或类似的实施？这将是非常有帮助的.

Answer 1

出于您的目的,类型的语法看起来很简单,您应该能够编写一个与语法形状大致匹配的递归下降解析器.

举一个具体的例子,假设我们正在认识一种类似的语言.

TYPE ::= PRIMITIVETYPE | TUPLETYPE
PRIMITIVETYPE ::= 'int'
TUPLETYPE ::= '(' ARGLIST ')'
ARGLIST ::= TYPE ARGLIST | TYPE

与原始问题不完全相同,但您应该能够看到相似之处.

递归下降解析器由每个生产规则的函数组成.

func ParseType(???) error {
    ???
}

func ParsePrimitiveType(???) error {
    ???
}

func ParseTupleType(???) error {
    ???
}

func ParseArgList(???) error {
    ???
}

在那里,我们将表示事情,我们不太知道该用什么作为？？？*,直到我们到达那里.我们至少会说,error如果我们无法解析,我们会得到一个.

每个函数的输入都是一些令牌流.在我们的例子中,这些令牌由以下序列组成:

 "int"
 "("
 ")"

我们可以想象一个Stream可能满足的东西:

type Stream interface {
    Peek() string  // peek at next token, stay where we are
    Next() string  // pick next token, move forward
}

让我们顺序遍历令牌流.

一个词法分析器负责采取类似的字符串或io.Reader和生产字符串标记此流.Lexer很容易编写:你可以想象只使用正则表达式或类似的东西将字符串分解为标记.

假设我们有一个令牌流,那么解析器只需要处理该流和一组非常有限的可能性.如前所述,每个生产规则对应于解析功能.在生产规则中,每个备选方案都是条件分支.如果语法特别简单(就像你的那样!),我们可以找出要采用的条件分支.

例如,让我们来看看TYPE它及其相应的ParseType功能:

TYPE ::= PRIMITIVETYPE | TUPLETYPE
PRIMITIVETYPE ::= 'int'
TUPLETYPE ::= '(' ARGLIST ')'

这怎么可能对应于ParseType？的定义？

制作说有两种可能性:它可以是(1)原始的,或(2)元组.我们可以查看令牌流:如果我们看到"int",那么我们知道它是原始的.如果我们看到a "(",那么因为唯一的可能性是它是元组类型,我们可以调用tupletype解析器函数并让它做脏工作.

重要的是要注意:如果我们看不到一个"("也不一个"int",那么可怕的东西出了问题!我们只是通过查看语法来了解这一点.我们可以看到每个类型都必须从FIRST开始解析,从这两个标记中的一个开始.

好吧,让我们编写代码.

func ParseType(s Stream) error {
    peeked := s.Peek()
    if peeked == "int" {
        return ParsePrimitiveType(s)
    }
    if peeked == "(" {
        return ParseTupleType(s)
    }
    return fmt.Errorf("ParseType on %#v", peeked)
}

解析PRIMITIVETYPE和TUPLETYPE同样直接.

func ParsePrimitiveType(s Stream) error {
    next := s.Next()
    if next == "int" {
        return nil
    }
    return fmt.Errorf("ParsePrimitiveType on %#v", next)
}

func ParseTupleType(s Stream) error {
    lparen := s.Next()
    if lparen != "(" {
        return fmt.Errorf("ParseTupleType on %#v", lparen)
    }

    err := ParseArgList(s)
    if err != nil {
        return err
    }

    rparen := s.Next()
    if rparen != ")" {
        return fmt.Errorf("ParseTupleType on %#v", rparen)
    }

    return nil
}

唯一可能导致某些问题的是参数列表的解析器.让我们来看看规则.

ARGLIST ::= TYPE ARGLIST | TYPE

如果我们尝试编写函数ParseArgList,我们可能会卡住,因为我们还不知道要做出哪个选择.我们选择第一个还是第二个选择？

好吧,让我们至少解析出两种选择共同的部分:TYPE部分.

func ParseArgList(s Stream) error {
    err := ParseType(s)
    if err != nil {
        return err
    }

    /// ... FILL ME IN.  Do we call ParseArgList() again, or stop?
}

所以我们已经解析了前缀.如果是第二种情况,我们就完成了.但如果这是第一种情况怎么办？然后我们仍然需要阅读其他类型列表.

啊,但如果我们继续读取其他类型,那么流必须首先从另一种类型开始.我们知道,所有类型FIRST都以"int"或开始"(".所以我们可以看一下流.我们决定是否选择第一个或第二个选择取决于此!

func ParseArgList(s Stream) error {
    err := ParseType(s)
    if err != nil {
        return err
    }

    peeked := s.Peek()
    if peeked == "int" || peeked == "(" {
        // alternative 1
        return ParseArgList(s)
    }
    // alternative 2
    return nil
}

信不信由你,这几乎是我们所需要的.这是工作代码.

package main

import "fmt"

type Stream interface {
    Peek() string
    Next() string
}

type TokenSlice []string

func (s *TokenSlice) Peek() string {
    return (*s)[0]
}

func (s *TokenSlice) Next() string {
    result := (*s)[0]
    *s = (*s)[1:]
    return result
}

func ParseType(s Stream) error {
    peeked := s.Peek()
    if peeked == "int" {
        return ParsePrimitiveType(s)
    }
    if peeked == "(" {
        return ParseTupleType(s)
    }
    return fmt.Errorf("ParseType on %#v", peeked)
}

func ParsePrimitiveType(s Stream) error {
    next := s.Next()
    if next == "int" {
        return nil
    }
    return fmt.Errorf("ParsePrimitiveType on %#v", next)
}

func ParseTupleType(s Stream) error {
    lparen := s.Next()
    if lparen != "(" {
        return fmt.Errorf("ParseTupleType on %#v", lparen)
    }

    err := ParseArgList(s)
    if err != nil {
        return err
    }

    rparen := s.Next()
    if rparen != ")" {
        return fmt.Errorf("ParseTupleType on %#v", rparen)
    }

    return nil
}

func ParseArgList(s Stream) error {
    err := ParseType(s)
    if err != nil {
        return err
    }

    peeked := s.Peek()
    if peeked == "int" || peeked == "(" {
        // alternative 1
        return ParseArgList(s)
    }
    // alternative 2
    return nil
}

func main() {
    fmt.Println(ParseType(&TokenSlice{"int"}))
    fmt.Println(ParseType(&TokenSlice{"(", "int", ")"}))
    fmt.Println(ParseType(&TokenSlice{"(", "int", "int", ")"}))
    fmt.Println(ParseType(&TokenSlice{"(", "(", "int", ")", "(", "int", ")", ")"}))

    // Should show error:
    fmt.Println(ParseType(&TokenSlice{"(", ")"}))
}

当然,这是一个玩具解析器,因为它不能很好地处理某些类型的错误(比如输入的过早结束),并且令牌不仅应包括其文本内容,还应包括其良好错误报告的源位置.出于自己的目的,您还需要扩展解析器,以便它们不仅可以返回error,还可以从解析中获得某种有用的结果.

这个答案只是关于递归下降解析器如何工作的草图.但是你应该阅读一本好的编译器书来获取细节,因为你需要它们.在龙书,例如,至少花一个很好的一章讨论如何编写递归下降解析器用大量的技术细节.特别是,你想知道FIRST集的概念(我暗示过),因为在编写每个解析器函数时,你需要了解它们以选择适当的替代方案.