libgo/go/exp/ebnf/parser.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package ebnf
   6
   7 import (
   8         "io"
   9         "os"
  10         "scanner"
  11         "strconv"
  12 )
  13
  14 type parser struct {
  15         errors  errorList
  16         scanner scanner.Scanner
  17         pos     scanner.Position // token position
  18         tok     int              // one token look-ahead
  19         lit     string           // token literal
  20 }
  21
  22 func (p *parser) next() {
  23         p.tok = p.scanner.Scan()
  24         p.pos = p.scanner.Position
  25         p.lit = p.scanner.TokenText()
  26 }
  27
  28 func (p *parser) error(pos scanner.Position, msg string) {
  29         p.errors = append(p.errors, newError(pos, msg))
  30 }
  31
  32 func (p *parser) errorExpected(pos scanner.Position, msg string) {
  33         msg = `expected "` + msg + `"`
  34         if pos.Offset == p.pos.Offset {
  35                 // the error happened at the current position;
  36                 // make the error message more specific
  37                 msg += ", found " + scanner.TokenString(p.tok)
  38                 if p.tok < 0 {
  39                         msg += " " + p.lit
  40                 }
  41         }
  42         p.error(pos, msg)
  43 }
  44
  45 func (p *parser) expect(tok int) scanner.Position {
  46         pos := p.pos
  47         if p.tok != tok {
  48                 p.errorExpected(pos, scanner.TokenString(tok))
  49         }
  50         p.next() // make progress in any case
  51         return pos
  52 }
  53
  54 func (p *parser) parseIdentifier() *Name {
  55         pos := p.pos
  56         name := p.lit
  57         p.expect(scanner.Ident)
  58         return &Name{pos, name}
  59 }
  60
  61 func (p *parser) parseToken() *Token {
  62         pos := p.pos
  63         value := ""
  64         if p.tok == scanner.String {
  65                 value, _ = strconv.Unquote(p.lit)
  66                 // Unquote may fail with an error, but only if the scanner found
  67                 // an illegal string in the first place. In this case the error
  68                 // has already been reported.
  69                 p.next()
  70         } else {
  71                 p.expect(scanner.String)
  72         }
  73         return &Token{pos, value}
  74 }
  75
  76 // ParseTerm returns nil if no term was found.
  77 func (p *parser) parseTerm() (x Expression) {
  78         pos := p.pos
  79
  80         switch p.tok {
  81         case scanner.Ident:
  82                 x = p.parseIdentifier()
  83
  84         case scanner.String:
  85                 tok := p.parseToken()
  86                 x = tok
  87                 const ellipsis = '…' // U+2026, the horizontal ellipsis character
  88                 if p.tok == ellipsis {
  89                         p.next()
  90                         x = &Range{tok, p.parseToken()}
  91                 }
  92
  93         case '(':
  94                 p.next()
  95                 x = &Group{pos, p.parseExpression()}
  96                 p.expect(')')
  97
  98         case '[':
  99                 p.next()
 100                 x = &Option{pos, p.parseExpression()}
 101                 p.expect(']')
 102
 103         case '{':
 104                 p.next()
 105                 x = &Repetition{pos, p.parseExpression()}
 106                 p.expect('}')
 107         }
 108
 109         return x
 110 }
 111
 112 func (p *parser) parseSequence() Expression {
 113         var list Sequence
 114
 115         for x := p.parseTerm(); x != nil; x = p.parseTerm() {
 116                 list = append(list, x)
 117         }
 118
 119         // no need for a sequence if list.Len() < 2
 120         switch len(list) {
 121         case 0:
 122                 p.errorExpected(p.pos, "term")
 123                 return &Bad{p.pos, "term expected"}
 124         case 1:
 125                 return list[0]
 126         }
 127
 128         return list
 129 }
 130
 131 func (p *parser) parseExpression() Expression {
 132         var list Alternative
 133
 134         for {
 135                 list = append(list, p.parseSequence())
 136                 if p.tok != '|' {
 137                         break
 138                 }
 139                 p.next()
 140         }
 141         // len(list) > 0
 142
 143         // no need for an Alternative node if list.Len() < 2
 144         if len(list) == 1 {
 145                 return list[0]
 146         }
 147
 148         return list
 149 }
 150
 151 func (p *parser) parseProduction() *Production {
 152         name := p.parseIdentifier()
 153         p.expect('=')
 154         var expr Expression
 155         if p.tok != '.' {
 156                 expr = p.parseExpression()
 157         }
 158         p.expect('.')
 159         return &Production{name, expr}
 160 }
 161
 162 func (p *parser) parse(filename string, src io.Reader) Grammar {
 163         p.scanner.Init(src)
 164         p.scanner.Filename = filename
 165         p.next() // initializes pos, tok, lit
 166
 167         grammar := make(Grammar)
 168         for p.tok != scanner.EOF {
 169                 prod := p.parseProduction()
 170                 name := prod.Name.String
 171                 if _, found := grammar[name]; !found {
 172                         grammar[name] = prod
 173                 } else {
 174                         p.error(prod.Pos(), name+" declared already")
 175                 }
 176         }
 177
 178         return grammar
 179 }
 180
 181 // Parse parses a set of EBNF productions from source src.
 182 // It returns a set of productions. Errors are reported
 183 // for incorrect syntax and if a production is declared
 184 // more than once; the filename is used only for error
 185 // positions.
 186 //
 187 func Parse(filename string, src io.Reader) (Grammar, os.Error) {
 188         var p parser
 189         grammar := p.parse(filename, src)
 190         return grammar, p.errors.Error()
 191 }