Detect unused-symbol error

When there are productions and terminals that are cannot be reached from the start symbol, the compiler reports an error.

3 files changed, 145 insertions, 1 deletions

diff --git a/driver/parser_test.go b/driver/parser_test.go
index 73d8fac..e32e34c 100644
--- a/driver/parser_test.go
+++ b/driver/parser_test.go
@@ -148,6 +148,46 @@ bar_text: "bar";
 				),
 			),
 		},
+		// Production `b` is unused.
+		{
+			specSrc: `
+a
+    : foo
+    ;
+b
+    : foo;
+foo: "foo";
+`,
+			src:     `foo`,
+			specErr: true,
+		},
+		// Terminal `bar` is unused.
+		{
+			specSrc: `
+s
+    : foo
+    ;
+foo: "foo";
+bar: "bar";
+`,
+			src:     `foo`,
+			specErr: true,
+		},
+		// Production `b` and terminal `bar` is unused.
+		{
+			specSrc: `
+a
+    : foo
+    ;
+b
+    : bar
+    ;
+foo: "foo";
+bar: "bar";
+`,
+			src:     `foo`,
+			specErr: true,
+		},
 		{
 			specSrc: `
 mode_tran_seq
@@ -258,6 +298,9 @@ bar: "bar";
 		{
 			specSrc: `
 s
+    : foo
+    ;
+foo
     : "foo" #ast #(s $1...)
     ;
 `,
diff --git a/grammar/grammar.go b/grammar/grammar.go
index 6130e55..20bddfe 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -43,6 +43,31 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
 		return nil, err
 	}
 
+	unusedProds, unusedTerms, err := findUnusedSymbols(b.AST)
+	if err != nil {
+		return nil, err
+	}
+
+	for _, sym := range symTabAndLexSpec.skipSyms {
+		delete(unusedTerms, sym)
+	}
+
+	for sym, prod := range unusedProds {
+		b.errs = append(b.errs, &verr.SpecError{
+			Cause:  semErrUnusedProduction,
+			Detail: sym,
+			Row:    prod.Pos.Row,
+		})
+	}
+
+	for sym, prod := range unusedTerms {
+		b.errs = append(b.errs, &verr.SpecError{
+			Cause:  semErrUnusedTerminal,
+			Detail: sym,
+			Row:    prod.Pos.Row,
+		})
+	}
+
 	if len(b.errs) > 0 {
 		return nil, b.errs
 	}
@@ -58,17 +83,89 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
 	}, nil
 }
 
+func findUnusedSymbols(root *spec.RootNode) (map[string]*spec.ProductionNode, map[string]*spec.ProductionNode, error) {
+	prods := map[string]*spec.ProductionNode{}
+	lexProds := map[string]*spec.ProductionNode{}
+	check := map[string]bool{}
+	{
+		for _, p := range root.Productions {
+			prods[p.LHS] = p
+			check[p.LHS] = false
+			for _, alt := range p.RHS {
+				for _, e := range alt.Elements {
+					if e.ID == "" {
+						continue
+					}
+					check[e.ID] = false
+				}
+			}
+		}
+		for _, p := range root.LexProductions {
+			lexProds[p.LHS] = p
+			check[p.LHS] = false
+		}
+
+		start := root.Productions[0]
+		check[start.LHS] = true
+		markUsedSymbols(check, prods, start)
+	}
+
+	unusedProds := map[string]*spec.ProductionNode{}
+	unusedTerms := map[string]*spec.ProductionNode{}
+	for sym, used := range check {
+		if used {
+			continue
+		}
+
+		if p, ok := prods[sym]; ok {
+			unusedProds[sym] = p
+			continue
+		}
+		if p, ok := lexProds[sym]; ok {
+			unusedTerms[sym] = p
+			continue
+		}
+		return nil, nil, fmt.Errorf("a definition of unused production was not found: %v", sym)
+	}
+
+	return unusedProds, unusedTerms, nil
+}
+
+func markUsedSymbols(check map[string]bool, prods map[string]*spec.ProductionNode, prod *spec.ProductionNode) {
+	for _, alt := range prod.RHS {
+		for _, e := range alt.Elements {
+			if e.ID == "" {
+				continue
+			}
+
+			check[e.ID] = true
+
+			p, ok := prods[e.ID]
+			if !ok {
+				continue
+			}
+
+			// Remove a production to avoid inifinite recursion.
+			delete(prods, prod.LHS)
+
+			markUsedSymbols(check, prods, p)
+		}
+	}
+}
+
 type symbolTableAndLexSpec struct {
 	symTab      *symbolTable
 	anonPat2Sym map[string]symbol
 	sym2AnonPat map[symbol]string
 	lexSpec     *mlspec.LexSpec
 	skip        []mlspec.LexKind
+	skipSyms    []string
 }
 
 func (b *GrammarBuilder) genSymbolTableAndLexSpec(root *spec.RootNode) (*symbolTableAndLexSpec, error) {
 	symTab := newSymbolTable()
 	skipKinds := []mlspec.LexKind{}
+	skipSyms := []string{}
 	entries := []*mlspec.LexEntry{}
 	for _, prod := range root.LexProductions {
 		if _, exist := symTab.toSymbol(prod.LHS); exist {
@@ -95,6 +192,7 @@ func (b *GrammarBuilder) genSymbolTableAndLexSpec(root *spec.RootNode) (*symbolT
 		}
 		if skip {
 			skipKinds = append(skipKinds, mlspec.LexKind(prod.LHS))
+			skipSyms = append(skipSyms, prod.LHS)
 		}
 		entries = append(entries, entry)
 	}
@@ -171,7 +269,8 @@ func (b *GrammarBuilder) genSymbolTableAndLexSpec(root *spec.RootNode) (*symbolT
 		lexSpec: &mlspec.LexSpec{
 			Entries: entries,
 		},
-		skip: skipKinds,
+		skip:     skipKinds,
+		skipSyms: skipSyms,
 	}, nil
 }
 
diff --git a/grammar/semantic_error.go b/grammar/semantic_error.go
index ca84cf0..9006124 100644
--- a/grammar/semantic_error.go
+++ b/grammar/semantic_error.go
@@ -15,6 +15,8 @@ func (e *SemanticError) Error() string {
 }
 
 var (
+	semErrUnusedProduction    = newSemanticError("unused production")
+	semErrUnusedTerminal      = newSemanticError("unused terminal")
 	semErrNoProduction        = newSemanticError("a grammar needs at least one production")
 	semErrUndefinedSym        = newSemanticError("undefined symbol")
 	semErrDuplicateProduction = newSemanticError("duplicate production")