如何实现一个 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 | TUPLETYPEPRIMITIVETYPE ::= 'int'TUPLETYPE ::= '(' ARGLIST ')'ARGLIST ::= TYPE ARGLIST | TYPE与您的原始问题不完全相同，但您应该能够看到相似之处。递归下降解析器由每个产生式规则的函数组成。func ParseType(???) error {    ???}func ParsePrimitiveType(???) error {    ???}func ParseTupleType(???) error {    ???}func ParseArgList(???) error {    ???}在我们到达那里之前，我们将表示我们不太知道该放什么的东西???*。我们至少现在会说，error如果我们无法解析，我们会得到一个。每个函数的输入都是一些令牌流。在我们的例子中，这些令牌由以下序列组成： "int" "(" ")"我们可以想象 aStream可能满足以下条件：type Stream interface {    Peek() string  // peek at next token, stay where we are    Next() string  // pick next token, move forward}让我们依次遍历令牌流。一个词法分析器负责采取类似的字符串或io.Reader和生产字符串标记此流。词法分析器相当容易编写：您可以想象只使用正则表达式或类似的东西将字符串分解为标记。假设我们有一个令牌流，那么解析器只需要处理该流和一组非常有限的可能性。如前所述，每个产生式规则对应一个解析函数。在产生式规则中，每个替代项都是一个条件分支。如果语法特别简单（就像你的一样！），我们可以找出要采用哪个条件分支。例如，让我们看看TYPE它的对应ParseType函数：TYPE ::= PRIMITIVETYPE | TUPLETYPEPRIMITIVETYPE ::= 'int'TUPLETYPE ::= '(' ARGLIST ')'这如何对应于 的定义ParseType？产生式说有两种可能性：它可以是（1）原始的，或者是（2）元组的。我们可以查看令牌流：如果我们看到"int"，那么我们就知道它是原始的。如果我们看到 a "("，那么由于唯一的可能性是它是元组类型，我们可以调用 tupletype 解析器函数并让它做脏活。重要的是要注意：如果我们既没有看到 a"("也没有看到an "int"，那么就出现了可怕的错误！我们仅通过查看语法就知道这一点。我们可以看到，每种类型都必须首先从这两个标记之一开始解析。好，我们来写代码。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 mainimport "fmt"type Stream interface {    Peek() string    Next() string}type TokenSlice []stringfunc (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 集的概念（我暗示过），因为在编写每个解析器函数时，您需要了解它们以选择适合的替代方案。