Parser Combinator

parser.go

package main

import (
	"fmt"
	"io"
	"strings"
	"regexp"
	"reflect"
)

type RuneReaderSeeker interface {
	io.RuneReader
	io.Reader
	io.Seeker
}

type Match interface {
	Print(indent int, indenter string)
}

type MatchString string

type MatchTree []Match

func Lit(text string) func(rs RuneReaderSeeker) (Match, error) {
	return func(rs RuneReaderSeeker) (Match, error) {
		pos, _ := rs.Seek(0, 1)
		b := make([]byte, len(text))
		c, _ := rs.Read(b)
		if c < len(text) {
			rs.Seek(pos, 0)
			return nil, fmt.Errorf("Unexpected EOF")
		}
		if string(b) == text {
			m := MatchString(text)
			return &m, nil
		}
		rs.Seek(pos, 0)
		return nil, fmt.Errorf("Expected %s, got %s", text, string(b))
	}
}

func Set(set string) func(rs RuneReaderSeeker) (Match, error) {
	r := regexp.MustCompile("^[" + set + "]")
	return func(rs RuneReaderSeeker) (Match, error) {
		pos, _ := rs.Seek(0, 1)

		m := r.FindReaderIndex(rs)
		if m != nil {
			b := make([]byte, m[1])
			rs.Seek(pos, 0)
			rs.Read(b)
			m := MatchString(string(b))
			return &m, nil 
		}
		rs.Seek(pos, 0)
		return nil, fmt.Errorf("Expected %s", set)
	}
}

func And(ps ...func(rs RuneReaderSeeker) (Match, error)) func(rs RuneReaderSeeker) (Match, error) {
	return func(rs RuneReaderSeeker) (Match, error) {
		pos, _ := rs.Seek(0, 1)
		
		ms := make(MatchTree, 0)
		
		for _, p := range ps {
			match, err := p(rs)
			if err != nil {
				rs.Seek(pos, 0)
				return nil, err	
			}
			if match != nil {
				ms = append(ms, match)
			}
		}
		if len(ms) == 1 {
			return ms[0], nil
		}
		return ms, nil
	}
}

func Or(ps ...func(rs RuneReaderSeeker) (Match, error)) func(rs RuneReaderSeeker) (Match, error) {
	return func(rs RuneReaderSeeker) (Match, error) {
		
		for _, p := range ps {
			match, err := p(rs)
			if err == nil {
				return match, nil	
			}
		}
		return nil, fmt.Errorf("Or error")

	}
}

func Mult(n, m int, p func(rs RuneReaderSeeker) (Match, error)) func(rs RuneReaderSeeker) (Match, error) {
	if m == 0 {
		m = int(^uint(0) >> 1)
	}
	return func(rs RuneReaderSeeker) (Match, error) {
		pos, _ := rs.Seek(0, 1)
		ms := make(MatchTree, 0)
		for i := 0; i < m; i++ {
			match, err := p(rs)
			if err != nil {
				if len(ms) < n {
					rs.Seek(pos, 0)
					return nil, fmt.Errorf("Error: not enough")
				}
				return ms, nil
			}
			if match != nil {
				ms = append(ms, match)
			}
		}
		if len(ms) < n {
			rs.Seek(pos, 0)
			return nil, fmt.Errorf("Error: not enough")
		}
		return ms, nil
	}
}

func Ignore(p func(rs RuneReaderSeeker) (Match, error)) func(rs RuneReaderSeeker) (Match, error) {
	return func(rs RuneReaderSeeker) (Match, error) {
		_, err := p(rs)
		if err != nil {
			return nil, err
		}
		return nil, nil
	}
}

func Combine(p func(rs RuneReaderSeeker) (Match, error)) func(rs RuneReaderSeeker) (Match, error) {
	return func(rs RuneReaderSeeker) (Match, error) {
		m, err := p(rs)
		if err != nil {
			return nil, err
		}
		if t, ok := m.(MatchTree); ok {
			s := ""
			for _, v := range t {
				s += string(*v.(*MatchString))
			}
			m := MatchString(s)
			return &m, nil
		}
		return m, nil
	}
}

func Build(i interface{}, ps ...func(rs RuneReaderSeeker) (Match, error)) func(rs RuneReaderSeeker) (Match, error) {
	return func(rs RuneReaderSeeker) (Match, error) {
		pos, _ := rs.Seek(0, 1)
		
		newi := reflect.New(reflect.TypeOf(i))
		field := 0
		for _, p := range ps {
			match, err := p(rs)
			if err != nil {
				rs.Seek(pos, 0)
				return nil, err	
			}
			if match != nil {
				newi.Elem().Field(field).SetString(string(*match.(*MatchString)))
				field++
			}
		}
		
		return newi.Interface().(Match), nil
	}
}

type VariableDef struct {
	Name string
	Type string
	Value string
}

func (v VariableDef) Print(indent int, indenter string) {
	fmt.Printf("%s%s %s\n", strings.Repeat(indenter, indent), v.Type, v.Name)
}

func (m MatchTree) Print(indent int, indenter string) {
	for _, v := range m {
		v.Print(indent+1, indenter)
	}
}

func (m MatchString) Print(indent int, indenter string) {
	fmt.Printf("%s%s\n", strings.Repeat(indenter, indent), m)
}

var (
	VariableName = Combine(And(Mult(0, 0, Set("a-zA-Z")), WS))
	VariableType = Lit("int")
	VariableValue = Combine(And(Mult(0, 0, Set("0-9")), WS))
	WS = Ignore(Mult(0, 0, Set(" \t\n")))
	Variable = And(Build(VariableDef{}, VariableName, VariableType), WS)
)

func main() {
	Grammar := Mult(0, 0, Variable)

	fmt.Println("foo int\nbar int")
	test := strings.NewReader("foo int\nbar int")
	m, err := Grammar(test)
	if m == nil {
		fmt.Println(err)
	} else {
		m.Print(0, "|")
	}
}