用go实现Parsers & Lexers

在当今网络应用和REST API的时代，编写解析器似乎是一种垂死的艺术。你可能会认为编写解析器是一个复杂的工作，只保留给编程语言设计师，但我想消除这种观念。在过去几年中，我为JSON，CSS3和数据库查询语言编写了解析器，所写的解析器越多，我越喜欢他们。

基础（The Basics）

让我们从基础开始：什么是词法分析器？什么解析器？当我们分析一种语言（或从技术上讲，一种“正式语法”）时，我们分两个阶段进行。首先我们将一系列的字符分解成tokens。对于类似SQL的语言，这些tokens可能是“whitespace“，”number“，“SELECT“等。这个处理过程叫作lexing（或者tokenizing，或scanning）

以此简单的SQL SELECT语句为例：

SELECT * FROM mytable

当我们标记（tokenize）这个字符串时，我们会得到：

`SELECT` • `WS` • `ASTERISK` • `WS` • `FROM` • `WS` • `STRING<"mytable">`

这个过程称为词法分析（lexical analysis），与阅读时我们如何分解句子中的单词相似。这些tokens随后被反馈给执行语义分析的解析器。

解析器的任务是理解这些token，并确保它们的顺序正确。这类似于我们如何从句子中组合单词得出意思。我们的解析器将从token序列中构造出一个抽象语法树（AST），而AST是我们的应用程序将使用的。

在SQL SELECT示例中，我们的AST可能如下所示：

type SelectStatement struct {

         Fields []string

         TableName string

}

解析器生成器 （Parser Generators）

许多人使用解析器生成器（Parser Generators）为他们自动写一个解析器（parser）和词法分析器（lexer）。有很多工具可以做到这一点：lex，yacc，ragel。还有一个内置在go 工具链中的用go实现的yacc（goyacc）。

然而，在多次使用解析器生成器后，我发现有些问题。首先，他们涉及到学习一种新的语言来声明你的语言格式，其次，他们很难调试。例如，尝试阅读ruby语言的yacc文件。Eek！

在看完Rob Pike关于lexical scanning的演讲和读完go标准库包的实现后，我意识到手写一个自己的parser和lexer多么简单和容易。让我们用一个简单的例子来演示这个过程。

用Go写一个lexer

定义我们的tokens

我们首先为SQL SELECT语句编写一个简单的解析器和词法分析器。首先，我们需要用定义在我们的语言中允许的标记。我们只允许SQL 语言的一小部分：

// Token represents a lexical token.

type Token int

const (

         // Special tokens

         ILLEGAL Token = iota

         EOF

         WS

         // Literals

         IDENT // fields, table_name

         // Misc characters

         ASTERISK // *

         COMMA    // ,

         // Keywords

         SELECT

         FROM

)

我们将使用这些tokens来表示字符序列。例如WS将表示一个或多个空白字符，IDENT将表示一个标识符，例如字段名或表名称。

定义字符类  （Defining character classes）

定义可以检查字符类型的函数很有用。这里我们定义两个函数，一个用于检查一个字符是否为空格，另一个用于检查字符是否是字母。

func isWhitespace(ch rune) bool {

         return ch == ' ' || ch == '\t' || ch == '\n'

}

func isLetter(ch rune) bool {

         return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')

}

定义“EOF”也是有用的，以便像任何其他character一样对的EOF：

var eof = rune(0)

Scanning our input

接下来，我们要定义我们的扫描器类型。这个类型将用一个bufio.Reader包装输入阅读器，我们可以从头部取字符。我们还添加帮助函数（helper function），用于从底层Reader读取，取消读取字符。

// Scanner represents a lexical scanner.

type Scanner struct {

         r *bufio.Reader

}

// NewScanner returns a new instance of Scanner.

func NewScanner(r io.Reader) *Scanner {

         return &Scanner{r: bufio.NewReader(r)}

}

// read reads the next rune from the bufferred reader.

// Returns the rune(0) if an error occurs (or io.EOF is returned).

func (s *Scanner) read() rune {

         ch, _, err := s.r.ReadRune()

         if err != nil {

                 return eof

         }

         return ch

}

// unread places the previously read rune back on the reader.

func (s *Scanner) unread() { _ = s.r.UnreadRune() }

Scanner的入口函数是Scan（）方法，它返回下一个token和它所代表的文字字符串。

// Scan returns the next token and literal value.

func (s *Scanner) Scan() (tok Token, lit string) {

         // Read the next rune.

         ch := s.read()

         // If we see whitespace then consume all contiguous whitespace.

         // If we see a letter then consume as an ident or reserved word.

         if isWhitespace(ch) {

                 s.unread()

                 return s.scanWhitespace()

         } else if isLetter(ch) {

                 s.unread()

                 return s.scanIdent()

         }

         // Otherwise read the individual character.

         switch ch {

         case eof:

                 return EOF, ""

         case '*':

                 return ASTERISK, string(ch)

         case ',':

                 return COMMA, string(ch)

         }

         return ILLEGAL, string(ch)

}

该入口函数从读取第一个字符开始。如果字符是whitespace，那么它将与所有连续的whitespace一起使用。如果是一个letter，则被视为identifier和keyword的开始。否则，我们将检查它是否是我们的单字符tokens之一。

扫描连续字符  Scanning contiguous characters

当我们想要连续使用多个字符时，我们可以在一个简单的循环中执行此操作。在scanWhitespace（）中，我们假设在碰到一个非空格字符前所有字符都是whitespaces。

// scanWhitespace consumes the current rune and all contiguous whitespace.

