// Code generated by vartan-go. DO NOT EDIT. package test import ( "fmt" "io" ) type Grammar interface { // Class returns a class of grammar. Class() string // 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 // 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 // TerminalAlias returns an alias for a terminal. TerminalAlias(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) // Skip returns true when a token must be skipped on syntax analysis. Skip() bool } 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). When the grammar has the LALR class, 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{}, } if p.gram.Class() != "lalr" { p.disableLAC = true } 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 tok.Skip() { 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 } if alias := p.gram.TerminalAlias(term); alias != "" { kinds = append(kinds, alias) } else { 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 terminalAliases []string astActions [][]int } func NewGrammar() *grammarImpl { return &grammarImpl{ recoverProductions: []int{ 0, 0, 0, 1, 0, 0, 0, }, action: []int{ 0, 0, 0, 0, -2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -3, 0, 0, 0, -4, 0, 0, 0, 0, 0, -5, 0, 0, 6, 0, 0, -2, 6, 0, 0, 3, 0, 0, 3, 3, 0, 0, 0, 0, 0, 5, 5, 0, 0, 0, 0, 0, -2, -9, 0, 0, 0, 0, 0, 4, 4, 0, 0, 2, 0, 0, 2, 2, 0, }, goTo: []int{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, alternativeSymbolCounts: []int{ 0, 1, 4, 3, 2, 1, 0, }, errorTrapperStates: []int{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, }, nonTerminals: []string{ "", "tree'", "tree", "tree_list", }, lhsSymbols: []int{ 0, 1, 2, 2, 3, 3, 3, }, terminals: []string{ "", "", "error", "ws", "l_paren", "r_paren", "identifier", }, terminalAliases: []string{ "", "", "", "", "(", ")", "", }, astActions: [][]int{ nil, nil, { 2, -3, }, { 2, }, { -1, 2, }, nil, nil, }, } } func (g *grammarImpl) Class() string { return "lalr" } 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*7+terminal] } func (g *grammarImpl) GoTo(state int, lhs int) int { return g.goTo[state*4+lhs] } func (g *grammarImpl) AlternativeSymbolCount(prod int) int { return g.alternativeSymbolCounts[prod] } func (g *grammarImpl) TerminalCount() int { return 7 } 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) TerminalAlias(terminal int) string { return g.terminalAliases[terminal] } func (g *grammarImpl) ASTAction(prod int) []int { return g.astActions[prod] } type vToken struct { terminalID int skip bool 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) Skip() bool { return t.skip } func (t *vToken) Position() (int, int) { return t.tok.Row, t.tok.Col } var kindToTerminal = []int{ 0, 3, 4, 5, 6, } var skip = []int{ 0, 1, 0, 0, 0, } type tokenStream struct { lex *Lexer kindToTerminal []int skip []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], skip: skip[tok.KindID] > 0, tok: tok, }, nil }