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

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

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

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
`)
}