diff options
| -rw-r--r-- | driver/parser_test.go | 43 | ||||
| -rw-r--r-- | grammar/grammar.go | 101 | ||||
| -rw-r--r-- | grammar/semantic_error.go | 2 |
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") |