diff options
| Commit | 3bc02cca36343ba5c731e1912ff7b8488dd0ef06 (patch) | |
|---|---|---|
| Author | 2022-10-18 22:06:38 +0300 | |
| Committer | 2022-10-18 22:06:38 +0300 | |
| Files | dbc4b3f38e690e288f343e21ecce2d8e7e12558c | |
| IPL-3bc02cca36343ba5c731e1912ff7b8488dd0ef06.tar IPL-3bc02cca36343ba5c731e1912ff7b8488dd0ef06.tar.gz IPL-3bc02cca36343ba5c731e1912ff7b8488dd0ef06.zip | ||
| Parent | 09e4a0fb39dd19b7a44a463cbb6777fd7f49588b (diff) | |
Add tree-sitter toy parser for arithmetic expressions
5 files changed, 703 insertions, 0 deletions
| -rw-r--r-- | demo/tree-sitter-calc/grammar.js | 30 | ||||
| -rw-r--r-- | demo/tree-sitter-calc/package.json | 17 | ||||
| -rw-r--r-- | demo/tree-sitter-calc/src/parser.c | 431 | ||||
| -rw-r--r-- | demo/tree-sitter-calc/src/tree_sitter/parser.h | 224 | ||||
| -rw-r--r-- | demo/tree-sitter-calc/test.calc | 1 |
diff --git a/demo/tree-sitter-calc/grammar.js b/demo/tree-sitter-calc/grammar.js new file mode 100644 index 0000000..16d3d8e --- /dev/null +++ b/demo/tree-sitter-calc/grammar.js @@ -0,0 +1,30 @@ +module.exports = grammar({
+ name: 'Calc',
+ rules: {
+ source_file: $ => $.expression,
+
+ expression: $ => choice(
+ $.term,
+ $.unary_expression,
+ $.binary_expression,
+ ),
+
+ unary_expression: $ => prec.left(1, seq('-', $.term)),
+
+ binary_expression: $ => choice(
+ prec.left(2, seq($.expression, '+', $.expression)),
+ prec.left(2, seq($.expression, '-', $.expression)),
+ prec.left(3, seq($.expression, '*', $.expression)),
+ prec.left(3, seq($.expression, '/', $.expression)),
+ ),
+
+ term: $ => choice(
+ $.identifier,
+ $.number,
+ seq('(', $.expression, ')'),
+ ),
+
+ identifier: $ => /[a-z_]+/,
+ number: $ => /[0-9][0-9.]*/,
+ }
+});
diff --git a/demo/tree-sitter-calc/package.json b/demo/tree-sitter-calc/package.json new file mode 100644 index 0000000..f7442c3 --- /dev/null +++ b/demo/tree-sitter-calc/package.json @@ -0,0 +1,17 @@ +{ + "name": "tree-sitter-calc", + "version": "0.9.9", + "description": "Tree-sitter parser for arithmetic expressions", + "main": "grammar.js", + "scripts": { + "test": "echo \"Error: no test specified\" && exit 1" + }, + "author": "Dimitar Trendafilov", + "license": "MIT", + "dependencies": { + "nan": "^2.17.0" + }, + "devDependencies": { + "tree-sitter-cli": "^0.20.7" + } +} diff --git a/demo/tree-sitter-calc/src/parser.c b/demo/tree-sitter-calc/src/parser.c new file mode 100644 index 0000000..5483d0d --- /dev/null +++ b/demo/tree-sitter-calc/src/parser.c @@ -0,0 +1,431 @@ +#include <tree_sitter/parser.h> + +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wmissing-field-initializers" +#endif + +#define LANGUAGE_VERSION 14 +#define STATE_COUNT 15 +#define LARGE_STATE_COUNT 5 +#define SYMBOL_COUNT 14 +#define ALIAS_COUNT 0 +#define TOKEN_COUNT 9 +#define EXTERNAL_TOKEN_COUNT 0 +#define FIELD_COUNT 0 +#define MAX_ALIAS_SEQUENCE_LENGTH 3 +#define PRODUCTION_ID_COUNT 1 + +enum { + anon_sym_DASH = 1, + anon_sym_PLUS = 2, + anon_sym_STAR = 3, + anon_sym_SLASH = 4, + anon_sym_LPAREN = 5, + anon_sym_RPAREN = 6, + sym_identifier = 7, + sym_number = 8, + sym_source_file = 9, + sym_expression = 10, + sym_unary_expression = 11, + sym_binary_expression = 12, + sym_term = 13, +}; + +static const char * const ts_symbol_names[] = { + [ts_builtin_sym_end] = "end", + [anon_sym_DASH] = "-", + [anon_sym_PLUS] = "+", + [anon_sym_STAR] = "*", + [anon_sym_SLASH] = "/", + [anon_sym_LPAREN] = "(", + [anon_sym_RPAREN] = ")", + [sym_identifier] = "identifier", + [sym_number] = "number", + [sym_source_file] = "source_file", + [sym_expression] = "expression", + [sym_unary_expression] = "unary_expression", + [sym_binary_expression] = "binary_expression", + [sym_term] = "term", +}; + +static const TSSymbol ts_symbol_map[] = { + [ts_builtin_sym_end] = ts_builtin_sym_end, + [anon_sym_DASH] = anon_sym_DASH, + [anon_sym_PLUS] = anon_sym_PLUS, + [anon_sym_STAR] = anon_sym_STAR, + [anon_sym_SLASH] = anon_sym_SLASH, + [anon_sym_LPAREN] = anon_sym_LPAREN, + [anon_sym_RPAREN] = anon_sym_RPAREN, + [sym_identifier] = sym_identifier, + [sym_number] = sym_number, + [sym_source_file] = sym_source_file, + [sym_expression] = sym_expression, + [sym_unary_expression] = sym_unary_expression, + [sym_binary_expression] = sym_binary_expression, + [sym_term] = sym_term, +}; + +static const TSSymbolMetadata ts_symbol_metadata[] = { + [ts_builtin_sym_end] = { + .visible = false, + .named = true, + }, + [anon_sym_DASH] = { + .visible = true, + .named = false, + }, + [anon_sym_PLUS] = { + .visible = true, + .named = false, + }, + [anon_sym_STAR] = { + .visible = true, + .named = false, + }, + [anon_sym_SLASH] = { + .visible = true, + .named = false, + }, + [anon_sym_LPAREN] = { + .visible = true, + .named = false, + }, + [anon_sym_RPAREN] = { + .visible = true, + .named = false, + }, + [sym_identifier] = { + .visible = true, + .named = true, + }, + [sym_number] = { + .visible = true, + .named = true, + }, + [sym_source_file] = { + .visible = true, + .named = true, + }, + [sym_expression] = { + .visible = true, + .named = true, + }, + [sym_unary_expression] = { + .visible = true, + .named = true, + }, + [sym_binary_expression] = { + .visible = true, + .named = true, + }, + [sym_term] = { + .visible = true, + .named = true, + }, +}; + +static const TSSymbol ts_alias_sequences[PRODUCTION_ID_COUNT][MAX_ALIAS_SEQUENCE_LENGTH] = { + [0] = {0}, +}; + +static const uint16_t ts_non_terminal_alias_map[] = { + 0, +}; + +static const TSStateId ts_primary_state_ids[STATE_COUNT] = { + [0] = 0, + [1] = 1, + [2] = 2, + [3] = 3, + [4] = 4, + [5] = 5, + [6] = 6, + [7] = 7, + [8] = 8, + [9] = 9, + [10] = 10, + [11] = 11, + [12] = 12, + [13] = 13, + [14] = 14, +}; + +static bool ts_lex(TSLexer *lexer, TSStateId state) { + START_LEXER(); + eof = lexer->eof(lexer); + switch (state) { + case 0: + if (eof) ADVANCE(1); + if (lookahead == '(') ADVANCE(6); + if (lookahead == ')') ADVANCE(7); + if (lookahead == '*') ADVANCE(4); + if (lookahead == '+') ADVANCE(3); + if (lookahead == '-') ADVANCE(2); + if (lookahead == '/') ADVANCE(5); + if (lookahead == '\t' || + lookahead == '\n' || + lookahead == '\r' || + lookahead == ' ') SKIP(0) + if (('0' <= lookahead && lookahead <= '9')) ADVANCE(9); + if (lookahead == '_' || + ('a' <= lookahead && lookahead <= 'z')) ADVANCE(8); + END_STATE(); + case 1: + ACCEPT_TOKEN(ts_builtin_sym_end); + END_STATE(); + case 2: + ACCEPT_TOKEN(anon_sym_DASH); + END_STATE(); + case 3: + ACCEPT_TOKEN(anon_sym_PLUS); + END_STATE(); + case 4: + ACCEPT_TOKEN(anon_sym_STAR); + END_STATE(); + case 5: + ACCEPT_TOKEN(anon_sym_SLASH); + END_STATE(); + case 6: + ACCEPT_TOKEN(anon_sym_LPAREN); + END_STATE(); + case 7: + ACCEPT_TOKEN(anon_sym_RPAREN); + END_STATE(); + case 8: + ACCEPT_TOKEN(sym_identifier); + if (lookahead == '_' || + ('a' <= lookahead && lookahead <= 'z')) ADVANCE(8); + END_STATE(); + case 9: + ACCEPT_TOKEN(sym_number); + if (lookahead == '.' || + ('0' <= lookahead && lookahead <= '9')) ADVANCE(9); + END_STATE(); + default: + return false; + } +} + +static const TSLexMode ts_lex_modes[STATE_COUNT] = { + [0] = {.lex_state = 0}, + [1] = {.lex_state = 0}, + [2] = {.lex_state = 0}, + [3] = {.lex_state = 0}, + [4] = {.lex_state = 0}, + [5] = {.lex_state = 0}, + [6] = {.lex_state = 0}, + [7] = {.lex_state = 0}, + [8] = {.lex_state = 0}, + [9] = {.lex_state = 0}, + [10] = {.lex_state = 0}, + [11] = {.lex_state = 0}, + [12] = {.lex_state = 0}, + [13] = {.lex_state = 0}, + [14] = {.lex_state = 0}, +}; + +static const uint16_t ts_parse_table[LARGE_STATE_COUNT][SYMBOL_COUNT] = { + [0] = { + [ts_builtin_sym_end] = ACTIONS(1), + [anon_sym_DASH] = ACTIONS(1), + [anon_sym_PLUS] = ACTIONS(1), + [anon_sym_STAR] = ACTIONS(1), + [anon_sym_SLASH] = ACTIONS(1), + [anon_sym_LPAREN] = ACTIONS(1), + [anon_sym_RPAREN] = ACTIONS(1), + [sym_identifier] = ACTIONS(1), + [sym_number] = ACTIONS(1), + }, + [1] = { + [sym_source_file] = STATE(14), + [sym_expression] = STATE(11), + [sym_unary_expression] = STATE(6), + [sym_binary_expression] = STATE(6), + [sym_term] = STATE(6), + [anon_sym_DASH] = ACTIONS(3), + [anon_sym_LPAREN] = ACTIONS(5), + [sym_identifier] = ACTIONS(7), + [sym_number] = ACTIONS(7), + }, + [2] = { + [sym_expression] = STATE(12), + [sym_unary_expression] = STATE(6), + [sym_binary_expression] = STATE(6), + [sym_term] = STATE(6), + [anon_sym_DASH] = ACTIONS(3), + [anon_sym_LPAREN] = ACTIONS(5), + [sym_identifier] = ACTIONS(7), + [sym_number] = ACTIONS(7), + }, + [3] = { + [sym_expression] = STATE(9), + [sym_unary_expression] = STATE(6), + [sym_binary_expression] = STATE(6), + [sym_term] = STATE(6), + [anon_sym_DASH] = ACTIONS(3), + [anon_sym_LPAREN] = ACTIONS(5), + [sym_identifier] = ACTIONS(7), + [sym_number] = ACTIONS(7), + }, + [4] = { + [sym_expression] = STATE(10), + [sym_unary_expression] = STATE(6), + [sym_binary_expression] = STATE(6), + [sym_term] = STATE(6), + [anon_sym_DASH] = ACTIONS(3), + [anon_sym_LPAREN] = ACTIONS(5), + [sym_identifier] = ACTIONS(7), + [sym_number] = ACTIONS(7), + }, +}; + +static const uint16_t ts_small_parse_table[] = { + [0] = 1, + ACTIONS(9), 6, + ts_builtin_sym_end, + anon_sym_DASH, + anon_sym_PLUS, + anon_sym_STAR, + anon_sym_SLASH, + anon_sym_RPAREN, + [9] = 1, + ACTIONS(11), 6, + ts_builtin_sym_end, + anon_sym_DASH, + anon_sym_PLUS, + anon_sym_STAR, + anon_sym_SLASH, + anon_sym_RPAREN, + [18] = 1, + ACTIONS(13), 6, + ts_builtin_sym_end, + anon_sym_DASH, + anon_sym_PLUS, + anon_sym_STAR, + anon_sym_SLASH, + anon_sym_RPAREN, + [27] = 1, + ACTIONS(15), 6, + ts_builtin_sym_end, + anon_sym_DASH, + anon_sym_PLUS, + anon_sym_STAR, + anon_sym_SLASH, + anon_sym_RPAREN, + [36] = 2, + ACTIONS(19), 2, + anon_sym_STAR, + anon_sym_SLASH, + ACTIONS(17), 4, + ts_builtin_sym_end, + anon_sym_DASH, + anon_sym_PLUS, + anon_sym_RPAREN, + [47] = 1, + ACTIONS(17), 6, + ts_builtin_sym_end, + anon_sym_DASH, + anon_sym_PLUS, + anon_sym_STAR, + anon_sym_SLASH, + anon_sym_RPAREN, + [56] = 3, + ACTIONS(21), 1, + ts_builtin_sym_end, + ACTIONS(19), 2, + anon_sym_STAR, + anon_sym_SLASH, + ACTIONS(23), 2, + anon_sym_DASH, + anon_sym_PLUS, + [68] = 3, + ACTIONS(25), 1, + anon_sym_RPAREN, + ACTIONS(19), 2, + anon_sym_STAR, + anon_sym_SLASH, + ACTIONS(23), 2, + anon_sym_DASH, + anon_sym_PLUS, + [80] = 3, + ACTIONS(5), 1, + anon_sym_LPAREN, + STATE(7), 1, + sym_term, + ACTIONS(7), 2, + sym_identifier, + sym_number, + [91] = 1, + ACTIONS(27), 1, + ts_builtin_sym_end, +}; + +static const uint32_t ts_small_parse_table_map[] = { + [SMALL_STATE(5)] = 0, + [SMALL_STATE(6)] = 9, + [SMALL_STATE(7)] = 18, + [SMALL_STATE(8)] = 27, + [SMALL_STATE(9)] = 36, + [SMALL_STATE(10)] = 47, + [SMALL_STATE(11)] = 56, + [SMALL_STATE(12)] = 68, + [SMALL_STATE(13)] = 80, + [SMALL_STATE(14)] = 91, +}; + +static const TSParseActionEntry ts_parse_actions[] = { + [0] = {.entry = {.count = 0, .reusable = false}}, + [1] = {.entry = {.count = 1, .reusable = false}}, RECOVER(), + [3] = {.entry = {.count = 1, .reusable = true}}, SHIFT(13), + [5] = {.entry = {.count = 1, .reusable = true}}, SHIFT(2), + [7] = {.entry = {.count = 1, .reusable = true}}, SHIFT(5), + [9] = {.entry = {.count = 1, .reusable = true}}, REDUCE(sym_term, 1), + [11] = {.entry = {.count = 1, .reusable = true}}, REDUCE(sym_expression, 1), + [13] = {.entry = {.count = 1, .reusable = true}}, REDUCE(sym_unary_expression, 2), + [15] = {.entry = {.count = 1, .reusable = true}}, REDUCE(sym_term, 3), + [17] = {.entry = {.count = 1, .reusable = true}}, REDUCE(sym_binary_expression, 3), + [19] = {.entry = {.count = 1, .reusable = true}}, SHIFT(4), + [21] = {.entry = {.count = 1, .reusable = true}}, REDUCE(sym_source_file, 1), + [23] = {.entry = {.count = 1, .reusable = true}}, SHIFT(3), + [25] = {.entry = {.count = 1, .reusable = true}}, SHIFT(8), + [27] = {.entry = {.count = 1, .reusable = true}}, ACCEPT_INPUT(), +}; + +#ifdef __cplusplus +extern "C" { +#endif +#ifdef _WIN32 +#define extern __declspec(dllexport) +#endif + +extern const TSLanguage *tree_sitter_Calc(void) { + static const TSLanguage language = { + .version = LANGUAGE_VERSION, + .symbol_count = SYMBOL_COUNT, + .alias_count = ALIAS_COUNT, + .token_count = TOKEN_COUNT, + .external_token_count = EXTERNAL_TOKEN_COUNT, + .state_count = STATE_COUNT, + .large_state_count = LARGE_STATE_COUNT, + .production_id_count = PRODUCTION_ID_COUNT, + .field_count = FIELD_COUNT, + .max_alias_sequence_length = MAX_ALIAS_SEQUENCE_LENGTH, + .parse_table = &ts_parse_table[0][0], + .small_parse_table = ts_small_parse_table, + .small_parse_table_map = ts_small_parse_table_map, + .parse_actions = ts_parse_actions, + .symbol_names = ts_symbol_names, + .symbol_metadata = ts_symbol_metadata, + .public_symbol_map = ts_symbol_map, + .alias_map = ts_non_terminal_alias_map, + .alias_sequences = &ts_alias_sequences[0][0], + .lex_modes = ts_lex_modes, + .lex_fn = ts_lex, + .primary_state_ids = ts_primary_state_ids, + }; + return &language; +} +#ifdef __cplusplus +} +#endif diff --git a/demo/tree-sitter-calc/src/tree_sitter/parser.h b/demo/tree-sitter-calc/src/tree_sitter/parser.h new file mode 100644 index 0000000..2b14ac1 --- /dev/null +++ b/demo/tree-sitter-calc/src/tree_sitter/parser.h @@ -0,0 +1,224 @@ +#ifndef TREE_SITTER_PARSER_H_ +#define TREE_SITTER_PARSER_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> + +#define ts_builtin_sym_error ((TSSymbol)-1) +#define ts_builtin_sym_end 0 +#define TREE_SITTER_SERIALIZATION_BUFFER_SIZE 1024 + +typedef uint16_t TSStateId; + +#ifndef TREE_SITTER_API_H_ +typedef uint16_t TSSymbol; +typedef uint16_t TSFieldId; +typedef struct TSLanguage TSLanguage; +#endif + +typedef struct { + TSFieldId field_id; + uint8_t child_index; + bool inherited; +} TSFieldMapEntry; + +typedef struct { + uint16_t index; + uint16_t length; +} TSFieldMapSlice; + +typedef struct { + bool visible; + bool named; + bool supertype; +} TSSymbolMetadata; + +typedef struct TSLexer TSLexer; + +struct TSLexer { + int32_t lookahead; + TSSymbol result_symbol; + void (*advance)(TSLexer *, bool); + void (*mark_end)(TSLexer *); + uint32_t (*get_column)(TSLexer *); + bool (*is_at_included_range_start)(const TSLexer *); + bool (*eof)(const TSLexer *); +}; + +typedef enum { + TSParseActionTypeShift, + TSParseActionTypeReduce, + TSParseActionTypeAccept, + TSParseActionTypeRecover, +} TSParseActionType; + +typedef union { + struct { + uint8_t type; + TSStateId state; + bool extra; + bool repetition; + } shift; + struct { + uint8_t type; + uint8_t child_count; + TSSymbol symbol; + int16_t dynamic_precedence; + uint16_t production_id; + } reduce; + uint8_t type; +} TSParseAction; + +typedef struct { + uint16_t lex_state; + uint16_t external_lex_state; +} TSLexMode; + +typedef union { + TSParseAction action; + struct { + uint8_t count; + bool reusable; + } entry; +} TSParseActionEntry; + +struct TSLanguage { + uint32_t version; + uint32_t symbol_count; + uint32_t alias_count; + uint32_t token_count; + uint32_t external_token_count; + uint32_t state_count; + uint32_t large_state_count; + uint32_t production_id_count; + uint32_t field_count; + uint16_t max_alias_sequence_length; + const uint16_t *parse_table; + const uint16_t *small_parse_table; + const uint32_t *small_parse_table_map; + const TSParseActionEntry *parse_actions; + const char * const *symbol_names; + const char * const *field_names; + const TSFieldMapSlice *field_map_slices; + const TSFieldMapEntry *field_map_entries; + const TSSymbolMetadata *symbol_metadata; + const TSSymbol *public_symbol_map; + const uint16_t *alias_map; + const TSSymbol *alias_sequences; + const TSLexMode *lex_modes; + bool (*lex_fn)(TSLexer *, TSStateId); + bool (*keyword_lex_fn)(TSLexer *, TSStateId); + TSSymbol keyword_capture_token; + struct { + const bool *states; + const TSSymbol *symbol_map; + void *(*create)(void); + void (*destroy)(void *); + bool (*scan)(void *, TSLexer *, const bool *symbol_whitelist); + unsigned (*serialize)(void *, char *); + void (*deserialize)(void *, const char *, unsigned); + } external_scanner; + const TSStateId *primary_state_ids; +}; + +/* + * Lexer Macros + */ + +#define START_LEXER() \ + bool result = false; \ + bool skip = false; \ + bool eof = false; \ + int32_t lookahead; \ + goto start; \ + next_state: \ + lexer->advance(lexer, skip); \ + start: \ + skip = false; \ + lookahead = lexer->lookahead; + +#define ADVANCE(state_value) \ + { \ + state = state_value; \ + goto next_state; \ + } + +#define SKIP(state_value) \ + { \ + skip = true; \ + state = state_value; \ + goto next_state; \ + } + +#define ACCEPT_TOKEN(symbol_value) \ + result = true; \ + lexer->result_symbol = symbol_value; \ + lexer->mark_end(lexer); + +#define END_STATE() return result; + +/* + * Parse Table Macros + */ + +#define SMALL_STATE(id) id - LARGE_STATE_COUNT + +#define STATE(id) id + +#define ACTIONS(id) id + +#define SHIFT(state_value) \ + {{ \ + .shift = { \ + .type = TSParseActionTypeShift, \ + .state = state_value \ + } \ + }} + +#define SHIFT_REPEAT(state_value) \ + {{ \ + .shift = { \ + .type = TSParseActionTypeShift, \ + .state = state_value, \ + .repetition = true \ + } \ + }} + +#define SHIFT_EXTRA() \ + {{ \ + .shift = { \ + .type = TSParseActionTypeShift, \ + .extra = true \ + } \ + }} + +#define REDUCE(symbol_val, child_count_val, ...) \ + {{ \ + .reduce = { \ + .type = TSParseActionTypeReduce, \ + .symbol = symbol_val, \ + .child_count = child_count_val, \ + __VA_ARGS__ \ + }, \ + }} + +#define RECOVER() \ + {{ \ + .type = TSParseActionTypeRecover \ + }} + +#define ACCEPT_INPUT() \ + {{ \ + .type = TSParseActionTypeAccept \ + }} + +#ifdef __cplusplus +} +#endif + +#endif // TREE_SITTER_PARSER_H_ diff --git a/demo/tree-sitter-calc/test.calc b/demo/tree-sitter-calc/test.calc new file mode 100644 index 0000000..0f9776f --- /dev/null +++ b/demo/tree-sitter-calc/test.calc @@ -0,0 +1 @@ +-1 * (answer+b) * 6 * 7 / 42
|
