Golang高效扫描解析LL(1)语法的插件库Prattle的使用

概述

Prattle是一个通用的、支持Unicode的词法扫描器和自上而下的运算符优先级解析器，适用于解析LL(1)语法。扫描器和解析器可以独立使用。

安装

go get -u github.com/askeladdk/prattle

快速开始

使用Scanner扫描文本

使用Scanner通过ScanFunc扫描源文本生成一系列Token。使用Expect*、Skip和Advance方法来扫描标记。

// 准备扫描器
scanner := prattle.Scanner{
    // Scan扫描下一个标记并返回其类型
    Scan: func(s *prattle.Scanner) (kind int) {
        // 跳过所有空白字符
        s.ExpectAny(unicode.IsSpace)
        s.Skip()

        // 扫描下一个标记
        switch {
        case s.Done(): // 当所有输入都被消耗时停止
            return 0
        case s.Expect('+'): // 扫描加法运算符
            return 1
        case s.ExpectOne(unicode.IsDigit): // 扫描由一个或多个数字组成的数字
            s.ExpectAny(unicode.IsDigit)
            return 2
        }

        // 无效标记
        s.Advance()
        return -1
    },
}

使用Parser解析语法

使用Parser和Driver将Scanner生成的标记与ParseFunc关联。首先定义Driver。

// 定义解析Driver
type driver struct {
    stack []int
}

func (d *driver) push(i int) {
    d.stack = append(d.stack, i)
}

func (d *driver) pop() (i int) {
    n := len(d.stack)
    i, d.stack = d.stack[n-1], d.stack[:n-1]
    return
}

func (d *driver) number(p *prattle.Parser, t prattle.Token) error {
    n, _ := strconv.Atoi(t.Text)
    d.push(n)
    return nil
}

func (d *driver) add(p *prattle.Parser, t prattle.Token) error {
    // 解析右侧运算符
    _ = p.Parse(d.Precedence(t.Kind))

    right := d.pop()
    left := d.pop()
    sum := left + right
    fmt.Printf("%d + %d = %d\n", left, right, sum)
    d.push(sum)
    return nil
}

func (d *driver) Prefix(kind int) prattle.ParseFunc {
    return d.number
}

func (d *driver) Infix(kind int) prattle.ParseFunc {
    return d.add
}

func (d *driver) Precedence(kind int) int {
    return kind
}

func (d *driver) ParseError(t prattle.Token) error {
    return fmt.Errorf("%s", t)
}

// 准备解析器
parser := prattle.Parser{
    Driver: &driver{},
}

初始化并解析表达式

source := "1 + 23 + 456 + 7890"
scanner.InitWithString(source)
parser.Init(&scanner).Parse(0)

// 输出:
// 1 + 23 = 24
// 24 + 456 = 480
// 480 + 7890 = 8370

完整示例

以下是一个完整的计算器示例，展示了如何使用Prattle解析简单的数学表达式：

package main

import (
    "fmt"
    "strconv"
    "unicode"

    "github.com/askeladdk/prattle"
)

func main() {
    // 定义扫描器
    scanner := prattle.Scanner{
        Scan: func(s *prattle.Scanner) (kind int) {
            // 跳过空白
            s.ExpectAny(unicode.IsSpace)
            s.Skip()

            // 扫描标记
            switch {
            case s.Done():
                return 0
            case s.Expect('+'):
                return 1
            case s.ExpectOne(unicode.IsDigit):
                s.ExpectAny(unicode.IsDigit)
                return 2
            }

            // 无效标记
            s.Advance()
            return -1
        },
    }

    // 定义解析Driver
    type driver struct {
        stack []int
    }

    func (d *driver) push(i int) {
        d.stack = append(d.stack, i)
    }

    func (d *driver) pop() (i int) {
        n := len(d.stack)
        i, d.stack = d.stack[n-1], d.stack[:n-1]
        return
    }

    func (d *driver) number(p *prattle.Parser, t prattle.Token) error {
        n, _ := strconv.Atoi(t.Text)
        d.push(n)
        return nil
    }

    func (d *driver) add(p *prattle.Parser, t prattle.Token) error {
        _ = p.Parse(d.Precedence(t.Kind))
        right := d.pop()
        left := d.pop()
        sum := left + right
        fmt.Printf("%d + %d = %d\n", left, right, sum)
        d.push(sum)
        return nil
    }

    func (d *driver) Prefix(kind int) prattle.ParseFunc {
        return d.number
    }

    func (d *driver) Infix(kind int) prattle.ParseFunc {
        return d.add
    }

    func (d *driver) Precedence(kind int) int {
        return kind
    }

    func (d *driver) ParseError(t prattle.Token) error {
        return fmt.Errorf("%s", t)
    }

    // 初始化并解析
    parser := prattle.Parser{
        Driver: &driver{},
    }

    source := "1 + 23 + 456 + 7890"
    scanner.InitWithString(source)
    if err := parser.Init(&scanner).Parse(0); err != nil {
        fmt.Println("Parse error:", err)
    }
}

这个示例展示了Prattle的基本用法，包括如何定义扫描器、解析驱动以及如何将它们组合起来解析简单的加法表达式。