summaryrefslogtreecommitdiff
path: root/src/pkg/ebnf
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/ebnf')
-rw-r--r--src/pkg/ebnf/Makefile2
-rw-r--r--src/pkg/ebnf/ebnf.go91
-rw-r--r--src/pkg/ebnf/ebnf_test.go8
-rw-r--r--src/pkg/ebnf/parser.go68
4 files changed, 89 insertions, 80 deletions
diff --git a/src/pkg/ebnf/Makefile b/src/pkg/ebnf/Makefile
index 4a75c7432..f5555d272 100644
--- a/src/pkg/ebnf/Makefile
+++ b/src/pkg/ebnf/Makefile
@@ -2,7 +2,7 @@
# Use of this source code is governed by a BSD-style
# license that can be found in the LICENSE file.
-include ../../Make.$(GOARCH)
+include ../../Make.inc
TARG=ebnf
GOFILES=\
diff --git a/src/pkg/ebnf/ebnf.go b/src/pkg/ebnf/ebnf.go
index 898a48173..e5aabd582 100644
--- a/src/pkg/ebnf/ebnf.go
+++ b/src/pkg/ebnf/ebnf.go
@@ -23,7 +23,6 @@
package ebnf
import (
- "container/vector"
"go/scanner"
"go/token"
"os"
@@ -39,7 +38,7 @@ type (
// An Expression node represents a production expression.
Expression interface {
// Pos is the position of the first character of the syntactic construct
- Pos() token.Position
+ Pos() token.Pos
}
// An Alternative node represents a non-empty list of alternative expressions.
@@ -50,14 +49,14 @@ type (
// A Name node represents a production name.
Name struct {
- token.Position
- String string
+ StringPos token.Pos
+ String string
}
// A Token node represents a literal.
Token struct {
- token.Position
- String string
+ StringPos token.Pos
+ String string
}
// A List node represents a range of characters.
@@ -67,20 +66,20 @@ type (
// A Group node represents a grouped expression.
Group struct {
- token.Position
- Body Expression // (body)
+ Lparen token.Pos
+ Body Expression // (body)
}
// An Option node represents an optional expression.
Option struct {
- token.Position
- Body Expression // [body]
+ Lbrack token.Pos
+ Body Expression // [body]
}
// A Repetition node represents a repeated expression.
Repetition struct {
- token.Position
- Body Expression // {body}
+ Lbrace token.Pos
+ Body Expression // {body}
}
// A Production node represents an EBNF production.
@@ -96,20 +95,15 @@ type (
)
-func (x Alternative) Pos() token.Position {
- return x[0].Pos() // the parser always generates non-empty Alternative
-}
-
-
-func (x Sequence) Pos() token.Position {
- return x[0].Pos() // the parser always generates non-empty Sequences
-}
-
-
-func (x Range) Pos() token.Position { return x.Begin.Pos() }
-
-
-func (p *Production) Pos() token.Position { return p.Name.Pos() }
+func (x Alternative) Pos() token.Pos { return x[0].Pos() } // the parser always generates non-empty Alternative
+func (x Sequence) Pos() token.Pos { return x[0].Pos() } // the parser always generates non-empty Sequences
+func (x *Name) Pos() token.Pos { return x.StringPos }
+func (x *Token) Pos() token.Pos { return x.StringPos }
+func (x *Range) Pos() token.Pos { return x.Begin.Pos() }
+func (x *Group) Pos() token.Pos { return x.Lparen }
+func (x *Option) Pos() token.Pos { return x.Lbrack }
+func (x *Repetition) Pos() token.Pos { return x.Lbrace }
+func (x *Production) Pos() token.Pos { return x.Name.Pos() }
// ----------------------------------------------------------------------------
@@ -122,17 +116,23 @@ func isLexical(name string) bool {
type verifier struct {
+ fset *token.FileSet
scanner.ErrorVector
- worklist vector.Vector
+ worklist []*Production
reached Grammar // set of productions reached from (and including) the root production
grammar Grammar
}
+func (v *verifier) error(pos token.Pos, msg string) {
+ v.Error(v.fset.Position(pos), msg)
+}
+
+
func (v *verifier) push(prod *Production) {
name := prod.Name.String
if _, found := v.reached[name]; !found {
- v.worklist.Push(prod)
+ v.worklist = append(v.worklist, prod)
v.reached[name] = prod
}
}
@@ -141,7 +141,7 @@ func (v *verifier) push(prod *Production) {
func (v *verifier) verifyChar(x *Token) int {
s := x.String
if utf8.RuneCountInString(s) != 1 {
- v.Error(x.Pos(), "single char expected, found "+s)
+ v.error(x.Pos(), "single char expected, found "+s)
return 0
}
ch, _ := utf8.DecodeRuneInString(s)
@@ -167,12 +167,12 @@ func (v *verifier) verifyExpr(expr Expression, lexical bool) {
if prod, found := v.grammar[x.String]; found {
v.push(prod)
} else {
- v.Error(x.Pos(), "missing production "+x.String)
+ 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)
+ v.error(x.Pos(), "reference to non-lexical production "+x.String)
}
case *Token:
// nothing to do for now
@@ -180,7 +180,7 @@ func (v *verifier) verifyExpr(expr Expression, lexical bool) {
i := v.verifyChar(x.Begin)
j := v.verifyChar(x.End)
if i >= j {
- v.Error(x.Pos(), "decreasing character range")
+ v.error(x.Pos(), "decreasing character range")
}
case *Group:
v.verifyExpr(x.Body, lexical)
@@ -194,25 +194,32 @@ func (v *verifier) verifyExpr(expr Expression, lexical bool) {
}
-func (v *verifier) verify(grammar Grammar, start string) {
+func (v *verifier) verify(fset *token.FileSet, grammar Grammar, start string) {
// find root production
root, found := grammar[start]
if !found {
- var noPos token.Position
- v.Error(noPos, "no start production "+start)
+ // token.NoPos doesn't require a file set;
+ // ok to set v.fset only afterwards
+ v.error(token.NoPos, "no start production "+start)
return
}
// initialize verifier
+ v.fset = fset
v.ErrorVector.Reset()
- v.worklist.Resize(0, 0)
+ v.worklist = v.worklist[0:0]
v.reached = make(Grammar)
v.grammar = grammar
// work through the worklist
v.push(root)
- for v.worklist.Len() > 0 {
- prod := v.worklist.Pop().(*Production)
+ 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))
}
@@ -220,7 +227,7 @@ func (v *verifier) verify(grammar Grammar, start string) {
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")
+ v.error(prod.Pos(), name+" is unreachable")
}
}
}
@@ -232,8 +239,10 @@ func (v *verifier) verify(grammar Grammar, start string) {
// - all productions defined are used when beginning at start
// - lexical productions refer only to other lexical productions
//
-func Verify(grammar Grammar, start string) os.Error {
+// Position information is interpreted relative to the file set fset.
+//
+func Verify(fset *token.FileSet, grammar Grammar, start string) os.Error {
var v verifier
- v.verify(grammar, start)
+ v.verify(fset, grammar, start)
return v.GetError(scanner.Sorted)
}
diff --git a/src/pkg/ebnf/ebnf_test.go b/src/pkg/ebnf/ebnf_test.go
index a88d19bed..bbe530c27 100644
--- a/src/pkg/ebnf/ebnf_test.go
+++ b/src/pkg/ebnf/ebnf_test.go
@@ -5,11 +5,15 @@
package ebnf
import (
+ "go/token"
"io/ioutil"
"testing"
)
+var fset = token.NewFileSet()
+
+
var grammars = []string{
`Program = .
`,
@@ -40,11 +44,11 @@ var grammars = []string{
func check(t *testing.T, filename string, src []byte) {
- grammar, err := Parse(filename, src)
+ grammar, err := Parse(fset, filename, src)
if err != nil {
t.Errorf("Parse(%s) failed: %v", src, err)
}
- if err = Verify(grammar, "Program"); err != nil {
+ if err = Verify(fset, grammar, "Program"); err != nil {
t.Errorf("Verify(%s) failed: %v", src, err)
}
}
diff --git a/src/pkg/ebnf/parser.go b/src/pkg/ebnf/parser.go
index 649587879..ef72d91fd 100644
--- a/src/pkg/ebnf/parser.go
+++ b/src/pkg/ebnf/parser.go
@@ -5,7 +5,6 @@
package ebnf
import (
- "container/vector"
"go/scanner"
"go/token"
"os"
@@ -14,11 +13,12 @@ import (
type parser struct {
+ fset *token.FileSet
scanner.ErrorVector
scanner scanner.Scanner
- pos token.Position // token position
- tok token.Token // one token look-ahead
- lit []byte // token literal
+ pos token.Pos // token position
+ tok token.Token // one token look-ahead
+ lit []byte // token literal
}
@@ -32,9 +32,14 @@ func (p *parser) next() {
}
-func (p *parser) errorExpected(pos token.Position, msg string) {
+func (p *parser) error(pos token.Pos, msg string) {
+ p.Error(p.fset.Position(pos), msg)
+}
+
+
+func (p *parser) errorExpected(pos token.Pos, msg string) {
msg = "expected " + msg
- if pos.Offset == p.pos.Offset {
+ if pos == p.pos {
// the error happened at the current position;
// make the error message more specific
msg += ", found '" + p.tok.String() + "'"
@@ -42,11 +47,11 @@ func (p *parser) errorExpected(pos token.Position, msg string) {
msg += " " + string(p.lit)
}
}
- p.Error(pos, msg)
+ p.error(pos, msg)
}
-func (p *parser) expect(tok token.Token) token.Position {
+func (p *parser) expect(tok token.Token) token.Pos {
pos := p.pos
if p.tok != tok {
p.errorExpected(pos, "'"+tok.String()+"'")
@@ -116,36 +121,30 @@ func (p *parser) parseTerm() (x Expression) {
func (p *parser) parseSequence() Expression {
- var list vector.Vector
+ var list Sequence
for x := p.parseTerm(); x != nil; x = p.parseTerm() {
- list.Push(x)
+ list = append(list, x)
}
// no need for a sequence if list.Len() < 2
- switch list.Len() {
+ switch len(list) {
case 0:
return nil
case 1:
- return list.At(0).(Expression)
+ return list[0]
}
- // convert list into a sequence
- seq := make(Sequence, list.Len())
- for i := 0; i < list.Len(); i++ {
- seq[i] = list.At(i).(Expression)
- }
- return seq
+ return list
}
func (p *parser) parseExpression() Expression {
- var list vector.Vector
+ var list Alternative
for {
- x := p.parseSequence()
- if x != nil {
- list.Push(x)
+ if x := p.parseSequence(); x != nil {
+ list = append(list, x)
}
if p.tok != token.OR {
break
@@ -154,19 +153,14 @@ func (p *parser) parseExpression() Expression {
}
// no need for an Alternative node if list.Len() < 2
- switch list.Len() {
+ switch len(list) {
case 0:
return nil
case 1:
- return list.At(0).(Expression)
+ return list[0]
}
- // convert list into an Alternative node
- alt := make(Alternative, list.Len())
- for i := 0; i < list.Len(); i++ {
- alt[i] = list.At(i).(Expression)
- }
- return alt
+ return list
}
@@ -179,10 +173,11 @@ func (p *parser) parseProduction() *Production {
}
-func (p *parser) parse(filename string, src []byte) Grammar {
+func (p *parser) parse(fset *token.FileSet, filename string, src []byte) Grammar {
// initialize parser
+ p.fset = fset
p.ErrorVector.Reset()
- p.scanner.Init(filename, src, p, 0)
+ p.scanner.Init(fset, filename, src, p, 0)
p.next() // initializes pos, tok, lit
grammar := make(Grammar)
@@ -192,7 +187,7 @@ func (p *parser) parse(filename string, src []byte) Grammar {
if _, found := grammar[name]; !found {
grammar[name] = prod
} else {
- p.Error(prod.Pos(), name+" declared already")
+ p.error(prod.Pos(), name+" declared already")
}
}
@@ -203,10 +198,11 @@ func (p *parser) parse(filename string, src []byte) 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.
+// more than once. Position information is recorded relative
+// to the file set fset.
//
-func Parse(filename string, src []byte) (Grammar, os.Error) {
+func Parse(fset *token.FileSet, filename string, src []byte) (Grammar, os.Error) {
var p parser
- grammar := p.parse(filename, src)
+ grammar := p.parse(fset, filename, src)
return grammar, p.GetError(scanner.Sorted)
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-01 18:35:13 +0000