| // 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 || p.tok == scanner.RawString { |
| 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, scanner.RawString: |
| 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() |
| } |