parsing - 如何实现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

为了您的目的，类型的语法看起来很简单，您应该可以编写一个与语法形状大致匹配的recursive descent parser。

举一个具体的例子，假设我们正在识别一种相似的语言。

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

与您的原始问题不太完全相同，但是您应该能够看到相似之处。

递归下降解析器由每个生产规则的功能组成。

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

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

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

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

我们将在此处表示不完全知道要放入 ??? * 的东西，直到到达那里。至少现在我们要说的是，如果无法解析，我们会得到一个 error。

每个功能的输入都是一些 token 流。在我们的情况下，这些 token 由以下序列组成:

 "int"
 "("
 ")"

我们可以想象 Stream可能满足以下条件:

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

让我们依次浏览 token 流。

词法分析器负责获取诸如字符串或 io.Reader之类的内容，并生成此字符串 token 流。词法分析器相当容易编写:您可以想象仅使用正则表达式或类似方法将字符串分解为标记。

假设我们有一个 token 流，那么解析器仅需要处理该流和一组非常有限的可能性。如前所述，每个生产规则对应于一个解析函数。在生产规则中，每个替代方案都是条件分支。如果语法特别简单(如您所愿!)，我们可以找出采用哪个条件分支。

例如，让我们看一下 TYPE及其对应的 ParseType函数:

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

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

生产说有两种可能性:它可以是(1)基本类型，也可以是(2)元组。我们可以窥视 token 流:如果看到 "int"，那么我们知道它是原始的。如果看到 "("，则由于唯一的可能就是它的元组类型，因此我们可以调用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
}

信不信由你，这就是我们所需要的。这是 working code。

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，而且还从解析中获得一些有用的结果。

这个答案只是递归下降解析器如何工作的草图。但是您确实应该读一本好的编译器书以获取详细信息，因为您需要它们。例如， Dragon Book在有关如何编写具有大量技术细节的递归下降解析器上花费了至少一章。特别是，您想了解FIRST集的概念(我曾暗示过)，因为在编写每个解析器函数时，您需要了解它们以选择合适的替代方案。