ЯП с нуля до прототипа (Лексер) #113.11.2022 00:02

Привет первая статья на хабре. Поправляйте если что-то не так.

UPD: Была переписана пока лежала в песочнице
UPD: И ещё разок

Предисловие

Идея написать свой ЯП появилась достаточно давно, но не хватало мотивации приступить к изучению. Отталкивало то, что крупные компании годами разрабатывают свои языки, чтобы они были работоспособны, а тут я хочу обойти их всех разом и создать удобный для себя ЯП. Но с чего--то всё таки нужно начинать. Хотя бы калькулятор уже бы был победой. Далее я буду называть свой язык программирования — Lize(читай «Лайз»).

Внимание: Я ничего не знаю про то как делать ЯП, я буду изучать всё и одновременно писать статью

Что делаем?

Это будет транспилятор из Lize в Typescript, написанный на … Typescript. Что касается будущего синтаксиса, то пока это опустим, вернёмся к этому когда будет достаточно знаний. В дополнение я буду публиковать весь код на github.

Первое же гугление дало мне знание о таких вещах как Лексер, Парсер, AST (Абстрактное синтаксическое дерево). Ничего не знаю про два последних, забудем пока про них и начнём с первого.

Что такое лексер?

Лексер — он же сканер, он же токенизатор. Первый этап преобразования простого текста который мы считаем за программу на нашем языке (Lize) в программу которую поймёт компьютер (но в нашем случае мы обойдёмся транспиляцией/переводом из нашего ЯП в TypeScript)

В моей голове это просто такая вещь которая превращает последовательность символов в последовательность подстрок имеющих некоторый id и значение.

Мы будем представлять его так: [имя: значение] или так: (строка:столбец;ширина) [имя: значение].

Стоит уточнить, что символ звёздочки или слэш ни в коем случае не должен считаться знаком умножения или деления. Этап токенизации должен просто разбить исходник на токены, а потом на этапе парсинга определять, это умножение или разыменование.

// ❌ Не правильно
tokenize(`4 * 3 / 2`) // [number: 4], [multiply], [number: 3], [divide], [number: 2]
// ✅ правильно
tokenize(`4 * 3 / 2`) // [number: 4], [asterisk], [number: 3], [slash], [number: 2]

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

Обработка ошибок

Мы же любим когда наш любимый ЯП тыкает нам носом туда где мы облажались. Давайте забудем про проблему ошибок раз и навсегда. Функция error это магия JS и TS, позволяет создавать ошибки в одну строчку. Я опустил реализацию, дабы не нагружать статью, весь код вы сможете посмотреть на github.

// Примеры ошибок
export namespace LexerErrors {
  export const SampleError = 
      error('SampleError', 'Sample error message')
  export const ErrorWithArgument = 
      error<[string]>('ErrorWithArgument', 'Argument: {}')
  export const UnexpectedCharacter = 
      error<[line: number, column: number]>('UnexpectedCharacter', 'Unexpected character at {}:{}')
}

// Пример
throw new SampleError
throw new ErrorWithArgument('hey')
throw new UnexpectedCharacter(1, 2)

Реализация лексера

Для начала разберёмся со структурой токена как объекта. У него будет имя/идентификатор по которому мы сможем его опознать, значение токена, если это например число или строка и его положение в исходном коде.

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

export class Span {
  constructor(
    private readonly src: string,
    readonly start: number,
    readonly end: number,
  ) {}

  get width() {
    return this.end - this.start
  }

  get line() {
    return (this.src.slice(0, this.start).match(/\n/g) || '').length
  }

  get column() {
    const lines = this.src.slice(0, this.start).split('\n')
    if(lines.length === 1) return this.start
    return this.start - lines.slice(0, lines.length - 1).join('\n').length - 1
  }
}

Ну, а теперь сам Token. В качестве идентификатора токена будет выступать сам класс, а точнее его имя. Например, чтобы проверить что некоторый токен это символ звёздочки, просто используйте token instanceof Asterisk

