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