Lexer.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427
  1. /*
  2. * Copyright (c) 2020, Stephan Unverwerth <s.unverwerth@gmx.de>
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. *
  8. * 1. Redistributions of source code must retain the above copyright notice, this
  9. * list of conditions and the following disclaimer.
  10. *
  11. * 2. Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  19. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  21. * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  22. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  23. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #include "Lexer.h"
  27. #include <AK/HashMap.h>
  28. #include <AK/StringBuilder.h>
  29. #include <ctype.h>
  30. #include <stdio.h>
  31. namespace JS {
  32. HashMap<String, TokenType> Lexer::s_keywords;
  33. HashMap<String, TokenType> Lexer::s_three_char_tokens;
  34. HashMap<String, TokenType> Lexer::s_two_char_tokens;
  35. HashMap<char, TokenType> Lexer::s_single_char_tokens;
  36. Lexer::Lexer(StringView source)
  37. : m_source(source)
  38. , m_current_token(TokenType::Eof, StringView(nullptr), StringView(nullptr), 0, 0)
  39. {
  40. if (s_keywords.is_empty()) {
  41. s_keywords.set("await", TokenType::Await);
  42. s_keywords.set("break", TokenType::Break);
  43. s_keywords.set("case", TokenType::Case);
  44. s_keywords.set("catch", TokenType::Catch);
  45. s_keywords.set("class", TokenType::Class);
  46. s_keywords.set("const", TokenType::Const);
  47. s_keywords.set("continue", TokenType::Continue);
  48. s_keywords.set("default", TokenType::Default);
  49. s_keywords.set("delete", TokenType::Delete);
  50. s_keywords.set("do", TokenType::Do);
  51. s_keywords.set("else", TokenType::Else);
  52. s_keywords.set("false", TokenType::BoolLiteral);
  53. s_keywords.set("finally", TokenType::Finally);
  54. s_keywords.set("for", TokenType::For);
  55. s_keywords.set("function", TokenType::Function);
  56. s_keywords.set("if", TokenType::If);
  57. s_keywords.set("in", TokenType::In);
  58. s_keywords.set("instanceof", TokenType::Instanceof);
  59. s_keywords.set("interface", TokenType::Interface);
  60. s_keywords.set("let", TokenType::Let);
  61. s_keywords.set("new", TokenType::New);
  62. s_keywords.set("null", TokenType::NullLiteral);
  63. s_keywords.set("return", TokenType::Return);
  64. s_keywords.set("switch", TokenType::Switch);
  65. s_keywords.set("this", TokenType::This);
  66. s_keywords.set("throw", TokenType::Throw);
  67. s_keywords.set("true", TokenType::BoolLiteral);
  68. s_keywords.set("try", TokenType::Try);
  69. s_keywords.set("typeof", TokenType::Typeof);
  70. s_keywords.set("var", TokenType::Var);
  71. s_keywords.set("void", TokenType::Void);
  72. s_keywords.set("while", TokenType::While);
  73. s_keywords.set("yield", TokenType::Yield);
  74. }
  75. if (s_three_char_tokens.is_empty()) {
  76. s_three_char_tokens.set("===", TokenType::EqualsEqualsEquals);
  77. s_three_char_tokens.set("!==", TokenType::ExclamationMarkEqualsEquals);
  78. s_three_char_tokens.set("**=", TokenType::AsteriskAsteriskEquals);
  79. s_three_char_tokens.set("<<=", TokenType::ShiftLeftEquals);
  80. s_three_char_tokens.set(">>=", TokenType::ShiftRightEquals);
  81. s_three_char_tokens.set(">>>", TokenType::UnsignedShiftRight);
  82. s_three_char_tokens.set("...", TokenType::TripleDot);
  83. }
  84. if (s_two_char_tokens.is_empty()) {
  85. s_two_char_tokens.set("=>", TokenType::Arrow);
  86. s_two_char_tokens.set("+=", TokenType::PlusEquals);
  87. s_two_char_tokens.set("-=", TokenType::MinusEquals);
  88. s_two_char_tokens.set("*=", TokenType::AsteriskEquals);
  89. s_two_char_tokens.set("/=", TokenType::SlashEquals);
  90. s_two_char_tokens.set("%=", TokenType::PercentEquals);
  91. s_two_char_tokens.set("&=", TokenType::AmpersandEquals);
  92. s_two_char_tokens.set("|=", TokenType::PipeEquals);
  93. s_two_char_tokens.set("&&", TokenType::DoubleAmpersand);
  94. s_two_char_tokens.set("||", TokenType::DoublePipe);
  95. s_two_char_tokens.set("??", TokenType::DoubleQuestionMark);
  96. s_two_char_tokens.set("**", TokenType::DoubleAsterisk);
  97. s_two_char_tokens.set("==", TokenType::EqualsEquals);
  98. s_two_char_tokens.set("<=", TokenType::LessThanEquals);
  99. s_two_char_tokens.set(">=", TokenType::GreaterThanEquals);
  100. s_two_char_tokens.set("!=", TokenType::ExclamationMarkEquals);
  101. s_two_char_tokens.set("--", TokenType::MinusMinus);
  102. s_two_char_tokens.set("++", TokenType::PlusPlus);
  103. s_two_char_tokens.set("<<", TokenType::ShiftLeft);
  104. s_two_char_tokens.set(">>", TokenType::ShiftRight);
  105. s_two_char_tokens.set("?.", TokenType::QuestionMarkPeriod);
  106. }
  107. if (s_single_char_tokens.is_empty()) {
  108. s_single_char_tokens.set('&', TokenType::Ampersand);
  109. s_single_char_tokens.set('*', TokenType::Asterisk);
  110. s_single_char_tokens.set('[', TokenType::BracketOpen);
  111. s_single_char_tokens.set(']', TokenType::BracketClose);
  112. s_single_char_tokens.set('^', TokenType::Caret);
  113. s_single_char_tokens.set(':', TokenType::Colon);
  114. s_single_char_tokens.set(',', TokenType::Comma);
  115. s_single_char_tokens.set('{', TokenType::CurlyOpen);
  116. s_single_char_tokens.set('}', TokenType::CurlyClose);
  117. s_single_char_tokens.set('=', TokenType::Equals);
  118. s_single_char_tokens.set('!', TokenType::ExclamationMark);
  119. s_single_char_tokens.set('-', TokenType::Minus);
  120. s_single_char_tokens.set('(', TokenType::ParenOpen);
  121. s_single_char_tokens.set(')', TokenType::ParenClose);
  122. s_single_char_tokens.set('%', TokenType::Percent);
  123. s_single_char_tokens.set('.', TokenType::Period);
  124. s_single_char_tokens.set('|', TokenType::Pipe);
  125. s_single_char_tokens.set('+', TokenType::Plus);
  126. s_single_char_tokens.set('?', TokenType::QuestionMark);
  127. s_single_char_tokens.set(';', TokenType::Semicolon);
  128. s_single_char_tokens.set('/', TokenType::Slash);
  129. s_single_char_tokens.set('~', TokenType::Tilde);
  130. s_single_char_tokens.set('<', TokenType::LessThan);
  131. s_single_char_tokens.set('>', TokenType::GreaterThan);
  132. }
  133. consume();
  134. }
  135. void Lexer::consume()
  136. {
  137. if (m_position >= m_source.length()) {
  138. m_position = m_source.length() + 1;
  139. m_current_char = EOF;
  140. return;
  141. }
  142. if (m_current_char == '\n') {
  143. m_line_number++;
  144. m_line_column = 1;
  145. } else {
  146. m_line_column++;
  147. }
  148. m_current_char = m_source[m_position++];
  149. }
  150. void Lexer::consume_exponent()
  151. {
  152. consume();
  153. if (m_current_char == '-' || m_current_char == '+')
  154. consume();
  155. while (isdigit(m_current_char)) {
  156. consume();
  157. }
  158. }
  159. bool Lexer::match(char a, char b) const
  160. {
  161. if (m_position >= m_source.length())
  162. return false;
  163. return m_current_char == a
  164. && m_source[m_position] == b;
  165. }
  166. bool Lexer::match(char a, char b, char c) const
  167. {
  168. if (m_position + 1 >= m_source.length())
  169. return false;
  170. return m_current_char == a
  171. && m_source[m_position] == b
  172. && m_source[m_position + 1] == c;
  173. }
  174. bool Lexer::match(char a, char b, char c, char d) const
  175. {
  176. if (m_position + 2 >= m_source.length())
  177. return false;
  178. return m_current_char == a
  179. && m_source[m_position] == b
  180. && m_source[m_position + 1] == c
  181. && m_source[m_position + 2] == d;
  182. }
  183. bool Lexer::is_eof() const
  184. {
  185. return m_current_char == EOF;
  186. }
  187. bool Lexer::is_identifier_start() const
  188. {
  189. return isalpha(m_current_char) || m_current_char == '_' || m_current_char == '$';
  190. }
  191. bool Lexer::is_identifier_middle() const
  192. {
  193. return is_identifier_start() || isdigit(m_current_char);
  194. }
  195. bool Lexer::is_line_comment_start() const
  196. {
  197. return match('/', '/') || match('<', '!', '-', '-') || match('-', '-', '>');
  198. }
  199. bool Lexer::is_block_comment_start() const
  200. {
  201. return match('/', '*');
  202. }
  203. bool Lexer::is_block_comment_end() const
  204. {
  205. return match('*', '/');
  206. }
  207. bool Lexer::is_numeric_literal_start() const
  208. {
  209. return isdigit(m_current_char) || (m_current_char == '.' && m_position < m_source.length() && isdigit(m_source[m_position]));
  210. }
  211. void Lexer::syntax_error(const char* msg)
  212. {
  213. m_has_errors = true;
  214. if (m_log_errors)
  215. fprintf(stderr, "Syntax Error: %s (line: %zu, column: %zu)\n", msg, m_line_number, m_line_column);
  216. }
  217. Token Lexer::next()
  218. {
  219. size_t trivia_start = m_position;
  220. // consume whitespace and comments
  221. while (true) {
  222. if (isspace(m_current_char)) {
  223. do {
  224. consume();
  225. } while (isspace(m_current_char));
  226. } else if (is_line_comment_start()) {
  227. consume();
  228. do {
  229. consume();
  230. } while (!is_eof() && m_current_char != '\n');
  231. } else if (is_block_comment_start()) {
  232. consume();
  233. do {
  234. consume();
  235. } while (!is_eof() && !is_block_comment_end());
  236. consume(); // consume *
  237. consume(); // consume /
  238. } else {
  239. break;
  240. }
  241. }
  242. size_t value_start = m_position;
  243. auto token_type = TokenType::Invalid;
  244. if (is_identifier_start()) {
  245. // identifier or keyword
  246. do {
  247. consume();
  248. } while (is_identifier_middle());
  249. StringView value = m_source.substring_view(value_start - 1, m_position - value_start);
  250. auto it = s_keywords.find(value);
  251. if (it == s_keywords.end()) {
  252. token_type = TokenType::Identifier;
  253. } else {
  254. token_type = it->value;
  255. }
  256. } else if (is_numeric_literal_start()) {
  257. if (m_current_char == '0') {
  258. consume();
  259. if (m_current_char == '.') {
  260. // decimal
  261. consume();
  262. while (isdigit(m_current_char)) {
  263. consume();
  264. }
  265. if (m_current_char == 'e' || m_current_char == 'E') {
  266. consume_exponent();
  267. }
  268. } else if (m_current_char == 'e' || m_current_char == 'E') {
  269. consume_exponent();
  270. } else if (m_current_char == 'o' || m_current_char == 'O') {
  271. // octal
  272. consume();
  273. while (m_current_char >= '0' && m_current_char <= '7') {
  274. consume();
  275. }
  276. } else if (m_current_char == 'b' || m_current_char == 'B') {
  277. // binary
  278. consume();
  279. while (m_current_char == '0' || m_current_char == '1') {
  280. consume();
  281. }
  282. } else if (m_current_char == 'x' || m_current_char == 'X') {
  283. // hexadecimal
  284. consume();
  285. while (isxdigit(m_current_char)) {
  286. consume();
  287. }
  288. } else if (isdigit(m_current_char)) {
  289. // octal without 'O' prefix. Forbidden in 'strict mode'
  290. // FIXME: We need to make sure this produces a syntax error when in strict mode
  291. do {
  292. consume();
  293. } while (isdigit(m_current_char));
  294. }
  295. } else {
  296. // 1...9 or period
  297. while (isdigit(m_current_char)) {
  298. consume();
  299. }
  300. if (m_current_char == '.') {
  301. consume();
  302. while (isdigit(m_current_char)) {
  303. consume();
  304. }
  305. }
  306. if (m_current_char == 'e' || m_current_char == 'E') {
  307. consume_exponent();
  308. }
  309. }
  310. token_type = TokenType::NumericLiteral;
  311. } else if (m_current_char == '"' || m_current_char == '\'' || m_current_char == '`') {
  312. char stop_char = m_current_char;
  313. consume();
  314. while (m_current_char != stop_char && m_current_char != '\n' && !is_eof()) {
  315. if (m_current_char == '\\') {
  316. consume();
  317. }
  318. consume();
  319. }
  320. if (m_current_char != stop_char) {
  321. syntax_error("unterminated string literal");
  322. token_type = TokenType::UnterminatedStringLiteral;
  323. } else {
  324. consume();
  325. if (stop_char == '`')
  326. token_type = TokenType::TemplateLiteral;
  327. else
  328. token_type = TokenType::StringLiteral;
  329. }
  330. } else if (m_current_char == EOF) {
  331. token_type = TokenType::Eof;
  332. } else {
  333. // There is only one four-char operator: >>>=
  334. bool found_four_char_token = false;
  335. if (match('>', '>', '>', '=')) {
  336. found_four_char_token = true;
  337. consume();
  338. consume();
  339. consume();
  340. consume();
  341. token_type = TokenType::UnsignedShiftRightEquals;
  342. }
  343. bool found_three_char_token = false;
  344. if (!found_four_char_token && m_position + 1 < m_source.length()) {
  345. char second_char = m_source[m_position];
  346. char third_char = m_source[m_position + 1];
  347. char three_chars[] { (char)m_current_char, second_char, third_char, 0 };
  348. auto it = s_three_char_tokens.find(three_chars);
  349. if (it != s_three_char_tokens.end()) {
  350. found_three_char_token = true;
  351. consume();
  352. consume();
  353. consume();
  354. token_type = it->value;
  355. }
  356. }
  357. bool found_two_char_token = false;
  358. if (!found_four_char_token && !found_three_char_token && m_position < m_source.length()) {
  359. char second_char = m_source[m_position];
  360. char two_chars[] { (char)m_current_char, second_char, 0 };
  361. auto it = s_two_char_tokens.find(two_chars);
  362. if (it != s_two_char_tokens.end()) {
  363. found_two_char_token = true;
  364. consume();
  365. consume();
  366. token_type = it->value;
  367. }
  368. }
  369. bool found_one_char_token = false;
  370. if (!found_four_char_token && !found_three_char_token && !found_two_char_token) {
  371. auto it = s_single_char_tokens.find(m_current_char);
  372. if (it != s_single_char_tokens.end()) {
  373. found_one_char_token = true;
  374. consume();
  375. token_type = it->value;
  376. }
  377. }
  378. if (!found_four_char_token && !found_three_char_token && !found_two_char_token && !found_one_char_token) {
  379. consume();
  380. token_type = TokenType::Invalid;
  381. }
  382. }
  383. m_current_token = Token(
  384. token_type,
  385. m_source.substring_view(trivia_start - 1, value_start - trivia_start),
  386. m_source.substring_view(value_start - 1, m_position - value_start),
  387. m_line_number,
  388. m_line_column - m_position + value_start);
  389. return m_current_token;
  390. }
  391. }