从零开始实现 Lua 解释器之词法分析

警告⚠️:这将是一个又臭又长的数不胜数教程,教程结束之时段,你将有所一个除了性能差劲、扩展性差、标准库不完美之外,其他方都跟官方相差无几的
Lua
语言解释器。说白了,这个系列之课实现的凡一个玩具语言,仅供就学,无实用性。请小心
Follow,请小心 Follow,请谨慎 Follow。

立马是依照系列教程的老三篇,如果你莫扣了之前的稿子,请从头观看。

前言


此次我们以为 SLua
实现完全的词法解析器。词法解析的职责比较简单,所以编写起来难度也不怪。在高达等同篇教程被,我们引入了
Token 类型,词法解析器做的作业就是是把用户输入的源代码转化成为一个 Token
序列。在本文中我们将编制一个新的花色:Scanner
(扫描器),完成词法分析的职责。

题外话:我烦废话,所以我会尽量将语言组织的简单易亮。如果您觉得文章产生词不达意之地方,欢迎在评论区或发私信提出来,我会马上改进,为后续之读者谢谢你。

运办法


以 Scanner 完成后,我们可这样来使其:

// slua.go

package main

import (
    "fmt"
    "strings"

    "github.com/ksco/slua/scanner"
)

func main() {
    defer func() {
        if err := recover(); err != nil {
            fmt.Println(err)
        }
    }()

    r := strings.NewReader("local 你好 = 'Hello, 世界'")
    s := scanner.New(r)

    t := s.Scan()
    for t.Category != scanner.TokenEOF {
        fmt.Printf("Type:%v Value:%v\n", t.Category, t)
        t = s.Scan()
    }
}

一经您莫熟悉 Go 语言,可能会见对下面就段代码感到纳闷。

defer func() {
if err := recover(); err != nil {
fmt.Println(err)
}
}()

讲:Go 语言应用 panic 来废弃来荒唐,使程序上“恐慌”模式,可以以
defer 和 recover
来处理错误,恢复运行。预知详情,请看即篇稿子:英文版(需要翻墙)、中文版

得看到,scanner 模块提供了 New 函数,用来实例化一个 Scanner
类型,它承受一个饱 io.RuneReader
接口的参数。在上头的代码中,为了测试好,我们传入了一个 strings.Reader
作为参数。

除此以外,Scanner 类还导出了一个办法 Scan,每次调用这个函数,都见面回下一个
Token,直到文件截止完(返回值的 Category 为 TokenEOF 即为了却)。

故此用 io.RuneReader,而休是越来越广大的
io.ByteReader,是为我们怀念吃 SLua 支持
UNICODE,可以采取中文作为标志符(Identifier),很 Cool 吧?

地方的程序的输出如下:

$ go run slua.go
Type:local Value:local
Type:<id> Value:你好
Type:= Value:=
Type:<string> Value:Hello, 世界

切实落实


New 方法

哼了,最终成果展示了,现在我们不怕来贯彻其!首先第一步,我们用定义
Scanner 类型。

type Scanner struct {
    reader  io.RuneReader
    module  string
    current rune
    line    int
    column  int
    buffer  []rune
}

脚逐一分解每个参数的意。

  • reader:自然想到,我们得仓储传上的 io.RuneReader 参数。
  • module:如果程序运行出错的话,我们得理解究竟是在谁阶段起的掠,是词法分析、语法分析还是语义分析?module
    字段用于存储时所于的模块。
  • current:存储时四处位置的 rune 字符。
  • line、column:因为 Token 需要仓储所当的行和列,所以 Scanner
    就待保障这点儿单变量。
  • buffer 作为缓冲区,用作解析字符串和数字。

这般,我们虽可定义 scanner.New 函数了:

const eof rune = 0

func New(reader io.RuneReader) *Scanner {
    s := new(Scanner)
    s.module = "scanner"
    s.reader = reader
    s.line = 1
    s.current = eof
}

等等,你是无是遗漏为 column 字段做初始化了?

Go 语言会呢非初始化的变量设定一个默认的初始值:数字型的默认值为
0、字符串默认为 “”、指针默认为 nil 等等,所以 column 值为
0,这恰就是是咱想的。

Scan 方法初探

下面我们就算起来定义前面提到过的 Scan
方法。但在此之前,我们还得定义有个体的拉扯方法。

