Handwritten Parsers & Lexers in Go ，翻译
用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 intconst ( // 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联系我。
相关推荐
uber-go/guide 的中文翻译
参考链接:https://github.com/xxjwxc/uber_go_guide_cn
时间：2023-07-19 06:20
