OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #library('Peg Parser'); | 5 #library('Peg Parser'); |
6 | 6 |
7 /* | 7 /* |
8 * The following functions are combinators for building Rules. | 8 * The following functions are combinators for building Rules. |
9 * | 9 * |
10 * A rule is one of the following | 10 * A rule is one of the following |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
76 flags[code - lo] = true; | 76 flags[code - lo] = true; |
77 | 77 |
78 return CHARCODE((code) => code >= lo && code <= hi && flags[code - lo]); | 78 return CHARCODE((code) => code >= lo && code <= hi && flags[code - lo]); |
79 } | 79 } |
80 | 80 |
81 /** | 81 /** |
82 * Matches the end of the input. | 82 * Matches the end of the input. |
83 * | 83 * |
84 * END does not generate a value. | 84 * END does not generate a value. |
85 */ | 85 */ |
86 _Rule get END() => new _EndOfInputRule(); | 86 _Rule get END => new _EndOfInputRule(); |
87 | 87 |
88 /** | 88 /** |
89 * Throws an exception. | 89 * Throws an exception. |
90 */ | 90 */ |
91 _Rule ERROR(String message) => new _ErrorRule(message); | 91 _Rule ERROR(String message) => new _ErrorRule(message); |
92 | 92 |
93 /** | 93 /** |
94 * Matches [rule] but does not consume the input. Useful for matching a right | 94 * Matches [rule] but does not consume the input. Useful for matching a right |
95 * context. | 95 * context. |
96 * | 96 * |
(...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
216 /** | 216 /** |
217 * A grammar is a collection of symbols and rules that may be used to parse an | 217 * A grammar is a collection of symbols and rules that may be used to parse an |
218 * input. | 218 * input. |
219 */ | 219 */ |
220 class Grammar { | 220 class Grammar { |
221 Map<String, Symbol> _symbols; | 221 Map<String, Symbol> _symbols; |
222 | 222 |
223 /** This rule may be set by the user to define whitespace. */ | 223 /** This rule may be set by the user to define whitespace. */ |
224 _Rule _whitespace; | 224 _Rule _whitespace; |
225 | 225 |
226 _Rule get whitespace() => _whitespace; | 226 _Rule get whitespace => _whitespace; |
227 void set whitespace(rule) { _whitespace = _compile(rule); } | 227 void set whitespace(rule) { _whitespace = _compile(rule); } |
228 | 228 |
229 Grammar() { | 229 Grammar() { |
230 _symbols = new Map<String, Symbol>(); | 230 _symbols = new Map<String, Symbol>(); |
231 whitespace = CHAR(' \t\r\n'); | 231 whitespace = CHAR(' \t\r\n'); |
232 } | 232 } |
233 | 233 |
234 /** | 234 /** |
235 * operator [] is used to find or create symbols. Symbols may appear in rules | 235 * operator [] is used to find or create symbols. Symbols may appear in rules |
236 * to define recursive rules. | 236 * to define recursive rules. |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
372 } | 372 } |
373 } | 373 } |
374 // Delegate the matching logic to the the specialized function. | 374 // Delegate the matching logic to the the specialized function. |
375 return _match(state, pos); | 375 return _match(state, pos); |
376 } | 376 } |
377 | 377 |
378 // Overridden in subclasses to match the rule. | 378 // Overridden in subclasses to match the rule. |
379 _match(_ParserState state, int pos) => null; | 379 _match(_ParserState state, int pos) => null; |
380 | 380 |
381 // Does the rule generate a value (AST) with the match? | 381 // Does the rule generate a value (AST) with the match? |
382 bool get generatesValue() => false; | 382 bool get generatesValue => false; |
383 | 383 |
384 get defaultValue() => null; | 384 get defaultValue => null; |
385 } | 385 } |
386 | 386 |
387 int _skip_whitespace(state, pos) { | 387 int _skip_whitespace(state, pos) { |
388 // Returns the next non-whitespace position. | 388 // Returns the next non-whitespace position. |
389 // This is done by matching the optional whitespaceRule with the current text. | 389 // This is done by matching the optional whitespaceRule with the current text. |
390 if (state.whitespaceRule == null) | 390 if (state.whitespaceRule == null) |
391 return pos; | 391 return pos; |
392 state.inWhitespaceMode = true; | 392 state.inWhitespaceMode = true; |
393 state.inhibitExpectedTrackingDepth++; | 393 state.inhibitExpectedTrackingDepth++; |
394 while (true) { | 394 while (true) { |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
474 | 474 |
475 class _SymbolRule extends _Rule { | 475 class _SymbolRule extends _Rule { |
476 final Symbol _symbol; | 476 final Symbol _symbol; |
477 _SymbolRule(Symbol this._symbol); | 477 _SymbolRule(Symbol this._symbol); |
478 _match(_ParserState state, int pos) { | 478 _match(_ParserState state, int pos) { |
479 if (_symbol._rule == null) | 479 if (_symbol._rule == null) |
480 throw new Exception("Symbol '${_symbol.name}' is undefined"); | 480 throw new Exception("Symbol '${_symbol.name}' is undefined"); |
481 return _symbol._rule.match(state, pos); | 481 return _symbol._rule.match(state, pos); |
482 } | 482 } |
483 | 483 |
484 bool get generatesValue() => true; | 484 bool get generatesValue => true; |
485 | 485 |
486 toString() => '<${_symbol.name}>'; | 486 toString() => '<${_symbol.name}>'; |
487 } | 487 } |
488 | 488 |
489 class _SkipRule extends _Rule { | 489 class _SkipRule extends _Rule { |
490 // A rule that has no value. | 490 // A rule that has no value. |
491 _Rule _rule; | 491 _Rule _rule; |
492 _SkipRule(_Rule this._rule); | 492 _SkipRule(_Rule this._rule); |
493 _match(_ParserState state, int pos) { | 493 _match(_ParserState state, int pos) { |
494 var match = _rule.matchAfterWS(state, pos); | 494 var match = _rule.matchAfterWS(state, pos); |
(...skipping 15 matching lines...) Expand all Loading... |
510 _match(_ParserState state, int pos) { | 510 _match(_ParserState state, int pos) { |
511 if (pos + _len > state._end) | 511 if (pos + _len > state._end) |
512 return null; | 512 return null; |
513 for (int i = 0; i < _len; i++) { | 513 for (int i = 0; i < _len; i++) { |
514 if (state._text.charCodeAt(pos + i) != _string.charCodeAt(i)) | 514 if (state._text.charCodeAt(pos + i) != _string.charCodeAt(i)) |
515 return null; | 515 return null; |
516 } | 516 } |
517 return [pos + _len, null]; | 517 return [pos + _len, null]; |
518 } | 518 } |
519 | 519 |
520 //get defaultValue() => _string; | 520 //get defaultValue => _string; |
521 | 521 |
522 toString() => '"$_string"'; | 522 toString() => '"$_string"'; |
523 | 523 |
524 description() => "'$_string'"; | 524 description() => "'$_string'"; |
525 } | 525 } |
526 | 526 |
527 class _RegExpRule extends _Rule { | 527 class _RegExpRule extends _Rule { |
528 RegExp _re; | 528 RegExp _re; |
529 _RegExpRule(this._re) { | 529 _RegExpRule(this._re) { |
530 // There is no convenient way to match an anchored substring. | 530 // There is no convenient way to match an anchored substring. |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
562 | 562 |
563 _match(_ParserState state, int pos) { | 563 _match(_ParserState state, int pos) { |
564 var match = _rule.matchAfterWS(state, pos); | 564 var match = _rule.matchAfterWS(state, pos); |
565 if (match == null) { | 565 if (match == null) { |
566 return null; | 566 return null; |
567 } | 567 } |
568 var endPos = match[0]; | 568 var endPos = match[0]; |
569 return [endPos, _extract(state._text, pos, endPos)]; | 569 return [endPos, _extract(state._text, pos, endPos)]; |
570 } | 570 } |
571 | 571 |
572 bool get generatesValue() => true; | 572 bool get generatesValue => true; |
573 | 573 |
574 toString() => 'TEXT($_rule)'; | 574 toString() => 'TEXT($_rule)'; |
575 } | 575 } |
576 | 576 |
577 _Rule _compileMultiRule(List rules, | 577 _Rule _compileMultiRule(List rules, |
578 bool allowReducer, | 578 bool allowReducer, |
579 finish(compiledRules, valueCount, reducer)) { | 579 finish(compiledRules, valueCount, reducer)) { |
580 int valueCount = 0; | 580 int valueCount = 0; |
581 List compiledRules = new List<_Rule>(); | 581 List compiledRules = new List<_Rule>(); |
582 Function reducer; | 582 Function reducer; |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
639 if (_generatingSubRules == 0) | 639 if (_generatingSubRules == 0) |
640 return [pos, null]; | 640 return [pos, null]; |
641 if (_generatingSubRules == 1) | 641 if (_generatingSubRules == 1) |
642 return [pos, sequence[0]]; | 642 return [pos, sequence[0]]; |
643 return [pos, sequence]; | 643 return [pos, sequence]; |
644 } else { | 644 } else { |
645 return [pos, _apply(_reducer, sequence)]; | 645 return [pos, _apply(_reducer, sequence)]; |
646 } | 646 } |
647 } | 647 } |
648 | 648 |
649 bool get generatesValue() => _generatesValue; | 649 bool get generatesValue => _generatesValue; |
650 | 650 |
651 toString() => _formatMultiRule('SEQ', _rules); | 651 toString() => _formatMultiRule('SEQ', _rules); |
652 } | 652 } |
653 | 653 |
654 class _ChoiceRule extends _Rule { | 654 class _ChoiceRule extends _Rule { |
655 // This rule matches the first component rule that matches. | 655 // This rule matches the first component rule that matches. |
656 List<_Rule> _rules; | 656 List<_Rule> _rules; |
657 _ChoiceRule(List<_Rule> this._rules); | 657 _ChoiceRule(List<_Rule> this._rules); |
658 | 658 |
659 _match(state, pos) { | 659 _match(state, pos) { |
660 for (var rule in _rules) { | 660 for (var rule in _rules) { |
661 var match = rule.match(state, pos); | 661 var match = rule.match(state, pos); |
662 if (match != null) { | 662 if (match != null) { |
663 /* | 663 /* |
664 if (!rule.generatesValue) { | 664 if (!rule.generatesValue) { |
665 var value = rule.defaultValue; | 665 var value = rule.defaultValue; |
666 if (value != null) | 666 if (value != null) |
667 return [match[0], value]; | 667 return [match[0], value]; |
668 } | 668 } |
669 */ | 669 */ |
670 return match; | 670 return match; |
671 } | 671 } |
672 } | 672 } |
673 return null; | 673 return null; |
674 } | 674 } |
675 | 675 |
676 bool get generatesValue() => true; | 676 bool get generatesValue => true; |
677 | 677 |
678 toString() => _formatMultiRule('OR', _rules); | 678 toString() => _formatMultiRule('OR', _rules); |
679 } | 679 } |
680 | 680 |
681 class _OptionalRule extends _Rule { | 681 class _OptionalRule extends _Rule { |
682 _Rule _rule; | 682 _Rule _rule; |
683 _OptionalRule(_Rule this._rule); | 683 _OptionalRule(_Rule this._rule); |
684 _match(_ParserState state, int pos) { | 684 _match(_ParserState state, int pos) { |
685 var match = _rule.match(state, pos); | 685 var match = _rule.match(state, pos); |
686 if (_rule.generatesValue) | 686 if (_rule.generatesValue) |
687 return match == null | 687 return match == null |
688 ? [pos, null] | 688 ? [pos, null] |
689 : match; | 689 : match; |
690 return match == null | 690 return match == null |
691 ? [pos, false] | 691 ? [pos, false] |
692 : [match[0], true]; | 692 : [match[0], true]; |
693 } | 693 } |
694 | 694 |
695 bool get generatesValue() => true; | 695 bool get generatesValue => true; |
696 | 696 |
697 toString() => 'MAYBE($_rule)'; | 697 toString() => 'MAYBE($_rule)'; |
698 } | 698 } |
699 | 699 |
700 class _ContextRule extends _Rule { | 700 class _ContextRule extends _Rule { |
701 _Rule _rule; | 701 _Rule _rule; |
702 _ContextRule(_Rule this._rule); | 702 _ContextRule(_Rule this._rule); |
703 _match(_ParserState state, int pos) { | 703 _match(_ParserState state, int pos) { |
704 // TODO: protect error state. | 704 // TODO: protect error state. |
705 var match = _rule._match(state, pos); | 705 var match = _rule._match(state, pos); |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
754 newPos = match[0]; | 754 newPos = match[0]; |
755 } | 755 } |
756 match = _rule.match(state, newPos); | 756 match = _rule.match(state, newPos); |
757 if (match == null) | 757 if (match == null) |
758 return [pos, result]; | 758 return [pos, result]; |
759 pos = match[0]; | 759 pos = match[0]; |
760 result.add(match[1]); | 760 result.add(match[1]); |
761 } | 761 } |
762 } | 762 } |
763 | 763 |
764 bool get generatesValue() => true; | 764 bool get generatesValue => true; |
765 | 765 |
766 toString() => 'MANY(min:$_min, $_rule${_separator==null?'':", sep: $_separator
"})'; | 766 toString() => 'MANY(min:$_min, $_rule${_separator==null?'':", sep: $_separator
"})'; |
767 } | 767 } |
768 | 768 |
769 class _MemoRule extends _Rule { | 769 class _MemoRule extends _Rule { |
770 final _Rule _rule; | 770 final _Rule _rule; |
771 | 771 |
772 var parseInstance; | 772 var parseInstance; |
773 | 773 |
774 // A map from position to result. Can this be replaced with something | 774 // A map from position to result. Can this be replaced with something |
(...skipping 14 matching lines...) Expand all Loading... |
789 // inWhitespaceMode, error position info etc?) | 789 // inWhitespaceMode, error position info etc?) |
790 // Stored result can be null (memoized failure). | 790 // Stored result can be null (memoized failure). |
791 if (map.containsKey(pos)) { | 791 if (map.containsKey(pos)) { |
792 return map[pos]; | 792 return map[pos]; |
793 } | 793 } |
794 var match = _rule.match(state, pos); | 794 var match = _rule.match(state, pos); |
795 map[pos] = match; | 795 map[pos] = match; |
796 return match; | 796 return match; |
797 } | 797 } |
798 | 798 |
799 bool get generatesValue() => _rule.generatesValue; | 799 bool get generatesValue => _rule.generatesValue; |
800 | 800 |
801 toString() => 'MEMO($_rule)'; | 801 toString() => 'MEMO($_rule)'; |
802 } | 802 } |
803 | 803 |
804 _apply(fn, List args) { | 804 _apply(fn, List args) { |
805 switch (args.length) { | 805 switch (args.length) { |
806 case 0: return fn(); | 806 case 0: return fn(); |
807 case 1: return fn(args[0]); | 807 case 1: return fn(args[0]); |
808 case 2: return fn(args[0], args[1]); | 808 case 2: return fn(args[0], args[1]); |
809 case 3: return fn(args[0], args[1], args[2]); | 809 case 3: return fn(args[0], args[1], args[2]); |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
849 add(s); | 849 add(s); |
850 add(t); | 850 add(t); |
851 add(u); | 851 add(u); |
852 add(v); | 852 add(v); |
853 add(w); | 853 add(w); |
854 add(x); | 854 add(x); |
855 add(y); | 855 add(y); |
856 add(z); | 856 add(z); |
857 return list; | 857 return list; |
858 } | 858 } |
OLD | NEW |