Subversion Repositories openrisc

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package ebnf is a library for EBNF grammars. The input is text ([]byte)
// satisfying the following grammar (represented itself in EBNF):
//
//      Production  = name "=" [ Expression ] "." .
//      Expression  = Alternative { "|" Alternative } .
//      Alternative = Term { Term } .
//      Term        = name | token [ "…" token ] | Group | Option | Repetition .
//      Group       = "(" Expression ")" .
//      Option      = "[" Expression "]" .
//      Repetition  = "{" Expression "}" .
//
// A name is a Go identifier, a token is a Go string, and comments
// and white space follow the same rules as for the Go language.
// Production names starting with an uppercase Unicode letter denote
// non-terminal productions (i.e., productions which allow white-space
// and comments between tokens); all other production names denote
// lexical productions.
//
package ebnf

import (
        "errors"
        "fmt"
        "text/scanner"
        "unicode"
        "unicode/utf8"
)

// ----------------------------------------------------------------------------
// Error handling

type errorList []error

func (list errorList) Err() error {
        if len(list) == 0 {
                return nil
        }
        return list
}

func (list errorList) Error() string {
        switch len(list) {
        case 0:
                return "no errors"
        case 1:
                return list[0].Error()
        }
        return fmt.Sprintf("%s (and %d more errors)", list[0], len(list)-1)
}

func newError(pos scanner.Position, msg string) error {
        return errors.New(fmt.Sprintf("%s: %s", pos, msg))
}

// ----------------------------------------------------------------------------
// Internal representation

type (
        // An Expression node represents a production expression.
        Expression interface {
                // Pos is the position of the first character of the syntactic construct
                Pos() scanner.Position
        }

        // An Alternative node represents a non-empty list of alternative expressions.
        Alternative []Expression // x | y | z

        // A Sequence node represents a non-empty list of sequential expressions.
        Sequence []Expression // x y z

        // A Name node represents a production name.
        Name struct {
                StringPos scanner.Position
                String    string
        }

        // A Token node represents a literal.
        Token struct {
                StringPos scanner.Position
                String    string
        }

        // A List node represents a range of characters.
        Range struct {
                Begin, End *Token // begin ... end
        }

        // A Group node represents a grouped expression.
        Group struct {
                Lparen scanner.Position
                Body   Expression // (body)
        }

        // An Option node represents an optional expression.
        Option struct {
                Lbrack scanner.Position
                Body   Expression // [body]
        }

        // A Repetition node represents a repeated expression.
        Repetition struct {
                Lbrace scanner.Position
                Body   Expression // {body}
        }

        // A Production node represents an EBNF production.
        Production struct {
                Name *Name
                Expr Expression
        }

        // A Bad node stands for pieces of source code that lead to a parse error.
        Bad struct {
                TokPos scanner.Position
                Error  string // parser error message
        }

        // A Grammar is a set of EBNF productions. The map
        // is indexed by production name.
        //
        Grammar map[string]*Production
)

func (x Alternative) Pos() scanner.Position { return x[0].Pos() } // the parser always generates non-empty Alternative
func (x Sequence) Pos() scanner.Position    { return x[0].Pos() } // the parser always generates non-empty Sequences
func (x *Name) Pos() scanner.Position       { return x.StringPos }
func (x *Token) Pos() scanner.Position      { return x.StringPos }
func (x *Range) Pos() scanner.Position      { return x.Begin.Pos() }
func (x *Group) Pos() scanner.Position      { return x.Lparen }
func (x *Option) Pos() scanner.Position     { return x.Lbrack }
func (x *Repetition) Pos() scanner.Position { return x.Lbrace }
func (x *Production) Pos() scanner.Position { return x.Name.Pos() }
func (x *Bad) Pos() scanner.Position        { return x.TokPos }

// ----------------------------------------------------------------------------
// Grammar verification

func isLexical(name string) bool {
        ch, _ := utf8.DecodeRuneInString(name)
        return !unicode.IsUpper(ch)
}

type verifier struct {
        errors   errorList
        worklist []*Production
        reached  Grammar // set of productions reached from (and including) the root production
        grammar  Grammar
}

func (v *verifier) error(pos scanner.Position, msg string) {
        v.errors = append(v.errors, newError(pos, msg))
}

func (v *verifier) push(prod *Production) {
        name := prod.Name.String
        if _, found := v.reached[name]; !found {
                v.worklist = append(v.worklist, prod)
                v.reached[name] = prod
        }
}

func (v *verifier) verifyChar(x *Token) rune {
        s := x.String
        if utf8.RuneCountInString(s) != 1 {
                v.error(x.Pos(), "single char expected, found "+s)
                return 0
        }
        ch, _ := utf8.DecodeRuneInString(s)
        return ch
}

func (v *verifier) verifyExpr(expr Expression, lexical bool) {
        switch x := expr.(type) {
        case nil:
                // empty expression
        case Alternative:
                for _, e := range x {
                        v.verifyExpr(e, lexical)
                }
        case Sequence:
                for _, e := range x {
                        v.verifyExpr(e, lexical)
                }
        case *Name:
                // a production with this name must exist;
                // add it to the worklist if not yet processed
                if prod, found := v.grammar[x.String]; found {
                        v.push(prod)
                } else {
                        v.error(x.Pos(), "missing production "+x.String)
                }
                // within a lexical production references
                // to non-lexical productions are invalid
                if lexical && !isLexical(x.String) {
                        v.error(x.Pos(), "reference to non-lexical production "+x.String)
                }
        case *Token:
                // nothing to do for now
        case *Range:
                i := v.verifyChar(x.Begin)
                j := v.verifyChar(x.End)
                if i >= j {
                        v.error(x.Pos(), "decreasing character range")
                }
        case *Group:
                v.verifyExpr(x.Body, lexical)
        case *Option:
                v.verifyExpr(x.Body, lexical)
        case *Repetition:
                v.verifyExpr(x.Body, lexical)
        case *Bad:
                v.error(x.Pos(), x.Error)
        default:
                panic(fmt.Sprintf("internal error: unexpected type %T", expr))
        }
}

func (v *verifier) verify(grammar Grammar, start string) {
        // find root production
        root, found := grammar[start]
        if !found {
                var noPos scanner.Position
                v.error(noPos, "no start production "+start)
                return
        }

        // initialize verifier
        v.worklist = v.worklist[0:0]
        v.reached = make(Grammar)
        v.grammar = grammar

        // work through the worklist
        v.push(root)
        for {
                n := len(v.worklist) - 1
                if n < 0 {
                        break
                }
                prod := v.worklist[n]
                v.worklist = v.worklist[0:n]
                v.verifyExpr(prod.Expr, isLexical(prod.Name.String))
        }

        // check if all productions were reached
        if len(v.reached) < len(v.grammar) {
                for name, prod := range v.grammar {
                        if _, found := v.reached[name]; !found {
                                v.error(prod.Pos(), name+" is unreachable")
                        }
                }
        }
}

// Verify checks that:
//      - all productions used are defined
//      - all productions defined are used when beginning at start
//      - lexical productions refer only to other lexical productions
//
// Position information is interpreted relative to the file set fset.
//
func Verify(grammar Grammar, start string) error {
        var v verifier
        v.verify(grammar, start)
        return v.errors.Err()
}