Go言語で簡単なパーサー書いてみた

Go言語は初心者なのでまずいところあると思う。

今回作ったもの

簡単な四則演算パーサー。

こんな感じのBNFを解析しながら実行する。

parser.bnf

top  ::= "?"? line | ""
line ::= (ident "=")? line | expr
expr ::= term (("+" | "-") term)*
term ::= fact (("*" | "/") fact)*
fact ::= "(" expr ")"
       | ("+" | "-") fact
       | number
       | ident

number :::= [0-9]+
ident  :::= [a-zA-Z]+

説明不要だと思うけど、+と-と*と/は四則演算で、=は代入演算子。
先頭に?が付いている場合は結果を表示する。

というどこかで見たことのあるような四則演算機。

実装

ほぼBNFの名前通りにメソッド名が付けられているから分かりやすいと思う。

parser.go

package main

import (
    "bufio"
    "errors"
    "fmt"
    "os"
    "strconv"
    "unicode"
)

//位置情報
type SrcInfo struct {
    Src string
    Row int
    Col int
}

//エラー
type ParseError struct {
    Info    SrcInfo
    Message string
}

//パースの状態
type ParseState struct {
    buffer []rune
    point  int
    info   SrcInfo
}

//変数の環境（グローバル変数かよ！）
var (
    env map[string]int64
)

//エラー表示用メソッド
func (e SrcInfo) Error() string {
    return fmt.Sprintf("%s(%d,%d)",
        e.Src, e.Row, e.Col)
}

func (e ParseError) Error() string {
    return fmt.Sprintf("%s : %s",
        e.Info.Error(), e.Message)
}

//現在のパース位置から文字を取得
func (p *ParseState) at() rune {
    var ret rune
    l := len(p.buffer)
    if l <= p.point {
        ret = 0
    } else {
        ret = p.buffer[p.point]
    }
    return ret
}

//文字を取得して一つ進める
func (p *ParseState) next() rune {
    c := p.at()
    if c == 0 {
        return c
    } else if c == '\n' {
        p.info.Row += 1
        p.info.Col = 1
    } else {
        p.info.Col += 1
    }
    p.point += 1
    return c
}

//パーサーユーティリティ

//ParseErrorを作る
func (p *ParseState) error(message string) error {
    return ParseError{
        Info:    p.info,
        Message: message,
    }
}

//ParseStateのコピー（バックトラック用）
func (p *ParseState) Copy() (copy *ParseState) {
    copy = new(ParseState)
    *copy = *p
    return
}



func NewParseState(src string, buffer string) ParseState {
    return ParseState{
        buffer: []rune(buffer),
        info: SrcInfo{
            Src: src,
            Col: 1,
            Row: 1,
        },
    }
}

//トークンパーサー達

//空白を読み飛ばす
func (p *ParseState) skip() {
    for c := p.at(); unicode.IsSpace(c); c = p.at() {
        p.next()
    }
}

//指定した文字があるかどうか
func (p *ParseState) char(e rune) bool {
    ret := false
    c := p.at()
    if c == e {
        ret = true
        p.next()
        p.skip()
    }
    return ret
}

//数値リテラル
// number :::= [0-9]+
func (p *ParseState) number() (x int64, err error) {
    begin := p.point
    for c := p.at(); unicode.IsDigit(c); c = p.at() {
        p.next()
    }
    end := p.point
    if begin == end {
        return 0, p.error("expect integer")
    }
    buf := string(p.buffer[begin:end])
    x, err = strconv.ParseInt(buf, 10, 64)
    p.skip()
    return
}

//識別子
// ident :::= [a-zA-Z]+
func (p *ParseState) ident() (buf string, err error) {
    begin := p.point
    for c := p.at(); unicode.IsLetter(c); c = p.at() {
        p.next()
    }
    end := p.point
    if begin == end {
        return "", p.error("expect ident")
    }
    buf = string(p.buffer[begin:end])
    p.skip()
    return
}

//パーサー

// top ::= "?"? line | ""
func (p *ParseState) Parse() (display bool, x int64, err error) {
    p.skip()
    if p.at() == 0 {
        return
    }
    display = p.char('?')
    x, err = p.line()
    if err == nil && p.at() != 0 {
        err = p.error("expect operator")
    }
    return
}

// line ::= ident "=" line | expr
func (p *ParseState) line() (x int64, err error) {
    var id string
    p_ := p.Copy()
    if id, err = p.ident(); err == nil {
        if p.char('=') {
            if x, err = p.line(); err != nil {
                return
            }
            env[id] = x
            return
        } else {
            *p = *p_
        }
    }
    return p.expr()
}

// expr ::= term (("+" | "-") term)*
func (p *ParseState) expr() (x int64, err error) {
    x, err = p.term()
    for true {
        var y int64
        if p.char('+') {
            y, err = p.term()
            if err != nil {
                return
            }
            x += y
        } else if p.char('-') {
            y, err = p.term()
            if err != err {
                return
            }
            x -= y
        } else {
            p.skip()
            break
        }
    }
    return
}

// term ::= fact (("*" | "/") fact)*
func (p *ParseState) term() (x int64, err error) {
    x, err = p.fact()
    for true {
        var y int64
        if p.char('*') {
            y, err = p.fact()
            if err != nil {
                return
            }
            x *= y
        } else if p.char('/') {
            y, err = p.fact()
            if err != err {
                return
            }
            if y == 0 {
                return 0, errors.New("error : zero division")
            }
            x /= y
        } else {
            p.skip()
            break
        }
    }
    return
}

// fact ::= "(" expr ")"
//        | ("+" | "-") fact
//        | number
//        | ident
func (p *ParseState) fact() (x int64, err error) {
    if p.char('+') {
        return p.fact()
    }
    if p.char('-') {
        x, err = p.fact()
        x = -x
        return
    }
    if p.char('(') {
        x, err = p.expr()
        if err == nil && !p.char(')') {
            err = p.error("expect ')'")
        }
        return
    }
    if x, err = p.number(); err == nil {
        return
    }
    var id string
    if id, err = p.ident(); err == nil {
        var ok bool
        if x, ok = env[id]; !ok {
            return 0, errors.New("error : undeclared variable '" + id + "'")
        }
        return
    }
    return 0, p.error("except number or ident")
}

//REPLのReadとLoopを司るところ
func PromptLoop(prompt string, loop func(string) error) {
    stdin := bufio.NewReader(os.Stdin)
    for err := error(nil); err == nil; {
        var line string
        fmt.Printf("%s", prompt)
        line, err = stdin.ReadString('\n')
        if err != nil {
            return
        }
        err = loop(line)
    }
}

//初期化
func init() {
    env = make(map[string]int64)
}


func main() {
    fmt.Print(`calculator
Use Ctrl-Z plus return to exit
`)
    PromptLoop("# ", func(line string) error {
        p := NewParseState("prompt", line)
        display, x, err := p.Parse()
        if err != nil {
            fmt.Fprintf(os.Stdout, "%s\n", err.Error())
        } else if display {
            fmt.Printf(">> %d\n", x)
        }
        return nil
    })
    fmt.Print(`
see you
`)
}

エラー処理とか作り込んだら思ったより長くなってしまった。
それでも、C言語で書くよりは短く書けたはず。それ以上に、やや特徴的なオブジェクト指向のおけげで、Javaで同じ事をやろうとしたら設計がかなり面倒な作業になるところも、試行錯誤しながら作っていきやすかった。、Go言語のスケーラブルな仕様はいいと思う。

最初にも書いた通り、Go言語はずぶの素人なので、どなたか添削していただけるとありがたいです。