export class Token {
  constructor(readonly value: string, readonly span: Span) {}
}

// Тип конструктора пригодится позже
export type TokenKind = typeof Token

Добавим статический метод tokenize, который мы будем переопределять для каждого токена. Он будет искать токены, принимая строку исходного кода и возвращая длину токена. Если возвращённое число -1, будем считать, что токен найти не удалось. Мы не предполагаем, что Token будет инстансирован напрямую без наследования, поэтому кинем ошибку

static tokenize(src: string): number {
  throw new AbstractToken // Abstract token can't be used
}

Искать токены мы будем при помощи регулярных выражений, это невероятно просто и красиво. А чтобы проще и быстрей создавать виды токенов я решил написать билдер. Это может немного сбить с толку, но по сути это функция которая за нас реализует каждый класс токена.

// Пачка типов
type GroupString = string | RegExp
type GroupValue = GroupString | (() => GroupString)
type ConditionFn = () => boolean
type Subscriber = (result: number) => void

interface Condition {
  not?: boolean
  fn: ConditionFn
}

interface Group {
  value: GroupValue
  main?: boolean
  escape?: boolean
}

// "Макрос" для реализации видов токенов
export const kind = (name: string) => {
  const Class = namedClass(class extends Token {
    // Группы токенизации, по простому просто части одного
    // регулярного выражения
    private static readonly _groups: Group[] = []
    // Условия при соблюдении которых токен будет засчитываться
    private static readonly _conditions: Condition[] = []
    // Подписчики. Они будут вызваны если токен будет найден
    private static readonly _subscribers: Subscriber[] = []

    // Regex группа может быть вычислена
    // resolveGroup вернёт вычисленную группу,
    // если её можно вычислить
    private static resolveGroup(group: GroupValue) {
      return typeof group === 'function' ? group() : group
    }

    // Добавляем группу(ы)
    static group(...parts: GroupValue[]): typeof Class {
      Class._groups.push(...parts.map(value => ({ value })))
      return Class
    }

    // Устанавливаем главную группу,
    // ту, длину которой засчитает лексер
    static main(part: GroupValue): typeof Class {
      Class._groups.push({ value: part, main: true })
      return Class
    }

    // Добавляем разрешающее условие(я)
    static allow(...conditions: ConditionFn[]): typeof Class {
      Class._conditions.push(...conditions.map(fn => ({ fn })))
      return Class
    }

    // Добавляем запрещающее условие(я)
    static disallow(...conditions: ConditionFn[]): typeof Class {
      Class._conditions.push(...conditions.map(fn => ({ fn, not: true })))
      return Class
    }

    // Устанавливаем группу для последовательности символов
    static plain(text: GroupValue): typeof Class {
      Class._groups.push({ value: text, escape: true, main: true })
      return Class
    }

    // Добавляем подписчика
    static on(...subscriber: Subscriber[]): typeof Class {
      Class._subscribers.push(...subscriber)
      return Class
    }

    // Оповещаем подписчиков об успешной токенизации
    private static emit(value: number) {
      Class._subscribers.forEach(s => s(value))
    }

    // Компилируем все условия и получаем полное регулярное выражение
    // при соблюдении всех условий
    private static compile(doMatch = true): RegExp | undefined {
      // Собираем результаты условий
      for (const condition of this._conditions) {
        // Вычисляем результат
        let result = condition.fn()
        // Меняем на противоположный, если добавляли через
        // disallow
        if (condition.not) result = !result
        if (!result) {
          doMatch = false
          return
        }
      }
      // Формируем регулярное выражение
      return RegExp(`^${this._groups.map(g => {
        // Вычисляем группу
        const group = Class.resolveGroup(g.value)
        // Проверяем разные кейсы и в зависимости от этого
        // устанавливаем конечное значение группы
        const value = typeof group === 'object' ? group.source : g.escape ? escapeRegex(group) : group
        // оборачиваем группу
        return `(${value})`
      }).join('')}`)
    }

    // Прибавляем 1, поскольку метод match возвращает
    // всё совпадение, а потом группы.
    // И смотрите как удобно, если главной группы нет,
    // то берём всё, тк -1 + 1 = 0, а 0 это всё совпадение
    private static getMainIndex() {
      return Class._groups.findIndex(g => g.main === true) + 1
    }

    // Реализуем главный метод токенизации
    static tokenize(src: string) {
      // Компилируем выражение, если его нет, то пропускаем токен
      const regex = Class.compile()
      if (!regex) return -1
      // матчим строку
      const matches = src.match(regex)
      if (!matches) return -1
      // Берём главную группу
      const result: number = matches[Class.getMainIndex()].length
      // Оповещаем подписчиков об успешной находке
      if (result >= 0) Class.emit(result)
      // Возвращаем длину токена
      return result
    }
  }, name)
  return Class
}

