LEFT | RIGHT |
(no file at all) | |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // Package ebnf is a library for EBNF grammars. The input is text ([]byte) | 5 // Package ebnf is a library for EBNF grammars. The input is text ([]byte) |
6 // satisfying the following grammar (represented itself in EBNF): | 6 // satisfying the following grammar (represented itself in EBNF): |
7 // | 7 // |
8 // Production = name "=" [ Expression ] "." . | 8 // Production = name "=" [ Expression ] "." . |
9 // Expression = Alternative { "|" Alternative } . | 9 // Expression = Alternative { "|" Alternative } . |
10 // Alternative = Term { Term } . | 10 // Alternative = Term { Term } . |
(...skipping 12 matching lines...) Expand all Loading... |
23 package ebnf | 23 package ebnf |
24 | 24 |
25 import ( | 25 import ( |
26 "go/scanner" | 26 "go/scanner" |
27 "go/token" | 27 "go/token" |
28 "os" | 28 "os" |
29 "unicode" | 29 "unicode" |
30 "utf8" | 30 "utf8" |
31 ) | 31 ) |
32 | 32 |
33 | |
34 // ---------------------------------------------------------------------------- | 33 // ---------------------------------------------------------------------------- |
35 // Internal representation | 34 // Internal representation |
36 | 35 |
37 type ( | 36 type ( |
38 // An Expression node represents a production expression. | 37 // An Expression node represents a production expression. |
39 Expression interface { | 38 Expression interface { |
40 // Pos is the position of the first character of the syntactic c
onstruct | 39 // Pos is the position of the first character of the syntactic c
onstruct |
41 Pos() token.Pos | 40 Pos() token.Pos |
42 } | 41 } |
43 | 42 |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
92 Production struct { | 91 Production struct { |
93 Name *Name | 92 Name *Name |
94 Expr Expression | 93 Expr Expression |
95 } | 94 } |
96 | 95 |
97 // A Grammar is a set of EBNF productions. The map | 96 // A Grammar is a set of EBNF productions. The map |
98 // is indexed by production name. | 97 // is indexed by production name. |
99 // | 98 // |
100 Grammar map[string]*Production | 99 Grammar map[string]*Production |
101 ) | 100 ) |
102 | |
103 | 101 |
104 func (x Alternative) Pos() token.Pos { return x[0].Pos() } // the parser always
generates non-empty Alternative | 102 func (x Alternative) Pos() token.Pos { return x[0].Pos() } // the parser always
generates non-empty Alternative |
105 func (x Sequence) Pos() token.Pos { return x[0].Pos() } // the parser always
generates non-empty Sequences | 103 func (x Sequence) Pos() token.Pos { return x[0].Pos() } // the parser always
generates non-empty Sequences |
106 func (x *Name) Pos() token.Pos { return x.StringPos } | 104 func (x *Name) Pos() token.Pos { return x.StringPos } |
107 func (x *Token) Pos() token.Pos { return x.StringPos } | 105 func (x *Token) Pos() token.Pos { return x.StringPos } |
108 func (x *Range) Pos() token.Pos { return x.Begin.Pos() } | 106 func (x *Range) Pos() token.Pos { return x.Begin.Pos() } |
109 func (x *Group) Pos() token.Pos { return x.Lparen } | 107 func (x *Group) Pos() token.Pos { return x.Lparen } |
110 func (x *Option) Pos() token.Pos { return x.Lbrack } | 108 func (x *Option) Pos() token.Pos { return x.Lbrack } |
111 func (x *Repetition) Pos() token.Pos { return x.Lbrace } | 109 func (x *Repetition) Pos() token.Pos { return x.Lbrace } |
112 func (x *Bad) Pos() token.Pos { return x.TokPos } | 110 func (x *Bad) Pos() token.Pos { return x.TokPos } |
113 func (x *Production) Pos() token.Pos { return x.Name.Pos() } | 111 func (x *Production) Pos() token.Pos { return x.Name.Pos() } |
114 | 112 |
115 | |
116 // ---------------------------------------------------------------------------- | 113 // ---------------------------------------------------------------------------- |
117 // Grammar verification | 114 // Grammar verification |
118 | 115 |
119 func isLexical(name string) bool { | 116 func isLexical(name string) bool { |
120 ch, _ := utf8.DecodeRuneInString(name) | 117 ch, _ := utf8.DecodeRuneInString(name) |
121 return !unicode.IsUpper(ch) | 118 return !unicode.IsUpper(ch) |
122 } | 119 } |
123 | |
124 | 120 |
125 type verifier struct { | 121 type verifier struct { |
126 fset *token.FileSet | 122 fset *token.FileSet |
127 scanner.ErrorVector | 123 scanner.ErrorVector |
128 worklist []*Production | 124 worklist []*Production |
129 reached Grammar // set of productions reached from (and including) the
root production | 125 reached Grammar // set of productions reached from (and including) the
root production |
130 grammar Grammar | 126 grammar Grammar |
131 } | 127 } |
132 | 128 |
133 | |
134 func (v *verifier) error(pos token.Pos, msg string) { | 129 func (v *verifier) error(pos token.Pos, msg string) { |
135 v.Error(v.fset.Position(pos), msg) | 130 v.Error(v.fset.Position(pos), msg) |
136 } | 131 } |
137 | |
138 | 132 |
139 func (v *verifier) push(prod *Production) { | 133 func (v *verifier) push(prod *Production) { |
140 name := prod.Name.String | 134 name := prod.Name.String |
141 if _, found := v.reached[name]; !found { | 135 if _, found := v.reached[name]; !found { |
142 v.worklist = append(v.worklist, prod) | 136 v.worklist = append(v.worklist, prod) |
143 v.reached[name] = prod | 137 v.reached[name] = prod |
144 } | 138 } |
145 } | 139 } |
146 | 140 |
147 | |
148 func (v *verifier) verifyChar(x *Token) int { | 141 func (v *verifier) verifyChar(x *Token) int { |
149 s := x.String | 142 s := x.String |
150 if utf8.RuneCountInString(s) != 1 { | 143 if utf8.RuneCountInString(s) != 1 { |
151 v.error(x.Pos(), "single char expected, found "+s) | 144 v.error(x.Pos(), "single char expected, found "+s) |
152 return 0 | 145 return 0 |
153 } | 146 } |
154 ch, _ := utf8.DecodeRuneInString(s) | 147 ch, _ := utf8.DecodeRuneInString(s) |
155 return ch | 148 return ch |
156 } | 149 } |
157 | |
158 | 150 |
159 func (v *verifier) verifyExpr(expr Expression, lexical bool) { | 151 func (v *verifier) verifyExpr(expr Expression, lexical bool) { |
160 switch x := expr.(type) { | 152 switch x := expr.(type) { |
161 case nil: | 153 case nil: |
162 // empty expression | 154 // empty expression |
163 case Alternative: | 155 case Alternative: |
164 for _, e := range x { | 156 for _, e := range x { |
165 v.verifyExpr(e, lexical) | 157 v.verifyExpr(e, lexical) |
166 } | 158 } |
167 case Sequence: | 159 case Sequence: |
(...skipping 25 matching lines...) Expand all Loading... |
193 v.verifyExpr(x.Body, lexical) | 185 v.verifyExpr(x.Body, lexical) |
194 case *Option: | 186 case *Option: |
195 v.verifyExpr(x.Body, lexical) | 187 v.verifyExpr(x.Body, lexical) |
196 case *Repetition: | 188 case *Repetition: |
197 v.verifyExpr(x.Body, lexical) | 189 v.verifyExpr(x.Body, lexical) |
198 default: | 190 default: |
199 panic("unreachable") | 191 panic("unreachable") |
200 } | 192 } |
201 } | 193 } |
202 | 194 |
203 | |
204 func (v *verifier) verify(fset *token.FileSet, grammar Grammar, start string) { | 195 func (v *verifier) verify(fset *token.FileSet, grammar Grammar, start string) { |
205 // find root production | 196 // find root production |
206 root, found := grammar[start] | 197 root, found := grammar[start] |
207 if !found { | 198 if !found { |
208 // token.NoPos doesn't require a file set; | 199 // token.NoPos doesn't require a file set; |
209 // ok to set v.fset only afterwards | 200 // ok to set v.fset only afterwards |
210 v.error(token.NoPos, "no start production "+start) | 201 v.error(token.NoPos, "no start production "+start) |
211 return | 202 return |
212 } | 203 } |
213 | 204 |
(...skipping 19 matching lines...) Expand all Loading... |
233 // check if all productions were reached | 224 // check if all productions were reached |
234 if len(v.reached) < len(v.grammar) { | 225 if len(v.reached) < len(v.grammar) { |
235 for name, prod := range v.grammar { | 226 for name, prod := range v.grammar { |
236 if _, found := v.reached[name]; !found { | 227 if _, found := v.reached[name]; !found { |
237 v.error(prod.Pos(), name+" is unreachable") | 228 v.error(prod.Pos(), name+" is unreachable") |
238 } | 229 } |
239 } | 230 } |
240 } | 231 } |
241 } | 232 } |
242 | 233 |
243 | |
244 // Verify checks that: | 234 // Verify checks that: |
245 // - all productions used are defined | 235 // - all productions used are defined |
246 // - all productions defined are used when beginning at start | 236 // - all productions defined are used when beginning at start |
247 // - lexical productions refer only to other lexical productions | 237 // - lexical productions refer only to other lexical productions |
248 // | 238 // |
249 // Position information is interpreted relative to the file set fset. | 239 // Position information is interpreted relative to the file set fset. |
250 // | 240 // |
251 func Verify(fset *token.FileSet, grammar Grammar, start string) os.Error { | 241 func Verify(fset *token.FileSet, grammar Grammar, start string) os.Error { |
252 var v verifier | 242 var v verifier |
253 v.verify(fset, grammar, start) | 243 v.verify(fset, grammar, start) |
254 return v.GetError(scanner.Sorted) | 244 return v.GetError(scanner.Sorted) |
255 } | 245 } |
LEFT | RIGHT |