libgo/go/go/parser/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 // A parser for Go source files. Input may be provided in a variety of
   6 // forms (see the various Parse* functions); the output is an abstract
   7 // syntax tree (AST) representing the Go source. The parser is invoked
   8 // through one of the Parse* functions.
   9 //
  10 package parser
  11
  12 import (
  13         "fmt"
  14         "go/ast"
  15         "go/scanner"
  16         "go/token"
  17 )
  18
  19
  20 // The mode parameter to the Parse* functions is a set of flags (or 0).
  21 // They control the amount of source code parsed and other optional
  22 // parser functionality.
  23 //
  24 const (
  25         PackageClauseOnly uint = 1 << iota // parsing stops after package clause
  26         ImportsOnly                        // parsing stops after import declarations
  27         ParseComments                      // parse comments and add them to AST
  28         Trace                              // print a trace of parsed productions
  29         DeclarationErrors                  // report declaration errors
  30 )
  31
  32
  33 // The parser structure holds the parser's internal state.
  34 type parser struct {
  35         file *token.File
  36         scanner.ErrorVector
  37         scanner scanner.Scanner
  38
  39         // Tracing/debugging
  40         mode   uint // parsing mode
  41         trace  bool // == (mode & Trace != 0)
  42         indent uint // indentation used for tracing output
  43
  44         // Comments
  45         comments    []*ast.CommentGroup
  46         leadComment *ast.CommentGroup // last lead comment
  47         lineComment *ast.CommentGroup // last line comment
  48
  49         // Next token
  50         pos  token.Pos   // token position
  51         tok  token.Token // one token look-ahead
  52         lit_ []byte      // token literal (slice into original source, don't hold on to it)
  53
  54         // Non-syntactic parser control
  55         exprLev int // < 0: in control clause, >= 0: in expression
  56
  57         // Ordinary identifer scopes
  58         pkgScope   *ast.Scope   // pkgScope.Outer == nil
  59         topScope   *ast.Scope   // top-most scope; may be pkgScope
  60         unresolved []*ast.Ident // unresolved global identifiers
  61
  62         // Label scope
  63         // (maintained by open/close LabelScope)
  64         labelScope  *ast.Scope     // label scope for current function
  65         targetStack [][]*ast.Ident // stack of unresolved labels
  66 }
  67
  68
  69 // scannerMode returns the scanner mode bits given the parser's mode bits.
  70 func scannerMode(mode uint) uint {
  71         var m uint = scanner.InsertSemis
  72         if mode&ParseComments != 0 {
  73                 m |= scanner.ScanComments
  74         }
  75         return m
  76 }
  77
  78
  79 func (p *parser) init(fset *token.FileSet, filename string, src []byte, mode uint) {
  80         p.file = fset.AddFile(filename, fset.Base(), len(src))
  81         p.scanner.Init(p.file, src, p, scannerMode(mode))
  82
  83         p.mode = mode
  84         p.trace = mode&Trace != 0 // for convenience (p.trace is used frequently)
  85
  86         p.next()
  87
  88         // set up the pkgScope here (as opposed to in parseFile) because
  89         // there are other parser entry points (ParseExpr, etc.)
  90         p.openScope()
  91         p.pkgScope = p.topScope
  92
  93         // for the same reason, set up a label scope
  94         p.openLabelScope()
  95 }
  96
  97
  98 func (p *parser) lit() []byte {
  99         // make a copy of p.lit_ so that we don't hold on to
 100         // a copy of the entire source indirectly in the AST
 101         t := make([]byte, len(p.lit_))
 102         copy(t, p.lit_)
 103         return t
 104 }
 105
 106
 107 // ----------------------------------------------------------------------------
 108 // Scoping support
 109
 110 func (p *parser) openScope() {
 111         p.topScope = ast.NewScope(p.topScope)
 112 }
 113
 114
 115 func (p *parser) closeScope() {
 116         p.topScope = p.topScope.Outer
 117 }
 118
 119
 120 func (p *parser) openLabelScope() {
 121         p.labelScope = ast.NewScope(p.labelScope)
 122         p.targetStack = append(p.targetStack, nil)
 123 }
 124
 125
 126 func (p *parser) closeLabelScope() {
 127         // resolve labels
 128         n := len(p.targetStack) - 1
 129         scope := p.labelScope
 130         for _, ident := range p.targetStack[n] {
 131                 ident.Obj = scope.Lookup(ident.Name)
 132                 if ident.Obj == nil && p.mode&DeclarationErrors != 0 {
 133                         p.error(ident.Pos(), fmt.Sprintf("label %s undefined", ident.Name))
 134                 }
 135         }
 136         // pop label scope
 137         p.targetStack = p.targetStack[0:n]
 138         p.labelScope = p.labelScope.Outer
 139 }
 140
 141
 142 func (p *parser) declare(decl interface{}, scope *ast.Scope, kind ast.ObjKind, idents ...*ast.Ident) {
 143         for _, ident := range idents {
 144                 if ident.Name != "_" {
 145                         obj := ast.NewObj(kind, ident.Name)
 146                         // remember the corresponding declaration for redeclaration
 147                         // errors and global variable resolution/typechecking phase
 148                         obj.Decl = decl
 149                         alt := scope.Insert(obj)
 150                         if alt != obj && p.mode&DeclarationErrors != 0 {
 151                                 prevDecl := ""
 152                                 if pos := alt.Pos(); pos.IsValid() {
 153                                         prevDecl = fmt.Sprintf("\n\tprevious declaration at %s", p.file.Position(pos))
 154                                 }
 155                                 p.error(ident.Pos(), fmt.Sprintf("%s redeclared in this block%s", ident.Name, prevDecl))
 156                         }
 157                         ident.Obj = obj
 158                 }
 159         }
 160 }
 161
 162
 163 func (p *parser) shortVarDecl(idents []*ast.Ident) {
 164         // Go spec: A short variable declaration may redeclare variables
 165         // provided they were originally declared in the same block with
 166         // the same type, and at least one of the non-blank variables is new.
 167         n := 0 // number of new variables
 168         for _, ident := range idents {
 169                 if ident.Name != "_" {
 170                         obj := ast.NewObj(ast.Var, ident.Name)
 171                         // short var declarations cannot have redeclaration errors
 172                         // and are not global => no need to remember the respective
 173                         // declaration
 174                         alt := p.topScope.Insert(obj)
 175                         if alt == obj {
 176                                 n++ // new declaration
 177                         }
 178                         ident.Obj = alt
 179                 }
 180         }
 181         if n == 0 && p.mode&DeclarationErrors != 0 {
 182                 p.error(idents[0].Pos(), "no new variables on left side of :=")
 183         }
 184 }
 185
 186
 187 func (p *parser) resolve(ident *ast.Ident) {
 188         if ident.Name == "_" {
 189                 return
 190         }
 191         // try to resolve the identifier
 192         for s := p.topScope; s != nil; s = s.Outer {
 193                 if obj := s.Lookup(ident.Name); obj != nil {
 194                         ident.Obj = obj
 195                         return
 196                 }
 197         }
 198         // collect unresolved global identifiers; ignore the others
 199         if p.topScope == p.pkgScope {
 200                 p.unresolved = append(p.unresolved, ident)
 201         }
 202 }
 203
 204
 205 // ----------------------------------------------------------------------------
 206 // Parsing support
 207
 208 func (p *parser) printTrace(a ...interface{}) {
 209         const dots = ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . " +
 210                 ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "
 211         const n = uint(len(dots))
 212         pos := p.file.Position(p.pos)
 213         fmt.Printf("%5d:%3d: ", pos.Line, pos.Column)
 214         i := 2 * p.indent
 215         for ; i > n; i -= n {
 216                 fmt.Print(dots)
 217         }
 218         fmt.Print(dots[0:i])
 219         fmt.Println(a...)
 220 }
 221
 222
 223 func trace(p *parser, msg string) *parser {
 224         p.printTrace(msg, "(")
 225         p.indent++
 226         return p
 227 }
 228
 229
 230 // Usage pattern: defer un(trace(p, "..."));
 231 func un(p *parser) {
 232         p.indent--
 233         p.printTrace(")")
 234 }
 235
 236
 237 // Advance to the next token.
 238 func (p *parser) next0() {
 239         // Because of one-token look-ahead, print the previous token
 240         // when tracing as it provides a more readable output. The
 241         // very first token (!p.pos.IsValid()) is not initialized
 242         // (it is token.ILLEGAL), so don't print it .
 243         if p.trace && p.pos.IsValid() {
 244                 s := p.tok.String()
 245                 switch {
 246                 case p.tok.IsLiteral():
 247                         p.printTrace(s, string(p.lit_))
 248                 case p.tok.IsOperator(), p.tok.IsKeyword():
 249                         p.printTrace("\"" + s + "\"")
 250                 default:
 251                         p.printTrace(s)
 252                 }
 253         }
 254
 255         p.pos, p.tok, p.lit_ = p.scanner.Scan()
 256 }
 257
 258 // Consume a comment and return it and the line on which it ends.
 259 func (p *parser) consumeComment() (comment *ast.Comment, endline int) {
 260         // /*-style comments may end on a different line than where they start.
 261         // Scan the comment for '\n' chars and adjust endline accordingly.
 262         endline = p.file.Line(p.pos)
 263         if p.lit_[1] == '*' {
 264                 for _, b := range p.lit_ {
 265                         if b == '\n' {
 266                                 endline++
 267                         }
 268                 }
 269         }
 270
 271         comment = &ast.Comment{p.pos, p.lit()}
 272         p.next0()
 273
 274         return
 275 }
 276
 277
 278 // Consume a group of adjacent comments, add it to the parser's
 279 // comments list, and return it together with the line at which
 280 // the last comment in the group ends. An empty line or non-comment
 281 // token terminates a comment group.
 282 //
 283 func (p *parser) consumeCommentGroup() (comments *ast.CommentGroup, endline int) {
 284         var list []*ast.Comment
 285         endline = p.file.Line(p.pos)
 286         for p.tok == token.COMMENT && endline+1 >= p.file.Line(p.pos) {
 287                 var comment *ast.Comment
 288                 comment, endline = p.consumeComment()
 289                 list = append(list, comment)
 290         }
 291
 292         // add comment group to the comments list
 293         comments = &ast.CommentGroup{list}
 294         p.comments = append(p.comments, comments)
 295
 296         return
 297 }
 298
 299
 300 // Advance to the next non-comment token. In the process, collect
 301 // any comment groups encountered, and remember the last lead and
 302 // and line comments.
 303 //
 304 // A lead comment is a comment group that starts and ends in a
 305 // line without any other tokens and that is followed by a non-comment
 306 // token on the line immediately after the comment group.
 307 //
 308 // A line comment is a comment group that follows a non-comment
 309 // token on the same line, and that has no tokens after it on the line
 310 // where it ends.
 311 //
 312 // Lead and line comments may be considered documentation that is
 313 // stored in the AST.
 314 //
 315 func (p *parser) next() {
 316         p.leadComment = nil
 317         p.lineComment = nil
 318         line := p.file.Line(p.pos) // current line
 319         p.next0()
 320
 321         if p.tok == token.COMMENT {
 322                 var comment *ast.CommentGroup
 323                 var endline int
 324
 325                 if p.file.Line(p.pos) == line {
 326                         // The comment is on same line as previous token; it
 327                         // cannot be a lead comment but may be a line comment.
 328                         comment, endline = p.consumeCommentGroup()
 329                         if p.file.Line(p.pos) != endline {
 330                                 // The next token is on a different line, thus
 331                                 // the last comment group is a line comment.
 332                                 p.lineComment = comment
 333                         }
 334                 }
 335
 336                 // consume successor comments, if any
 337                 endline = -1
 338                 for p.tok == token.COMMENT {
 339                         comment, endline = p.consumeCommentGroup()
 340                 }
 341
 342                 if endline+1 == p.file.Line(p.pos) {
 343                         // The next token is following on the line immediately after the
 344                         // comment group, thus the last comment group is a lead comment.
 345                         p.leadComment = comment
 346                 }
 347         }
 348 }
 349
 350
 351 func (p *parser) error(pos token.Pos, msg string) {
 352         p.Error(p.file.Position(pos), msg)
 353 }
 354
 355
 356 func (p *parser) errorExpected(pos token.Pos, msg string) {
 357         msg = "expected " + msg
 358         if pos == p.pos {
 359                 // the error happened at the current position;
 360                 // make the error message more specific
 361                 if p.tok == token.SEMICOLON && p.lit_[0] == '\n' {
 362                         msg += ", found newline"
 363                 } else {
 364                         msg += ", found '" + p.tok.String() + "'"
 365                         if p.tok.IsLiteral() {
 366                                 msg += " " + string(p.lit_)
 367                         }
 368                 }
 369         }
 370         p.error(pos, msg)
 371 }
 372
 373
 374 func (p *parser) expect(tok token.Token) token.Pos {
 375         pos := p.pos
 376         if p.tok != tok {
 377                 p.errorExpected(pos, "'"+tok.String()+"'")
 378         }
 379         p.next() // make progress
 380         return pos
 381 }
 382
 383
 384 func (p *parser) expectSemi() {
 385         if p.tok != token.RPAREN && p.tok != token.RBRACE {
 386                 p.expect(token.SEMICOLON)
 387         }
 388 }
 389
 390
 391 // ----------------------------------------------------------------------------
 392 // Identifiers
 393
 394 func (p *parser) parseIdent() *ast.Ident {
 395         pos := p.pos
 396         name := "_"
 397         if p.tok == token.IDENT {
 398                 name = string(p.lit_)
 399                 p.next()
 400         } else {
 401                 p.expect(token.IDENT) // use expect() error handling
 402         }
 403         return &ast.Ident{pos, name, nil}
 404 }
 405
 406
 407 func (p *parser) parseIdentList() (list []*ast.Ident) {
 408         if p.trace {
 409                 defer un(trace(p, "IdentList"))
 410         }
 411
 412         list = append(list, p.parseIdent())
 413         for p.tok == token.COMMA {
 414                 p.next()
 415                 list = append(list, p.parseIdent())
 416         }
 417
 418         return
 419 }
 420
 421
 422 // ----------------------------------------------------------------------------
 423 // Common productions
 424
 425 func (p *parser) parseExprList() (list []ast.Expr) {
 426         if p.trace {
 427                 defer un(trace(p, "ExpressionList"))
 428         }
 429
 430         list = append(list, p.parseExpr())
 431         for p.tok == token.COMMA {
 432                 p.next()
 433                 list = append(list, p.parseExpr())
 434         }
 435
 436         return
 437 }
 438
 439
 440 // ----------------------------------------------------------------------------
 441 // Types
 442
 443 func (p *parser) parseType() ast.Expr {
 444         if p.trace {
 445                 defer un(trace(p, "Type"))
 446         }
 447
 448         typ := p.tryType()
 449
 450         if typ == nil {
 451                 pos := p.pos
 452                 p.errorExpected(pos, "type")
 453                 p.next() // make progress
 454                 return &ast.BadExpr{pos, p.pos}
 455         }
 456
 457         return typ
 458 }
 459
 460
 461 func (p *parser) parseQualifiedIdent() ast.Expr {
 462         if p.trace {
 463                 defer un(trace(p, "QualifiedIdent"))
 464         }
 465
 466         ident := p.parseIdent()
 467         p.resolve(ident)
 468         var x ast.Expr = ident
 469         if p.tok == token.PERIOD {
 470                 // first identifier is a package identifier
 471                 p.next()
 472                 sel := p.parseIdent()
 473                 x = &ast.SelectorExpr{x, sel}
 474         }
 475
 476         return x
 477 }
 478
 479
 480 func (p *parser) parseTypeName() ast.Expr {
 481         if p.trace {
 482                 defer un(trace(p, "TypeName"))
 483         }
 484
 485         return p.parseQualifiedIdent()
 486 }
 487
 488
 489 func (p *parser) parseArrayType(ellipsisOk bool) ast.Expr {
 490         if p.trace {
 491                 defer un(trace(p, "ArrayType"))
 492         }
 493
 494         lbrack := p.expect(token.LBRACK)
 495         var len ast.Expr
 496         if ellipsisOk && p.tok == token.ELLIPSIS {
 497                 len = &ast.Ellipsis{p.pos, nil}
 498                 p.next()
 499         } else if p.tok != token.RBRACK {
 500                 len = p.parseExpr()
 501         }
 502         p.expect(token.RBRACK)
 503         elt := p.parseType()
 504
 505         return &ast.ArrayType{lbrack, len, elt}
 506 }
 507
 508
 509 func (p *parser) makeIdentList(list []ast.Expr) []*ast.Ident {
 510         idents := make([]*ast.Ident, len(list))
 511         for i, x := range list {
 512                 ident, isIdent := x.(*ast.Ident)
 513                 if !isIdent {
 514                         pos := x.(ast.Expr).Pos()
 515                         p.errorExpected(pos, "identifier")
 516                         ident = &ast.Ident{pos, "_", nil}
 517                 }
 518                 idents[i] = ident
 519         }
 520         return idents
 521 }
 522
 523
 524 func (p *parser) parseFieldDecl() *ast.Field {
 525         if p.trace {
 526                 defer un(trace(p, "FieldDecl"))
 527         }
 528
 529         doc := p.leadComment
 530
 531         // fields
 532         list, typ := p.parseVarList(false)
 533
 534         // optional tag
 535         var tag *ast.BasicLit
 536         if p.tok == token.STRING {
 537                 tag = &ast.BasicLit{p.pos, p.tok, p.lit()}
 538                 p.next()
 539         }
 540
 541         // analyze case
 542         var idents []*ast.Ident
 543         if typ != nil {
 544                 // IdentifierList Type
 545                 idents = p.makeIdentList(list)
 546         } else {
 547                 // ["*"] TypeName (AnonymousField)
 548                 typ = list[0] // we always have at least one element
 549                 if n := len(list); n > 1 || !isTypeName(deref(typ)) {
 550                         pos := typ.Pos()
 551                         p.errorExpected(pos, "anonymous field")
 552                         typ = &ast.BadExpr{pos, list[n-1].End()}
 553                 }
 554         }
 555
 556         p.expectSemi() // call before accessing p.linecomment
 557
 558         return &ast.Field{doc, idents, typ, tag, p.lineComment}
 559 }
 560
 561
 562 func (p *parser) parseStructType() *ast.StructType {
 563         if p.trace {
 564                 defer un(trace(p, "StructType"))
 565         }
 566
 567         pos := p.expect(token.STRUCT)
 568         lbrace := p.expect(token.LBRACE)
 569         var list []*ast.Field
 570         for p.tok == token.IDENT || p.tok == token.MUL || p.tok == token.LPAREN {
 571                 // a field declaration cannot start with a '(' but we accept
 572                 // it here for more robust parsing and better error messages
 573                 // (parseFieldDecl will check and complain if necessary)
 574                 list = append(list, p.parseFieldDecl())
 575         }
 576         rbrace := p.expect(token.RBRACE)
 577
 578         return &ast.StructType{pos, &ast.FieldList{lbrace, list, rbrace}, false}
 579 }
 580
 581
 582 func (p *parser) parsePointerType() *ast.StarExpr {
 583         if p.trace {
 584                 defer un(trace(p, "PointerType"))
 585         }
 586
 587         star := p.expect(token.MUL)
 588         base := p.parseType()
 589
 590         return &ast.StarExpr{star, base}
 591 }
 592
 593
 594 func (p *parser) tryVarType(isParam bool) ast.Expr {
 595         if isParam && p.tok == token.ELLIPSIS {
 596                 pos := p.pos
 597                 p.next()
 598                 typ := p.tryType() // don't use parseType so we can provide better error message
 599                 if typ == nil {
 600                         p.error(pos, "'...' parameter is missing type")
 601                         typ = &ast.BadExpr{pos, p.pos}
 602                 }
 603                 if p.tok != token.RPAREN {
 604                         p.error(pos, "can use '...' with last parameter type only")
 605                 }
 606                 return &ast.Ellipsis{pos, typ}
 607         }
 608         return p.tryType()
 609 }
 610
 611
 612 func (p *parser) parseVarType(isParam bool) ast.Expr {
 613         typ := p.tryVarType(isParam)
 614         if typ == nil {
 615                 pos := p.pos
 616                 p.errorExpected(pos, "type")
 617                 p.next() // make progress
 618                 typ = &ast.BadExpr{pos, p.pos}
 619         }
 620         return typ
 621 }
 622
 623
 624 func (p *parser) parseVarList(isParam bool) (list []ast.Expr, typ ast.Expr) {
 625         if p.trace {
 626                 defer un(trace(p, "VarList"))
 627         }
 628
 629         // a list of identifiers looks like a list of type names
 630         for {
 631                 // parseVarType accepts any type (including parenthesized ones)
 632                 // even though the syntax does not permit them here: we
 633                 // accept them all for more robust parsing and complain
 634                 // afterwards
 635                 list = append(list, p.parseVarType(isParam))
 636                 if p.tok != token.COMMA {
 637                         break
 638                 }
 639                 p.next()
 640         }
 641
 642         // if we had a list of identifiers, it must be followed by a type
 643         typ = p.tryVarType(isParam)
 644
 645         return
 646 }
 647
 648
 649 func (p *parser) parseParameterList(scope *ast.Scope, ellipsisOk bool) (params []*ast.Field) {
 650         if p.trace {
 651                 defer un(trace(p, "ParameterList"))
 652         }
 653
 654         list, typ := p.parseVarList(ellipsisOk)
 655         if typ != nil {
 656                 // IdentifierList Type
 657                 idents := p.makeIdentList(list)
 658                 field := &ast.Field{nil, idents, typ, nil, nil}
 659                 params = append(params, field)
 660                 // Go spec: The scope of an identifier denoting a function
 661                 // parameter or result variable is the function body.
 662                 p.declare(field, scope, ast.Var, idents...)
 663                 if p.tok == token.COMMA {
 664                         p.next()
 665                 }
 666
 667                 for p.tok != token.RPAREN && p.tok != token.EOF {
 668                         idents := p.parseIdentList()
 669                         typ := p.parseVarType(ellipsisOk)
 670                         field := &ast.Field{nil, idents, typ, nil, nil}
 671                         params = append(params, field)
 672                         // Go spec: The scope of an identifier denoting a function
 673                         // parameter or result variable is the function body.
 674                         p.declare(field, scope, ast.Var, idents...)
 675                         if p.tok != token.COMMA {
 676                                 break
 677                         }
 678                         p.next()
 679                 }
 680
 681         } else {
 682                 // Type { "," Type } (anonymous parameters)
 683                 params = make([]*ast.Field, len(list))
 684                 for i, x := range list {
 685                         params[i] = &ast.Field{Type: x}
 686                 }
 687         }
 688
 689         return
 690 }
 691
 692
 693 func (p *parser) parseParameters(scope *ast.Scope, ellipsisOk bool) *ast.FieldList {
 694         if p.trace {
 695                 defer un(trace(p, "Parameters"))
 696         }
 697
 698         var params []*ast.Field
 699         lparen := p.expect(token.LPAREN)
 700         if p.tok != token.RPAREN {
 701                 params = p.parseParameterList(scope, ellipsisOk)
 702         }
 703         rparen := p.expect(token.RPAREN)
 704
 705         return &ast.FieldList{lparen, params, rparen}
 706 }
 707
 708
 709 func (p *parser) parseResult(scope *ast.Scope) *ast.FieldList {
 710         if p.trace {
 711                 defer un(trace(p, "Result"))
 712         }
 713
 714         if p.tok == token.LPAREN {
 715                 return p.parseParameters(scope, false)
 716         }
 717
 718         typ := p.tryType()
 719         if typ != nil {
 720                 list := make([]*ast.Field, 1)
 721                 list[0] = &ast.Field{Type: typ}
 722                 return &ast.FieldList{List: list}
 723         }
 724
 725         return nil
 726 }
 727
 728
 729 func (p *parser) parseSignature(scope *ast.Scope) (params, results *ast.FieldList) {
 730         if p.trace {
 731                 defer un(trace(p, "Signature"))
 732         }
 733
 734         params = p.parseParameters(scope, true)
 735         results = p.parseResult(scope)
 736
 737         return
 738 }
 739
 740
 741 func (p *parser) parseFuncType() (*ast.FuncType, *ast.Scope) {
 742         if p.trace {
 743                 defer un(trace(p, "FuncType"))
 744         }
 745
 746         pos := p.expect(token.FUNC)
 747         scope := ast.NewScope(p.topScope) // function scope
 748         params, results := p.parseSignature(scope)
 749
 750         return &ast.FuncType{pos, params, results}, scope
 751 }
 752
 753
 754 func (p *parser) parseMethodSpec() *ast.Field {
 755         if p.trace {
 756                 defer un(trace(p, "MethodSpec"))
 757         }
 758
 759         doc := p.leadComment
 760         var idents []*ast.Ident
 761         var typ ast.Expr
 762         x := p.parseQualifiedIdent()
 763         if ident, isIdent := x.(*ast.Ident); isIdent && p.tok == token.LPAREN {
 764                 // method
 765                 idents = []*ast.Ident{ident}
 766                 scope := ast.NewScope(nil) // method scope
 767                 params, results := p.parseSignature(scope)
 768                 typ = &ast.FuncType{token.NoPos, params, results}
 769         } else {
 770                 // embedded interface
 771                 typ = x
 772         }
 773         p.expectSemi() // call before accessing p.linecomment
 774
 775         return &ast.Field{doc, idents, typ, nil, p.lineComment}
 776 }
 777
 778
 779 func (p *parser) parseInterfaceType() *ast.InterfaceType {
 780         if p.trace {
 781                 defer un(trace(p, "InterfaceType"))
 782         }
 783
 784         pos := p.expect(token.INTERFACE)
 785         lbrace := p.expect(token.LBRACE)
 786         var list []*ast.Field
 787         for p.tok == token.IDENT {
 788                 list = append(list, p.parseMethodSpec())
 789         }
 790         rbrace := p.expect(token.RBRACE)
 791
 792         return &ast.InterfaceType{pos, &ast.FieldList{lbrace, list, rbrace}, false}
 793 }
 794
 795
 796 func (p *parser) parseMapType() *ast.MapType {
 797         if p.trace {
 798                 defer un(trace(p, "MapType"))
 799         }
 800
 801         pos := p.expect(token.MAP)
 802         p.expect(token.LBRACK)
 803         key := p.parseType()
 804         p.expect(token.RBRACK)
 805         value := p.parseType()
 806
 807         return &ast.MapType{pos, key, value}
 808 }
 809
 810
 811 func (p *parser) parseChanType() *ast.ChanType {
 812         if p.trace {
 813                 defer un(trace(p, "ChanType"))
 814         }
 815
 816         pos := p.pos
 817         dir := ast.SEND | ast.RECV
 818         if p.tok == token.CHAN {
 819                 p.next()
 820                 if p.tok == token.ARROW {
 821                         p.next()
 822                         dir = ast.SEND
 823                 }
 824         } else {
 825                 p.expect(token.ARROW)
 826                 p.expect(token.CHAN)
 827                 dir = ast.RECV
 828         }
 829         value := p.parseType()
 830
 831         return &ast.ChanType{pos, dir, value}
 832 }
 833
 834
 835 func (p *parser) tryRawType(ellipsisOk bool) ast.Expr {
 836         switch p.tok {
 837         case token.IDENT:
 838                 return p.parseTypeName()
 839         case token.LBRACK:
 840                 return p.parseArrayType(ellipsisOk)
 841         case token.STRUCT:
 842                 return p.parseStructType()
 843         case token.MUL:
 844                 return p.parsePointerType()
 845         case token.FUNC:
 846                 typ, _ := p.parseFuncType()
 847                 return typ
 848         case token.INTERFACE:
 849                 return p.parseInterfaceType()
 850         case token.MAP:
 851                 return p.parseMapType()
 852         case token.CHAN, token.ARROW:
 853                 return p.parseChanType()
 854         case token.LPAREN:
 855                 lparen := p.pos
 856                 p.next()
 857                 typ := p.parseType()
 858                 rparen := p.expect(token.RPAREN)
 859                 return &ast.ParenExpr{lparen, typ, rparen}
 860         }
 861
 862         // no type found
 863         return nil
 864 }
 865
 866
 867 func (p *parser) tryType() ast.Expr { return p.tryRawType(false) }
 868
 869
 870 // ----------------------------------------------------------------------------
 871 // Blocks
 872
 873 func (p *parser) parseStmtList() (list []ast.Stmt) {
 874         if p.trace {
 875                 defer un(trace(p, "StatementList"))
 876         }
 877
 878         for p.tok != token.CASE && p.tok != token.DEFAULT && p.tok != token.RBRACE && p.tok != token.EOF {
 879                 list = append(list, p.parseStmt())
 880         }
 881
 882         return
 883 }
 884
 885
 886 func (p *parser) parseBody(scope *ast.Scope) *ast.BlockStmt {
 887         if p.trace {
 888                 defer un(trace(p, "Body"))
 889         }
 890
 891         lbrace := p.expect(token.LBRACE)
 892         p.topScope = scope // open function scope
 893         p.openLabelScope()
 894         list := p.parseStmtList()
 895         p.closeLabelScope()
 896         p.closeScope()
 897         rbrace := p.expect(token.RBRACE)
 898
 899         return &ast.BlockStmt{lbrace, list, rbrace}
 900 }
 901
 902
 903 func (p *parser) parseBlockStmt() *ast.BlockStmt {
 904         if p.trace {
 905                 defer un(trace(p, "BlockStmt"))
 906         }
 907
 908         lbrace := p.expect(token.LBRACE)
 909         p.openScope()
 910         list := p.parseStmtList()
 911         p.closeScope()
 912         rbrace := p.expect(token.RBRACE)
 913
 914         return &ast.BlockStmt{lbrace, list, rbrace}
 915 }
 916
 917
 918 // ----------------------------------------------------------------------------
 919 // Expressions
 920
 921 func (p *parser) parseFuncTypeOrLit() ast.Expr {
 922         if p.trace {
 923                 defer un(trace(p, "FuncTypeOrLit"))
 924         }
 925
 926         typ, scope := p.parseFuncType()
 927         if p.tok != token.LBRACE {
 928                 // function type only
 929                 return typ
 930         }
 931
 932         p.exprLev++
 933         body := p.parseBody(scope)
 934         p.exprLev--
 935
 936         return &ast.FuncLit{typ, body}
 937 }
 938
 939
 940 // parseOperand may return an expression or a raw type (incl. array
 941 // types of the form [...]T. Callers must verify the result.
 942 //
 943 func (p *parser) parseOperand() ast.Expr {
 944         if p.trace {
 945                 defer un(trace(p, "Operand"))
 946         }
 947
 948         switch p.tok {
 949         case token.IDENT:
 950                 ident := p.parseIdent()
 951                 p.resolve(ident)
 952                 return ident
 953
 954         case token.INT, token.FLOAT, token.IMAG, token.CHAR, token.STRING:
 955                 x := &ast.BasicLit{p.pos, p.tok, p.lit()}
 956                 p.next()
 957                 return x
 958
 959         case token.LPAREN:
 960                 lparen := p.pos
 961                 p.next()
 962                 p.exprLev++
 963                 x := p.parseExpr()
 964                 p.exprLev--
 965                 rparen := p.expect(token.RPAREN)
 966                 return &ast.ParenExpr{lparen, x, rparen}
 967
 968         case token.FUNC:
 969                 return p.parseFuncTypeOrLit()
 970
 971         default:
 972                 t := p.tryRawType(true) // could be type for composite literal or conversion
 973                 if t != nil {
 974                         return t
 975                 }
 976         }
 977
 978         pos := p.pos
 979         p.errorExpected(pos, "operand")
 980         p.next() // make progress
 981         return &ast.BadExpr{pos, p.pos}
 982 }
 983
 984
 985 func (p *parser) parseSelectorOrTypeAssertion(x ast.Expr) ast.Expr {
 986         if p.trace {
 987                 defer un(trace(p, "SelectorOrTypeAssertion"))
 988         }
 989
 990         p.expect(token.PERIOD)
 991         if p.tok == token.IDENT {
 992                 // selector
 993                 sel := p.parseIdent()
 994                 return &ast.SelectorExpr{x, sel}
 995         }
 996
 997         // type assertion
 998         p.expect(token.LPAREN)
 999         var typ ast.Expr
1000         if p.tok == token.TYPE {
1001                 // type switch: typ == nil
1002                 p.next()
1003         } else {
1004                 typ = p.parseType()
1005         }
1006         p.expect(token.RPAREN)
1007
1008         return &ast.TypeAssertExpr{x, typ}
1009 }
1010
1011
1012 func (p *parser) parseIndexOrSlice(x ast.Expr) ast.Expr {
1013         if p.trace {
1014                 defer un(trace(p, "IndexOrSlice"))
1015         }
1016
1017         lbrack := p.expect(token.LBRACK)
1018         p.exprLev++
1019         var low, high ast.Expr
1020         isSlice := false
1021         if p.tok != token.COLON {
1022                 low = p.parseExpr()
1023         }
1024         if p.tok == token.COLON {
1025                 isSlice = true
1026                 p.next()
1027                 if p.tok != token.RBRACK {
1028                         high = p.parseExpr()
1029                 }
1030         }
1031         p.exprLev--
1032         rbrack := p.expect(token.RBRACK)
1033
1034         if isSlice {
1035                 return &ast.SliceExpr{x, lbrack, low, high, rbrack}
1036         }
1037         return &ast.IndexExpr{x, lbrack, low, rbrack}
1038 }
1039
1040
1041 func (p *parser) parseCallOrConversion(fun ast.Expr) *ast.CallExpr {
1042         if p.trace {
1043                 defer un(trace(p, "CallOrConversion"))
1044         }
1045
1046         lparen := p.expect(token.LPAREN)
1047         p.exprLev++
1048         var list []ast.Expr
1049         var ellipsis token.Pos
1050         for p.tok != token.RPAREN && p.tok != token.EOF && !ellipsis.IsValid() {
1051                 list = append(list, p.parseExpr())
1052                 if p.tok == token.ELLIPSIS {
1053                         ellipsis = p.pos
1054                         p.next()
1055                 }
1056                 if p.tok != token.COMMA {
1057                         break
1058                 }
1059                 p.next()
1060         }
1061         p.exprLev--
1062         rparen := p.expect(token.RPAREN)
1063
1064         return &ast.CallExpr{fun, lparen, list, ellipsis, rparen}
1065 }
1066
1067
1068 func (p *parser) parseElement(keyOk bool) ast.Expr {
1069         if p.trace {
1070                 defer un(trace(p, "Element"))
1071         }
1072
1073         if p.tok == token.LBRACE {
1074                 return p.parseLiteralValue(nil)
1075         }
1076
1077         x := p.parseExpr()
1078         if keyOk && p.tok == token.COLON {
1079                 colon := p.pos
1080                 p.next()
1081                 x = &ast.KeyValueExpr{x, colon, p.parseElement(false)}
1082         }
1083         return x
1084 }
1085
1086
1087 func (p *parser) parseElementList() (list []ast.Expr) {
1088         if p.trace {
1089                 defer un(trace(p, "ElementList"))
1090         }
1091
1092         for p.tok != token.RBRACE && p.tok != token.EOF {
1093                 list = append(list, p.parseElement(true))
1094                 if p.tok != token.COMMA {
1095                         break
1096                 }
1097                 p.next()
1098         }
1099
1100         return
1101 }
1102
1103
1104 func (p *parser) parseLiteralValue(typ ast.Expr) ast.Expr {
1105         if p.trace {
1106                 defer un(trace(p, "LiteralValue"))
1107         }
1108
1109         lbrace := p.expect(token.LBRACE)
1110         var elts []ast.Expr
1111         p.exprLev++
1112         if p.tok != token.RBRACE {
1113                 elts = p.parseElementList()
1114         }
1115         p.exprLev--
1116         rbrace := p.expect(token.RBRACE)
1117         return &ast.CompositeLit{typ, lbrace, elts, rbrace}
1118 }
1119
1120
1121 // checkExpr checks that x is an expression (and not a type).
1122 func (p *parser) checkExpr(x ast.Expr) ast.Expr {
1123         switch t := unparen(x).(type) {
1124         case *ast.BadExpr:
1125         case *ast.Ident:
1126         case *ast.BasicLit:
1127         case *ast.FuncLit:
1128         case *ast.CompositeLit:
1129         case *ast.ParenExpr:
1130                 panic("unreachable")
1131         case *ast.SelectorExpr:
1132         case *ast.IndexExpr:
1133         case *ast.SliceExpr:
1134         case *ast.TypeAssertExpr:
1135                 if t.Type == nil {
1136                         // the form X.(type) is only allowed in type switch expressions
1137                         p.errorExpected(x.Pos(), "expression")
1138                         x = &ast.BadExpr{x.Pos(), x.End()}
1139                 }
1140         case *ast.CallExpr:
1141         case *ast.StarExpr:
1142         case *ast.UnaryExpr:
1143                 if t.Op == token.RANGE {
1144                         // the range operator is only allowed at the top of a for statement
1145                         p.errorExpected(x.Pos(), "expression")
1146                         x = &ast.BadExpr{x.Pos(), x.End()}
1147                 }
1148         case *ast.BinaryExpr:
1149         default:
1150                 // all other nodes are not proper expressions
1151                 p.errorExpected(x.Pos(), "expression")
1152                 x = &ast.BadExpr{x.Pos(), x.End()}
1153         }
1154         return x
1155 }
1156
1157
1158 // isTypeName returns true iff x is a (qualified) TypeName.
1159 func isTypeName(x ast.Expr) bool {
1160         switch t := x.(type) {
1161         case *ast.BadExpr:
1162         case *ast.Ident:
1163         case *ast.SelectorExpr:
1164                 _, isIdent := t.X.(*ast.Ident)
1165                 return isIdent
1166         default:
1167                 return false // all other nodes are not type names
1168         }
1169         return true
1170 }
1171
1172
1173 // isLiteralType returns true iff x is a legal composite literal type.
1174 func isLiteralType(x ast.Expr) bool {
1175         switch t := x.(type) {
1176         case *ast.BadExpr:
1177         case *ast.Ident:
1178         case *ast.SelectorExpr:
1179                 _, isIdent := t.X.(*ast.Ident)
1180                 return isIdent
1181         case *ast.ArrayType:
1182         case *ast.StructType:
1183         case *ast.MapType:
1184         default:
1185                 return false // all other nodes are not legal composite literal types
1186         }
1187         return true
1188 }
1189
1190
1191 // If x is of the form *T, deref returns T, otherwise it returns x.
1192 func deref(x ast.Expr) ast.Expr {
1193         if p, isPtr := x.(*ast.StarExpr); isPtr {
1194                 x = p.X
1195         }
1196         return x
1197 }
1198
1199
1200 // If x is of the form (T), unparen returns unparen(T), otherwise it returns x.
1201 func unparen(x ast.Expr) ast.Expr {
1202         if p, isParen := x.(*ast.ParenExpr); isParen {
1203                 x = unparen(p.X)
1204         }
1205         return x
1206 }
1207
1208
1209 // checkExprOrType checks that x is an expression or a type
1210 // (and not a raw type such as [...]T).
1211 //
1212 func (p *parser) checkExprOrType(x ast.Expr) ast.Expr {
1213         switch t := unparen(x).(type) {
1214         case *ast.ParenExpr:
1215                 panic("unreachable")
1216         case *ast.UnaryExpr:
1217                 if t.Op == token.RANGE {
1218                         // the range operator is only allowed at the top of a for statement
1219                         p.errorExpected(x.Pos(), "expression")
1220                         x = &ast.BadExpr{x.Pos(), x.End()}
1221                 }
1222         case *ast.ArrayType:
1223                 if len, isEllipsis := t.Len.(*ast.Ellipsis); isEllipsis {
1224                         p.error(len.Pos(), "expected array length, found '...'")
1225                         x = &ast.BadExpr{x.Pos(), x.End()}
1226                 }
1227         }
1228
1229         // all other nodes are expressions or types
1230         return x
1231 }
1232
1233
1234 func (p *parser) parsePrimaryExpr() ast.Expr {
1235         if p.trace {
1236                 defer un(trace(p, "PrimaryExpr"))
1237         }
1238
1239         x := p.parseOperand()
1240 L:
1241         for {
1242                 switch p.tok {
1243                 case token.PERIOD:
1244                         x = p.parseSelectorOrTypeAssertion(p.checkExpr(x))
1245                 case token.LBRACK:
1246                         x = p.parseIndexOrSlice(p.checkExpr(x))
1247                 case token.LPAREN:
1248                         x = p.parseCallOrConversion(p.checkExprOrType(x))
1249                 case token.LBRACE:
1250                         if isLiteralType(x) && (p.exprLev >= 0 || !isTypeName(x)) {
1251                                 x = p.parseLiteralValue(x)
1252                         } else {
1253                                 break L
1254                         }
1255                 default:
1256                         break L
1257                 }
1258         }
1259
1260         return x
1261 }
1262
1263
1264 func (p *parser) parseUnaryExpr() ast.Expr {
1265         if p.trace {
1266                 defer un(trace(p, "UnaryExpr"))
1267         }
1268
1269         switch p.tok {
1270         case token.ADD, token.SUB, token.NOT, token.XOR, token.AND, token.RANGE:
1271                 pos, op := p.pos, p.tok
1272                 p.next()
1273                 x := p.parseUnaryExpr()
1274                 return &ast.UnaryExpr{pos, op, p.checkExpr(x)}
1275
1276         case token.ARROW:
1277                 // channel type or receive expression
1278                 pos := p.pos
1279                 p.next()
1280                 if p.tok == token.CHAN {
1281                         p.next()
1282                         value := p.parseType()
1283                         return &ast.ChanType{pos, ast.RECV, value}
1284                 }
1285
1286                 x := p.parseUnaryExpr()
1287                 return &ast.UnaryExpr{pos, token.ARROW, p.checkExpr(x)}
1288
1289         case token.MUL:
1290                 // pointer type or unary "*" expression
1291                 pos := p.pos
1292                 p.next()
1293                 x := p.parseUnaryExpr()
1294                 return &ast.StarExpr{pos, p.checkExprOrType(x)}
1295         }
1296
1297         return p.parsePrimaryExpr()
1298 }
1299
1300
1301 func (p *parser) parseBinaryExpr(prec1 int) ast.Expr {
1302         if p.trace {
1303                 defer un(trace(p, "BinaryExpr"))
1304         }
1305
1306         x := p.parseUnaryExpr()
1307         for prec := p.tok.Precedence(); prec >= prec1; prec-- {
1308                 for p.tok.Precedence() == prec {
1309                         pos, op := p.pos, p.tok
1310                         p.next()
1311                         y := p.parseBinaryExpr(prec + 1)
1312                         x = &ast.BinaryExpr{p.checkExpr(x), pos, op, p.checkExpr(y)}
1313                 }
1314         }
1315
1316         return x
1317 }
1318
1319
1320 // TODO(gri): parseExpr may return a type or even a raw type ([..]int) -
1321 //            should reject when a type/raw type is obviously not allowed
1322 func (p *parser) parseExpr() ast.Expr {
1323         if p.trace {
1324                 defer un(trace(p, "Expression"))
1325         }
1326
1327         return p.parseBinaryExpr(token.LowestPrec + 1)
1328 }
1329
1330
1331 // ----------------------------------------------------------------------------
1332 // Statements
1333
1334 func (p *parser) parseSimpleStmt(labelOk bool) ast.Stmt {
1335         if p.trace {
1336                 defer un(trace(p, "SimpleStmt"))
1337         }
1338
1339         x := p.parseExprList()
1340
1341         switch p.tok {
1342         case
1343                 token.DEFINE, token.ASSIGN, token.ADD_ASSIGN,
1344                 token.SUB_ASSIGN, token.MUL_ASSIGN, token.QUO_ASSIGN,
1345                 token.REM_ASSIGN, token.AND_ASSIGN, token.OR_ASSIGN,
1346                 token.XOR_ASSIGN, token.SHL_ASSIGN, token.SHR_ASSIGN, token.AND_NOT_ASSIGN:
1347                 // assignment statement
1348                 pos, tok := p.pos, p.tok
1349                 p.next()
1350                 y := p.parseExprList()
1351                 if tok == token.DEFINE {
1352                         p.shortVarDecl(p.makeIdentList(x))
1353                 }
1354                 return &ast.AssignStmt{x, pos, tok, y}
1355         }
1356
1357         if len(x) > 1 {
1358                 p.errorExpected(x[0].Pos(), "1 expression")
1359                 // continue with first expression
1360         }
1361
1362         switch p.tok {
1363         case token.COLON:
1364                 // labeled statement
1365                 colon := p.pos
1366                 p.next()
1367                 if label, isIdent := x[0].(*ast.Ident); labelOk && isIdent {
1368                         // Go spec: The scope of a label is the body of the function
1369                         // in which it is declared and excludes the body of any nested
1370                         // function.
1371                         stmt := &ast.LabeledStmt{label, colon, p.parseStmt()}
1372                         p.declare(stmt, p.labelScope, ast.Lbl, label)
1373                         return stmt
1374                 }
1375                 p.error(x[0].Pos(), "illegal label declaration")
1376                 return &ast.BadStmt{x[0].Pos(), colon + 1}
1377
1378         case token.ARROW:
1379                 // send statement
1380                 arrow := p.pos
1381                 p.next() // consume "<-"
1382                 y := p.parseExpr()
1383                 return &ast.SendStmt{x[0], arrow, y}
1384
1385         case token.INC, token.DEC:
1386                 // increment or decrement
1387                 s := &ast.IncDecStmt{x[0], p.pos, p.tok}
1388                 p.next() // consume "++" or "--"
1389                 return s
1390         }
1391
1392         // expression
1393         return &ast.ExprStmt{x[0]}
1394 }
1395
1396
1397 func (p *parser) parseCallExpr() *ast.CallExpr {
1398         x := p.parseExpr()
1399         if call, isCall := x.(*ast.CallExpr); isCall {
1400                 return call
1401         }
1402         p.errorExpected(x.Pos(), "function/method call")
1403         return nil
1404 }
1405
1406
1407 func (p *parser) parseGoStmt() ast.Stmt {
1408         if p.trace {
1409                 defer un(trace(p, "GoStmt"))
1410         }
1411
1412         pos := p.expect(token.GO)
1413         call := p.parseCallExpr()
1414         p.expectSemi()
1415         if call == nil {
1416                 return &ast.BadStmt{pos, pos + 2} // len("go")
1417         }
1418
1419         return &ast.GoStmt{pos, call}
1420 }
1421
1422
1423 func (p *parser) parseDeferStmt() ast.Stmt {
1424         if p.trace {
1425                 defer un(trace(p, "DeferStmt"))
1426         }
1427
1428         pos := p.expect(token.DEFER)
1429         call := p.parseCallExpr()
1430         p.expectSemi()
1431         if call == nil {
1432                 return &ast.BadStmt{pos, pos + 5} // len("defer")
1433         }
1434
1435         return &ast.DeferStmt{pos, call}
1436 }
1437
1438
1439 func (p *parser) parseReturnStmt() *ast.ReturnStmt {
1440         if p.trace {
1441                 defer un(trace(p, "ReturnStmt"))
1442         }
1443
1444         pos := p.pos
1445         p.expect(token.RETURN)
1446         var x []ast.Expr
1447         if p.tok != token.SEMICOLON && p.tok != token.RBRACE {
1448                 x = p.parseExprList()
1449         }
1450         p.expectSemi()
1451
1452         return &ast.ReturnStmt{pos, x}
1453 }
1454
1455
1456 func (p *parser) parseBranchStmt(tok token.Token) *ast.BranchStmt {
1457         if p.trace {
1458                 defer un(trace(p, "BranchStmt"))
1459         }
1460
1461         pos := p.expect(tok)
1462         var label *ast.Ident
1463         if tok != token.FALLTHROUGH && p.tok == token.IDENT {
1464                 label = p.parseIdent()
1465                 // add to list of unresolved targets
1466                 n := len(p.targetStack) - 1
1467                 p.targetStack[n] = append(p.targetStack[n], label)
1468         }
1469         p.expectSemi()
1470
1471         return &ast.BranchStmt{pos, tok, label}
1472 }
1473
1474
1475 func (p *parser) makeExpr(s ast.Stmt) ast.Expr {
1476         if s == nil {
1477                 return nil
1478         }
1479         if es, isExpr := s.(*ast.ExprStmt); isExpr {
1480                 return p.checkExpr(es.X)
1481         }
1482         p.error(s.Pos(), "expected condition, found simple statement")
1483         return &ast.BadExpr{s.Pos(), s.End()}
1484 }
1485
1486
1487 func (p *parser) parseIfStmt() *ast.IfStmt {
1488         if p.trace {
1489                 defer un(trace(p, "IfStmt"))
1490         }
1491
1492         pos := p.expect(token.IF)
1493         p.openScope()
1494         defer p.closeScope()
1495
1496         var s ast.Stmt
1497         var x ast.Expr
1498         {
1499                 prevLev := p.exprLev
1500                 p.exprLev = -1
1501                 if p.tok == token.SEMICOLON {
1502                         p.next()
1503                         x = p.parseExpr()
1504                 } else {
1505                         s = p.parseSimpleStmt(false)
1506                         if p.tok == token.SEMICOLON {
1507                                 p.next()
1508                                 x = p.parseExpr()
1509                         } else {
1510                                 x = p.makeExpr(s)
1511                                 s = nil
1512                         }
1513                 }
1514                 p.exprLev = prevLev
1515         }
1516
1517         body := p.parseBlockStmt()
1518         var else_ ast.Stmt
1519         if p.tok == token.ELSE {
1520                 p.next()
1521                 else_ = p.parseStmt()
1522         } else {
1523                 p.expectSemi()
1524         }
1525
1526         return &ast.IfStmt{pos, s, x, body, else_}
1527 }
1528
1529
1530 func (p *parser) parseTypeList() (list []ast.Expr) {
1531         if p.trace {
1532                 defer un(trace(p, "TypeList"))
1533         }
1534
1535         list = append(list, p.parseType())
1536         for p.tok == token.COMMA {
1537                 p.next()
1538                 list = append(list, p.parseType())
1539         }
1540
1541         return
1542 }
1543
1544
1545 func (p *parser) parseCaseClause(exprSwitch bool) *ast.CaseClause {
1546         if p.trace {
1547                 defer un(trace(p, "CaseClause"))
1548         }
1549
1550         pos := p.pos
1551         var list []ast.Expr
1552         if p.tok == token.CASE {
1553                 p.next()
1554                 if exprSwitch {
1555                         list = p.parseExprList()
1556                 } else {
1557                         list = p.parseTypeList()
1558                 }
1559         } else {
1560                 p.expect(token.DEFAULT)
1561         }
1562
1563         colon := p.expect(token.COLON)
1564         p.openScope()
1565         body := p.parseStmtList()
1566         p.closeScope()
1567
1568         return &ast.CaseClause{pos, list, colon, body}
1569 }
1570
1571
1572 func isExprSwitch(s ast.Stmt) bool {
1573         if s == nil {
1574                 return true
1575         }
1576         if e, ok := s.(*ast.ExprStmt); ok {
1577                 if a, ok := e.X.(*ast.TypeAssertExpr); ok {
1578                         return a.Type != nil // regular type assertion
1579                 }
1580                 return true
1581         }
1582         return false
1583 }
1584
1585
1586 func (p *parser) parseSwitchStmt() ast.Stmt {
1587         if p.trace {
1588                 defer un(trace(p, "SwitchStmt"))
1589         }
1590
1591         pos := p.expect(token.SWITCH)
1592         p.openScope()
1593         defer p.closeScope()
1594
1595         var s1, s2 ast.Stmt
1596         if p.tok != token.LBRACE {
1597                 prevLev := p.exprLev
1598                 p.exprLev = -1
1599                 if p.tok != token.SEMICOLON {
1600                         s2 = p.parseSimpleStmt(false)
1601                 }
1602                 if p.tok == token.SEMICOLON {
1603                         p.next()
1604                         s1 = s2
1605                         s2 = nil
1606                         if p.tok != token.LBRACE {
1607                                 s2 = p.parseSimpleStmt(false)
1608                         }
1609                 }
1610                 p.exprLev = prevLev
1611         }
1612
1613         exprSwitch := isExprSwitch(s2)
1614         lbrace := p.expect(token.LBRACE)
1615         var list []ast.Stmt
1616         for p.tok == token.CASE || p.tok == token.DEFAULT {
1617                 list = append(list, p.parseCaseClause(exprSwitch))
1618         }
1619         rbrace := p.expect(token.RBRACE)
1620         p.expectSemi()
1621         body := &ast.BlockStmt{lbrace, list, rbrace}
1622
1623         if exprSwitch {
1624                 return &ast.SwitchStmt{pos, s1, p.makeExpr(s2), body}
1625         }
1626         // type switch
1627         // TODO(gri): do all the checks!
1628         return &ast.TypeSwitchStmt{pos, s1, s2, body}
1629 }
1630
1631
1632 func (p *parser) parseCommClause() *ast.CommClause {
1633         if p.trace {
1634                 defer un(trace(p, "CommClause"))
1635         }
1636
1637         p.openScope()
1638         pos := p.pos
1639         var comm ast.Stmt
1640         if p.tok == token.CASE {
1641                 p.next()
1642                 lhs := p.parseExprList()
1643                 if p.tok == token.ARROW {
1644                         // SendStmt
1645                         if len(lhs) > 1 {
1646                                 p.errorExpected(lhs[0].Pos(), "1 expression")
1647                                 // continue with first expression
1648                         }
1649                         arrow := p.pos
1650                         p.next()
1651                         rhs := p.parseExpr()
1652                         comm = &ast.SendStmt{lhs[0], arrow, rhs}
1653                 } else {
1654                         // RecvStmt
1655                         pos := p.pos
1656                         tok := p.tok
1657                         var rhs ast.Expr
1658                         if tok == token.ASSIGN || tok == token.DEFINE {
1659                                 // RecvStmt with assignment
1660                                 if len(lhs) > 2 {
1661                                         p.errorExpected(lhs[0].Pos(), "1 or 2 expressions")
1662                                         // continue with first two expressions
1663                                         lhs = lhs[0:2]
1664                                 }
1665                                 p.next()
1666                                 rhs = p.parseExpr()
1667                                 if tok == token.DEFINE {
1668                                         p.shortVarDecl(p.makeIdentList(lhs))
1669                                 }
1670                         } else {
1671                                 // rhs must be single receive operation
1672                                 if len(lhs) > 1 {
1673                                         p.errorExpected(lhs[0].Pos(), "1 expression")
1674                                         // continue with first expression
1675                                 }
1676                                 rhs = lhs[0]
1677                                 lhs = nil // there is no lhs
1678                         }
1679                         if x, isUnary := rhs.(*ast.UnaryExpr); !isUnary || x.Op != token.ARROW {
1680                                 p.errorExpected(rhs.Pos(), "send or receive operation")
1681                                 rhs = &ast.BadExpr{rhs.Pos(), rhs.End()}
1682                         }
1683                         if lhs != nil {
1684                                 comm = &ast.AssignStmt{lhs, pos, tok, []ast.Expr{rhs}}
1685                         } else {
1686                                 comm = &ast.ExprStmt{rhs}
1687                         }
1688                 }
1689         } else {
1690                 p.expect(token.DEFAULT)
1691         }
1692
1693         colon := p.expect(token.COLON)
1694         body := p.parseStmtList()
1695         p.closeScope()
1696
1697         return &ast.CommClause{pos, comm, colon, body}
1698 }
1699
1700
1701 func (p *parser) parseSelectStmt() *ast.SelectStmt {
1702         if p.trace {
1703                 defer un(trace(p, "SelectStmt"))
1704         }
1705
1706         pos := p.expect(token.SELECT)
1707         lbrace := p.expect(token.LBRACE)
1708         var list []ast.Stmt
1709         for p.tok == token.CASE || p.tok == token.DEFAULT {
1710                 list = append(list, p.parseCommClause())
1711         }
1712         rbrace := p.expect(token.RBRACE)
1713         p.expectSemi()
1714         body := &ast.BlockStmt{lbrace, list, rbrace}
1715
1716         return &ast.SelectStmt{pos, body}
1717 }
1718
1719
1720 func (p *parser) parseForStmt() ast.Stmt {
1721         if p.trace {
1722                 defer un(trace(p, "ForStmt"))
1723         }
1724
1725         pos := p.expect(token.FOR)
1726         p.openScope()
1727         defer p.closeScope()
1728
1729         var s1, s2, s3 ast.Stmt
1730         if p.tok != token.LBRACE {
1731                 prevLev := p.exprLev
1732                 p.exprLev = -1
1733                 if p.tok != token.SEMICOLON {
1734                         s2 = p.parseSimpleStmt(false)
1735                 }
1736                 if p.tok == token.SEMICOLON {
1737                         p.next()
1738                         s1 = s2
1739                         s2 = nil
1740                         if p.tok != token.SEMICOLON {
1741                                 s2 = p.parseSimpleStmt(false)
1742                         }
1743                         p.expectSemi()
1744                         if p.tok != token.LBRACE {
1745                                 s3 = p.parseSimpleStmt(false)
1746                         }
1747                 }
1748                 p.exprLev = prevLev
1749         }
1750
1751         body := p.parseBlockStmt()
1752         p.expectSemi()
1753
1754         if as, isAssign := s2.(*ast.AssignStmt); isAssign {
1755                 // possibly a for statement with a range clause; check assignment operator
1756                 if as.Tok != token.ASSIGN && as.Tok != token.DEFINE {
1757                         p.errorExpected(as.TokPos, "'=' or ':='")
1758                         return &ast.BadStmt{pos, body.End()}
1759                 }
1760                 // check lhs
1761                 var key, value ast.Expr
1762                 switch len(as.Lhs) {
1763                 case 2:
1764                         key, value = as.Lhs[0], as.Lhs[1]
1765                 case 1:
1766                         key = as.Lhs[0]
1767                 default:
1768                         p.errorExpected(as.Lhs[0].Pos(), "1 or 2 expressions")
1769                         return &ast.BadStmt{pos, body.End()}
1770                 }
1771                 // check rhs
1772                 if len(as.Rhs) != 1 {
1773                         p.errorExpected(as.Rhs[0].Pos(), "1 expression")
1774                         return &ast.BadStmt{pos, body.End()}
1775                 }
1776                 if rhs, isUnary := as.Rhs[0].(*ast.UnaryExpr); isUnary && rhs.Op == token.RANGE {
1777                         // rhs is range expression
1778                         // (any short variable declaration was handled by parseSimpleStat above)
1779                         return &ast.RangeStmt{pos, key, value, as.TokPos, as.Tok, rhs.X, body}
1780                 }
1781                 p.errorExpected(s2.Pos(), "range clause")
1782                 return &ast.BadStmt{pos, body.End()}
1783         }
1784
1785         // regular for statement
1786         return &ast.ForStmt{pos, s1, p.makeExpr(s2), s3, body}
1787 }
1788
1789
1790 func (p *parser) parseStmt() (s ast.Stmt) {
1791         if p.trace {
1792                 defer un(trace(p, "Statement"))
1793         }
1794
1795         switch p.tok {
1796         case token.CONST, token.TYPE, token.VAR:
1797                 s = &ast.DeclStmt{p.parseDecl()}
1798         case
1799                 // tokens that may start a top-level expression
1800                 token.IDENT, token.INT, token.FLOAT, token.CHAR, token.STRING, token.FUNC, token.LPAREN, // operand
1801                 token.LBRACK, token.STRUCT, // composite type
1802                 token.MUL, token.AND, token.ARROW, token.ADD, token.SUB, token.XOR: // unary operators
1803                 s = p.parseSimpleStmt(true)
1804                 // because of the required look-ahead, labeled statements are
1805                 // parsed by parseSimpleStmt - don't expect a semicolon after
1806                 // them
1807                 if _, isLabeledStmt := s.(*ast.LabeledStmt); !isLabeledStmt {
1808                         p.expectSemi()
1809                 }
1810         case token.GO:
1811                 s = p.parseGoStmt()
1812         case token.DEFER:
1813                 s = p.parseDeferStmt()
1814         case token.RETURN:
1815                 s = p.parseReturnStmt()
1816         case token.BREAK, token.CONTINUE, token.GOTO, token.FALLTHROUGH:
1817                 s = p.parseBranchStmt(p.tok)
1818         case token.LBRACE:
1819                 s = p.parseBlockStmt()
1820                 p.expectSemi()
1821         case token.IF:
1822                 s = p.parseIfStmt()
1823         case token.SWITCH:
1824                 s = p.parseSwitchStmt()
1825         case token.SELECT:
1826                 s = p.parseSelectStmt()
1827         case token.FOR:
1828                 s = p.parseForStmt()
1829         case token.SEMICOLON:
1830                 s = &ast.EmptyStmt{p.pos}
1831                 p.next()
1832         case token.RBRACE:
1833                 // a semicolon may be omitted before a closing "}"
1834                 s = &ast.EmptyStmt{p.pos}
1835         default:
1836                 // no statement found
1837                 pos := p.pos
1838                 p.errorExpected(pos, "statement")
1839                 p.next() // make progress
1840                 s = &ast.BadStmt{pos, p.pos}
1841         }
1842
1843         return
1844 }
1845
1846
1847 // ----------------------------------------------------------------------------
1848 // Declarations
1849
1850 type parseSpecFunction func(p *parser, doc *ast.CommentGroup, iota int) ast.Spec
1851
1852
1853 func parseImportSpec(p *parser, doc *ast.CommentGroup, _ int) ast.Spec {
1854         if p.trace {
1855                 defer un(trace(p, "ImportSpec"))
1856         }
1857
1858         var ident *ast.Ident
1859         switch p.tok {
1860         case token.PERIOD:
1861                 ident = &ast.Ident{p.pos, ".", nil}
1862                 p.next()
1863         case token.IDENT:
1864                 ident = p.parseIdent()
1865         }
1866
1867         var path *ast.BasicLit
1868         if p.tok == token.STRING {
1869                 path = &ast.BasicLit{p.pos, p.tok, p.lit()}
1870                 p.next()
1871         } else {
1872                 p.expect(token.STRING) // use expect() error handling
1873         }
1874         p.expectSemi() // call before accessing p.linecomment
1875
1876         return &ast.ImportSpec{doc, ident, path, p.lineComment}
1877 }
1878
1879
1880 func parseConstSpec(p *parser, doc *ast.CommentGroup, iota int) ast.Spec {
1881         if p.trace {
1882                 defer un(trace(p, "ConstSpec"))
1883         }
1884
1885         idents := p.parseIdentList()
1886         typ := p.tryType()
1887         var values []ast.Expr
1888         if typ != nil || p.tok == token.ASSIGN || iota == 0 {
1889                 p.expect(token.ASSIGN)
1890                 values = p.parseExprList()
1891         }
1892         p.expectSemi() // call before accessing p.linecomment
1893
1894         // Go spec: The scope of a constant or variable identifier declared inside
1895         // a function begins at the end of the ConstSpec or VarSpec and ends at
1896         // the end of the innermost containing block.
1897         // (Global identifiers are resolved in a separate phase after parsing.)
1898         spec := &ast.ValueSpec{doc, idents, typ, values, p.lineComment}
1899         p.declare(spec, p.topScope, ast.Con, idents...)
1900
1901         return spec
1902 }
1903
1904
1905 func parseTypeSpec(p *parser, doc *ast.CommentGroup, _ int) ast.Spec {
1906         if p.trace {
1907                 defer un(trace(p, "TypeSpec"))
1908         }
1909
1910         ident := p.parseIdent()
1911         typ := p.parseType()
1912         p.expectSemi() // call before accessing p.linecomment
1913
1914         // Go spec: The scope of a type identifier declared inside a function begins
1915         // at the identifier in the TypeSpec and ends at the end of the innermost
1916         // containing block.
1917         // (Global identifiers are resolved in a separate phase after parsing.)
1918         spec := &ast.TypeSpec{doc, ident, typ, p.lineComment}
1919         p.declare(spec, p.topScope, ast.Typ, ident)
1920
1921         return spec
1922 }
1923
1924
1925 func parseVarSpec(p *parser, doc *ast.CommentGroup, _ int) ast.Spec {
1926         if p.trace {
1927                 defer un(trace(p, "VarSpec"))
1928         }
1929
1930         idents := p.parseIdentList()
1931         typ := p.tryType()
1932         var values []ast.Expr
1933         if typ == nil || p.tok == token.ASSIGN {
1934                 p.expect(token.ASSIGN)
1935                 values = p.parseExprList()
1936         }
1937         p.expectSemi() // call before accessing p.linecomment
1938
1939         // Go spec: The scope of a constant or variable identifier declared inside
1940         // a function begins at the end of the ConstSpec or VarSpec and ends at
1941         // the end of the innermost containing block.
1942         // (Global identifiers are resolved in a separate phase after parsing.)
1943         spec := &ast.ValueSpec{doc, idents, typ, values, p.lineComment}
1944         p.declare(spec, p.topScope, ast.Var, idents...)
1945
1946         return spec
1947 }
1948
1949
1950 func (p *parser) parseGenDecl(keyword token.Token, f parseSpecFunction) *ast.GenDecl {
1951         if p.trace {
1952                 defer un(trace(p, "GenDecl("+keyword.String()+")"))
1953         }
1954
1955         doc := p.leadComment
1956         pos := p.expect(keyword)
1957         var lparen, rparen token.Pos
1958         var list []ast.Spec
1959         if p.tok == token.LPAREN {
1960                 lparen = p.pos
1961                 p.next()
1962                 for iota := 0; p.tok != token.RPAREN && p.tok != token.EOF; iota++ {
1963                         list = append(list, f(p, p.leadComment, iota))
1964                 }
1965                 rparen = p.expect(token.RPAREN)
1966                 p.expectSemi()
1967         } else {
1968                 list = append(list, f(p, nil, 0))
1969         }
1970
1971         return &ast.GenDecl{doc, pos, keyword, lparen, list, rparen}
1972 }
1973
1974
1975 func (p *parser) parseReceiver(scope *ast.Scope) *ast.FieldList {
1976         if p.trace {
1977                 defer un(trace(p, "Receiver"))
1978         }
1979
1980         pos := p.pos
1981         par := p.parseParameters(scope, false)
1982
1983         // must have exactly one receiver
1984         if par.NumFields() != 1 {
1985                 p.errorExpected(pos, "exactly one receiver")
1986                 // TODO determine a better range for BadExpr below
1987                 par.List = []*ast.Field{&ast.Field{Type: &ast.BadExpr{pos, pos}}}
1988                 return par
1989         }
1990
1991         // recv type must be of the form ["*"] identifier
1992         recv := par.List[0]
1993         base := deref(recv.Type)
1994         if _, isIdent := base.(*ast.Ident); !isIdent {
1995                 p.errorExpected(base.Pos(), "(unqualified) identifier")
1996                 par.List = []*ast.Field{&ast.Field{Type: &ast.BadExpr{recv.Pos(), recv.End()}}}
1997         }
1998
1999         return par
2000 }
2001
2002
2003 func (p *parser) parseFuncDecl() *ast.FuncDecl {
2004         if p.trace {
2005                 defer un(trace(p, "FunctionDecl"))
2006         }
2007
2008         doc := p.leadComment
2009         pos := p.expect(token.FUNC)
2010         scope := ast.NewScope(p.topScope) // function scope
2011
2012         var recv *ast.FieldList
2013         if p.tok == token.LPAREN {
2014                 recv = p.parseReceiver(scope)
2015         }
2016
2017         ident := p.parseIdent()
2018
2019         params, results := p.parseSignature(scope)
2020
2021         var body *ast.BlockStmt
2022         if p.tok == token.LBRACE {
2023                 body = p.parseBody(scope)
2024         }
2025         p.expectSemi()
2026
2027         decl := &ast.FuncDecl{doc, recv, ident, &ast.FuncType{pos, params, results}, body}
2028         if recv == nil {
2029                 // Go spec: The scope of an identifier denoting a constant, type,
2030                 // variable, or function (but not method) declared at top level
2031                 // (outside any function) is the package block.
2032                 //
2033                 // init() functions cannot be referred to and there may
2034                 // be more than one - don't put them in the pkgScope
2035                 if ident.Name != "init" {
2036                         p.declare(decl, p.pkgScope, ast.Fun, ident)
2037                 }
2038         }
2039
2040         return decl
2041 }
2042
2043
2044 func (p *parser) parseDecl() ast.Decl {
2045         if p.trace {
2046                 defer un(trace(p, "Declaration"))
2047         }
2048
2049         var f parseSpecFunction
2050         switch p.tok {
2051         case token.CONST:
2052                 f = parseConstSpec
2053
2054         case token.TYPE:
2055                 f = parseTypeSpec
2056
2057         case token.VAR:
2058                 f = parseVarSpec
2059
2060         case token.FUNC:
2061                 return p.parseFuncDecl()
2062
2063         default:
2064                 pos := p.pos
2065                 p.errorExpected(pos, "declaration")
2066                 p.next() // make progress
2067                 decl := &ast.BadDecl{pos, p.pos}
2068                 return decl
2069         }
2070
2071         return p.parseGenDecl(p.tok, f)
2072 }
2073
2074
2075 func (p *parser) parseDeclList() (list []ast.Decl) {
2076         if p.trace {
2077                 defer un(trace(p, "DeclList"))
2078         }
2079
2080         for p.tok != token.EOF {
2081                 list = append(list, p.parseDecl())
2082         }
2083
2084         return
2085 }
2086
2087
2088 // ----------------------------------------------------------------------------
2089 // Source files
2090
2091 func (p *parser) parseFile() *ast.File {
2092         if p.trace {
2093                 defer un(trace(p, "File"))
2094         }
2095
2096         // package clause
2097         doc := p.leadComment
2098         pos := p.expect(token.PACKAGE)
2099         // Go spec: The package clause is not a declaration;
2100         // the package name does not appear in any scope.
2101         ident := p.parseIdent()
2102         p.expectSemi()
2103
2104         var decls []ast.Decl
2105
2106         // Don't bother parsing the rest if we had errors already.
2107         // Likely not a Go source file at all.
2108
2109         if p.ErrorCount() == 0 && p.mode&PackageClauseOnly == 0 {
2110                 // import decls
2111                 for p.tok == token.IMPORT {
2112                         decls = append(decls, p.parseGenDecl(token.IMPORT, parseImportSpec))
2113                 }
2114
2115                 if p.mode&ImportsOnly == 0 {
2116                         // rest of package body
2117                         for p.tok != token.EOF {
2118                                 decls = append(decls, p.parseDecl())
2119                         }
2120                 }
2121         }
2122
2123         if p.topScope != p.pkgScope {
2124                 panic("internal error: imbalanced scopes")
2125         }
2126
2127         // resolve global identifiers within the same file
2128         i := 0
2129         for _, ident := range p.unresolved {
2130                 // i <= index for current ident
2131                 ident.Obj = p.pkgScope.Lookup(ident.Name)
2132                 if ident.Obj == nil {
2133                         p.unresolved[i] = ident
2134                         i++
2135                 }
2136         }
2137
2138         return &ast.File{doc, pos, ident, decls, p.pkgScope, p.unresolved[0:i], p.comments}
2139 }