Go 语言提供了简短的拜会权限的决定,但它并无 public 和 private
等要字,而且其的权决定是对准模块的,而非是相仿。规则非常简单:如果类型、常量、函数等的首字母是大写的,那它就是是模块外可见的。如果首配母小写,那其便只好以模块内访问。

func (s *Scanner) next() rune {
    ch, _, err := s.reader.ReadRune()
    if err == nil {
        s.column++
    }
    return ch
}

next 函数非常简单,它利用 ReadRune 函数来读取一个字符,如果读取成功便以
column +1,然后用读取到之字符返回。如果读取失败,ch 也
0,这正就是是我们定义之 eof 常量。

发了 next 函数,我们可以开始定义 Scan 函数。

func (s *Scanner) Scan() *Token {
    if s.current == eof {
        s.current = s.next()
    }

    for s.current != eof {
        switch s.current {
        case ' ', '\t', '\v', '\f':
            s.current = s.next()
        default:
            s.current = s.next()
        }
    }
    return NewToken()
}

第一我们判断 s.current 是否也 eof,如果是就调用 next
函数为那赋值。剩下的有的该还特别爱掌握。第一个 case
是为了失去除源代码中之空白符。剩下的字符我们少用 default 分支简单处理。

拍卖换行符

更换行符的处理较为简单:

case '\r', '\n':
    s.newLine()

假如手上的字符为 \r、\n,就调用 newLine 方法。newLine 定义如下:

func (s *Scanner) newLine() {
    ch := s.next()
    if (ch == '\r' || ch == '\n') && ch != s.current {
        s.current = s.next()
    } else {
        s.current = ch
    }
    s.line++
    s.column = 0
}

注意,如果下一个字符也是 \r 或
\n,且非跟当前字符相同,则少独易行符就集合召开啊一个来拍卖。

这样做是为系统匹配:

\r = CR (Carriage Return) 在 OSX 之前用于 Mac OS 的换行符。

\n = LF (Line Feed) 用于 OSX/Unix 系统的换行符。

\r\n = CR + LF 用于 Windows 系统的换行符。

参考链接:StackOverflow

剖析单字节操作符

于教授如何剖析操作符之前,需要介绍任何一个私家方法:

func (s *Scanner) normalToken(category string) *Token {
    return &Token{
        Line:     s.line,
        Column:   s.column,
        Category: category,
    }
}

是函数根据传入的种和 Scanner 内部存储的队列信息,构造出一个 Token
实例,并返回其指针。有矣她,我们就算得分析单个字符长度的操作符了。

case '+', '*', '/', '#', '(', ')', ';', ',':
    t := s.current
    s.current = s.next()
    return s.normalToken(string(t))

对地方定义的 normalToken
方法,我们注意到,它不得不定义尚无增大信种类的 Token,所以对
TokenNumber、TokenID 和 TokenString,我们尚用做点额外的工作:

func (s *Scanner) stringToken(value, category string) *Token {
    t := s.normalToken(category)
    t.Value = value
    return t
}

func (s *Scanner) numberToken(value float64) *Token {
    t := s.normalToken(TokenNumber)
    t.Value = value
    return t
}

stringToken 之所以还索要传入类型,是因它们发 TokenString 和 TokenID
两种选择。

剖析注释

诠释的剖析为未麻烦:

case '-':
    n := s.next()
    if n == '-' {
        s.comment()
    } else {
        s.current = n
        return s.normalToken(TokenSub)
    }

Lua 使用 -- 这是一个单行注释 来代表单行注释,跟 C/C++
的单行注释规则一样,只不过不是 // 而是 –。
之所以,如果我们相遇一个 –
符号,就得看一下它下一个号,如果下一个符号还是
-,则说明这是一个单行注释。否则,就当 TokenSub 类型处理。

而是注释,我们尽管调用 comment 方法来拍卖,它的概念如下:

func (s *Scanner) comment() {
    s.current = s.next()
    for s.current != '\r' && s.current != '\n' && s.current != eof {
        s.current = s.next()
    }
}

逻辑很简单,我们直接向下读取,直到遇到换行符或读取到文件尾(EOF)为止。

错误处理

接下,我们尚来字符串、标记符(包括要字)和数字要处理。在此之前,我们要事先介绍一下
SLua 的错误处理方式。

