// Copyright 2009 The Go Authors. All rights reserved.
|
// Copyright 2009 The Go Authors. All rights reserved.
|
// Use of this source code is governed by a BSD-style
|
// Use of this source code is governed by a BSD-style
|
// license that can be found in the LICENSE file.
|
// license that can be found in the LICENSE file.
|
|
|
package ebnf
|
package ebnf
|
|
|
import (
|
import (
|
"io"
|
"io"
|
"strconv"
|
"strconv"
|
"text/scanner"
|
"text/scanner"
|
)
|
)
|
|
|
type parser struct {
|
type parser struct {
|
errors errorList
|
errors errorList
|
scanner scanner.Scanner
|
scanner scanner.Scanner
|
pos scanner.Position // token position
|
pos scanner.Position // token position
|
tok rune // one token look-ahead
|
tok rune // one token look-ahead
|
lit string // token literal
|
lit string // token literal
|
}
|
}
|
|
|
func (p *parser) next() {
|
func (p *parser) next() {
|
p.tok = p.scanner.Scan()
|
p.tok = p.scanner.Scan()
|
p.pos = p.scanner.Position
|
p.pos = p.scanner.Position
|
p.lit = p.scanner.TokenText()
|
p.lit = p.scanner.TokenText()
|
}
|
}
|
|
|
func (p *parser) error(pos scanner.Position, msg string) {
|
func (p *parser) error(pos scanner.Position, msg string) {
|
p.errors = append(p.errors, newError(pos, msg))
|
p.errors = append(p.errors, newError(pos, msg))
|
}
|
}
|
|
|
func (p *parser) errorExpected(pos scanner.Position, msg string) {
|
func (p *parser) errorExpected(pos scanner.Position, msg string) {
|
msg = `expected "` + msg + `"`
|
msg = `expected "` + msg + `"`
|
if pos.Offset == p.pos.Offset {
|
if pos.Offset == p.pos.Offset {
|
// the error happened at the current position;
|
// the error happened at the current position;
|
// make the error message more specific
|
// make the error message more specific
|
msg += ", found " + scanner.TokenString(p.tok)
|
msg += ", found " + scanner.TokenString(p.tok)
|
if p.tok < 0 {
|
if p.tok < 0 {
|
msg += " " + p.lit
|
msg += " " + p.lit
|
}
|
}
|
}
|
}
|
p.error(pos, msg)
|
p.error(pos, msg)
|
}
|
}
|
|
|
func (p *parser) expect(tok rune) scanner.Position {
|
func (p *parser) expect(tok rune) scanner.Position {
|
pos := p.pos
|
pos := p.pos
|
if p.tok != tok {
|
if p.tok != tok {
|
p.errorExpected(pos, scanner.TokenString(tok))
|
p.errorExpected(pos, scanner.TokenString(tok))
|
}
|
}
|
p.next() // make progress in any case
|
p.next() // make progress in any case
|
return pos
|
return pos
|
}
|
}
|
|
|
func (p *parser) parseIdentifier() *Name {
|
func (p *parser) parseIdentifier() *Name {
|
pos := p.pos
|
pos := p.pos
|
name := p.lit
|
name := p.lit
|
p.expect(scanner.Ident)
|
p.expect(scanner.Ident)
|
return &Name{pos, name}
|
return &Name{pos, name}
|
}
|
}
|
|
|
func (p *parser) parseToken() *Token {
|
func (p *parser) parseToken() *Token {
|
pos := p.pos
|
pos := p.pos
|
value := ""
|
value := ""
|
if p.tok == scanner.String {
|
if p.tok == scanner.String {
|
value, _ = strconv.Unquote(p.lit)
|
value, _ = strconv.Unquote(p.lit)
|
// Unquote may fail with an error, but only if the scanner found
|
// Unquote may fail with an error, but only if the scanner found
|
// an illegal string in the first place. In this case the error
|
// an illegal string in the first place. In this case the error
|
// has already been reported.
|
// has already been reported.
|
p.next()
|
p.next()
|
} else {
|
} else {
|
p.expect(scanner.String)
|
p.expect(scanner.String)
|
}
|
}
|
return &Token{pos, value}
|
return &Token{pos, value}
|
}
|
}
|
|
|
// ParseTerm returns nil if no term was found.
|
// ParseTerm returns nil if no term was found.
|
func (p *parser) parseTerm() (x Expression) {
|
func (p *parser) parseTerm() (x Expression) {
|
pos := p.pos
|
pos := p.pos
|
|
|
switch p.tok {
|
switch p.tok {
|
case scanner.Ident:
|
case scanner.Ident:
|
x = p.parseIdentifier()
|
x = p.parseIdentifier()
|
|
|
case scanner.String:
|
case scanner.String:
|
tok := p.parseToken()
|
tok := p.parseToken()
|
x = tok
|
x = tok
|
const ellipsis = '…' // U+2026, the horizontal ellipsis character
|
const ellipsis = '…' // U+2026, the horizontal ellipsis character
|
if p.tok == ellipsis {
|
if p.tok == ellipsis {
|
p.next()
|
p.next()
|
x = &Range{tok, p.parseToken()}
|
x = &Range{tok, p.parseToken()}
|
}
|
}
|
|
|
case '(':
|
case '(':
|
p.next()
|
p.next()
|
x = &Group{pos, p.parseExpression()}
|
x = &Group{pos, p.parseExpression()}
|
p.expect(')')
|
p.expect(')')
|
|
|
case '[':
|
case '[':
|
p.next()
|
p.next()
|
x = &Option{pos, p.parseExpression()}
|
x = &Option{pos, p.parseExpression()}
|
p.expect(']')
|
p.expect(']')
|
|
|
case '{':
|
case '{':
|
p.next()
|
p.next()
|
x = &Repetition{pos, p.parseExpression()}
|
x = &Repetition{pos, p.parseExpression()}
|
p.expect('}')
|
p.expect('}')
|
}
|
}
|
|
|
return x
|
return x
|
}
|
}
|
|
|
func (p *parser) parseSequence() Expression {
|
func (p *parser) parseSequence() Expression {
|
var list Sequence
|
var list Sequence
|
|
|
for x := p.parseTerm(); x != nil; x = p.parseTerm() {
|
for x := p.parseTerm(); x != nil; x = p.parseTerm() {
|
list = append(list, x)
|
list = append(list, x)
|
}
|
}
|
|
|
// no need for a sequence if list.Len() < 2
|
// no need for a sequence if list.Len() < 2
|
switch len(list) {
|
switch len(list) {
|
case 0:
|
case 0:
|
p.errorExpected(p.pos, "term")
|
p.errorExpected(p.pos, "term")
|
return &Bad{p.pos, "term expected"}
|
return &Bad{p.pos, "term expected"}
|
case 1:
|
case 1:
|
return list[0]
|
return list[0]
|
}
|
}
|
|
|
return list
|
return list
|
}
|
}
|
|
|
func (p *parser) parseExpression() Expression {
|
func (p *parser) parseExpression() Expression {
|
var list Alternative
|
var list Alternative
|
|
|
for {
|
for {
|
list = append(list, p.parseSequence())
|
list = append(list, p.parseSequence())
|
if p.tok != '|' {
|
if p.tok != '|' {
|
break
|
break
|
}
|
}
|
p.next()
|
p.next()
|
}
|
}
|
// len(list) > 0
|
// len(list) > 0
|
|
|
// no need for an Alternative node if list.Len() < 2
|
// no need for an Alternative node if list.Len() < 2
|
if len(list) == 1 {
|
if len(list) == 1 {
|
return list[0]
|
return list[0]
|
}
|
}
|
|
|
return list
|
return list
|
}
|
}
|
|
|
func (p *parser) parseProduction() *Production {
|
func (p *parser) parseProduction() *Production {
|
name := p.parseIdentifier()
|
name := p.parseIdentifier()
|
p.expect('=')
|
p.expect('=')
|
var expr Expression
|
var expr Expression
|
if p.tok != '.' {
|
if p.tok != '.' {
|
expr = p.parseExpression()
|
expr = p.parseExpression()
|
}
|
}
|
p.expect('.')
|
p.expect('.')
|
return &Production{name, expr}
|
return &Production{name, expr}
|
}
|
}
|
|
|
func (p *parser) parse(filename string, src io.Reader) Grammar {
|
func (p *parser) parse(filename string, src io.Reader) Grammar {
|
p.scanner.Init(src)
|
p.scanner.Init(src)
|
p.scanner.Filename = filename
|
p.scanner.Filename = filename
|
p.next() // initializes pos, tok, lit
|
p.next() // initializes pos, tok, lit
|
|
|
grammar := make(Grammar)
|
grammar := make(Grammar)
|
for p.tok != scanner.EOF {
|
for p.tok != scanner.EOF {
|
prod := p.parseProduction()
|
prod := p.parseProduction()
|
name := prod.Name.String
|
name := prod.Name.String
|
if _, found := grammar[name]; !found {
|
if _, found := grammar[name]; !found {
|
grammar[name] = prod
|
grammar[name] = prod
|
} else {
|
} else {
|
p.error(prod.Pos(), name+" declared already")
|
p.error(prod.Pos(), name+" declared already")
|
}
|
}
|
}
|
}
|
|
|
return grammar
|
return grammar
|
}
|
}
|
|
|
// Parse parses a set of EBNF productions from source src.
|
// Parse parses a set of EBNF productions from source src.
|
// It returns a set of productions. Errors are reported
|
// It returns a set of productions. Errors are reported
|
// for incorrect syntax and if a production is declared
|
// for incorrect syntax and if a production is declared
|
// more than once; the filename is used only for error
|
// more than once; the filename is used only for error
|
// positions.
|
// positions.
|
//
|
//
|
func Parse(filename string, src io.Reader) (Grammar, error) {
|
func Parse(filename string, src io.Reader) (Grammar, error) {
|
var p parser
|
var p parser
|
grammar := p.parse(filename, src)
|
grammar := p.parse(filename, src)
|
return grammar, p.errors.Err()
|
return grammar, p.errors.Err()
|
}
|
}
|
|
|