func (s *Scanner) scanWhitespace() (tok Token, lit string) {

         // Create a buffer and read the current character into it.

         var buf bytes.Buffer

         buf.WriteRune(s.read())

         // Read every subsequent whitespace character into the buffer.

         // Non-whitespace characters and EOF will cause the loop to exit.

         for {

                 if ch := s.read(); ch == eof {

                          break

                 } else if !isWhitespace(ch) {

                          s.unread()

                          break

                 } else {

                          buf.WriteRune(ch)

                 }

         }

         return WS, buf.String()

}

相同的逻辑可以应用于扫描identifiers。在scanident()中，我们将读取所有字母和下划线，直到遇到不同的字符：

// scanIdent consumes the current rune and all contiguous ident runes.

func (s *Scanner) scanIdent() (tok Token, lit string) {

         // Create a buffer and read the current character into it.

         var buf bytes.Buffer

         buf.WriteRune(s.read())

         // Read every subsequent ident character into the buffer.

         // Non-ident characters and EOF will cause the loop to exit.

         for {

                 if ch := s.read(); ch == eof {

                          break

                 } else if !isLetter(ch) && !isDigit(ch) && ch != '_' {

                          s.unread()

                          break

                 } else {

                          _, _ = buf.WriteRune(ch)

                 }

         }

         // If the string matches a keyword then return that keyword.

         switch strings.ToUpper(buf.String()) {

         case "SELECT":

                 return SELECT, buf.String()

         case "FROM":

                 return FROM, buf.String()

         }

         // Otherwise return as a regular identifier.

         return IDENT, buf.String()

}

这个函数在后面会检查文字字符串是否是一个保留字，如果是，将返回一个指定的token。

用Go写一个解析器 Writing a Parser in Go

设置解析器

一旦我们准备好lexer，解析SQL语句就变得更加容易了。首先定义我们的parser：

// Parser represents a parser.

type Parser struct {

         s   *Scanner

         buf struct {

                 tok Token  // last read token

                 lit string // last read literal

                 n   int    // buffer size (max=1)

         }

}

// NewParser returns a new instance of Parser.

func NewParser(r io.Reader) *Parser {

         return &Parser{s: NewScanner(r)}

}

我们的解析器只是包装了我们的scanner，还为上一个读取token添加了缓冲区。我们定义helper function进行扫描和取消扫描，以便使用这个缓冲区。

// scan returns the next token from the underlying scanner.

// If a token has been unscanned then read that instead.

func (p *Parser) scan() (tok Token, lit string) {

         // If we have a token on the buffer, then return it.

         if p.buf.n != 0 {

                 p.buf.n = 0

                 return p.buf.tok, p.buf.lit

         }

         // Otherwise read the next token from the scanner.

         tok, lit = p.s.Scan()

         // Save it to the buffer in case we unscan later.

         p.buf.tok, p.buf.lit = tok, lit

         return

}

// unscan pushes the previously read token back onto the buffer.

func (p *Parser) unscan() { p.buf.n = 1 }

我们的parser此时已经不关心whitespaces了，所以将定义一个helper 函数来查找下一个非空白标记（token）

// scanIgnoreWhitespace scans the next non-whitespace token.

func (p *Parser) scanIgnoreWhitespace() (tok Token, lit string) {

         tok, lit = p.scan()

         if tok == WS {

                 tok, lit = p.scan()

         }

         return

}

解析输入 Parsing the input

我们的解析器的entry function是parse()方法。该函数将从Reader中解析下一个SELECT语句。如果reader中有多个语句，那么我们可以重复调用这个函数。

func (p *Parser) Parse() (*SelectStatement, error)

我们将这个函数分解成几个小部分。首先定义我们要从函数返回的AST结构

stmt := &SelectStatement{}

然后我们要确保有一个SELECT token。如果没有看到我们期望的token，那么将返回一个错误来报告我们我们发现的字符串。

if tok, lit := p.scanIgnoreWhitespace(); tok != SELECT {

         return nil, fmt.Errorf("found %q, expected SELECT", lit)

}

接下来要解析以逗号分隔的字段列表。在我们的解析器中，我们只考虑identifiers和一个星号作为可能的字段：

for {

         // Read a field.

         tok, lit := p.scanIgnoreWhitespace()

         if tok != IDENT && tok != ASTERISK {

                 return nil, fmt.Errorf("found %q, expected field", lit)

         }

         stmt.Fields = append(stmt.Fields, lit)

         // If the next token is not a comma then break the loop.

         if tok, _ := p.scanIgnoreWhitespace(); tok != COMMA {

                 p.unscan()

                 break

         }

}

在字段列表后，我们希望看到一个From关键字：

// Next we should see the "FROM" keyword.

if tok, lit := p.scanIgnoreWhitespace(); tok != FROM {

         return nil, fmt.Errorf("found %q, expected FROM", lit)

}

然后我们想要看到选择的表的名称。这应该是标识符token

tok, lit := p.scanIgnoreWhitespace()

if tok != IDENT {

         return nil, fmt.Errorf("found %q, expected table name", lit)

}

stmt.TableName = lit

如果到了这一步，我们已经成功分析了一个简单的SQL SELECT 语句，这样我们就可以返回我们的AST结构：

return stmt, nil

恭喜！你已经建立了一个可以工作的parser

深入了解，你可以在以下位置找到本示例完整的源代码（带有测试）https://github.com/benbjohnson/sql-parser

这个解析器的例子深受InfluxQL解析器的启发。如果您有兴趣深入了解并理解多个语句解析，表达式解析或运算符优先级，那么我建议您查看仓库：

https://github.com/influxdb/influxdb/tree/master/influxql

如果您有任何问题或想聊聊解析器，请在Twitter上@benbjohnson联系我。