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

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

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

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

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

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

Материалы


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

Похожие публикации

Комментарии 13
    0
    Честно? Не стоило вам создавать библиотеку ))) Не разобравшись с темой. Тот же лексический анализ гораздо более эффективно решается одной регуляркой с группами в которых регулярки под каждый токен, а не тупое разбивание всего на пробелы.
      +3
      Классический лексический анализ в языках программирования делается безо всяких регулярок.
      Пихать регулярки в этот процесс можно разве что от незнания, как работать с байтами
        0
        Если вы имеете ввиду конечные автоматы, то они работают еще медленней чем регулярки. Неоднократно пытался переписать свои лексеры на них. (я говорю про их реализацию в js)
          +3
          js регулярки как-то оптимизируются особо? Так-то регулярки преобразуются в конечные автоматы, а значит последние не могут быть медленней.
            0
            Я имел ввиду писать конечный автомат руками, либо пользоваться регулярками. JS регулярки компилятся в те же конечные автоматы в итоге.
          0
          Я с вами полностью согласен, хороший компилятор (как и его части), это и есть — конечный автомат.
          В том случае, если есть конкретно поставленный язык.
          Мое решение — больше подходит для динамического, быстрого описания языка, что может быть полезным, если библиотека языка, который используется в поставленной задаче, еще не был написан для веба ранее.
          0
          Согласен ( по поводу одной регулярки :) ), вы подали мне идею — перед парсингом, генерировать единую регулярку, используя ранее описанные группы.
          Тогда, можно стать на шаг ближе, к генерированию настраиваемого, конечного автомата.

            0
            github.com/angrycoding/regexp-lexer/blob/master/index.js вот посмотрите, мой вариант универсального токенайзера. Здесь пример использования: github.com/MegafonWebLab/histone-javascript/blob/master/src/parser/Parser.js

            Мне вот интересно, а что это за метод парсинга такой? Можно подробнее как то либо в комментариях, либо статьей. Я то просто использую рекурсивный спуск, остальное как то не зашло. Не врубился. А то что описали вы — выглядит интересно.
              0
              Если верить википедии, то у меня, тоже своего рода «Метод рекурсивного спуска»
              ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0
              А конкретнее, его реализация, под названием «Парсер с возвратом»

              Только у меня, если ни одно правило не применимо к токену, то он пропускается.
              По этому, он гарантирует завершение.

              В моей реализации, правила — это последовательности (токенов, других правил, конкретных значений)

              Например, у нас есть правило, определяющее «Определение переменной», оно состоит из последовательности токенов: Тип, Идентификатор, знак равно, значение, разделитель(например точка с запятой)

              Если проверяемый токен имеет тип — «Тип», то мы проверяем следующий токен на совпадение с типом — «Идентификатор».
              Если типы не сошлись, то мы пишем в стек ошибку «Unexpected Identificator» + место в source-map
              Если другое правило подошло к стартовому токену, то стек очищается, иначе в коллбэк улетает синтаксическая ошибка, т.к. у проверяемого токена, наиболее вероятный нетерминал — «Определение переменной»
          0
          Стесняюсь спросить, а если в строковую константу засунуть целое предложение, вы его тоже разобьёте на токены, выкинув пробелы между словами?
            0
            Не совсем :)
            Каждый токен хранит свой индекс начала и конца в исходном коде, результирующая строка будет взята с исходного кода, начиная от символа начала строки, заканчивая символом конца строки, при этом сохранив то же кол-во пробелов, табов и переносов строк, что были изначально.
              0

              Экранирование символов поддерживается? А экранирование экранирования?


              const a = ’ab\’cd’;
              const a = ’ab\’cd’;

                0
                На данный момент, только экранирование экранирования.

                const a = 'ab\\'cd';

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

          Самое читаемое