Всем привет! Я, как программист, всегда ищу пути для улучшения своих навыков. В один пятничный вечер, в мою голову пришла мысль — «А не написать ли мне компилятор?»
Кому интересно узнать, что из этого получилось, добро пожаловать под кат.
Исходя из «Классической теории компилятора» В. Э. Карпова, можно выделить 5 основных этапов компиляции:
- Лексический анализ
- Синтаксический анализ
- Генерация middle кода
- Оптимизация
- Генерация конечного, объектного, кода
Про все, пять частей, можно писать уйму предложений и статей. Но, сегодня, мы поговорим о первых двух и как я выделил их структуру в отдельную библиотеку.
Когда я решился на написание, пусть даже небольшой части, компилятора, то я не задумывался, для какого именно языка я пишу, по этой причине, результатом стала библиотека для лексического и синтаксического анализа любого языка.
Токенизация
Перед тем, как строить синтаксическое и лексическое дерево, генерировать результирующий код и заниматься другими вкусными вещами, исходный код требуется разбить на строки, символы, цифры.
Где каждый элемент будет иметь точно определенный тип. Токены с неопределенным типом при синтаксическом анализе будут рассматриваться как синтаксические ошибки.
В контексте компиляции, исходный код рассматривается как 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 -> должен быть точкой с запятой
],
Я реализовал несколько вариаций узлов, для разных целей: определение последовательностей токенов, определение группы элементов(Аргументы, блоки). Что позволяет без проблем парсить стрелочные функции.
Прочесть о всех вариация Солверов и Узлов, которые я реализовал, вы сможете в документации данной библиотеки.
Материалы
→ Ссылка на исходный код: Тык
→ Классическая теория компиляторов
Автор: IIIarp