Go 语言定义了一个 error 接口:

type error interface {
        Error() string
}

倘满足这个接口的路就可以一直开吧参数传入 panic
函数。所以我们定义了满足这接口的 Error 类型:

package scanner

import "fmt"

type Error struct {
    module string
    line   int
    column int
    str    string
}

func (e *Error) Error() string {
    return fmt.Sprintf("%v:%v:%v %v", e.module, e.line, e.column, e.str)
}

切切实实代码就不详细说了,一看即懂得。

浅析数字

数字之分析算是比较麻烦的一部分了。

case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
    return s.number(false)
case '.':
    n := s.next()
    if n == '.' {
        s.current = s.next()
        return s.normalToken(TokenConcat)
    } else {
        s.buffer = s.buffer[:0]
        s.buffer = append(s.buffer, s.current)
        s.current = n
        return s.number(true)
    }

如果代码所示,如果我们相遇数字符号,就调用 number 方法。另外,Lua 和 C
语言相似,允许小于 1 的浮点数省略前面的 0,直接坐 . 号开始,例如
.141592653。但假如我们连年碰到两只点号,则印证是 TokenConcat。number
的概念如下:

func (s *Scanner) number(point bool) *Token {
    if !point {
        s.buffer = s.buffer[:0]
        for unicode.IsDigit(s.current) {
            s.buffer = append(s.buffer, s.current)
            s.current = s.next()
        }
        if s.current == '.' {
            s.buffer = append(s.buffer, s.current)
            s.current = s.next()
        }
    }
    for unicode.IsDigit(s.current) {
        s.buffer = append(s.buffer, s.current)
        s.current = s.next()
    }
    str := string(s.buffer)
    number, err := strconv.ParseFloat(str, 64)
    if err != nil {
        panic(&Error{
            module: s.module,
            line:   s.line,
            column: s.column,
            str:    "parse number " + str + " error: invalid syntax",
        })
    }
    return s.numberToken(number)
}

number 函数接受一个参数,用来表示是否早已遇到了 . 号了。另外我们采用了
unicode.IsDigit 来判定是否为数字字符,使用了 strconv.ParseFloat
将字符串转换为数字。吁留心错误处理方式,和文首的演示代码配合着圈(panic
和 recover)。

解析 ~= 操作符

Lua 使用 ~= 来代表未齐,逻辑等同于 C/C++ 中之 !=
操作符。解析代码如下:

case '~':
    n := s.next()
    if n != '=' {
        panic(&Error{
            module: s.module,
            line:   s.line,
            column: s.column,
            str:    "expect '=' after '~'",
        })
    }
    s.current = s.next()
    return s.normalToken(TokenNotEqual)
解析 =、==、<、<=、>、>= 操作符
case '=':
    return s.xequal(TokenEqual)
case '>':
    return s.xequal(TokenGreaterEqual)
case '<':
    return s.xequal(TokenLessEqual)

xequal 方法定义如下:

func (s *Scanner) xequal(category string) *Token {
    t := s.current
    ch := s.next()
    if ch == '=' {
        s.current = s.next()
        return s.normalToken(category)
    }
    s.current = ch
    return s.normalToken(string(t))
}

xequal 的逻辑是:如果同当眼前标记后面的凡一个 = 符号,则回传入的门类的
Token,否则就算赶回时标记所表示色的 Token。

解析单行字符串
case '\'', '"':
    return s.singlelineString()

与 Python 类似,Lua 的单行字符串可以包于 ‘ 或 ” 中。singlelineString
方法定义入下:

func (s *Scanner) singlelineString() *Token {
    quote := s.current
    s.current = s.next()
    s.buffer = s.buffer[:0]
    for s.current != quote {
        if s.current == eof {
            panic(&Error{
                module: s.module,
                line:   s.line,
                column: s.column,
                str:    "incomplete string at <eof>",
            })
        }
        if s.current == '\r' || s.current == '\n' {
            panic(&Error{
                module: s.module,
                line:   s.line,
                column: s.column,
                str:    "incomplete string at <eol>",
            })
        }
        s.stringChar()
    }
    s.current = s.next()
    return s.stringToken(string(s.buffer), TokenString)
}

