讓 Go 很容易手寫 Parser

Pratt Parser 是一種非常容易手寫，代碼可讀性很好，而且性能不錯的 Parser 編寫方式（Pratt Parsers: Expression Parsing Made Easy）。實現了一個框架來支持各種手寫 Pratt Parser 的需求。比如，要對下面這個表達式進行求值。

4/(1+1)+2

求值的結果應該是 4。下面這個手寫 Parser 就實現了這樣一個遞歸下降的解析過程。

import "github.com/modern-go/parse"import "github.com/modern-go/parse/read"const precedenceAssignment = 1const precedenceConditional = 2const precedenceSum = 3const precedenceProduct = 4const precedenceExponent = 5const precedencePrefix = 6const precedencePostfix = 7const precedenceCall = 8type exprLexer struct { value *valueToken plus *plusToken minus *minusToken multiply *multiplyToken divide *divideToken group *groupToken}var expr = &exprLexer{}func (lexer *exprLexer) Parse(src *parse.Source, precedence int) interface{} { return parse.Parse(src, lexer, precedence)}func (lexer *exprLexer) InfixToken(src *parse.Source) (parse.InfixToken, int) { switch src.Peek1() { case +: return lexer.plus, precedenceSum case -: return lexer.minus, precedenceSum case *: return lexer.multiply, precedenceProduct case /: return lexer.divide, precedenceProduct default: return nil, 0 }}func (lexer *exprLexer) PrefixToken(src *parse.Source) parse.PrefixToken { switch src.Peek1() { case (: return lexer.group case -: return lexer.minus default: return lexer.value }}type valueToken struct {}func (token *valueToken) PrefixParse(src *parse.Source) interface{} { return read.Int(src)}type plusToken struct {}func (token *plusToken) InfixParse(src *parse.Source, left interface{}) interface{} { leftValue := left.(int) src.Consume1(+) rightValue := expr.Parse(src, precedenceSum).(int) return leftValue + rightValue}type minusToken struct {}func (token *minusToken) PrefixParse(src *parse.Source) interface{} { src.Consume1(-) expr := expr.Parse(src, precedencePrefix).(int) return -expr}func (token *minusToken) InfixParse(src *parse.Source, left interface{}) interface{} { leftValue := left.(int) src.Consume1(-) rightValue := expr.Parse(src, precedenceSum).(int) return leftValue - rightValue}type multiplyToken struct {}func (token *multiplyToken) InfixParse(src *parse.Source, left interface{}) interface{} { leftValue := left.(int) src.Consume1(*) rightValue := expr.Parse(src, precedenceProduct).(int) return leftValue * rightValue}type divideToken struct {}func (token *divideToken) InfixParse(src *parse.Source, left interface{}) interface{} { leftValue := left.(int) src.Consume1(/) rightValue := expr.Parse(src, precedenceProduct).(int) return leftValue / rightValue}type groupToken struct {}func (token *groupToken) PrefixParse(src *parse.Source) interface{} { src.Consume1(() expr := expr.Parse(src, 0) src.Consume1()) return expr}

主要提供的可復用的東西有三個。

• parse.Parse：主循環代碼
• parse.Source：支持 look ahead，支持 byte by byte，支持 rune by rune，支持 savepoint 回溯
• read /discard：一些經過優化的，常見的匹配字元串讀取代碼，比如 discard 當前連續的空格等等，比如 http://read.Int(src) 讀取10進位的字元串。

首先是 "parse.Parse" 這個 main loop：

func Parse(src *Source, lexer Lexer, precedence int) interface{} { token := lexer.PrefixToken(src) if token == nil { src.ReportError(errors.New("can not parse")) return nil } InfoLogger.Println("prefix", ">>>", reflect.TypeOf(token)) left := token.PrefixParse(src) InfoLogger.Println("prefix", "<<<", reflect.TypeOf(token)) for { if src.Error() != nil { return left } token, infixPrecedence := lexer.InfixToken(src) if token == nil { return left } if precedence >= infixPrecedence { concurrent.InfoLogger.Println("precedence skip ", reflect.TypeOf(token), precedence, infixPrecedence) return left } concurrent.InfoLogger.Println("infix ", ">>>", reflect.TypeOf(token)) left = token.InfixParse(src, left) concurrent.InfoLogger.Println("infix ", "<<<", reflect.TypeOf(token)) } return left}

其次是 parse.Source。可以看一下回溯的能力

// UnicodeRange read unicode until one not in table,// the bytes will be appended to the space passed in.// If space is nil, new space will be allocated from heapfunc UnicodeRange(src *parse.Source, space []byte, table *unicode.RangeTable) []byte { src.Savepoint("UnicodeRange") length := 0 for src.Error() == nil { r, n := src.PeekRune() if !unicode.Is(table, r) { break } length += n src.ConsumeN(n) } if src.FatalError() != nil { return nil } src.RollbackTo("UnicodeRange") return src.CopyN(space, length)}

庫的代碼在這裡：

modern-go/parsegithub.com
推薦閱讀：