Пятница программиста, или как я писал библиотеку для лексического и синтаксического анализа кода

Всем привет! Я, как программист, всегда ищу пути для улучшения своих навыков. В один пятничный вечер, в мою голову пришла мысль — «А не написать ли мне компилятор?»

Кому интересно узнать, что из этого получилось, добро пожаловать под кат.

Исходя из «Классической теории компилятора» В. Э. Карпова, можно выделить 5 основных этапов компиляции:

1. Лексический анализ
2. Синтаксический анализ
3. Генерация middle кода
4. Оптимизация
5. Генерация конечного, объектного, кода

Про все, пять частей, можно писать уйму предложений и статей. Но, сегодня, мы поговорим о первых двух и как я выделил их структуру в отдельную библиотеку.

Когда я решился на написание, пусть даже небольшой части, компилятора, то я не задумывался, для какого именно языка я пишу, по этой причине, результатом стала библиотека для лексического и синтаксического анализа любого языка.

Токенизация

Перед тем, как строить синтаксическое и лексическое дерево, генерировать результирующий код и заниматься другими вкусными вещами, исходный код требуется разбить на строки, символы, цифры.

Где каждый элемент будет иметь точно определенный тип. Токены с неопределенным типом при синтаксическом анализе будут рассматриваться как синтаксические ошибки.

В контексте компиляции, исходный код рассматривается как source-map, хорошей практикой будет хранить его в процессе лексического и синтаксического анализа для обратной связи с программистом и указания синтаксических ошибок в исходном коде.

Разбить исходный код на массив токенов, можно при помощи простого регулярного выражения:

/\S+/gm

Оно может меняться в зависимости от дополнительных условий парсинга, таких как: парсинг переносов строк, парсинг табов, парсинг пробелов.

Результатом разделения, будет массив слов исходного кода, причем слова парсятся от пробела до пробела, т.е. такая конструкция:

let hello = 'world';

Будет преобразована в следующий набор токенов:

["let", "hello", "=", "'world';"]

Что-бы получить финальный набор токенов, требуется пройтись по каждому из них, дополнительным регулярным выражением:

/(\W)|(\w+)/gm

Результатом будет, требуемый нам набор токенов:

["let", "hello", "=", "'", "world", "'", ";"]

Все токены, которые мы получили, мы записываем в массив, вместе с их индексами в source-map

Лексический анализ

Теперь, когда мы имеем массив токенов, нам нужно определить их тип, для передачи их на синтаксический анализ.

Алгоритм, который определяет токены и их типы, носит название — Лексер
Токен и его тип, который определяет Лексер, носит название — Лексема

Каждый токен может иметь однозначно определенный тип, например:

['let', 'const', 'var'] // Keywords
['=', '+', '-', '*', '/'] // Operators
И т.д.

Я же, реализовал схему определения типов токенов, при помощи, так называемых, Solver'ов.
Работает это следующим образом:

1. Вы определяете константы, для типов токенов:

const DefaultTokenTypes = {
    KEYWORD: "Keyword",
    IDENTIFIER: "Identifier",
    OPERATOR: "Operator",
    DELIMITER: "Delimiter",
    LINEBREAK: "Linebreak",
    STRING: "String",
    NUMERIC: "Numeric",
    UNKNOWN: 'Unknown'
};

2. Далее, следует определить, так называемые Solver'ы:

const solvers = {};

solvers[MyTokenTypes.KEYWORD] = {
    include: [
        'const',
        'let'
    ]
};

solvers[MyTokenTypes.NUMERIC] = {
    regexp: /^[0-9.]*$/gm
};

solvers[DefaultTokenTypes.STRING] = {
    type: StringSolver,
    delimiters: ['"', "'", '`']
};

solvers[MyTokenTypes.IDENTIFIER] = {
    regexp: /^[a-zA-Z_][a-zA-Z_0-9]*$/gm
};

solvers[MyTokenTypes.DELIMITER] = {
    default: true
};

Как видно, токены могут иметь различные вариации настройки:

include — Массив слов, по совпадению с которыми, может определяться тип токена.
regexp — Регулярное выражение, по совпадению с которым, может определяться тип токена.
default — Стандартный тип, для неопределенных токенов.

Так же, можно заметить, параметр type, который указывает, что данный солвер нужно наследовать от того, который указан в type

В данном случае, солвер определяет строки, которые заключены в один из символов, указанных в delimiters

3. Применяем солверы для массива токенов и получаем массив типизированных токенов. Для данного, исходного кода:

let a = 50;

Получаем следующее дерево:

[
  {
    "type": "Keyword",
    "value": "let",
    "range": [0, 3]
  },
  {
    "type": "Identifier",
    "value": "a",
    "range": [4, 5]
  },
  {
    "type": "Delimiter",
    "value": "=",
    "range": [6, 7]
  },
  {
    "type": "Numeric",
    "value": "50",
    "range": [8, 10]
  },
  {
    "type": "Delimiter",
    "value": ";",
    "range": [10, 11]
  }
]

Где range — Начало и конце фрагмента в исходном коде.

Синтаксический анализ

После получения массива лексем, следует распарсить их и определить синтаксическую структуру(древо) исходного кода.

Существуют различные варианты парсинга, я же, выбрал нисходящий, прямой, алгоритм.

Токены парсятся один за другим, используя массив шаблонов. При совпадении шаблона с текущей последовательностью токенов — в синтаксическом дереве, создается новая ветка.

Пример одного шаблона из массива:

let declaration = new SequenceNode({
    tokenType: MyTokenTypes.KEYWORD,
    type: MyNodeTypes.DECLARATION,
    sequence: [
        {type: MyTokenTypes.KEYWORD},
        {type: MyTokenTypes.IDENTIFIER},
        {type: MyTokenTypes.DELIMITER},
        {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]},
        ';' 
    ],
    onError: (e) => {
        //e - Syntax error
    }
});

tokenType — Описывает токен, с которого начинать проверку на совпадение.
type — Описывает тип узла, все типы — так же должны быть определены, аналогично типам токенов.
sequence — Массив последовательности, в нем содержаться типы токенов, конкретные значения или же другие узлы синтаксического дерева.
onError — Callback, который сработает при синтаксической ошибке, во время парсинга данного узла, он возвращает тип ошибки + ее место в исходном коде.

Разберем sequence данного узла:

[
        {type: MyTokenTypes.KEYWORD}, // Текущий токен -> должен быть ключевым словом
        {type: MyTokenTypes.IDENTIFIER},// Текущий токен + 1 -> должен быть идентификатором
        {type: MyTokenTypes.DELIMITER},// Текущий токен + 2 -> должен быть разделителем
        {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]},// Текущий токен + 2 -> должен быть строкой или числом
        ';' // Текущий токен + 3 -> должен быть точкой с запятой
],

Я реализовал несколько вариаций узлов, для разных целей: определение последовательностей токенов, определение группы элементов(Аргументы, блоки). Что позволяет без проблем парсить стрелочные функции.

Прочесть о всех вариация Солверов и Узлов, которые я реализовал, вы сможете в документации данной библиотеки.

Материалы

→ Ссылка на исходный код: Тык
→ Классическая теория компиляторов