C语言从零开始实现 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
类型的完全定义就是得了。你可在这查看完的源代码:scanner/scanner.go、scanner/error.go。

尽管 Scanner
的概念完成了,但我们连没进行单元测试,所以我们无明白程序中是否在未知的
Bug,这明摆着对连续之支付是不利的。幸运的是,Go 语言提供了强大的 testing
包用于单元测试,你可以学习一下这个包之采取办法,并就此该对 scanner
模块进行完的单元测试。因为词法分析的单元测试比较简单,就非详细说了。

得源代码


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

赶巧起玩 Github
和简书,所以并未任何粉丝和关注量(哭),如果您以为这篇教程有辅助,请不要吝啬给文章点单爱,给
Github 上之档次点个 Star。如果能够 Follow 一下简书和 Github
的账号就还好啊,我耶会越有动力将之系列写下来。:)