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

import (
        "io"
        "strconv"
        "text/scanner"
)

type parser struct {
        errors  errorList
        scanner scanner.Scanner
        pos     scanner.Position // token position
        tok     rune             // one token look-ahead
        lit     string           // token literal
}

func (p *parser) next() {
        p.tok = p.scanner.Scan()
        p.pos = p.scanner.Position
        p.lit = p.scanner.TokenText()
}

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

func (p *parser) errorExpected(pos scanner.Position, msg string) {
        msg = `expected "` + msg + `"`
        if pos.Offset == p.pos.Offset {
                // the error happened at the current position;
                // make the error message more specific
                msg += ", found " + scanner.TokenString(p.tok)
                if p.tok < 0 {
                        msg += " " + p.lit
                }
        }
        p.error(pos, msg)
}

func (p *parser) expect(tok rune) scanner.Position {
        pos := p.pos
        if p.tok != tok {
                p.errorExpected(pos, scanner.TokenString(tok))
        }
        p.next() // make progress in any case
        return pos
}

func (p *parser) parseIdentifier() *Name {
        pos := p.pos
        name := p.lit
        p.expect(scanner.Ident)
        return &Name{pos, name}
}

func (p *parser) parseToken() *Token {
        pos := p.pos
        value := ""
        if p.tok == scanner.String {
                value, _ = strconv.Unquote(p.lit)
                // Unquote may fail with an error, but only if the scanner found
                // an illegal string in the first place. In this case the error
                // has already been reported.
                p.next()
        } else {
                p.expect(scanner.String)
        }
        return &Token{pos, value}
}

// ParseTerm returns nil if no term was found.
func (p *parser) parseTerm() (x Expression) {
        pos := p.pos

        switch p.tok {
        case scanner.Ident:
                x = p.parseIdentifier()

        case scanner.String:
                tok := p.parseToken()
                x = tok
                const ellipsis = '…' // U+2026, the horizontal ellipsis character
                if p.tok == ellipsis {
                        p.next()
                        x = &Range{tok, p.parseToken()}
                }

        case '(':
                p.next()
                x = &Group{pos, p.parseExpression()}
                p.expect(')')

        case '[':
                p.next()
                x = &Option{pos, p.parseExpression()}
                p.expect(']')

        case '{':
                p.next()
                x = &Repetition{pos, p.parseExpression()}
                p.expect('}')
        }

        return x
}

func (p *parser) parseSequence() Expression {
        var list Sequence

        for x := p.parseTerm(); x != nil; x = p.parseTerm() {
                list = append(list, x)
        }

        // no need for a sequence if list.Len() < 2
        switch len(list) {
        case 0:
                p.errorExpected(p.pos, "term")
                return &Bad{p.pos, "term expected"}
        case 1:
                return list[0]
        }

        return list
}

func (p *parser) parseExpression() Expression {
        var list Alternative

        for {
                list = append(list, p.parseSequence())
                if p.tok != '|' {
                        break
                }
                p.next()
        }
        // len(list) > 0

        // no need for an Alternative node if list.Len() < 2
        if len(list) == 1 {
                return list[0]
        }

        return list
}

func (p *parser) parseProduction() *Production {
        name := p.parseIdentifier()
        p.expect('=')
        var expr Expression
        if p.tok != '.' {
                expr = p.parseExpression()
        }
        p.expect('.')
        return &Production{name, expr}
}

func (p *parser) parse(filename string, src io.Reader) Grammar {
        p.scanner.Init(src)
        p.scanner.Filename = filename
        p.next() // initializes pos, tok, lit

        grammar := make(Grammar)
        for p.tok != scanner.EOF {
                prod := p.parseProduction()
                name := prod.Name.String
                if _, found := grammar[name]; !found {
                        grammar[name] = prod
                } else {
                        p.error(prod.Pos(), name+" declared already")
                }
        }

        return grammar
}

// Parse parses a set of EBNF productions from source src.
// It returns a set of productions. Errors are reported
// for incorrect syntax and if a production is declared
// more than once; the filename is used only for error
// positions.
//
func Parse(filename string, src io.Reader) (Grammar, error) {
        var p parser
        grammar := p.parse(filename, src)
        return grammar, p.errors.Err()
}