Теперь можем приступить к созданию видов токенов. Начнём с чего-то простого. Токенизируем простое числовое выражение.

Вот какие виды токенов мы может тут найти: Число, Открывающая Круглая Скобка, Закрывающая Круглая Скобка, Звёздочка, Слэш и Пробел (да, мы его тоже считаем)

// scripts/1.ts
const src = `(2 * 3) / 6`

const Number = kind('Number').main(/\d+/)
const Asterisk = kind('Asterisk').plain('*')
const Slash = kind('Slash').plain('/')
const OpenParen = kind('OpenParen').plain('(')
const CloseParen = kind('CloseParen').plain(')')
const Whitespace = kind('Whitespace').main(/[^\S\r\n]+/)

Приступим к классу лексера. Я также буду использовать подход с использованием итератора, чтобы мы могли контролировать процесс.

export class Lexer {
  // Длина проанализированного текста
  private index = 0

  constructor(
    // Берём на вход исходник
    private src: string,
    // Виды(kinds) токенов
    private readonly kinds: TokenKind[],
  ) {}

  next() { /* ... */}

  // Реализуем итератор
  [Symbol.iterator]() {
    return {
      next: () => {
        return { done: this.done, value: this.next() }
      },
    }
  }

  // Вернуть true если всё токенизировали
  get done() {
    return this.index === this.src.length
  }
}

Реализуем метод next. Он будет перебирать виды токенов и подставлять в них строку исходника, если метод tokenize каждого вида токена не вернёт число больше -1, то кидаем ошибку: «Неожиданный токен» иначе возвращаем экземпляр токена.

next() {
  // Выполняем проход по всем видам токенов
  for (const kind of this.kinds) {
    // Токенизируем исходную строку начиная с this.index
    const result = kind.tokenize?.(this.src.slice(this.index)) ?? -1\
    // Если не нашли, то идём дальше
    if (result === -1) continue
    // возвращаем экземпляр токена и обновляем this.index
    return new kind(this.src.slice(this.index, this.index + result), new Span(this.src, this.index, this.index += result))
  }
  // Если ни один из токенов не дал о себе знать,
  // то мы наткнулись на неизвестную или неверную часть программы
  throw new UnexpectedToken
}

Добавим функцию для сбора всех токенов.

export const tokenize = (lexer: Lexer) => {
  const tokens: Token[] = []
  while (!lexer.done) tokens.push(lexer.next())
  return tokens
}

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

const kinds = [Number, Asterisk, Slash, OpenParen, CloseParen, Whitespace]

const result = tokenize(new Lexer(src, kinds))

// (0:0;1)  [OpenParen: (]
// (0:1;1)  [Number: 2]   
// (0:2;1)  [Whitespace: •]
// (0:3;1)  [Asterisk: *]
// (0:4;1)  [Whitespace: •]
// (0:5;1)  [Number: 3]
// (0:6;1)  [CloseParen: )]
// (0:7;1)  [Whitespace: •]
// (0:8;1)  [Slash: /]
// (0:9;1)  [Whitespace: •]
// (0:10;1) [Number: 6]

