ll1/parser/parser.go

// Uses an ll1 grammar to parse an input from an ll1 flexer to an Ast.
package parser

// import "fmt"
import . "src.eruta.nl/beoran/ll1/common"
import . "src.eruta.nl/beoran/ll1/ast"
import . "src.eruta.nl/beoran/ll1/grammar"
import . "src.eruta.nl/beoran/ll1/flexer"

// A TokenMapper maps a token to a Species.
type TokenMapper interface {
	// Returns the species to use for the grammar rule. If nil, the token
	// may be skipped.
	Map(t Rule) Species
}

type DefaultMapper struct{}

func (DefaultMapper) Map(r Rule) Species {
	return MakeSpecies(r.Name())
}

type Parser struct {
	Grammar
	TokenMapper
	Tokens []Token
	Index  int
	Errors []error
	Result Ast
	// current location in the ast being built.
	Now       Ast
	Recursion int
}

func (p *Parser) MakeError(msg string, args ...interface{}) error {
	return MakeErrorToken(p.Token().Location(), msg, args...)
}

func (p *Parser) AddError(msg string, args ...interface{}) error {
	err := MakeErrorToken(p.Token().Location(), msg, args...)
	p.Errors = append(p.Errors, err)
	return err
}

func (g Parser) Token() Token {
	if g.Index < len(g.Tokens) {
		return g.Tokens[g.Index]
	}
	last := g.Tokens[len(g.Tokens)-1]
	return MakeErrorToken(last.Location(), "Unexpected end of input.")
}

func (g *Parser) Expect(kind Kind) Token {
	tok := g.Token()
	if tok.Kind() == kind {
		g.Index++
		return tok
	}
	return nil
}

func (g *Parser) Accept(kinds ...Kind) Token {
	tok := g.Token()
	for _, kind := range kinds {
		if tok.Kind() == kind {
			g.Index++
			return tok
		}
	}
	return nil
}

func (g *Parser) Require(kinds ...Kind) Token {
	tok := g.Accept(kinds...)
	if tok != nil {
		return tok
	}
	g.AddError("Expected: %v", kinds)
	return nil
}

func (p *Parser) ParseTerminal(term Terminal) error {
	tok := p.Expect(term.Kind)
	if tok == nil {
		return p.MakeError("Expected token kind: %d", term.Kind)
	}
	spec := p.Map(term)
	NewChild(p.Now, spec, tok)
	// now should alreqdy be of suitable kind to accept a terminal token child.
	return nil
}

func (g *Parser) ParseEpsilon(term Epsilon) error {
	return nil
}

func (p *Parser) ParseEnd(term EndOfInput) error {
	if p.Index >= (len(p.Tokens) - 1) {
		p.Index = len(p.Tokens) // reach the end.
		return nil
	} else {
		return p.MakeError("Expected end of input.")
	}
}

func (p *Parser) PopUp() {
	if p.Now != nil && p.Now.Parent() != nil {
		p.Now = p.Now.Parent()
	}
}

func (p *Parser) ParseReference(ref Reference) error {
	rule, err := ref.Resolve()
	if err != nil {
		return err
	}
	return p.ParseRule(rule)
}

func (p *Parser) ParseSequence(seq Sequence) error {
	spec := p.Map(seq)
	p.Now = NewChild(p.Now, spec, p.Token())
	defer p.PopUp()
	for _, rule := range seq.Rules {
		err := p.ParseRule(rule)
		if err != nil {
			p.Errors = append(p.Errors, err)
			return err
		}
	}
	return nil
}

/*
func (p *Parser) ParseOptinalAlternates(alt Alternates) error {
	for _, rule := range alt.Rules {
		if IsReference(rule) {

		}
		err := p.ParseRule(rule)
		if err != nil {
			errors = append(errors, err)
		} else { // one alternate was OK here.
			return nil
		}
	}
	// If we get here no alternate was ok.
	p.Errors = append(p.Errors, errors...)
	return p.MakeError("Could not parse alternate.")
}
*/

func (p *Parser) ParseAlternates(alt Alternates) error {
	spec := p.Map(alt)
	p.Now = NewChild(p.Now, spec, p.Token())
	defer p.PopUp()
	errors := []error{}
	hasEpsilon := false

	for _, rule := range alt.Rules {
		if IsEpsilon(rule) {
			hasEpsilon = true
		} else {
			first, _ := rule.FirstSet()
			if first.ContainsKind(p.Token().Kind()) {
				err := p.ParseRule(rule)
				if err != nil {
					errors = append(errors, err)
				} else { // this alternate was OK here.
					return nil
				}
			}
		}
	}
	if hasEpsilon { // No match is ok.
		return nil
	}
	// If we get here no alternate was ok.
	p.Errors = append(p.Errors, errors...)
	return p.MakeError("Could not parse alternate.")
}

func (p *Parser) ParseRule(r Rule) error {
	p.Recursion++
	if p.Recursion > 800 {
		panic("Too much recursion in grammar.")
	}
	switch rv := r.(type) {
	case Epsilon:
		p.ParseEpsilon(rv)
	case EndOfInput:
		p.ParseEnd(rv)
	case Terminal:
		p.ParseTerminal(rv)
	case Alternates:
		p.ParseAlternates(rv)
	case Sequence:
		p.ParseSequence(rv)
	case Reference:
		p.ParseReference(rv)
	default:
		panic("Unknown rule type in ParseRule.")
	}
	// p.Now.AddChild()
	return nil
}

func (p *Parser) Parse(input []Token) error {
	p.Tokens = input
	p.Recursion = 0
	p.Errors = []error{}
	p.Result = NewAstNone()
	p.Now = p.Result
	return p.ParseRule(p.Grammar.Top)
	return nil
}