Remove the expected terminals field from the parsing table

The driver searches the expected terminals corresponding to each state if necessary.

4 files changed, 20 insertions, 36 deletions

diff --git a/driver/parser.go b/driver/parser.go
index 8cd6511..91f364e 100644
--- a/driver/parser.go
+++ b/driver/parser.go
@@ -185,7 +185,7 @@ ACTION_LOOP:
 				Col:               tok.Col,
 				Message:           "unexpected token",
 				Token:             tok,
-				ExpectedTerminals: p.expectedTerms(p.top()),
+				ExpectedTerminals: p.searchLookahead(p.top()),
 			})
 
 			ok := p.trapError()
@@ -456,28 +456,33 @@ func (p *Parser) SyntaxErrors() []*SyntaxError {
 	return p.synErrs
 }
 
-func (p *Parser) expectedTerms(state int) []string {
+func (p *Parser) searchLookahead(state int) []string {
 	kinds := []string{}
-	terms := p.gram.ParsingTable.ExpectedTerminals[state]
+	term2Kind := p.gram.LexicalSpecification.Maleeni.TerminalToKind
+	kindNames := p.gram.LexicalSpecification.Maleeni.Spec.KindNames
 	aliases := p.gram.LexicalSpecification.Maleeni.KindAliases
-	for _, tsym := range terms {
+	termCount := p.gram.ParsingTable.TerminalCount
+	base := p.top() * termCount
+	for term := 0; term < termCount; term++ {
+		if p.gram.ParsingTable.Action[base+term] == 0 {
+			continue
+		}
+
 		// We don't add the error symbol to the look-ahead symbols because users cannot input the error symbol
 		// intentionally.
-		if tsym == p.gram.ParsingTable.ErrorSymbol {
+		if term == p.gram.ParsingTable.ErrorSymbol {
 			continue
 		}
 
-		if tsym == p.gram.ParsingTable.EOFSymbol {
+		if term == p.gram.ParsingTable.EOFSymbol {
 			kinds = append(kinds, "<eof>")
 			continue
 		}
 
-		if alias := aliases[tsym]; alias != "" {
+		if alias := aliases[term]; alias != "" {
 			kinds = append(kinds, alias)
 		} else {
-			term2Kind := p.gram.LexicalSpecification.Maleeni.TerminalToKind
-			kindNames := p.gram.LexicalSpecification.Maleeni.Spec.KindNames
-			kinds = append(kinds, kindNames[term2Kind[tsym]].String())
+			kinds = append(kinds, kindNames[term2Kind[term]].String())
 		}
 	}
 
diff --git a/grammar/grammar.go b/grammar/grammar.go
index 1f4f166..efa0f35 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -1165,7 +1165,6 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error
 			ErrorSymbol:             gram.errorSymbol.num().Int(),
 			ErrorTrapperStates:      tab.errorTrapperStates,
 			RecoverProductions:      recoverProds,
-			ExpectedTerminals:       tab.expectedTerminals,
 		},
 		ASTAction: &spec.ASTAction{
 			Entries: astActEnties,
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go
index a82ef60..aa88ad5 100644
--- a/grammar/parsing_table.go
+++ b/grammar/parsing_table.go
@@ -97,12 +97,11 @@ var (
 )
 
 type ParsingTable struct {
-	actionTable       []actionEntry
-	goToTable         []goToEntry
-	stateCount        int
-	terminalCount     int
-	nonTerminalCount  int
-	expectedTerminals [][]int
+	actionTable      []actionEntry
+	goToTable        []goToEntry
+	stateCount       int
+	terminalCount    int
+	nonTerminalCount int
 
 	// errorTrapperStates's index means a state number, and when `errorTrapperStates[stateNum]` is `1`,
 	// the state has an item having the following form. The `α` and `β` can be empty.
@@ -158,7 +157,6 @@ func (b *lrTableBuilder) build() (*ParsingTable, error) {
 			stateCount:         len(b.automaton.states),
 			terminalCount:      b.termCount,
 			nonTerminalCount:   b.nonTermCount,
-			expectedTerminals:  make([][]int, len(b.automaton.states)),
 			errorTrapperStates: make([]int, len(b.automaton.states)),
 			InitialState:       initialState.num,
 		}
@@ -169,12 +167,9 @@ func (b *lrTableBuilder) build() (*ParsingTable, error) {
 			ptab.errorTrapperStates[state.num] = 1
 		}
 
-		eTerms := map[int]struct{}{}
-
 		for sym, kID := range state.next {
 			nextState := b.automaton.states[kID]
 			if sym.isTerminal() {
-				eTerms[sym.num().Int()] = struct{}{}
 				b.writeShiftAction(ptab, state.num, sym, nextState.num)
 			} else {
 				ptab.writeGoTo(state.num, sym, nextState.num)
@@ -211,23 +206,9 @@ func (b *lrTableBuilder) build() (*ParsingTable, error) {
 			}
 
 			for a := range reducibleItem.lookAhead.symbols {
-				eTerms[a.num().Int()] = struct{}{}
 				b.writeReduceAction(ptab, state.num, a, reducibleProd.num)
 			}
 		}
-
-		ts := make([]int, len(eTerms))
-		{
-			i := 0
-			for t := range eTerms {
-				ts[i] = t
-				i++
-			}
-			sort.Slice(ts, func(i, j int) bool {
-				return ts[i] < ts[j]
-			})
-		}
-		ptab.expectedTerminals[state.num] = ts
 	}
 
 	return ptab, nil
diff --git a/spec/grammar.go b/spec/grammar.go
index 42e6dc2..8403308 100644
--- a/spec/grammar.go
+++ b/spec/grammar.go
@@ -37,7 +37,6 @@ type ParsingTable struct {
 	ErrorSymbol             int      `json:"error_symbol"`
 	ErrorTrapperStates      []int    `json:"error_trapper_states"`
 	RecoverProductions      []int    `json:"recover_productions"`
-	ExpectedTerminals       [][]int  `json:"expected_terminals"`
 }
 
 type ASTAction struct {