• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

HandwrittenParsers&LexersinGo(翻译)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

用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联系我。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Go-闭包发布时间:2022-07-12
下一篇:
go程序性能优化发布时间:2022-07-12
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap