path: root/src/urubu/spec/test/tree_parser.go

// Code generated by vartan-go. DO NOT EDIT.
package test

import (
	"fmt"
	"io"
)

type Grammar interface {
	// InitialState returns the initial state of a parser.
	InitialState() int

	// StartProduction returns the start production of grammar.
	StartProduction() int

	// Action returns an ACTION entry corresponding to a (state, terminal symbol) pair.
	Action(state int, terminal int) int

	// GoTo returns a GOTO entry corresponding to a (state, non-terminal symbol) pair.
	GoTo(state int, lhs int) int

	// ErrorTrapperState returns true when a state can shift the error symbol.
	ErrorTrapperState(state int) bool

	// LHS returns a LHS symbol of a production.
	LHS(prod int) int

	// AlternativeSymbolCount returns a symbol count of p production.
	AlternativeSymbolCount(prod int) int

	// RecoverProduction returns true when a production has the recover directive.
	RecoverProduction(prod int) bool

	// NonTerminal retuns a string representaion of a non-terminal symbol.
	NonTerminal(nonTerminal int) string

	// TerminalCount returns a terminal symbol count of grammar.
	TerminalCount() int

	// SkipTerminal returns true when a terminal symbol must be skipped on syntax analysis.
	SkipTerminal(terminal int) bool

	// EOF returns the EOF symbol.
	EOF() int

	// Error returns the error symbol.
	Error() int

	// Terminal retuns a string representaion of a terminal symbol.
	Terminal(terminal int) string

	// ASTAction returns an AST action entries.
	ASTAction(prod int) []int
}

type VToken interface {
	// TerminalID returns a terminal ID.
	TerminalID() int

	// Lexeme returns a lexeme.
	Lexeme() []byte

	// EOF returns true when a token represents EOF.
	EOF() bool

	// Invalid returns true when a token is invalid.
	Invalid() bool

	// Position returns (row, column) pair.
	Position() (int, int)
}

type TokenStream interface {
	Next() (VToken, error)
}

type SyntaxError struct {
	Row               int
	Col               int
	Message           string
	Token             VToken
	ExpectedTerminals []string
}

type ParserOption func(p *Parser) error

// DisableLAC disables LAC (lookahead correction). LAC is enabled by default.
func DisableLAC() ParserOption {
	return func(p *Parser) error {
		p.disableLAC = true
		return nil
	}
}

func SemanticAction(semAct SemanticActionSet) ParserOption {
	return func(p *Parser) error {
		p.semAct = semAct
		return nil
	}
}

type Parser struct {
	toks       TokenStream
	gram       Grammar
	stateStack *stateStack
	semAct     SemanticActionSet
	disableLAC bool
	onError    bool
	shiftCount int
	synErrs    []*SyntaxError
}

func NewParser(toks TokenStream, gram Grammar, opts ...ParserOption) (*Parser, error) {
	p := &Parser{
		toks:       toks,
		gram:       gram,
		stateStack: &stateStack{},
	}

	for _, opt := range opts {
		err := opt(p)
		if err != nil {
			return nil, err
		}
	}

	return p, nil
}

func (p *Parser) Parse() error {
	p.stateStack.push(p.gram.InitialState())
	tok, err := p.nextToken()
	if err != nil {
		return err
	}

ACTION_LOOP:
	for {
		act := p.lookupAction(tok)

		switch {
		case act < 0: // Shift
			nextState := act * -1

			recovered := false
			if p.onError {
				p.shiftCount++

				// When the parser performs shift three times, the parser recovers from the error state.
				if p.shiftCount >= 3 {
					p.onError = false
					p.shiftCount = 0
					recovered = true
				}
			}

			p.shift(nextState)

			if p.semAct != nil {
				p.semAct.Shift(tok, recovered)
			}

			tok, err = p.nextToken()
			if err != nil {
				return err
			}
		case act > 0: // Reduce
			prodNum := act

			recovered := false
			if p.onError && p.gram.RecoverProduction(prodNum) {
				p.onError = false
				p.shiftCount = 0
				recovered = true
			}

			accepted := p.reduce(prodNum)
			if accepted {
				if p.semAct != nil {
					p.semAct.Accept()
				}

				return nil
			}

			if p.semAct != nil {
				p.semAct.Reduce(prodNum, recovered)
			}
		default: // Error
			if p.onError {
				tok, err = p.nextToken()
				if err != nil {
					return err
				}
				if tok.EOF() {
					if p.semAct != nil {
						p.semAct.MissError(tok)
					}

					return nil
				}

				continue ACTION_LOOP
			}

			row, col := tok.Position()
			p.synErrs = append(p.synErrs, &SyntaxError{
				Row:               row,
				Col:               col,
				Message:           "unexpected token",
				Token:             tok,
				ExpectedTerminals: p.searchLookahead(p.stateStack.top()),
			})

			count, ok := p.trapError()
			if !ok {
				if p.semAct != nil {
					p.semAct.MissError(tok)
				}

				return nil
			}

			p.onError = true
			p.shiftCount = 0

			act, err := p.lookupActionOnError()
			if err != nil {
				return err
			}

			p.shift(act * -1)

			if p.semAct != nil {
				p.semAct.TrapAndShiftError(tok, count)
			}
		}
	}
}

// validateLookahead validates whether `term` is a valid lookahead in the current context. When `term` is valid,
// this method returns `true`.
func (p *Parser) validateLookahead(term int) bool {
	p.stateStack.enableExploratoryMode()
	defer p.stateStack.disableExploratoryMode()

	for {
		act := p.gram.Action(p.stateStack.topExploratorily(), term)

		switch {
		case act < 0: // Shift
			return true
		case act > 0: // Reduce
			prodNum := act

			lhs := p.gram.LHS(prodNum)
			if lhs == p.gram.LHS(p.gram.StartProduction()) {
				return true
			}
			n := p.gram.AlternativeSymbolCount(prodNum)
			p.stateStack.popExploratorily(n)
			state := p.gram.GoTo(p.stateStack.topExploratorily(), lhs)
			p.stateStack.pushExploratorily(state)
		default: // Error
			return false
		}
	}
}

func (p *Parser) nextToken() (VToken, error) {
	for {
		// We don't have to check whether the token is invalid because the kind ID of the invalid token is 0,
		// and the parsing table doesn't have an entry corresponding to the kind ID 0. Thus we can detect
		// a syntax error because the parser cannot find an entry corresponding to the invalid token.
		tok, err := p.toks.Next()
		if err != nil {
			return nil, err
		}

		if p.gram.SkipTerminal(tok.TerminalID()) {
			continue
		}

		return tok, nil
	}
}

func (p *Parser) tokenToTerminal(tok VToken) int {
	if tok.EOF() {
		return p.gram.EOF()
	}

	return tok.TerminalID()
}

func (p *Parser) lookupAction(tok VToken) int {
	if !p.disableLAC {
		term := p.tokenToTerminal(tok)
		if !p.validateLookahead(term) {
			return 0
		}
	}

	return p.gram.Action(p.stateStack.top(), p.tokenToTerminal(tok))
}

func (p *Parser) lookupActionOnError() (int, error) {
	act := p.gram.Action(p.stateStack.top(), p.gram.Error())
	if act >= 0 {
		return 0, fmt.Errorf("an entry must be a shift action by the error symbol; entry: %v, state: %v, symbol: %v", act, p.stateStack.top(), p.gram.Terminal(p.gram.Error()))
	}

	return act, nil
}

func (p *Parser) shift(nextState int) {
	p.stateStack.push(nextState)
}

func (p *Parser) reduce(prodNum int) bool {
	lhs := p.gram.LHS(prodNum)
	if lhs == p.gram.LHS(p.gram.StartProduction()) {
		return true
	}
	n := p.gram.AlternativeSymbolCount(prodNum)
	p.stateStack.pop(n)
	nextState := p.gram.GoTo(p.stateStack.top(), lhs)
	p.stateStack.push(nextState)
	return false
}

func (p *Parser) trapError() (int, bool) {
	count := 0
	for {
		if p.gram.ErrorTrapperState(p.stateStack.top()) {
			return count, true
		}

		if p.stateStack.top() != p.gram.InitialState() {
			p.stateStack.pop(1)
			count++
		} else {
			return 0, false
		}
	}
}

func (p *Parser) SyntaxErrors() []*SyntaxError {
	return p.synErrs
}