Производительность

console.time в среднем демонстрирует результат 0.3ms для выражения выше, однако первый старт занимает около 2.75ms. Не знаю хорошо это или не очень; в будущем попробуем тоже самое на rust и сравним производительность.

Заключение

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

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

Бонус

Токенизируем шаблонную строку

const src = "`I'm ${8 * 2}!`"

// Виды токенов. Мы не полностю реализуем поиск токенов,
// поскольку поиск некоторых из них будет зависеть от состояния лексера
const Plain = kind('Plain').main(/.+?/).group(/\${|}|`/)
const Asterisk = kind('Asterisk').plain('*')
const Number = kind('Number').main(/\d+/)
const Whitespace = kind('Whitespace').main(/[^\S\r\n]+/)
const Backtick = kind('Backtick').plain('`')
const OpenDollarBrace = kind('OpenDollarBrace').main(/\${/)
const CloseBrace = kind('CloseBrace').main(/}/)

// Расшиярем лексер, чтобы хранить собственное состояние
class CustomLexer extends Lexer {
  private template = false

  constructor(src: string) {
    // Реализуем алгоритмы поиска.

    // Обычный текст, ищем только если в состоянии шаблонной строки
    Plain.allow(() => this.template)
    // Символ шаблонной строки (`) если находим, то переключаем состояние
    Backtick.on(() => this.template = !this.template)
    // Начало шаблонного выражения, ищем если в состоянии шаблонной строки,
    // если находим, ВЫключаем режим шаблонной строки
    OpenDollarBrace
      .allow(() => this.template)
      .on(() => this.template = false)
    // Конец шаблонного выражения, ищем если НЕ в состоянии шаблонной строки
    // если находим, Включаем режим шаблонной строки
    CloseBrace
      .disallow(() => this.template)
      .on(() => this.template = true)
    // Тот случай когда порядок важен
    // Plain берёт любые символы и если он будет в начале, 
    // то просто "съест" начало шаблонного выражения
    super(src, [Backtick, OpenDollarBrace, CloseBrace, Asterisk, Number, Whitespace, Plain])
  }
}

Проверяем результат

const result = tokenize(new CustomLexer(src))

// (0:0;1)  [Backtick: `]
// (0:1;4)  [Plain: I'm•]
// (0:5;2)  [OpenDollarBrace: ${]
// (0:7;1)  [Number: 8]
// (0:8;1)  [Whitespace: •]
// (0:9;1)  [Asterisk: *]
// (0:10;1) [Whitespace: •]
// (0:11;1) [Number: 2]
// (0:12;1) [CloseBrace: }]
// (0:13;1) [Plain: !]
// (0:14;1) [Backtick: `]

А чё там с рекурсией?

const recursive = "`Hey ${`I'm recursive ${2 * 3}`}`"

Я прям потел когда смотрел на такую строку, но лексер сделал своё дело

(0:0;1)  [Backtick: `]
(0:1;4)  [Plain: Hey•]
(0:5;2)  [OpenDollarBrace: ${]
(0:7;1)  [Backtick: `]
(0:8;14) [Plain: I'm•recursive•]
(0:22;2) [OpenDollarBrace: ${]
(0:24;1) [Number: 2]
(0:25;1) [Whitespace: •]
(0:26;1) [Asterisk: *]
(0:27;1) [Whitespace: •]
(0:28;1) [Number: 3]
(0:29;1) [CloseBrace: }]
(0:30;1) [Backtick: `]
(0:31;1) [CloseBrace: }]
(0:32;1) [Backtick: `]

Спасибо что прочитали ВСЁ, ПРЯМ ВСЁ. Огромное спасибо. Буду очень рад оценке и комментарию.

© Habrahabr.ru