C语言从零初阶完成 Lua 解释器之词法分析

警告⚠️:那将是一个又臭又长的两种教程,教程截止的时候,你将拥有一个除了品质差劲、扩张性差、标准库不到家之外,其余方面都和法定相差无几的
Lua
语言解释器。说白了,那一个种类的课程完结的是一个玩具语言,仅供就学,无实用性。请小心
Follow,请谨慎 Follow,请谨慎 Follow。

那是本种类教程的第三篇,假诺您未曾看过此前的篇章,请从头观看。

前言


这次大家将为 SLua
已毕一体化的词法解析器。词法解析的天职比较简单,所以编写起来难度也不大。在上一篇教程中,大家引入了
Token 类型,词法解析器做的事务就是把用户输入的源代码转化成一个 Token
连串。在本文中大家将编辑一个新的类型:Scanner
(扫描器),落成词法分析的天职。

题外话:我看不惯废话,所以我会尽量将语言协会的简易易懂。如若你认为作品有词不平易的地点,欢迎在评论区或发私信提出来,我会立即立异,为持续的读者谢谢你。

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,那恰好就是大家盼望的。

拔取方法


在 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, 世界

获得源代码


代码已托管到 Github
上:SLua,每一个阶段的代码我都会创建一个
release,你可以直接下载作为参照。纵然提供了源代码,但并不指出直接复制粘贴,因为那样学到的知识会很简单忘记。

刚开首玩 Github
和简书,所以并未其余粉丝和关怀量(哭),假设你觉得那篇教程有扶持,请不要吝啬给文章点个爱护,给
Github 上的花色点个 Star。假如能 Follow 一下简书和 Github
的账号就更好啊,我也会越加有动力将这一个种类写下去。:)

解析 =、==、<、<=、>、>= 操作符
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。

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 分支不难处理。

剖析单字节操作符

在教学如何剖析操作符以前,须要介绍另一个私家方法:

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 '\'', '"':
    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.goscanner/error.go

即便如此 Scanner
的定义达成了,但大家并没有进展单元测试,所以我们不精晓程序中是或不是留存未知的
Bug,那明摆着对三番五次的付出是不利的。幸运的是,Go 语言提供了强劲的 testing
包用于单元测试,你能够学习一下这些包的利用方式,并用其对 scanner
模块进行完全的单元测试。因为词法分析的单元测试比较容易,就不详细说了。

错误处理

接下去,我们还有字符串、标记符(包含首要字)和数字须要处理。在此此前,大家必要先介绍一下
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 '\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

分析数字

数字的剖析算是相比较勤奋的有的了。

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)。

解析 ~= 操作符

C语言,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 '-':
    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)截止。

现实完成