func (p *Parser) searchLookahead(state int) []string {
	kinds := []string{}
	termCount := p.gram.TerminalCount()
	for term := 0; term < termCount; term++ {
		if p.disableLAC {
			if p.gram.Action(p.stateStack.top(), term) == 0 {
				continue
			}
		} else {
			if !p.validateLookahead(term) {
				continue
			}
		}

		// We don't add the error symbol to the look-ahead symbols because users cannot input the error symbol
		// intentionally.
		if term == p.gram.Error() {
			continue
		}

		kinds = append(kinds, p.gram.Terminal(term))
	}

	return kinds
}

type stateStack struct {
	items    []int
	itemsExp []int
}

func (s *stateStack) enableExploratoryMode() {
	s.itemsExp = make([]int, len(s.items))
	copy(s.itemsExp, s.items)
}

func (s *stateStack) disableExploratoryMode() {
	s.itemsExp = nil
}

func (s *stateStack) top() int {
	return s.items[len(s.items)-1]
}

func (s *stateStack) topExploratorily() int {
	return s.itemsExp[len(s.itemsExp)-1]
}

func (s *stateStack) push(state int) {
	s.items = append(s.items, state)
}

func (s *stateStack) pushExploratorily(state int) {
	s.itemsExp = append(s.itemsExp, state)
}

func (s *stateStack) pop(n int) {
	s.items = s.items[:len(s.items)-n]
}

func (s *stateStack) popExploratorily(n int) {
	s.itemsExp = s.itemsExp[:len(s.itemsExp)-n]
}

type grammarImpl struct {
	recoverProductions      []int
	action                  []int
	goTo                    []int
	alternativeSymbolCounts []int
	errorTrapperStates      []int
	nonTerminals            []string
	lhsSymbols              []int
	terminals               []string
	terminalSkip            []int
	astActions              [][]int
}

func NewGrammar() *grammarImpl {
	return &grammarImpl{
		recoverProductions: []int{
			0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0,
		},
		action: []int{
			0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			-3, 0, 0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0,
			-2, 7, 0, -11, 0, 0, -12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 4,
			4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -14, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -15, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 12, 12, 0, 0, -17, 12, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 16, -22, 0, 16, 16, 0, 0, 0, 0, 0, -23,
			-24, -25, -26, -27, -28, -29, 16, 0, 0, 0, 0, 5, 5, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 3, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -30, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			-31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -23, -24, -25, -26, -27, -28, -29, 15,
			0, 18, 0, 0, 18, 18, 0, 0, 0, 0, 0, 18, 18, 18, 18, 18, 18, 18, 18, 0,
			25, 0, 0, 25, 25, 0, 0, 0, 0, 0, 25, 25, 25, 25, 25, 25, 25, 25, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -33, 0, 19, 0,
			0, 19, 19, 0, 0, 0, 0, 0, 19, 19, 19, 19, 19, 19, 19, 19, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, -34, 0, 0, 0, 0, 0, 0, 20, 0, 0, 20,
			20, 0, 0, 0, 0, 0, 20, 20, 20, 20, 20, 20, 20, 20, 0, 21, 0, 0, 21, 21,
			0, 0, 0, 0, 0, 21, 21, 21, 21, 21, 21, 21, 21, 0, 22, 0, 0, 22, 22, 0,
			0, 0, 0, 0, 22, 22, 22, 22, 22, 22, 22, 22, 0, 23, 0, 0, 23, 23, 0, 0,
			0, 0, 0, 23, 23, 23, 23, 23, 23, 23, 23, 0, 24, 0, 0, 24, 24, 0, 0, 0,
			0, 0, 24, 24, 24, 24, 24, 24, 24, 24, 0, 10, 0, 0, 10, 10, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 0, 0, 13, 13, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 17, 17, 0, 0, 0, 0, 0, 17,
			17, 17, 17, 17, 17, 17, 17, 0, 14, 0, 0, 14, 14, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, -35, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -36,
			0, 0, 0, 0, 0, 26, 0, 0, 26, 26, 0, 0, 0, 0, 0, 26, 26, 26, 26, 26,
			26, 26, 26,
		},
		goTo: []int{
			0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 7, 8, 9, 0, 10, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 19, 20, 21, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 21,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0,
		},
		alternativeSymbolCounts: []int{
			0, 1, 4, 4, 3, 2, 1, 0, 1, 1, 3, 1, 0, 3, 3, 1, 0, 2, 1, 1,
			1, 1, 1, 1, 1, 1, 4,
		},
		errorTrapperStates: []int{
			0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		},
		nonTerminals: []string{
			"",
			"tree'",
			"tree",
			"tree_list",
			"string",
			"raw_string",
			"opt_raw_string_body",
			"interpreted_string",
			"opt_interpreted_string_body",
			"interpreted_string_body",
			"interpreted_string_elem",
			"codepoint_expr",
		},
		lhsSymbols: []int{
			0, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
			10, 10, 10, 10, 10, 10, 11,
		},
		terminals: []string{
			"",
			"<eof>",
			"error",
			"ws",
			"l_paren",
			"r_paren",
			"identifier",
			"raw_string_open",
			"raw_string_body",
			"raw_string_close",
			"interpreted_string_open",
			"interpreted_seq",
			"codepoint_prefix",
			"l_brace",
			"r_brace",
			"hex_digits",
			"escaped_seq",
			"escape_char",
			"interpreted_string_close",
		},
		terminalSkip: []int{
			0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		},
		astActions: [][]int{
			nil,
			nil,
			{
				2, -3,
			},
			{
				2, 3,
			},
			{
				2,
			},
			{
				-1, 2,
			},
			nil,
			nil,
			nil,
			nil,
			{
				-2,
			},
			nil,
			nil,
			{
				-2,
			},
			{
				2,
			},
			{
				-1,
			},
			nil,
			{
				-1, -2,
			},
			{
				-1,
			},
			nil,
			nil,
			nil,
			nil,
			nil,
			nil,
			nil,
			{
				3,
			},
		},
	}
}

