RegexParser.cpp 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176
  1. /*
  2. * Copyright 2017 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "src/sksl/lex/RegexParser.h"
  8. #include "src/sksl/lex/LexUtil.h"
  9. RegexNode RegexParser::parse(std::string source) {
  10. fSource = source;
  11. fIndex = 0;
  12. SkASSERT(fStack.size() == 0);
  13. this->regex();
  14. SkASSERT(fStack.size() == 1);
  15. SkASSERT(fIndex == source.size());
  16. return this->pop();
  17. }
  18. char RegexParser::peek() {
  19. if (fIndex >= fSource.size()) {
  20. return END;
  21. }
  22. return fSource[fIndex];
  23. }
  24. void RegexParser::expect(char c) {
  25. if (this->peek() != c) {
  26. printf("expected '%c' at index %d, but found '%c'", c, (int) fIndex, this->peek());
  27. exit(1);
  28. }
  29. ++fIndex;
  30. }
  31. RegexNode RegexParser::pop() {
  32. RegexNode result = fStack.top();
  33. fStack.pop();
  34. return result;
  35. }
  36. void RegexParser::term() {
  37. switch (this->peek()) {
  38. case '(': this->group(); break;
  39. case '[': this->set(); break;
  40. case '.': this->dot(); break;
  41. default: this->literal();
  42. }
  43. }
  44. void RegexParser::quantifiedTerm() {
  45. this->term();
  46. switch (this->peek()) {
  47. case '*': fStack.push(RegexNode(RegexNode::kStar_Kind, this->pop())); ++fIndex; break;
  48. case '+': fStack.push(RegexNode(RegexNode::kPlus_Kind, this->pop())); ++fIndex; break;
  49. case '?': fStack.push(RegexNode(RegexNode::kQuestion_Kind, this->pop())); ++fIndex; break;
  50. default: break;
  51. }
  52. }
  53. void RegexParser::sequence() {
  54. this->quantifiedTerm();
  55. for (;;) {
  56. switch (this->peek()) {
  57. case END: // fall through
  58. case '|': // fall through
  59. case ')': return;
  60. default:
  61. this->sequence();
  62. RegexNode right = this->pop();
  63. RegexNode left = this->pop();
  64. fStack.emplace(RegexNode::kConcat_Kind, std::move(left), std::move(right));
  65. }
  66. }
  67. }
  68. RegexNode RegexParser::escapeSequence(char c) {
  69. switch (c) {
  70. case 'n': return RegexNode(RegexNode::kChar_Kind, '\n');
  71. case 'r': return RegexNode(RegexNode::kChar_Kind, '\r');
  72. case 't': return RegexNode(RegexNode::kChar_Kind, '\t');
  73. case 's': return RegexNode(RegexNode::kCharset_Kind, " \t\n\r");
  74. default: return RegexNode(RegexNode::kChar_Kind, c);
  75. }
  76. }
  77. void RegexParser::literal() {
  78. char c = this->peek();
  79. if (c == '\\') {
  80. ++fIndex;
  81. fStack.push(this->escapeSequence(peek()));
  82. ++fIndex;
  83. }
  84. else {
  85. fStack.push(RegexNode(RegexNode::kChar_Kind, c));
  86. ++fIndex;
  87. }
  88. }
  89. void RegexParser::dot() {
  90. this->expect('.');
  91. fStack.push(RegexNode(RegexNode::kDot_Kind));
  92. }
  93. void RegexParser::group() {
  94. this->expect('(');
  95. this->regex();
  96. this->expect(')');
  97. }
  98. void RegexParser::setItem() {
  99. this->literal();
  100. if (this->peek() == '-') {
  101. ++fIndex;
  102. if (peek() == ']') {
  103. fStack.push(RegexNode(RegexNode::kChar_Kind, '-'));
  104. }
  105. else {
  106. literal();
  107. RegexNode end = this->pop();
  108. SkASSERT(end.fKind == RegexNode::kChar_Kind);
  109. RegexNode start = this->pop();
  110. SkASSERT(start.fKind == RegexNode::kChar_Kind);
  111. fStack.push(RegexNode(RegexNode::kRange_Kind, std::move(start), std::move(end)));
  112. }
  113. }
  114. }
  115. void RegexParser::set() {
  116. expect('[');
  117. size_t depth = fStack.size();
  118. RegexNode set(RegexNode::kCharset_Kind);
  119. if (this->peek() == '^') {
  120. ++fIndex;
  121. set.fPayload.fBool = true;
  122. }
  123. else {
  124. set.fPayload.fBool = false;
  125. }
  126. for (;;) {
  127. switch (this->peek()) {
  128. case ']':
  129. ++fIndex;
  130. while (fStack.size() > depth) {
  131. set.fChildren.push_back(this->pop());
  132. }
  133. fStack.push(std::move(set));
  134. return;
  135. case END:
  136. printf("unterminated character set\n");
  137. exit(1);
  138. default:
  139. this->setItem();
  140. }
  141. }
  142. }
  143. void RegexParser::regex() {
  144. this->sequence();
  145. switch (this->peek()) {
  146. case '|': {
  147. ++fIndex;
  148. this->regex();
  149. RegexNode right = this->pop();
  150. RegexNode left = this->pop();
  151. fStack.push(RegexNode(RegexNode::kOr_Kind, left, right));
  152. break;
  153. }
  154. case END: // fall through
  155. case ')':
  156. return;
  157. default:
  158. SkASSERT(false);
  159. }
  160. }