LEFT | RIGHT |
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 | 5 package ebnf |
6 | 6 |
7 import ( | 7 import ( |
8 "go/scanner" | 8 "go/scanner" |
9 "go/token" | 9 "go/token" |
10 "os" | 10 "os" |
11 "strconv" | 11 "strconv" |
12 ) | 12 ) |
13 | 13 |
14 | 14 |
15 type parser struct { | 15 type parser struct { |
16 fset *token.FileSet | 16 fset *token.FileSet |
17 scanner.ErrorVector | 17 scanner.ErrorVector |
18 scanner scanner.Scanner | 18 scanner scanner.Scanner |
19 » pos token.Pos ÿ// token positionÿ | 19 » pos token.Pos // token position |
20 » tok token.Token ÿ// one token look-aheadÿ | 20 » tok token.Token // one token look-ahead |
21 » lit string ÿ// token literalÿ | 21 » lit string // token literal |
22 } | 22 } |
23 | 23 |
24 | 24 |
25 func (p *parser) next() { | 25 func (p *parser) next() { |
26 p.pos, p.tok, p.lit = p.scanner.Scan() | 26 p.pos, p.tok, p.lit = p.scanner.Scan() |
27 if p.tok.IsKeyword() { | 27 if p.tok.IsKeyword() { |
28 » » ÿ// TODO Should keyword mapping always happen outside scanner?ÿ | 28 » » // TODO Should keyword mapping always happen outside scanner? |
29 » » ÿ// Or should there be a flag to scanner to enable keyword
mapping?ÿ | 29 » » // Or should there be a flag to scanner to enable keyword m
apping? |
30 p.tok = token.IDENT | 30 p.tok = token.IDENT |
31 } | 31 } |
32 } | 32 } |
33 | 33 |
34 | 34 |
35 func (p *parser) error(pos token.Pos, msg string) { | 35 func (p *parser) error(pos token.Pos, msg string) { |
36 p.Error(p.fset.Position(pos), msg) | 36 p.Error(p.fset.Position(pos), msg) |
37 } | 37 } |
38 | 38 |
39 | 39 |
40 func (p *parser) errorExpected(pos token.Pos, msg string) { | 40 func (p *parser) errorExpected(pos token.Pos, msg string) { |
41 msg = "expected " + msg | 41 msg = "expected " + msg |
42 if pos == p.pos { | 42 if pos == p.pos { |
43 » » ÿ// the error happened at the current position;ÿ | 43 » » // the error happened at the current position; |
44 » » ÿ// make the error message more specificÿ | 44 » » // make the error message more specific |
45 msg += ", found '" + p.tok.String() + "'" | 45 msg += ", found '" + p.tok.String() + "'" |
46 if p.tok.IsLiteral() { | 46 if p.tok.IsLiteral() { |
47 msg += " " + p.lit | 47 msg += " " + p.lit |
48 } | 48 } |
49 } | 49 } |
50 p.error(pos, msg) | 50 p.error(pos, msg) |
51 } | 51 } |
52 | 52 |
53 | 53 |
54 func (p *parser) expect(tok token.Token) token.Pos { | 54 func (p *parser) expect(tok token.Token) token.Pos { |
55 pos := p.pos | 55 pos := p.pos |
56 if p.tok != tok { | 56 if p.tok != tok { |
57 p.errorExpected(pos, "'"+tok.String()+"'") | 57 p.errorExpected(pos, "'"+tok.String()+"'") |
58 } | 58 } |
59 » p.next() ÿ// make progress in any caseÿ | 59 » p.next() // make progress in any case |
60 return pos | 60 return pos |
61 } | 61 } |
62 | 62 |
63 | 63 |
64 func (p *parser) parseIdentifier() *Name { | 64 func (p *parser) parseIdentifier() *Name { |
65 pos := p.pos | 65 pos := p.pos |
66 name := p.lit | 66 name := p.lit |
67 p.expect(token.IDENT) | 67 p.expect(token.IDENT) |
68 return &Name{pos, name} | 68 return &Name{pos, name} |
69 } | 69 } |
70 | 70 |
71 | 71 |
72 func (p *parser) parseToken() *Token { | 72 func (p *parser) parseToken() *Token { |
73 pos := p.pos | 73 pos := p.pos |
74 value := "" | 74 value := "" |
75 if p.tok == token.STRING { | 75 if p.tok == token.STRING { |
76 value, _ = strconv.Unquote(p.lit) | 76 value, _ = strconv.Unquote(p.lit) |
77 » » ÿ// Unquote may fail with an error, but only if the scanner foun
dÿ | 77 » » // Unquote may fail with an error, but only if the scanner found |
78 » » ÿ// an illegal string in the first place. In this case the error
ÿ | 78 » » // an illegal string in the first place. In this case the error |
79 » » ÿ// has already been reported.ÿ | 79 » » // has already been reported. |
80 p.next() | 80 p.next() |
81 } else { | 81 } else { |
82 p.expect(token.STRING) | 82 p.expect(token.STRING) |
83 } | 83 } |
84 return &Token{pos, value} | 84 return &Token{pos, value} |
85 } | 85 } |
86 | 86 |
87 | 87 |
88 func (p *parser) parseTerm() (x Expression) { | 88 func (p *parser) parseTerm() (x Expression) { |
89 pos := p.pos | 89 pos := p.pos |
(...skipping 30 matching lines...) Expand all Loading... |
120 } | 120 } |
121 | 121 |
122 | 122 |
123 func (p *parser) parseSequence() Expression { | 123 func (p *parser) parseSequence() Expression { |
124 var list Sequence | 124 var list Sequence |
125 | 125 |
126 for x := p.parseTerm(); x != nil; x = p.parseTerm() { | 126 for x := p.parseTerm(); x != nil; x = p.parseTerm() { |
127 list = append(list, x) | 127 list = append(list, x) |
128 } | 128 } |
129 | 129 |
130 » ÿ// no need for a sequence if list.Len() < 2ÿ | 130 » // no need for a sequence if list.Len() < 2 |
131 switch len(list) { | 131 switch len(list) { |
132 case 0: | 132 case 0: |
133 return nil | 133 return nil |
134 case 1: | 134 case 1: |
135 return list[0] | 135 return list[0] |
136 } | 136 } |
137 | 137 |
138 return list | 138 return list |
139 } | 139 } |
140 | 140 |
141 | 141 |
142 func (p *parser) parseExpression() Expression { | 142 func (p *parser) parseExpression() Expression { |
143 var list Alternative | 143 var list Alternative |
144 | 144 |
145 for { | 145 for { |
146 if x := p.parseSequence(); x != nil { | 146 if x := p.parseSequence(); x != nil { |
147 list = append(list, x) | 147 list = append(list, x) |
148 } | 148 } |
149 if p.tok != token.OR { | 149 if p.tok != token.OR { |
150 break | 150 break |
151 } | 151 } |
152 p.next() | 152 p.next() |
153 } | 153 } |
154 | 154 |
155 » ÿ// no need for an Alternative node if list.Len() < 2ÿ | 155 » // no need for an Alternative node if list.Len() < 2 |
156 switch len(list) { | 156 switch len(list) { |
157 case 0: | 157 case 0: |
158 return nil | 158 return nil |
159 case 1: | 159 case 1: |
160 return list[0] | 160 return list[0] |
161 } | 161 } |
162 | 162 |
163 return list | 163 return list |
164 } | 164 } |
165 | 165 |
166 | 166 |
167 func (p *parser) parseProduction() *Production { | 167 func (p *parser) parseProduction() *Production { |
168 name := p.parseIdentifier() | 168 name := p.parseIdentifier() |
169 p.expect(token.ASSIGN) | 169 p.expect(token.ASSIGN) |
170 expr := p.parseExpression() | 170 expr := p.parseExpression() |
171 p.expect(token.PERIOD) | 171 p.expect(token.PERIOD) |
172 return &Production{name, expr} | 172 return &Production{name, expr} |
173 } | 173 } |
174 | 174 |
175 | 175 |
176 func (p *parser) parse(fset *token.FileSet, filename string, src []byte) Grammar
{ | 176 func (p *parser) parse(fset *token.FileSet, filename string, src []byte) Grammar
{ |
177 » ÿ// initialize parserÿ | 177 » // initialize parser |
178 p.fset = fset | 178 p.fset = fset |
179 p.ErrorVector.Reset() | 179 p.ErrorVector.Reset() |
180 p.scanner.Init(fset.AddFile(filename, fset.Base(), len(src)), src, p, 0) | 180 p.scanner.Init(fset.AddFile(filename, fset.Base(), len(src)), src, p, 0) |
181 » p.next() ÿ// initializes pos, tok, litÿ | 181 » p.next() // initializes pos, tok, lit |
182 | 182 |
183 grammar := make(Grammar) | 183 grammar := make(Grammar) |
184 for p.tok != token.EOF { | 184 for p.tok != token.EOF { |
185 prod := p.parseProduction() | 185 prod := p.parseProduction() |
186 name := prod.Name.String | 186 name := prod.Name.String |
187 if _, found := grammar[name]; !found { | 187 if _, found := grammar[name]; !found { |
188 grammar[name] = prod | 188 grammar[name] = prod |
189 } else { | 189 } else { |
190 p.error(prod.Pos(), name+" declared already") | 190 p.error(prod.Pos(), name+" declared already") |
191 } | 191 } |
192 } | 192 } |
193 | 193 |
194 return grammar | 194 return grammar |
195 } | 195 } |
196 | 196 |
197 | 197 |
198 ÿ// Parse parses a set of EBNF productions from source src.ÿ | 198 // Parse parses a set of EBNF productions from source src. |
199 ÿ// It returns a set of productions. Errors are reportedÿ | 199 // It returns a set of productions. Errors are reported |
200 ÿ// for incorrect syntax and if a production is declaredÿ | 200 // for incorrect syntax and if a production is declared |
201 ÿ// more than once. Position information is recorded relativeÿ | 201 // more than once. Position information is recorded relative |
202 ÿ// to the file set fset.ÿ | 202 // to the file set fset. |
203 ÿ//ÿ | 203 // |
204 func Parse(fset *token.FileSet, filename string, src []byte) (Grammar, os.Error)
{ | 204 func Parse(fset *token.FileSet, filename string, src []byte) (Grammar, os.Error)
{ |
205 var p parser | 205 var p parser |
206 grammar := p.parse(fset, filename, src) | 206 grammar := p.parse(fset, filename, src) |
207 return grammar, p.GetError(scanner.Sorted) | 207 return grammar, p.GetError(scanner.Sorted) |
208 } | 208 } |
LEFT | RIGHT |