1// Package asmgotostate implements the asmgoto example with global state instead of GlobalStore. 2// 3// Very simplistic assembler language, only containing noop and jump instructions. 4// Jump instructions use labels as target, which may be defined optionally on ever code line. 5// 6// The global state is used to keep track of the labels as well as the unresolved targets for jump instructions. 7// 8// Example: 9// label: noop 10// jump label 11// 12package asmgotostate 13 14import ( 15 "bytes" 16 "errors" 17 "fmt" 18 "io" 19 "io/ioutil" 20 "math" 21 "os" 22 "sort" 23 "strconv" 24 "strings" 25 "unicode" 26 "unicode/utf8" 27) 28 29func toIfaceSlice(v interface{}) []interface{} { 30 if v == nil { 31 return nil 32 } 33 return v.([]interface{}) 34} 35 36var g = &grammar{ 37 rules: []*rule{ 38 { 39 name: "Program", 40 pos: position{line: 23, col: 1, offset: 598}, 41 expr: &actionExpr{ 42 pos: position{line: 23, col: 11, offset: 610}, 43 run: (*parser).callonProgram1, 44 expr: &seqExpr{ 45 pos: position{line: 23, col: 11, offset: 610}, 46 exprs: []interface{}{ 47 &stateCodeExpr{ 48 pos: position{line: 23, col: 11, offset: 610}, 49 run: (*parser).callonProgram3, 50 }, 51 &labeledExpr{ 52 pos: position{line: 23, col: 126, offset: 725}, 53 label: "lines", 54 expr: &zeroOrMoreExpr{ 55 pos: position{line: 23, col: 132, offset: 731}, 56 expr: &ruleRefExpr{ 57 pos: position{line: 23, col: 132, offset: 731}, 58 name: "Line", 59 }, 60 }, 61 }, 62 &ruleRefExpr{ 63 pos: position{line: 23, col: 138, offset: 737}, 64 name: "EOF", 65 }, 66 &andCodeExpr{ 67 pos: position{line: 23, col: 142, offset: 741}, 68 run: (*parser).callonProgram8, 69 }, 70 }, 71 }, 72 }, 73 }, 74 { 75 name: "Line", 76 pos: position{line: 32, col: 1, offset: 965}, 77 expr: &actionExpr{ 78 pos: position{line: 32, col: 8, offset: 974}, 79 run: (*parser).callonLine1, 80 expr: &seqExpr{ 81 pos: position{line: 32, col: 8, offset: 974}, 82 exprs: []interface{}{ 83 &ruleRefExpr{ 84 pos: position{line: 32, col: 8, offset: 974}, 85 name: "_", 86 }, 87 &labeledExpr{ 88 pos: position{line: 32, col: 10, offset: 976}, 89 label: "inst", 90 expr: &ruleRefExpr{ 91 pos: position{line: 32, col: 15, offset: 981}, 92 name: "Instruction", 93 }, 94 }, 95 &ruleRefExpr{ 96 pos: position{line: 32, col: 27, offset: 993}, 97 name: "_", 98 }, 99 &choiceExpr{ 100 pos: position{line: 32, col: 30, offset: 996}, 101 alternatives: []interface{}{ 102 &ruleRefExpr{ 103 pos: position{line: 32, col: 30, offset: 996}, 104 name: "nl", 105 }, 106 &ruleRefExpr{ 107 pos: position{line: 32, col: 35, offset: 1001}, 108 name: "EOF", 109 }, 110 }, 111 }, 112 }, 113 }, 114 }, 115 }, 116 { 117 name: "Instruction", 118 pos: position{line: 36, col: 1, offset: 1030}, 119 expr: &actionExpr{ 120 pos: position{line: 36, col: 15, offset: 1046}, 121 run: (*parser).callonInstruction1, 122 expr: &seqExpr{ 123 pos: position{line: 36, col: 15, offset: 1046}, 124 exprs: []interface{}{ 125 &zeroOrOneExpr{ 126 pos: position{line: 36, col: 15, offset: 1046}, 127 expr: &ruleRefExpr{ 128 pos: position{line: 36, col: 15, offset: 1046}, 129 name: "Label", 130 }, 131 }, 132 &ruleRefExpr{ 133 pos: position{line: 36, col: 22, offset: 1053}, 134 name: "_", 135 }, 136 &labeledExpr{ 137 pos: position{line: 36, col: 24, offset: 1055}, 138 label: "op", 139 expr: &choiceExpr{ 140 pos: position{line: 36, col: 29, offset: 1060}, 141 alternatives: []interface{}{ 142 &ruleRefExpr{ 143 pos: position{line: 36, col: 29, offset: 1060}, 144 name: "Noop", 145 }, 146 &ruleRefExpr{ 147 pos: position{line: 36, col: 36, offset: 1067}, 148 name: "Jump", 149 }, 150 }, 151 }, 152 }, 153 }, 154 }, 155 }, 156 }, 157 { 158 name: "Label", 159 pos: position{line: 40, col: 1, offset: 1096}, 160 expr: &seqExpr{ 161 pos: position{line: 40, col: 9, offset: 1106}, 162 exprs: []interface{}{ 163 &labeledExpr{ 164 pos: position{line: 40, col: 9, offset: 1106}, 165 label: "label", 166 expr: &ruleRefExpr{ 167 pos: position{line: 40, col: 15, offset: 1112}, 168 name: "labelIdentifier", 169 }, 170 }, 171 &stateCodeExpr{ 172 pos: position{line: 40, col: 31, offset: 1128}, 173 run: (*parser).callonLabel4, 174 }, 175 &litMatcher{ 176 pos: position{line: 40, col: 71, offset: 1168}, 177 val: ":", 178 ignoreCase: false, 179 }, 180 }, 181 }, 182 }, 183 { 184 name: "labelIdentifier", 185 pos: position{line: 42, col: 1, offset: 1173}, 186 expr: &actionExpr{ 187 pos: position{line: 42, col: 19, offset: 1193}, 188 run: (*parser).callonlabelIdentifier1, 189 expr: &seqExpr{ 190 pos: position{line: 42, col: 19, offset: 1193}, 191 exprs: []interface{}{ 192 &charClassMatcher{ 193 pos: position{line: 42, col: 19, offset: 1193}, 194 val: "[a-z]", 195 ranges: []rune{'a', 'z'}, 196 ignoreCase: false, 197 inverted: false, 198 }, 199 &zeroOrMoreExpr{ 200 pos: position{line: 42, col: 24, offset: 1198}, 201 expr: &charClassMatcher{ 202 pos: position{line: 42, col: 24, offset: 1198}, 203 val: "[a-z0-9]", 204 ranges: []rune{'a', 'z', '0', '9'}, 205 ignoreCase: false, 206 inverted: false, 207 }, 208 }, 209 }, 210 }, 211 }, 212 }, 213 { 214 name: "Noop", 215 pos: position{line: 46, col: 1, offset: 1242}, 216 expr: &actionExpr{ 217 pos: position{line: 46, col: 8, offset: 1251}, 218 run: (*parser).callonNoop1, 219 expr: &litMatcher{ 220 pos: position{line: 46, col: 8, offset: 1251}, 221 val: "noop", 222 ignoreCase: false, 223 }, 224 }, 225 }, 226 { 227 name: "Jump", 228 pos: position{line: 50, col: 1, offset: 1284}, 229 expr: &actionExpr{ 230 pos: position{line: 50, col: 8, offset: 1293}, 231 run: (*parser).callonJump1, 232 expr: &seqExpr{ 233 pos: position{line: 50, col: 8, offset: 1293}, 234 exprs: []interface{}{ 235 &litMatcher{ 236 pos: position{line: 50, col: 8, offset: 1293}, 237 val: "jump", 238 ignoreCase: false, 239 }, 240 &ruleRefExpr{ 241 pos: position{line: 50, col: 15, offset: 1300}, 242 name: "__", 243 }, 244 &labeledExpr{ 245 pos: position{line: 50, col: 18, offset: 1303}, 246 label: "label", 247 expr: &ruleRefExpr{ 248 pos: position{line: 50, col: 24, offset: 1309}, 249 name: "labelIdentifier", 250 }, 251 }, 252 &stateCodeExpr{ 253 pos: position{line: 50, col: 40, offset: 1325}, 254 run: (*parser).callonJump7, 255 }, 256 }, 257 }, 258 }, 259 }, 260 { 261 name: "nl", 262 displayName: "\"newline\"", 263 pos: position{line: 54, col: 1, offset: 1392}, 264 expr: &oneOrMoreExpr{ 265 pos: position{line: 54, col: 16, offset: 1409}, 266 expr: &charClassMatcher{ 267 pos: position{line: 54, col: 16, offset: 1409}, 268 val: "[\\n\\r]", 269 chars: []rune{'\n', '\r'}, 270 ignoreCase: false, 271 inverted: false, 272 }, 273 }, 274 }, 275 { 276 name: "__", 277 displayName: "\"whitespace\"", 278 pos: position{line: 56, col: 1, offset: 1418}, 279 expr: &oneOrMoreExpr{ 280 pos: position{line: 56, col: 19, offset: 1438}, 281 expr: &charClassMatcher{ 282 pos: position{line: 56, col: 19, offset: 1438}, 283 val: "[ \\t]", 284 chars: []rune{' ', '\t'}, 285 ignoreCase: false, 286 inverted: false, 287 }, 288 }, 289 }, 290 { 291 name: "_", 292 displayName: "\"optional whitespace\"", 293 pos: position{line: 58, col: 1, offset: 1446}, 294 expr: &zeroOrMoreExpr{ 295 pos: position{line: 58, col: 27, offset: 1474}, 296 expr: &charClassMatcher{ 297 pos: position{line: 58, col: 27, offset: 1474}, 298 val: "[ \\t]", 299 chars: []rune{' ', '\t'}, 300 ignoreCase: false, 301 inverted: false, 302 }, 303 }, 304 }, 305 { 306 name: "EOF", 307 pos: position{line: 60, col: 1, offset: 1482}, 308 expr: ¬Expr{ 309 pos: position{line: 60, col: 7, offset: 1490}, 310 expr: &anyMatcher{ 311 line: 60, col: 8, offset: 1491, 312 }, 313 }, 314 }, 315 }, 316} 317 318func (c *current) onProgram3() error { 319 if _, ok := c.state["labelLookup"]; !ok { 320 ll := make(labelLookup) 321 c.state["labelLookup"] = ll 322 } 323 return nil 324} 325 326func (p *parser) callonProgram3() error { 327 stack := p.vstack[len(p.vstack)-1] 328 _ = stack 329 return p.cur.onProgram3() 330} 331 332func (c *current) onProgram8(lines interface{}) (bool, error) { 333 return labelCheck(c) 334} 335 336func (p *parser) callonProgram8() (bool, error) { 337 stack := p.vstack[len(p.vstack)-1] 338 _ = stack 339 return p.cur.onProgram8(stack["lines"]) 340} 341 342func (c *current) onProgram1(lines interface{}) (interface{}, error) { 343 lines0 := toIfaceSlice(lines) 344 asmLines := make([]Instruction, 0, len(lines0)) 345 for _, line := range lines0 { 346 asmLines = append(asmLines, line.(Instruction)) 347 } 348 return asmLines, nil 349} 350 351func (p *parser) callonProgram1() (interface{}, error) { 352 stack := p.vstack[len(p.vstack)-1] 353 _ = stack 354 return p.cur.onProgram1(stack["lines"]) 355} 356 357func (c *current) onLine1(inst interface{}) (interface{}, error) { 358 return inst, nil 359} 360 361func (p *parser) callonLine1() (interface{}, error) { 362 stack := p.vstack[len(p.vstack)-1] 363 _ = stack 364 return p.cur.onLine1(stack["inst"]) 365} 366 367func (c *current) onInstruction1(op interface{}) (interface{}, error) { 368 return op, nil 369} 370 371func (p *parser) callonInstruction1() (interface{}, error) { 372 stack := p.vstack[len(p.vstack)-1] 373 _ = stack 374 return p.cur.onInstruction1(stack["op"]) 375} 376 377func (c *current) onLabel4(label interface{}) error { 378 return addLabel(c, label.(string)) 379} 380 381func (p *parser) callonLabel4() error { 382 stack := p.vstack[len(p.vstack)-1] 383 _ = stack 384 return p.cur.onLabel4(stack["label"]) 385} 386 387func (c *current) onlabelIdentifier1() (interface{}, error) { 388 return string(c.text), nil 389} 390 391func (p *parser) callonlabelIdentifier1() (interface{}, error) { 392 stack := p.vstack[len(p.vstack)-1] 393 _ = stack 394 return p.cur.onlabelIdentifier1() 395} 396 397func (c *current) onNoop1() (interface{}, error) { 398 return Noop{}, nil 399} 400 401func (p *parser) callonNoop1() (interface{}, error) { 402 stack := p.vstack[len(p.vstack)-1] 403 _ = stack 404 return p.cur.onNoop1() 405} 406 407func (c *current) onJump7(label interface{}) error { 408 return addJump(c, label.(string)) 409} 410 411func (p *parser) callonJump7() error { 412 stack := p.vstack[len(p.vstack)-1] 413 _ = stack 414 return p.cur.onJump7(stack["label"]) 415} 416 417func (c *current) onJump1(label interface{}) (interface{}, error) { 418 return getCurJump(c) 419} 420 421func (p *parser) callonJump1() (interface{}, error) { 422 stack := p.vstack[len(p.vstack)-1] 423 _ = stack 424 return p.cur.onJump1(stack["label"]) 425} 426 427var ( 428 // errNoRule is returned when the grammar to parse has no rule. 429 errNoRule = errors.New("grammar has no rule") 430 431 // errInvalidEntrypoint is returned when the specified entrypoint rule 432 // does not exit. 433 errInvalidEntrypoint = errors.New("invalid entrypoint") 434 435 // errInvalidEncoding is returned when the source is not properly 436 // utf8-encoded. 437 errInvalidEncoding = errors.New("invalid encoding") 438 439 // errMaxExprCnt is used to signal that the maximum number of 440 // expressions have been parsed. 441 errMaxExprCnt = errors.New("max number of expresssions parsed") 442) 443 444// Option is a function that can set an option on the parser. It returns 445// the previous setting as an Option. 446type Option func(*parser) Option 447 448// MaxExpressions creates an Option to stop parsing after the provided 449// number of expressions have been parsed, if the value is 0 then the parser will 450// parse for as many steps as needed (possibly an infinite number). 451// 452// The default for maxExprCnt is 0. 453func MaxExpressions(maxExprCnt uint64) Option { 454 return func(p *parser) Option { 455 oldMaxExprCnt := p.maxExprCnt 456 p.maxExprCnt = maxExprCnt 457 return MaxExpressions(oldMaxExprCnt) 458 } 459} 460 461// Entrypoint creates an Option to set the rule name to use as entrypoint. 462// The rule name must have been specified in the -alternate-entrypoints 463// if generating the parser with the -optimize-grammar flag, otherwise 464// it may have been optimized out. Passing an empty string sets the 465// entrypoint to the first rule in the grammar. 466// 467// The default is to start parsing at the first rule in the grammar. 468func Entrypoint(ruleName string) Option { 469 return func(p *parser) Option { 470 oldEntrypoint := p.entrypoint 471 p.entrypoint = ruleName 472 if ruleName == "" { 473 p.entrypoint = g.rules[0].name 474 } 475 return Entrypoint(oldEntrypoint) 476 } 477} 478 479// Statistics adds a user provided Stats struct to the parser to allow 480// the user to process the results after the parsing has finished. 481// Also the key for the "no match" counter is set. 482// 483// Example usage: 484// 485// input := "input" 486// stats := Stats{} 487// _, err := Parse("input-file", []byte(input), Statistics(&stats, "no match")) 488// if err != nil { 489// log.Panicln(err) 490// } 491// b, err := json.MarshalIndent(stats.ChoiceAltCnt, "", " ") 492// if err != nil { 493// log.Panicln(err) 494// } 495// fmt.Println(string(b)) 496// 497func Statistics(stats *Stats, choiceNoMatch string) Option { 498 return func(p *parser) Option { 499 oldStats := p.Stats 500 p.Stats = stats 501 oldChoiceNoMatch := p.choiceNoMatch 502 p.choiceNoMatch = choiceNoMatch 503 if p.Stats.ChoiceAltCnt == nil { 504 p.Stats.ChoiceAltCnt = make(map[string]map[string]int) 505 } 506 return Statistics(oldStats, oldChoiceNoMatch) 507 } 508} 509 510// Debug creates an Option to set the debug flag to b. When set to true, 511// debugging information is printed to stdout while parsing. 512// 513// The default is false. 514func Debug(b bool) Option { 515 return func(p *parser) Option { 516 old := p.debug 517 p.debug = b 518 return Debug(old) 519 } 520} 521 522// Memoize creates an Option to set the memoize flag to b. When set to true, 523// the parser will cache all results so each expression is evaluated only 524// once. This guarantees linear parsing time even for pathological cases, 525// at the expense of more memory and slower times for typical cases. 526// 527// The default is false. 528func Memoize(b bool) Option { 529 return func(p *parser) Option { 530 old := p.memoize 531 p.memoize = b 532 return Memoize(old) 533 } 534} 535 536// AllowInvalidUTF8 creates an Option to allow invalid UTF-8 bytes. 537// Every invalid UTF-8 byte is treated as a utf8.RuneError (U+FFFD) 538// by character class matchers and is matched by the any matcher. 539// The returned matched value, c.text and c.offset are NOT affected. 540// 541// The default is false. 542func AllowInvalidUTF8(b bool) Option { 543 return func(p *parser) Option { 544 old := p.allowInvalidUTF8 545 p.allowInvalidUTF8 = b 546 return AllowInvalidUTF8(old) 547 } 548} 549 550// Recover creates an Option to set the recover flag to b. When set to 551// true, this causes the parser to recover from panics and convert it 552// to an error. Setting it to false can be useful while debugging to 553// access the full stack trace. 554// 555// The default is true. 556func Recover(b bool) Option { 557 return func(p *parser) Option { 558 old := p.recover 559 p.recover = b 560 return Recover(old) 561 } 562} 563 564// GlobalStore creates an Option to set a key to a certain value in 565// the globalStore. 566func GlobalStore(key string, value interface{}) Option { 567 return func(p *parser) Option { 568 old := p.cur.globalStore[key] 569 p.cur.globalStore[key] = value 570 return GlobalStore(key, old) 571 } 572} 573 574// InitState creates an Option to set a key to a certain value in 575// the global "state" store. 576func InitState(key string, value interface{}) Option { 577 return func(p *parser) Option { 578 old := p.cur.state[key] 579 p.cur.state[key] = value 580 return InitState(key, old) 581 } 582} 583 584// ParseFile parses the file identified by filename. 585func ParseFile(filename string, opts ...Option) (i interface{}, err error) { 586 f, err := os.Open(filename) 587 if err != nil { 588 return nil, err 589 } 590 defer func() { 591 if closeErr := f.Close(); closeErr != nil { 592 err = closeErr 593 } 594 }() 595 return ParseReader(filename, f, opts...) 596} 597 598// ParseReader parses the data from r using filename as information in the 599// error messages. 600func ParseReader(filename string, r io.Reader, opts ...Option) (interface{}, error) { 601 b, err := ioutil.ReadAll(r) 602 if err != nil { 603 return nil, err 604 } 605 606 return Parse(filename, b, opts...) 607} 608 609// Parse parses the data from b using filename as information in the 610// error messages. 611func Parse(filename string, b []byte, opts ...Option) (interface{}, error) { 612 return newParser(filename, b, opts...).parse(g) 613} 614 615// position records a position in the text. 616type position struct { 617 line, col, offset int 618} 619 620func (p position) String() string { 621 return fmt.Sprintf("%d:%d [%d]", p.line, p.col, p.offset) 622} 623 624// savepoint stores all state required to go back to this point in the 625// parser. 626type savepoint struct { 627 position 628 rn rune 629 w int 630} 631 632type current struct { 633 pos position // start position of the match 634 text []byte // raw text of the match 635 636 // state is a store for arbitrary key,value pairs that the user wants to be 637 // tied to the backtracking of the parser. 638 // This is always rolled back if a parsing rule fails. 639 state storeDict 640 641 // globalStore is a general store for the user to store arbitrary key-value 642 // pairs that they need to manage and that they do not want tied to the 643 // backtracking of the parser. This is only modified by the user and never 644 // rolled back by the parser. It is always up to the user to keep this in a 645 // consistent state. 646 globalStore storeDict 647} 648 649type storeDict map[string]interface{} 650 651// the AST types... 652 653type grammar struct { 654 pos position 655 rules []*rule 656} 657 658type rule struct { 659 pos position 660 name string 661 displayName string 662 expr interface{} 663} 664 665type choiceExpr struct { 666 pos position 667 alternatives []interface{} 668} 669 670type actionExpr struct { 671 pos position 672 expr interface{} 673 run func(*parser) (interface{}, error) 674} 675 676type recoveryExpr struct { 677 pos position 678 expr interface{} 679 recoverExpr interface{} 680 failureLabel []string 681} 682 683type seqExpr struct { 684 pos position 685 exprs []interface{} 686} 687 688type throwExpr struct { 689 pos position 690 label string 691} 692 693type labeledExpr struct { 694 pos position 695 label string 696 expr interface{} 697} 698 699type expr struct { 700 pos position 701 expr interface{} 702} 703 704type andExpr expr 705type notExpr expr 706type zeroOrOneExpr expr 707type zeroOrMoreExpr expr 708type oneOrMoreExpr expr 709 710type ruleRefExpr struct { 711 pos position 712 name string 713} 714 715type stateCodeExpr struct { 716 pos position 717 run func(*parser) error 718} 719 720type andCodeExpr struct { 721 pos position 722 run func(*parser) (bool, error) 723} 724 725type notCodeExpr struct { 726 pos position 727 run func(*parser) (bool, error) 728} 729 730type litMatcher struct { 731 pos position 732 val string 733 ignoreCase bool 734} 735 736type charClassMatcher struct { 737 pos position 738 val string 739 basicLatinChars [128]bool 740 chars []rune 741 ranges []rune 742 classes []*unicode.RangeTable 743 ignoreCase bool 744 inverted bool 745} 746 747type anyMatcher position 748 749// errList cumulates the errors found by the parser. 750type errList []error 751 752func (e *errList) add(err error) { 753 *e = append(*e, err) 754} 755 756func (e errList) err() error { 757 if len(e) == 0 { 758 return nil 759 } 760 e.dedupe() 761 return e 762} 763 764func (e *errList) dedupe() { 765 var cleaned []error 766 set := make(map[string]bool) 767 for _, err := range *e { 768 if msg := err.Error(); !set[msg] { 769 set[msg] = true 770 cleaned = append(cleaned, err) 771 } 772 } 773 *e = cleaned 774} 775 776func (e errList) Error() string { 777 switch len(e) { 778 case 0: 779 return "" 780 case 1: 781 return e[0].Error() 782 default: 783 var buf bytes.Buffer 784 785 for i, err := range e { 786 if i > 0 { 787 buf.WriteRune('\n') 788 } 789 buf.WriteString(err.Error()) 790 } 791 return buf.String() 792 } 793} 794 795// parserError wraps an error with a prefix indicating the rule in which 796// the error occurred. The original error is stored in the Inner field. 797type parserError struct { 798 Inner error 799 pos position 800 prefix string 801 expected []string 802} 803 804// Error returns the error message. 805func (p *parserError) Error() string { 806 return p.prefix + ": " + p.Inner.Error() 807} 808 809// newParser creates a parser with the specified input source and options. 810func newParser(filename string, b []byte, opts ...Option) *parser { 811 stats := Stats{ 812 ChoiceAltCnt: make(map[string]map[string]int), 813 } 814 815 p := &parser{ 816 filename: filename, 817 errs: new(errList), 818 data: b, 819 pt: savepoint{position: position{line: 1}}, 820 recover: true, 821 cur: current{ 822 state: make(storeDict), 823 globalStore: make(storeDict), 824 }, 825 maxFailPos: position{col: 1, line: 1}, 826 maxFailExpected: make([]string, 0, 20), 827 Stats: &stats, 828 // start rule is rule [0] unless an alternate entrypoint is specified 829 entrypoint: g.rules[0].name, 830 emptyState: make(storeDict), 831 } 832 p.setOptions(opts) 833 834 if p.maxExprCnt == 0 { 835 p.maxExprCnt = math.MaxUint64 836 } 837 838 return p 839} 840 841// setOptions applies the options to the parser. 842func (p *parser) setOptions(opts []Option) { 843 for _, opt := range opts { 844 opt(p) 845 } 846} 847 848type resultTuple struct { 849 v interface{} 850 b bool 851 end savepoint 852} 853 854const choiceNoMatch = -1 855 856// Stats stores some statistics, gathered during parsing 857type Stats struct { 858 // ExprCnt counts the number of expressions processed during parsing 859 // This value is compared to the maximum number of expressions allowed 860 // (set by the MaxExpressions option). 861 ExprCnt uint64 862 863 // ChoiceAltCnt is used to count for each ordered choice expression, 864 // which alternative is used how may times. 865 // These numbers allow to optimize the order of the ordered choice expression 866 // to increase the performance of the parser 867 // 868 // The outer key of ChoiceAltCnt is composed of the name of the rule as well 869 // as the line and the column of the ordered choice. 870 // The inner key of ChoiceAltCnt is the number (one-based) of the matching alternative. 871 // For each alternative the number of matches are counted. If an ordered choice does not 872 // match, a special counter is incremented. The name of this counter is set with 873 // the parser option Statistics. 874 // For an alternative to be included in ChoiceAltCnt, it has to match at least once. 875 ChoiceAltCnt map[string]map[string]int 876} 877 878type parser struct { 879 filename string 880 pt savepoint 881 cur current 882 883 data []byte 884 errs *errList 885 886 depth int 887 recover bool 888 debug bool 889 890 memoize bool 891 // memoization table for the packrat algorithm: 892 // map[offset in source] map[expression or rule] {value, match} 893 memo map[int]map[interface{}]resultTuple 894 895 // rules table, maps the rule identifier to the rule node 896 rules map[string]*rule 897 // variables stack, map of label to value 898 vstack []map[string]interface{} 899 // rule stack, allows identification of the current rule in errors 900 rstack []*rule 901 902 // parse fail 903 maxFailPos position 904 maxFailExpected []string 905 maxFailInvertExpected bool 906 907 // max number of expressions to be parsed 908 maxExprCnt uint64 909 // entrypoint for the parser 910 entrypoint string 911 912 allowInvalidUTF8 bool 913 914 *Stats 915 916 choiceNoMatch string 917 // recovery expression stack, keeps track of the currently available recovery expression, these are traversed in reverse 918 recoveryStack []map[string]interface{} 919 920 // emptyState contains an empty storeDict, which is used to optimize cloneState if global "state" store is not used. 921 emptyState storeDict 922} 923 924// push a variable set on the vstack. 925func (p *parser) pushV() { 926 if cap(p.vstack) == len(p.vstack) { 927 // create new empty slot in the stack 928 p.vstack = append(p.vstack, nil) 929 } else { 930 // slice to 1 more 931 p.vstack = p.vstack[:len(p.vstack)+1] 932 } 933 934 // get the last args set 935 m := p.vstack[len(p.vstack)-1] 936 if m != nil && len(m) == 0 { 937 // empty map, all good 938 return 939 } 940 941 m = make(map[string]interface{}) 942 p.vstack[len(p.vstack)-1] = m 943} 944 945// pop a variable set from the vstack. 946func (p *parser) popV() { 947 // if the map is not empty, clear it 948 m := p.vstack[len(p.vstack)-1] 949 if len(m) > 0 { 950 // GC that map 951 p.vstack[len(p.vstack)-1] = nil 952 } 953 p.vstack = p.vstack[:len(p.vstack)-1] 954} 955 956// push a recovery expression with its labels to the recoveryStack 957func (p *parser) pushRecovery(labels []string, expr interface{}) { 958 if cap(p.recoveryStack) == len(p.recoveryStack) { 959 // create new empty slot in the stack 960 p.recoveryStack = append(p.recoveryStack, nil) 961 } else { 962 // slice to 1 more 963 p.recoveryStack = p.recoveryStack[:len(p.recoveryStack)+1] 964 } 965 966 m := make(map[string]interface{}, len(labels)) 967 for _, fl := range labels { 968 m[fl] = expr 969 } 970 p.recoveryStack[len(p.recoveryStack)-1] = m 971} 972 973// pop a recovery expression from the recoveryStack 974func (p *parser) popRecovery() { 975 // GC that map 976 p.recoveryStack[len(p.recoveryStack)-1] = nil 977 978 p.recoveryStack = p.recoveryStack[:len(p.recoveryStack)-1] 979} 980 981func (p *parser) print(prefix, s string) string { 982 if !p.debug { 983 return s 984 } 985 986 fmt.Printf("%s %d:%d:%d: %s [%#U]\n", 987 prefix, p.pt.line, p.pt.col, p.pt.offset, s, p.pt.rn) 988 return s 989} 990 991func (p *parser) in(s string) string { 992 p.depth++ 993 return p.print(strings.Repeat(" ", p.depth)+">", s) 994} 995 996func (p *parser) out(s string) string { 997 p.depth-- 998 return p.print(strings.Repeat(" ", p.depth)+"<", s) 999} 1000 1001func (p *parser) addErr(err error) { 1002 p.addErrAt(err, p.pt.position, []string{}) 1003} 1004 1005func (p *parser) addErrAt(err error, pos position, expected []string) { 1006 var buf bytes.Buffer 1007 if p.filename != "" { 1008 buf.WriteString(p.filename) 1009 } 1010 if buf.Len() > 0 { 1011 buf.WriteString(":") 1012 } 1013 buf.WriteString(fmt.Sprintf("%d:%d (%d)", pos.line, pos.col, pos.offset)) 1014 if len(p.rstack) > 0 { 1015 if buf.Len() > 0 { 1016 buf.WriteString(": ") 1017 } 1018 rule := p.rstack[len(p.rstack)-1] 1019 if rule.displayName != "" { 1020 buf.WriteString("rule " + rule.displayName) 1021 } else { 1022 buf.WriteString("rule " + rule.name) 1023 } 1024 } 1025 pe := &parserError{Inner: err, pos: pos, prefix: buf.String(), expected: expected} 1026 p.errs.add(pe) 1027} 1028 1029func (p *parser) failAt(fail bool, pos position, want string) { 1030 // process fail if parsing fails and not inverted or parsing succeeds and invert is set 1031 if fail == p.maxFailInvertExpected { 1032 if pos.offset < p.maxFailPos.offset { 1033 return 1034 } 1035 1036 if pos.offset > p.maxFailPos.offset { 1037 p.maxFailPos = pos 1038 p.maxFailExpected = p.maxFailExpected[:0] 1039 } 1040 1041 if p.maxFailInvertExpected { 1042 want = "!" + want 1043 } 1044 p.maxFailExpected = append(p.maxFailExpected, want) 1045 } 1046} 1047 1048// read advances the parser to the next rune. 1049func (p *parser) read() { 1050 p.pt.offset += p.pt.w 1051 rn, n := utf8.DecodeRune(p.data[p.pt.offset:]) 1052 p.pt.rn = rn 1053 p.pt.w = n 1054 p.pt.col++ 1055 if rn == '\n' { 1056 p.pt.line++ 1057 p.pt.col = 0 1058 } 1059 1060 if rn == utf8.RuneError && n == 1 { // see utf8.DecodeRune 1061 if !p.allowInvalidUTF8 { 1062 p.addErr(errInvalidEncoding) 1063 } 1064 } 1065} 1066 1067// restore parser position to the savepoint pt. 1068func (p *parser) restore(pt savepoint) { 1069 if p.debug { 1070 defer p.out(p.in("restore")) 1071 } 1072 if pt.offset == p.pt.offset { 1073 return 1074 } 1075 p.pt = pt 1076} 1077 1078// Cloner is implemented by any value that has a Clone method, which returns a 1079// copy of the value. This is mainly used for types which are not passed by 1080// value (e.g map, slice, chan) or structs that contain such types. 1081// 1082// This is used in conjunction with the global state feature to create proper 1083// copies of the state to allow the parser to properly restore the state in 1084// the case of backtracking. 1085type Cloner interface { 1086 Clone() interface{} 1087} 1088 1089// clone and return parser current state. 1090func (p *parser) cloneState() storeDict { 1091 if p.debug { 1092 defer p.out(p.in("cloneState")) 1093 } 1094 1095 if len(p.cur.state) == 0 { 1096 if len(p.emptyState) > 0 { 1097 p.emptyState = make(storeDict) 1098 } 1099 return p.emptyState 1100 } 1101 1102 state := make(storeDict, len(p.cur.state)) 1103 for k, v := range p.cur.state { 1104 if c, ok := v.(Cloner); ok { 1105 state[k] = c.Clone() 1106 } else { 1107 state[k] = v 1108 } 1109 } 1110 return state 1111} 1112 1113// restore parser current state to the state storeDict. 1114// every restoreState should applied only one time for every cloned state 1115func (p *parser) restoreState(state storeDict) { 1116 if p.debug { 1117 defer p.out(p.in("restoreState")) 1118 } 1119 p.cur.state = state 1120} 1121 1122// get the slice of bytes from the savepoint start to the current position. 1123func (p *parser) sliceFrom(start savepoint) []byte { 1124 return p.data[start.position.offset:p.pt.position.offset] 1125} 1126 1127func (p *parser) getMemoized(node interface{}) (resultTuple, bool) { 1128 if len(p.memo) == 0 { 1129 return resultTuple{}, false 1130 } 1131 m := p.memo[p.pt.offset] 1132 if len(m) == 0 { 1133 return resultTuple{}, false 1134 } 1135 res, ok := m[node] 1136 return res, ok 1137} 1138 1139func (p *parser) setMemoized(pt savepoint, node interface{}, tuple resultTuple) { 1140 if p.memo == nil { 1141 p.memo = make(map[int]map[interface{}]resultTuple) 1142 } 1143 m := p.memo[pt.offset] 1144 if m == nil { 1145 m = make(map[interface{}]resultTuple) 1146 p.memo[pt.offset] = m 1147 } 1148 m[node] = tuple 1149} 1150 1151func (p *parser) buildRulesTable(g *grammar) { 1152 p.rules = make(map[string]*rule, len(g.rules)) 1153 for _, r := range g.rules { 1154 p.rules[r.name] = r 1155 } 1156} 1157 1158func (p *parser) parse(g *grammar) (val interface{}, err error) { 1159 if len(g.rules) == 0 { 1160 p.addErr(errNoRule) 1161 return nil, p.errs.err() 1162 } 1163 1164 // TODO : not super critical but this could be generated 1165 p.buildRulesTable(g) 1166 1167 if p.recover { 1168 // panic can be used in action code to stop parsing immediately 1169 // and return the panic as an error. 1170 defer func() { 1171 if e := recover(); e != nil { 1172 if p.debug { 1173 defer p.out(p.in("panic handler")) 1174 } 1175 val = nil 1176 switch e := e.(type) { 1177 case error: 1178 p.addErr(e) 1179 default: 1180 p.addErr(fmt.Errorf("%v", e)) 1181 } 1182 err = p.errs.err() 1183 } 1184 }() 1185 } 1186 1187 startRule, ok := p.rules[p.entrypoint] 1188 if !ok { 1189 p.addErr(errInvalidEntrypoint) 1190 return nil, p.errs.err() 1191 } 1192 1193 p.read() // advance to first rune 1194 val, ok = p.parseRule(startRule) 1195 if !ok { 1196 if len(*p.errs) == 0 { 1197 // If parsing fails, but no errors have been recorded, the expected values 1198 // for the farthest parser position are returned as error. 1199 maxFailExpectedMap := make(map[string]struct{}, len(p.maxFailExpected)) 1200 for _, v := range p.maxFailExpected { 1201 maxFailExpectedMap[v] = struct{}{} 1202 } 1203 expected := make([]string, 0, len(maxFailExpectedMap)) 1204 eof := false 1205 if _, ok := maxFailExpectedMap["!."]; ok { 1206 delete(maxFailExpectedMap, "!.") 1207 eof = true 1208 } 1209 for k := range maxFailExpectedMap { 1210 expected = append(expected, k) 1211 } 1212 sort.Strings(expected) 1213 if eof { 1214 expected = append(expected, "EOF") 1215 } 1216 p.addErrAt(errors.New("no match found, expected: "+listJoin(expected, ", ", "or")), p.maxFailPos, expected) 1217 } 1218 1219 return nil, p.errs.err() 1220 } 1221 return val, p.errs.err() 1222} 1223 1224func listJoin(list []string, sep string, lastSep string) string { 1225 switch len(list) { 1226 case 0: 1227 return "" 1228 case 1: 1229 return list[0] 1230 default: 1231 return fmt.Sprintf("%s %s %s", strings.Join(list[:len(list)-1], sep), lastSep, list[len(list)-1]) 1232 } 1233} 1234 1235func (p *parser) parseRule(rule *rule) (interface{}, bool) { 1236 if p.debug { 1237 defer p.out(p.in("parseRule " + rule.name)) 1238 } 1239 1240 if p.memoize { 1241 res, ok := p.getMemoized(rule) 1242 if ok { 1243 p.restore(res.end) 1244 return res.v, res.b 1245 } 1246 } 1247 1248 start := p.pt 1249 p.rstack = append(p.rstack, rule) 1250 p.pushV() 1251 val, ok := p.parseExpr(rule.expr) 1252 p.popV() 1253 p.rstack = p.rstack[:len(p.rstack)-1] 1254 if ok && p.debug { 1255 p.print(strings.Repeat(" ", p.depth)+"MATCH", string(p.sliceFrom(start))) 1256 } 1257 1258 if p.memoize { 1259 p.setMemoized(start, rule, resultTuple{val, ok, p.pt}) 1260 } 1261 return val, ok 1262} 1263 1264func (p *parser) parseExpr(expr interface{}) (interface{}, bool) { 1265 var pt savepoint 1266 1267 if p.memoize { 1268 res, ok := p.getMemoized(expr) 1269 if ok { 1270 p.restore(res.end) 1271 return res.v, res.b 1272 } 1273 pt = p.pt 1274 } 1275 1276 p.ExprCnt++ 1277 if p.ExprCnt > p.maxExprCnt { 1278 panic(errMaxExprCnt) 1279 } 1280 1281 var val interface{} 1282 var ok bool 1283 switch expr := expr.(type) { 1284 case *actionExpr: 1285 val, ok = p.parseActionExpr(expr) 1286 case *andCodeExpr: 1287 val, ok = p.parseAndCodeExpr(expr) 1288 case *andExpr: 1289 val, ok = p.parseAndExpr(expr) 1290 case *anyMatcher: 1291 val, ok = p.parseAnyMatcher(expr) 1292 case *charClassMatcher: 1293 val, ok = p.parseCharClassMatcher(expr) 1294 case *choiceExpr: 1295 val, ok = p.parseChoiceExpr(expr) 1296 case *labeledExpr: 1297 val, ok = p.parseLabeledExpr(expr) 1298 case *litMatcher: 1299 val, ok = p.parseLitMatcher(expr) 1300 case *notCodeExpr: 1301 val, ok = p.parseNotCodeExpr(expr) 1302 case *notExpr: 1303 val, ok = p.parseNotExpr(expr) 1304 case *oneOrMoreExpr: 1305 val, ok = p.parseOneOrMoreExpr(expr) 1306 case *recoveryExpr: 1307 val, ok = p.parseRecoveryExpr(expr) 1308 case *ruleRefExpr: 1309 val, ok = p.parseRuleRefExpr(expr) 1310 case *seqExpr: 1311 val, ok = p.parseSeqExpr(expr) 1312 case *stateCodeExpr: 1313 val, ok = p.parseStateCodeExpr(expr) 1314 case *throwExpr: 1315 val, ok = p.parseThrowExpr(expr) 1316 case *zeroOrMoreExpr: 1317 val, ok = p.parseZeroOrMoreExpr(expr) 1318 case *zeroOrOneExpr: 1319 val, ok = p.parseZeroOrOneExpr(expr) 1320 default: 1321 panic(fmt.Sprintf("unknown expression type %T", expr)) 1322 } 1323 if p.memoize { 1324 p.setMemoized(pt, expr, resultTuple{val, ok, p.pt}) 1325 } 1326 return val, ok 1327} 1328 1329func (p *parser) parseActionExpr(act *actionExpr) (interface{}, bool) { 1330 if p.debug { 1331 defer p.out(p.in("parseActionExpr")) 1332 } 1333 1334 start := p.pt 1335 val, ok := p.parseExpr(act.expr) 1336 if ok { 1337 p.cur.pos = start.position 1338 p.cur.text = p.sliceFrom(start) 1339 state := p.cloneState() 1340 actVal, err := act.run(p) 1341 if err != nil { 1342 p.addErrAt(err, start.position, []string{}) 1343 } 1344 p.restoreState(state) 1345 1346 val = actVal 1347 } 1348 if ok && p.debug { 1349 p.print(strings.Repeat(" ", p.depth)+"MATCH", string(p.sliceFrom(start))) 1350 } 1351 return val, ok 1352} 1353 1354func (p *parser) parseAndCodeExpr(and *andCodeExpr) (interface{}, bool) { 1355 if p.debug { 1356 defer p.out(p.in("parseAndCodeExpr")) 1357 } 1358 1359 state := p.cloneState() 1360 1361 ok, err := and.run(p) 1362 if err != nil { 1363 p.addErr(err) 1364 } 1365 p.restoreState(state) 1366 1367 return nil, ok 1368} 1369 1370func (p *parser) parseAndExpr(and *andExpr) (interface{}, bool) { 1371 if p.debug { 1372 defer p.out(p.in("parseAndExpr")) 1373 } 1374 1375 pt := p.pt 1376 state := p.cloneState() 1377 p.pushV() 1378 _, ok := p.parseExpr(and.expr) 1379 p.popV() 1380 p.restoreState(state) 1381 p.restore(pt) 1382 1383 return nil, ok 1384} 1385 1386func (p *parser) parseAnyMatcher(any *anyMatcher) (interface{}, bool) { 1387 if p.debug { 1388 defer p.out(p.in("parseAnyMatcher")) 1389 } 1390 1391 if p.pt.rn == utf8.RuneError && p.pt.w == 0 { 1392 // EOF - see utf8.DecodeRune 1393 p.failAt(false, p.pt.position, ".") 1394 return nil, false 1395 } 1396 start := p.pt 1397 p.read() 1398 p.failAt(true, start.position, ".") 1399 return p.sliceFrom(start), true 1400} 1401 1402func (p *parser) parseCharClassMatcher(chr *charClassMatcher) (interface{}, bool) { 1403 if p.debug { 1404 defer p.out(p.in("parseCharClassMatcher")) 1405 } 1406 1407 cur := p.pt.rn 1408 start := p.pt 1409 1410 // can't match EOF 1411 if cur == utf8.RuneError && p.pt.w == 0 { // see utf8.DecodeRune 1412 p.failAt(false, start.position, chr.val) 1413 return nil, false 1414 } 1415 1416 if chr.ignoreCase { 1417 cur = unicode.ToLower(cur) 1418 } 1419 1420 // try to match in the list of available chars 1421 for _, rn := range chr.chars { 1422 if rn == cur { 1423 if chr.inverted { 1424 p.failAt(false, start.position, chr.val) 1425 return nil, false 1426 } 1427 p.read() 1428 p.failAt(true, start.position, chr.val) 1429 return p.sliceFrom(start), true 1430 } 1431 } 1432 1433 // try to match in the list of ranges 1434 for i := 0; i < len(chr.ranges); i += 2 { 1435 if cur >= chr.ranges[i] && cur <= chr.ranges[i+1] { 1436 if chr.inverted { 1437 p.failAt(false, start.position, chr.val) 1438 return nil, false 1439 } 1440 p.read() 1441 p.failAt(true, start.position, chr.val) 1442 return p.sliceFrom(start), true 1443 } 1444 } 1445 1446 // try to match in the list of Unicode classes 1447 for _, cl := range chr.classes { 1448 if unicode.Is(cl, cur) { 1449 if chr.inverted { 1450 p.failAt(false, start.position, chr.val) 1451 return nil, false 1452 } 1453 p.read() 1454 p.failAt(true, start.position, chr.val) 1455 return p.sliceFrom(start), true 1456 } 1457 } 1458 1459 if chr.inverted { 1460 p.read() 1461 p.failAt(true, start.position, chr.val) 1462 return p.sliceFrom(start), true 1463 } 1464 p.failAt(false, start.position, chr.val) 1465 return nil, false 1466} 1467 1468func (p *parser) incChoiceAltCnt(ch *choiceExpr, altI int) { 1469 choiceIdent := fmt.Sprintf("%s %d:%d", p.rstack[len(p.rstack)-1].name, ch.pos.line, ch.pos.col) 1470 m := p.ChoiceAltCnt[choiceIdent] 1471 if m == nil { 1472 m = make(map[string]int) 1473 p.ChoiceAltCnt[choiceIdent] = m 1474 } 1475 // We increment altI by 1, so the keys do not start at 0 1476 alt := strconv.Itoa(altI + 1) 1477 if altI == choiceNoMatch { 1478 alt = p.choiceNoMatch 1479 } 1480 m[alt]++ 1481} 1482 1483func (p *parser) parseChoiceExpr(ch *choiceExpr) (interface{}, bool) { 1484 if p.debug { 1485 defer p.out(p.in("parseChoiceExpr")) 1486 } 1487 1488 for altI, alt := range ch.alternatives { 1489 // dummy assignment to prevent compile error if optimized 1490 _ = altI 1491 1492 state := p.cloneState() 1493 1494 p.pushV() 1495 val, ok := p.parseExpr(alt) 1496 p.popV() 1497 if ok { 1498 p.incChoiceAltCnt(ch, altI) 1499 return val, ok 1500 } 1501 p.restoreState(state) 1502 } 1503 p.incChoiceAltCnt(ch, choiceNoMatch) 1504 return nil, false 1505} 1506 1507func (p *parser) parseLabeledExpr(lab *labeledExpr) (interface{}, bool) { 1508 if p.debug { 1509 defer p.out(p.in("parseLabeledExpr")) 1510 } 1511 1512 p.pushV() 1513 val, ok := p.parseExpr(lab.expr) 1514 p.popV() 1515 if ok && lab.label != "" { 1516 m := p.vstack[len(p.vstack)-1] 1517 m[lab.label] = val 1518 } 1519 return val, ok 1520} 1521 1522func (p *parser) parseLitMatcher(lit *litMatcher) (interface{}, bool) { 1523 if p.debug { 1524 defer p.out(p.in("parseLitMatcher")) 1525 } 1526 1527 ignoreCase := "" 1528 if lit.ignoreCase { 1529 ignoreCase = "i" 1530 } 1531 val := fmt.Sprintf("%q%s", lit.val, ignoreCase) 1532 start := p.pt 1533 for _, want := range lit.val { 1534 cur := p.pt.rn 1535 if lit.ignoreCase { 1536 cur = unicode.ToLower(cur) 1537 } 1538 if cur != want { 1539 p.failAt(false, start.position, val) 1540 p.restore(start) 1541 return nil, false 1542 } 1543 p.read() 1544 } 1545 p.failAt(true, start.position, val) 1546 return p.sliceFrom(start), true 1547} 1548 1549func (p *parser) parseNotCodeExpr(not *notCodeExpr) (interface{}, bool) { 1550 if p.debug { 1551 defer p.out(p.in("parseNotCodeExpr")) 1552 } 1553 1554 state := p.cloneState() 1555 1556 ok, err := not.run(p) 1557 if err != nil { 1558 p.addErr(err) 1559 } 1560 p.restoreState(state) 1561 1562 return nil, !ok 1563} 1564 1565func (p *parser) parseNotExpr(not *notExpr) (interface{}, bool) { 1566 if p.debug { 1567 defer p.out(p.in("parseNotExpr")) 1568 } 1569 1570 pt := p.pt 1571 state := p.cloneState() 1572 p.pushV() 1573 p.maxFailInvertExpected = !p.maxFailInvertExpected 1574 _, ok := p.parseExpr(not.expr) 1575 p.maxFailInvertExpected = !p.maxFailInvertExpected 1576 p.popV() 1577 p.restoreState(state) 1578 p.restore(pt) 1579 1580 return nil, !ok 1581} 1582 1583func (p *parser) parseOneOrMoreExpr(expr *oneOrMoreExpr) (interface{}, bool) { 1584 if p.debug { 1585 defer p.out(p.in("parseOneOrMoreExpr")) 1586 } 1587 1588 var vals []interface{} 1589 1590 for { 1591 p.pushV() 1592 val, ok := p.parseExpr(expr.expr) 1593 p.popV() 1594 if !ok { 1595 if len(vals) == 0 { 1596 // did not match once, no match 1597 return nil, false 1598 } 1599 return vals, true 1600 } 1601 vals = append(vals, val) 1602 } 1603} 1604 1605func (p *parser) parseRecoveryExpr(recover *recoveryExpr) (interface{}, bool) { 1606 if p.debug { 1607 defer p.out(p.in("parseRecoveryExpr (" + strings.Join(recover.failureLabel, ",") + ")")) 1608 } 1609 1610 p.pushRecovery(recover.failureLabel, recover.recoverExpr) 1611 val, ok := p.parseExpr(recover.expr) 1612 p.popRecovery() 1613 1614 return val, ok 1615} 1616 1617func (p *parser) parseRuleRefExpr(ref *ruleRefExpr) (interface{}, bool) { 1618 if p.debug { 1619 defer p.out(p.in("parseRuleRefExpr " + ref.name)) 1620 } 1621 1622 if ref.name == "" { 1623 panic(fmt.Sprintf("%s: invalid rule: missing name", ref.pos)) 1624 } 1625 1626 rule := p.rules[ref.name] 1627 if rule == nil { 1628 p.addErr(fmt.Errorf("undefined rule: %s", ref.name)) 1629 return nil, false 1630 } 1631 return p.parseRule(rule) 1632} 1633 1634func (p *parser) parseSeqExpr(seq *seqExpr) (interface{}, bool) { 1635 if p.debug { 1636 defer p.out(p.in("parseSeqExpr")) 1637 } 1638 1639 vals := make([]interface{}, 0, len(seq.exprs)) 1640 1641 pt := p.pt 1642 state := p.cloneState() 1643 for _, expr := range seq.exprs { 1644 val, ok := p.parseExpr(expr) 1645 if !ok { 1646 p.restoreState(state) 1647 p.restore(pt) 1648 return nil, false 1649 } 1650 vals = append(vals, val) 1651 } 1652 return vals, true 1653} 1654 1655func (p *parser) parseStateCodeExpr(state *stateCodeExpr) (interface{}, bool) { 1656 if p.debug { 1657 defer p.out(p.in("parseStateCodeExpr")) 1658 } 1659 1660 err := state.run(p) 1661 if err != nil { 1662 p.addErr(err) 1663 } 1664 return nil, true 1665} 1666 1667func (p *parser) parseThrowExpr(expr *throwExpr) (interface{}, bool) { 1668 if p.debug { 1669 defer p.out(p.in("parseThrowExpr")) 1670 } 1671 1672 for i := len(p.recoveryStack) - 1; i >= 0; i-- { 1673 if recoverExpr, ok := p.recoveryStack[i][expr.label]; ok { 1674 if val, ok := p.parseExpr(recoverExpr); ok { 1675 return val, ok 1676 } 1677 } 1678 } 1679 1680 return nil, false 1681} 1682 1683func (p *parser) parseZeroOrMoreExpr(expr *zeroOrMoreExpr) (interface{}, bool) { 1684 if p.debug { 1685 defer p.out(p.in("parseZeroOrMoreExpr")) 1686 } 1687 1688 var vals []interface{} 1689 1690 for { 1691 p.pushV() 1692 val, ok := p.parseExpr(expr.expr) 1693 p.popV() 1694 if !ok { 1695 return vals, true 1696 } 1697 vals = append(vals, val) 1698 } 1699} 1700 1701func (p *parser) parseZeroOrOneExpr(expr *zeroOrOneExpr) (interface{}, bool) { 1702 if p.debug { 1703 defer p.out(p.in("parseZeroOrOneExpr")) 1704 } 1705 1706 p.pushV() 1707 val, _ := p.parseExpr(expr.expr) 1708 p.popV() 1709 // whether it matched or not, consider it a match 1710 return val, true 1711} 1712