func (s *Scanner) stringChar() {
    if s.current == '\\' {
        s.current = s.next()
        if s.current == 'a' {
            s.buffer = append(s.buffer, '\a')
        } else if s.current == 'b' {
            s.buffer = append(s.buffer, '\b')
        } else if s.current == 'f' {
            s.buffer = append(s.buffer, '\f')
        } else if s.current == 'n' {
            s.buffer = append(s.buffer, '\n')
        } else if s.current == 'r' {
            s.buffer = append(s.buffer, '\r')
        } else if s.current == 't' {
            s.buffer = append(s.buffer, '\t')
        } else if s.current == 'v' {
            s.buffer = append(s.buffer, '\v')
        } else if s.current == '\\' {
            s.buffer = append(s.buffer, '\\')
        } else if s.current == '"' {
            s.buffer = append(s.buffer, '"')
        } else if s.current == '\'' {
            s.buffer = append(s.buffer, '\'')
        } else {
            panic(&Error{
                module: s.module,
                line:   s.line,
                column: s.column,
                str:    "unexpect character after '\\'",
            })
        }
    } else {
        s.buffer = append(s.buffer, s.current)
    }
    s.current = s.next()
}

里面,stringChar
函数用来处理字符串中冒出的转义字符。如果以字符串结束前碰到了移行符或读取到文件尾,则输出处错误信息。

及今毕,除了标记符(包括主要字),所有的 case
都分析了了,所以我们得以拿 TokenID 类型的剖析放在 default 中:

default:
    return s.id()

以 Lua 中,标记符需要以 _ 或其他非符号 UNICODE
字符开头,剩下的一部分除此之外还得蕴涵数字。

例如 hello_tempk_1077信息列表123さよなら
都是官的标记符。

呢之我们需要有个函数来赞助我们规定有字符是否也官方字符:

func isLetter(ch rune) bool {
    return ascii.IsLetter(byte(ch)) || ch == '_' ||
        ch >= 0x80 && unicode.IsLetter(ch)
}

其中 ascii.IsLetter 是咱们由定义之函数,定义如下:

package ascii

func IsLetter(ch byte) bool {
    return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z'
}

公可能会见意外,问啊我们若多之一举为,isLetter 完全可以这样来描写:

func isLetter(ch rune) bool {
    return ch == '_' || unicode.IsLetter(ch)
}

答案是由性能考虑。在 unicode.IsLetter
的内部贯彻着,需要寻找一个宏伟的列表来规定结果。而以代码中,绝大多数的标记符和拥有的第一字还是出于
ASCII 字符组成,我们以 || 操作符的“截断”特性来尽量避免调用
unicode.IsLetter 函数,以加强性能。

切实的讨论要见此帖子:地址(需翻墙)

id 函数的概念如下:

func (s *Scanner) id() *Token {
    if !isLetter(s.current) {
        panic(&Error{
            module: s.module,
            line:   s.line,
            column: s.column,
            str:    "unexpect character",
        })
    }

    s.buffer = s.buffer[:0]
    s.buffer = append(s.buffer, s.current)
    s.current = s.next()
    for isLetter(s.current) || unicode.IsDigit(s.current) {
        s.buffer = append(s.buffer, s.current)
        s.current = s.next()
    }

    str := string(s.buffer)
    if isKeyword(str) {
        return s.stringToken(str, str)
    }
    return s.stringToken(str, TokenID)
}

由来,Scanner
类型的圆定义就是到位了。你可以于是查看完的源代码C++:scanner/scanner.go、scanner/error.go。

则 Scanner
的概念完成了,但我们连不曾进展单元测试,所以我们无亮堂程序中是不是是未知之
Bug,这眼看对继续之开销是不利的。幸运的是,Go 语言提供了劲的 testing
包用于单元测试,你可上一下者保险之采用办法,并为此该对 scanner
模块进行完的单元测试。因为词法分析的单元测试比较简单,就未详细说了。

取得源代码


代码都托管到 Github
上:SLua,每一个阶段的代码我还见面创造一个
release,你得一直下充斥作为参照。虽然提供了来代码,但连无建议直接复制粘贴,因为这样效仿到的知识会很易忘。

恰开玩 Github
和简书,所以无其他粉丝及关注量(哭),如果你觉得就首教程有协助,请不要吝啬给文章点个喜,给
Github 上的门类点个 Star。如果能 Follow 一下简书和 Github
的账号就更好哪,我耶会见越来越有动力将以此系列写下去。:)