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

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

Исходя из «Классической теории компилятора» В. Э. Карпова, можно выделить 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 -> должен быть точкой с запятой ], 

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

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

Материалы

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