func (g *grammarImpl) InitialState() int {
	return 0
}

func (g *grammarImpl) StartProduction() int {
	return 1
}

func (g *grammarImpl) RecoverProduction(prod int) bool {
	return g.recoverProductions[prod] != 0
}

func (g *grammarImpl) Action(state int, terminal int) int {
	return g.action[state*19+terminal]
}

func (g *grammarImpl) GoTo(state int, lhs int) int {
	return g.goTo[state*12+lhs]
}

func (g *grammarImpl) AlternativeSymbolCount(prod int) int {
	return g.alternativeSymbolCounts[prod]
}

func (g *grammarImpl) TerminalCount() int {
	return 19
}

func (g *grammarImpl) SkipTerminal(terminal int) bool {
	return g.terminalSkip[terminal] == 1
}

func (g *grammarImpl) ErrorTrapperState(state int) bool {
	return g.errorTrapperStates[state] != 0
}

func (g *grammarImpl) NonTerminal(nonTerminal int) string {
	return g.nonTerminals[nonTerminal]
}

func (g *grammarImpl) LHS(prod int) int {
	return g.lhsSymbols[prod]
}

func (g *grammarImpl) EOF() int {
	return 1
}

func (g *grammarImpl) Error() int {
	return 2
}

func (g *grammarImpl) Terminal(terminal int) string {
	return g.terminals[terminal]
}

func (g *grammarImpl) ASTAction(prod int) []int {
	return g.astActions[prod]
}

type vToken struct {
	terminalID int
	tok        *Token
}

func (t *vToken) TerminalID() int {
	return t.terminalID
}

func (t *vToken) Lexeme() []byte {
	return t.tok.Lexeme
}

func (t *vToken) EOF() bool {
	return t.tok.EOF
}

func (t *vToken) Invalid() bool {
	return t.tok.Invalid
}

func (t *vToken) Position() (int, int) {
	return t.tok.Row, t.tok.Col
}

var kindToTerminal = []int{
	0, 3, 4, 5, 6, 7, 10, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18,
}

type tokenStream struct {
	lex            *Lexer
	kindToTerminal []int
}

func NewTokenStream(src io.Reader) (*tokenStream, error) {
	lex, err := NewLexer(NewLexSpec(), src)
	if err != nil {
		return nil, err
	}

	return &tokenStream{
		lex: lex,
	}, nil
}

func (t *tokenStream) Next() (VToken, error) {
	tok, err := t.lex.Next()
	if err != nil {
		return nil, err
	}
	return &vToken{
		terminalID: kindToTerminal[tok.KindID],
		tok:        tok,
	}, nil
}