Sep 5, 2024

Мягкое введение в компиляторы. Часть 1: лексический анализ и сканер

Моё путешествие в мир компиляторов началось, когда я попытался разобраться, как на самом деле работает AOT-компиляция в Angular, опирающаяся на статический анализ кода. После некоторой отладки я выяснил, что она сильно зависит от компилятора TypeScript, и тогда началась эпопея с его реверс-инжинирингом. Что интересно, большинство компиляторов реализованы на одних и тех же принципах, известных в совокупности как теория компиляторов. Хорошее владение этой теорией незаменимо при попытке понять внутреннее устройство компилятора.

Эта статья — первая в серии, которая обобщит всё, что я узнал, занимаясь реверс-инжинирингом компилятора TypeScript. Здесь я опишу концепции, важные для понимания первой стадии любого компилятора — лексического анализа. В статье лишь необходимый минимум теории и формализма, но она всё равно вышла в основном теоретической. В последней главе я показываю, как реализован сканер TypeScript, и даю нужные ссылки.

Грамматика TypeScript основана на спецификации ECMAScript (JavaScript), и я надеюсь, вам станет достаточно любопытно, чтобы пройти по ссылкам из статьи и познакомиться со спецификацией. Если вы это сделаете, то сможете понимать грамматику и изучать синтаксис будущих возможностей JavaScript задолго до того, как о них расскажут на MDN. Если вы дочитаете статью до конца, можете проверить себя, попробовав разобрать синтаксис декораторов, описанный в спецификации декораторов.

Статья довольно длинная и потому не рассчитана на чтение в один присест. Читайте её понемногу и дайте концепциям время улечься в голове. Если вы всегда хотели научиться читать спецификацию ECMAScript или понять, как работает компилятор (сканер), эта статья для вас.

Основные стадии

Компиляторы — это программы, которые переводят программу, написанную на одном языке, в программу на другом языке. Компилятор должен сначала понять программу на исходном языке, которую он получает на вход, а затем отобразить её функциональность в программу на целевом языке. Из-за разной природы этих двух задач имеет смысл разделить функциональность компилятора на два больших блока: front-end и back-end. Главная задача первого — понять программу на исходном языке, а второй сосредоточен на её преобразовании в программу на целевом языке.

Каждый блок состоит из последовательности нескольких фаз, где каждая стадия берёт входные данные от предыдущей, изменяет их, порождает собственное представление исходной программы и передаёт его следующей фазе. Front-end включает три основные стадии, называемые лексическим, синтаксическим и семантическим анализом. Первая фаза берёт исходный код как поток символов и выделяет отдельные слова (токены): имена переменных, ключевые слова и знаки пунктуации. Вторая фаза определяет корректность синтаксической организации программы и строит абстрактное синтаксическое дерево (AST). Семантический анализ проверяет, соответствует ли AST правилам языка (проверка типов, разрешение имён).

Эта статья посвящена первой стадии — лексическому анализу — и его главному действующему лицу, сканеру, он же распознаватель (recognizer).

Формальные языки и грамматика

Прежде чем перейти к реализации сканера, важно немного поговорить о естественных и формальных языках и их грамматиках. Естественные языки, вроде английского или французского, используются в основном для общения и развивались естественным путём. Формальные языки, напротив, создаются людьми для конкретных задач: языки программирования — чтобы выражать вычисления, математическая нотация — чтобы обозначать отношения между числами, и так далее.

И естественные, и формальные языки можно описать грамматикой. Грамматика — это набор правил, описывающих, как складывать последовательности символов: букв, слов (токенов) или предложений (инструкций), которые корректны с точки зрения синтаксиса языка. Грамматика естественных языков невероятно сложна и выясняется эмпирическим путём. Грамматика же формальных языков (формальная грамматика) обычно довольно проста и определяется так, как нам нужно. В зависимости от того, для какого типа символов мы хотим задавать правила, можно выделить несколько типов грамматики.

Лексическая грамматика описывает структуру словаря языка, то есть все токены (слова), которые можно использовать в языке. Например, в JavaScript и \, и d входят в алфавит языка, но грамматика не задаёт ни одного правила, по которому \, за которым сразу следует d, распознавался бы как корректный токен вне литерала регулярного выражения, поэтому если вы выполните такой код \d, то получите синтаксическую ошибку о некорректном токене:

\d
Uncaught SyntaxError: Invalid or unexpected token

Синтаксическая грамматика определяет структуру языка, то есть то, как токены (слова) могут располагаться, чтобы образовать инструкции (предложения). Например, лексическая грамматика JavaScript определяет два токена — var и const — но нет правила, гласящего, что за var может следовать const, поэтому если вы выполните такой код, то получите синтаксическую ошибку о неожидаемом токене:

var const
Uncaught SyntaxError: Unexpected token const

С точки зрения синтаксической грамматики ECMAScript это структурно недопустимая инструкция, и компилятор не ожидает, что токен const последует за токеном var в инструкции, которую мы написали выше. Обратите также внимание на разницу между unexpected (неожидаемый) и invalid (некорректный) в сообщениях об ошибках.

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

Лексический анализ — первая стадия трёхчастного процесса, с помощью которого компилятор понимает входную программу. Роль лексического анализа — разбить исходный код программы на подстроки, называемые токенами, и классифицировать каждый токен по его роли (классу токена). Программа, выполняющая этот анализ, называется сканером или лексическим анализатором. Она читает поток символов и складывает их в токены по правилам, заданным лексической грамматикой, которую также называют лексической спецификацией. Если правил, задающих конкретную последовательность символов, нет, сканер сообщает об ошибке. Именно это произошло с нашей строкой \d, породившей синтаксическую ошибку Invalid or unexpected token.

Каждому распознанному токену сканер присваивает синтаксическую категорию на основе грамматики. Список категорий, или классов токенов, для ECMAScript довольно обширен и содержит, среди прочего, такие классы, как Identifier, NumericLiteral и StringLiteral, а также различные ключевые слова вроде ConstKeyword, LetKeyword и IfKeyword.

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

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}

Если вам любопытно, какие токены определены в ECMAScript, посмотрите перечисление SyntaxKind (до комментария // Parse tree nodes) в реализации TypeScript.

Лексический анализатор можно реализовать так, чтобы он просканировал всю исходную программу и выдал полную последовательность токенов, или так, чтобы он сканировал постепенно и распознавал по одному токену за раз. Сканер, который превращает всю исходную программу в массив токенов до запуска парсера, встречается довольно редко, поскольку он напрасно расходует память. Поэтому сканеры обычно реализуют так, чтобы они выдавали токены только по запросу парсера, — так устроен и сканер TypeScript. Сканер TS интересен ещё и в другом отношении. Синтаксис JavaScript определяет несколько языковых конструкций, например регулярные выражения и шаблонные литералы, которые вносят неоднозначность при разборе, так что сканер может распознать разные наборы токенов в зависимости от контекста разбора. Поскольку этот контекст задаётся парсером при запросе токена, сканер TS в некотором смысле можно назвать управляемым парсером. Я объясню эту тонкость языка в разделе про несколько целевых символов.

Определение токенов

Возьмём знакомый случай объявления переменной в JavaScript, чтобы показать, как работают правила грамматики. В JavaScript мы можем объявить переменную через объявление const вот так:

const v = 3

Предположим для простоты, что инициализирующим значением может быть только числовой литерал. Глядя на исходный код, вы отчётливо видите слово const, объявляющее переменную v, оператор присваивания = и числовой литерал 3, используемый как инициализирующее значение переменной. Неудивительно, что сканер видит это иначе. Поскольку ECMAScript определяет исходный текст программы через символы Unicode, компилятор видит следующую последовательность кодовых точек:

c   o    n    s    t        v        =       3
99, 111, 110, 115, 116, 32, 118, 32, 61, 32, 51

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

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

А если бы вместо const было let, первым токеном был бы SyntaxKind.LetKeyword. Как только токен распознан, сканер сохраняет его значение (лексему) в свойстве tokenValue, к которому можно обратиться методом getTokenValue.

Регулярная грамматика

ECMAScript задаёт правила распознавания входного потока символов Unicode как токенов с помощью регулярной грамматики. Согласно классификации грамматик Хомского регулярная грамматика — самый ограниченный тип с наименьшей выразительной силой. Она годится только для описания того, как могут быть построены токены, но не может использоваться для описания структуры предложения. Однако чем больше ограничений на грамматику, тем легче её описывать и разбирать. А поскольку в этой главе нас интересует именно определение и разбор токенов, это идеально подходящая грамматика.

В следующей статье серии мы познакомимся с контекстно-свободной грамматикой (тип 2). Этот тип грамматики допускает рекурсивные конструкции и используется для определения структуры программы (инструкций). Остальные две категории грамматик из классификации Хомского — неограниченные и контекстно-зависимые грамматики — мощнее типов 2 и 3, но куда менее полезны, поскольку для них нельзя построить эффективные парсеры.

Важно отметить, что большинство учебных материалов не используют регулярную грамматику при объяснении сканеров, а вместо этого задают лексическую спецификацию через регулярные выражения. Однако, поскольку ECMAScript использует для этого именно регулярную грамматику, я буду объяснять на ней.

Знакомимся с грамматикой

Теперь попробуем посмотреть, как можно построить грамматику и правила, которые помогают TypeScript определить список токенов, показанный выше. Вот он снова — и нам нужно задать правила распознавания каждого токена в инструкции:

const v = 3
{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

Каждое правило в грамматике задаётся с помощью продукций (правил вывода). Продукция — это правило замены, задающее возможные подстановки, которые можно рекурсивно выполнять, чтобы порождать новые последовательности символов. В JavaScript мы можем объявить переменную либо токеном const, либо let, поэтому для символа Keyword можно задать такое правило:

Keyword ::
    const
    let

Правило для символа Keyword имеет две продукции, гласящие, что символ Keyword может быть заменён либо строкой const, либо let. Keyword — это искусственная переменная, называемая нетерминальным символом: у неё есть продукции и её можно заменять (процесс замен на ней не завершается). Замены обычно называют выводами (derivations). Продукции const и let, которые есть у этого символа, называются терминалами, потому что у них нет никаких выводов. Терминальные символы, у которых нет продукций, и есть те самые строки, которые можно встретить в исходной программе. Искусственные нетерминальные символы используются в грамматике только для задания правил замены и никогда не распознаются в исходной программе как корректные токены. ECMAScript определяет для нетерминального символа Keyword много других продукций, таких как if, else, for, do, while, function, class и т. д.

Для задания грамматики ECMAScript использует такую произвольную форму:

non_terminal_symbol ::
  symbol1 symbol2  (правило вывода 1: Symbol1, за которым идёт Symbol2)
  symbol3 symbol4  (правило вывода 2: Symbol3, за которым идёт Symbol4)

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

только терминалы,
либо терминалы и единственный нетерминал, который всегда стоит в начале (леволинейная) или всегда в конце (праволинейная):

non_terminal_symbol ::
  terminal_symbol
non_terminal_symbol ::
  terminal_symbol non_terminal_symbol   (праволинейная)
non_terminal_symbol ::
  non_terminal_symbol terminal_symbol   (леволинейная)

Контекстно-свободная грамматика свободнее и допускает любое число терминалов и нетерминалов в правой части. И РГ, и КСГ могут иметь любое число альтернатив (продукций) для каждого символа в левой части:

non_terminal_symbol ::
  правило вывода 1
  правило вывода 2
  ...
  правило вывода n

Существуют и другие нотации грамматик, например форма Бэкуса — Наура (BNF), которая использует такой синтаксис:

nonterminal_symbol ::= symbol1 | symbol2

так что наше правило грамматики для Keyword записывалось бы как:

Keyword ::= const | let

Другие альтернативные нотации заменяют ::= на ->, и тогда правило выглядит так:

Keyword -> const | let

В этом отношении ECMAScript использует свой собственный произвольный формат, объяснённый выше. Детали нотации грамматики описаны в разделе Grammar Notation, и я настоятельно рекомендую его прочитать. Вот некоторые важные части:

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

Применение правил вывода

Правило вывода применяется к символу заменой одного вхождения левой части этого правила на его правую часть. Звучит громоздко, поэтому давайте посмотрим на примере. Допустим, вы хотите определить язык зарезервированных слов. Грамматика такого языка начнётся с нетерминального символа ReservedWord. ECMAScript задаёт для него следующие продукции:

ReservedWord ::
  Keyword
  FutureReservedWord
  NullLiteral
  BooleanLiteral

но ограничимся пока только Keyword:

ReservedWord ::
  Keyword

Ранее мы задали грамматику для Keyword так:

Keyword ::
    const
    let

Итак, сначала заменив ReservedWord на Keyword, а затем заменив Keyword на его продукции, мы можем получить язык, в котором два слова — const и let. Такой язык мы назвали бы конечным, поскольку он может содержать максимум 2 разные строки. Все существующие языки бесконечны, потому что число комбинаций, которые они могут содержать, потенциально бесконечно. Скоро мы увидим, почему так происходит, когда посмотрим на грамматику идентификатора.

В нашей грамматике выше ReservedWord называется начальным символом, потому что именно с этого символа мы начали порождать строки. Грамматика ECMAScript определяет несколько начальных символов и называет их целевыми символами (goal symbols). Позже в статье я объясню, зачем это нужно.

Процесс, который позволил нам стартовать с начального символа ReservedWord и прийти к строке const или let, называется выводом (derivation). Вывод строки для грамматики — это последовательность применений правил грамматики, которая преобразует начальный символ в строку. Вывод доказывает, что строка принадлежит языку грамматики. Например, мы знаем, что const — корректное выражение, потому что ReservedWord можно раскрыть в Keyword, а каждый Keyword можно раскрыть в строку const или let.

Рекурсивная природа грамматики

Рекурсивную природу грамматики можно показать на именах переменных, которые в контексте компиляторов обычно называют идентификаторами. Как вы уже знаете, в нашем примере const v = 3 имя переменной v распознаётся как Identifier. Identifier определён в ECMAScript так:

Identifier ::
    IdentifierName but not ReservedWord

Это, по сути, говорит нам, что зарезервированные слова — подмножество IdentifierName, поэтому правила распознавания имён идентификаторов и зарезервированных слов одни и те же. Это значит, что как только сканер распознал IdentifierName, он должен отметить его как Identifier, если это не зарезервированное слово, иначе ему присваивается подходящий класс из категории ReservedWord. Именно это компилятор TypeScript и делает в функции getIdentifierToken. Список зарезервированных слов состоит в основном из ключевых слов вроде const, let, if, else, for и т. д., которые мы видели выше, плюс литералы null, true и false.

Так как же задать грамматику для IdentifierName? Вы, вероятно, знаете, что некоторые символы, например цифры, не могут стоять в начале имени переменной, тогда как само имя может содержать гораздо более широкий набор символов, включая цифры. Так что нужно отделить то, с чего имя может начинаться, от того, чем оно может продолжаться. Из-за этого грамматику нужно задавать двумя нетерминальными символами в последовательности:

IdentifierName ::
    IdentifierStart IdentifierPart

Важно, что и IdentifierStart, и IdentifierPart обозначают один символ из набора кодовых точек Unicode, используемых в соответствующих позициях имени идентификатора. Я не буду углубляться, но если вам любопытно — прочитайте Valid JavaScript variable names in ECMAScript 5. И поскольку и IdentifierStart, и IdentifierPart раскрываются в один символ из заданных алфавитов, определение выше гласит, что любое имя IdentifierName имеет длину два символа. А это не то, что нам нужно. Если вы посмотрите на грамматику ECMAScript, то увидите такое определение:

IdentifierName ::
    IdentifierStart
    IdentifierName IdentifierPart

Разберём его. Первая продукция гласит, что имя идентификатора может быть длиной один символ из набора символов, задаваемого IdentifierStart. Если вывести вторую продукцию рекурсивно несколько раз, вы увидите, что она может раскрыться в произвольно большое число символов, начинающееся с IdentifierStart и продолжающееся IdentifierPart:

IdentifierStart IdentifierPart IdentifierPart … IdentifierPart

Вот тут-то рекурсия и оказывается кстати. Рекурсивно заменяя IdentifierName второй продукцией IdentifierName IdentifierPart, мы можем сопоставить строку любой длины.

Любопытно, что некоторые нотации грамматик вводят нестандартные операторы повторения, такие как * или {…}, что дало бы такую грамматику:

IdentifierName ::
    IdentifierStart IdentifierPart*

IdentifierName ::
    IdentifierStart {IdentifierPart}

Роль пробельных символов

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

newObject
{class: SyntaxKind.Identifier, lexeme: 'newObject'}

Здесь newObject получает категорию Identifier. Это происходит за счёт рекурсивного вывода продукции IdentifierPart, как мы видели выше, и поскольку каждый символ в слове newObject попадает в набор символов, заданный для символа IdentifierPart, сканер распознаёт всю строку как один единственный токен. Вот другой пример:

new Object
{class: SyntaxKind.NewKeyword, lexeme: 'new'}
{class: SyntaxKind.Identifier, lexeme: 'Object'}

Теперь, хотя символы те же, они разбираются как два отдельных токена из-за наличия пробела. Сканер способен разделить токены, потому что при выводе продукций IdentifierPart он не признаёт пробел допустимым символом для IdentifierPart и выдаёт токен IdentifierName с лексемой new длиной 3 символа. Затем он ищет токен new в списках ключевых слов и помечает его как NewKeyword (этот поиск я объясню позже).

В других случаях разделить токены помогают символы вроде (, которые нельзя использовать как IdentifierPart:

if(s=3){...}
IfKeyword OpenParenToken ...

Пробельные символы также упоминаются как отдельный класс токенов для целевого символа InputElementDiv:

InputElementDiv::
    WhiteSpace
    LineTerminator
    ...

Задание правил для операторов присваивания и числовых литералов

Я показал, как задаётся грамматика для ключевого слова const и идентификатора v. Теперь осталось только задать правила для знака равенства и числа 3:

ConstToken Identifier = 3

Знак равенства — это то, чем мы в JavaScript присваиваем значение переменной. Есть много других операторов присваивания, и все они удобно сгруппированы под символом AssignmentOperator:

AssignmentOperator : one of
    *= /= %= += -= <<= >>= >>>= &= ^= |= **=

И последняя деталь — число 3. В JavaScript числа можно записывать во множестве форм: десятичный литерал с дробной частью 1.58, двоичный 0b11 или шестнадцатеричный 0x11 литералы, экспоненциальная форма 5e2 и так далее. Имеет смысл сгруппировать всё это под символом NumericLiteral:

NumericLiteral::
  DecimalLiteral
  BinaryIntegerLiteral
  OctalIntegerLiteral
  HexIntegerLiteral

Все они — нетерминальные символы. По ссылкам можно проследить продукции каждого нетерминала вплоть до терминальных символов.

Несколько целевых символов

Исследуя процесс вывода, мы узнали, что он начинается с целевого (начального) символа. И вот здесь лексическая грамматика ECMAScript становится сложной, поскольку она определяет несколько целевых символов. Рассмотрим такой фрагмент кода:

/foo/g

Если сканер ECMAScript начнёт выводить эту инструкцию, используя основной целевой (начальный) символ InputElementDiv со следующими правилами вывода:

InputElementDiv ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    DivPunctuator
    RightBracePunctuator

он распознает такой поток токенов:

/             foo            /             g
DivPunctuator IdentifierName DivPunctuator IdentifierName

Однако если вы достаточно долго программировали на JS, то знаете, что /foo/g — это литерал регулярного выражения. Значит, он должен быть распознан как один токен RegularExpressionLiteral по такому правилу грамматики:

RegularExpressionLiteral ::
    / RegularExpressionBody / RegularExpressionFlags

У базового целевого символа InputElementDiv нет выводов, которые могли бы привести сканер к символу RegularExpressionLiteral. Поэтому нам нужно определить новый целевой символ InputElementRegExp с продукцией для литерала регулярного выражения:

InputElementRegExp ::
    WhiteSpace
    ...
    RegularExpressionLiteral

С этим целевым символом сканер правильно распознает /foo/g как RegularExpressionLiteral. Но теперь вы можете спросить: а как сканер узнаёт, какой целевой символ использовать при разборе токена? Как я упоминал ранее в статье, целевой символ (контекст) задаётся парсером. Парсер запрашивает у сканера токены один за другим, и если текущий контекст разбора допускает использование целевого символа InputElementRegExp, парсер просит сканер распознавать токены с этим целевым символом.

Например, предположим, что парсер сейчас разбирает PrimaryExpression, у которого такая грамматика:

PrimaryExpression :
    this
    IdentifierLiteral
    …
    RegularExpressionLiteral

Грамматика гласит, что литерал регулярного выражения может быть выведен из первичного выражения, поэтому парсер задаёт целевой символ InputElementRegExp для сканера. Компилятор TypeScript реализован так, что он пересканирует текущий токен, если обнаруживает, что текущий контекст допускает целевые символы, отличные от основного InputElementDiv. ECMAScript определяет и несколько других целевых символов — чтобы узнать о них больше, посмотрите этот отличный ответ на StackOverflow.

Регулярные выражения

Иногда лексическая грамматика задаётся с помощью оператора повторения вместо рекурсии. Например, вот как грамматика Java 8 определяет символ IdentifierChars, эквивалентный символу IdentifierName с рекурсивными продукциями в ECMAScript:

IdentifierChars:
    JavaLetter {JavaLetterOrDigit}
JavaLetter:
    any Unicode character that is a "Java letter"
JavaLetterOrDigit:
    any Unicode character that is a "Java letter-or-digit"

Фигурные скобки вокруг JavaLetterOrDigit — это нотация повторения, как объяснено в документе по грамматике:

Синтаксис {x} в правой части продукции обозначает ноль или более вхождений x.

У такого способа задания грамматики есть особое свойство: подставляя вместо каждого нетерминала (кроме корневого) его правую часть, вы можете свести её к единственной продукции для корня, где справа стоят только терминалы. Такое сведённое выражение затем легко преобразуется в регулярное выражение (regex). Например, для IdentifierChars мы получили бы следующее:

[range of Java letter][range of Java letter-or-digit]*

Использование оператора повторения в правилах регулярной грамматики вместо рекурсивных конструкций не является общепринятым. Если грамматика задана стандартной нотацией с рекурсивными конструкциями, механическое преобразование грамматики в регулярные выражения нетривиально: сначала нужно преобразовать грамматику в недетерминированный конечный автомат (НКА, объясняется ниже), а затем НКА — в регулярные выражения. Однако зачастую куда проще придумать эквивалентное регулярное выражение, применив «логическое мышление».

И регулярная грамматика, и регулярное выражение могут описывать последовательность символов, взятых из фиксированного набора, и взаимозаменяемы. По этой причине регулярные выражения повсеместно используются для задания лексической спецификации вместо регулярной грамматики. Например, так поступают генераторы лексических анализаторов (сканеров), такие как Flex.

Конечный автомат

Помимо регулярной грамматики и регулярных выражений есть ещё один способ задания лексической спецификации — конечные автоматы (КА). Все они — просто три разных формализма, делающих по сути одно и то же: распознающих наборы символов. Главная причина, по которой у нас есть три способа делать одно и то же, в том, что они разрабатывались независимо. КА, однако, даёт лучшую мысленную модель для описания реализации сканера, и мы будем использовать его именно для этого.

Автомат можно объяснить через алгоритм посимвольного распознавания слов. Допустим, мы хотим распознать токен const. Нам нужно написать код, который проверяет c, за которым идёт o, за которым n, и так далее до последнего символа t. Если изобразить каждый шаг программы как диаграмму переходов, мы получим следующие состояния.

диаграмма переходов ДКА для распознавания ключевого слова const

У каждого автомата есть состояния, изображённые на диаграмме кружками. В этой статье я буду говорить только об автомате, у которого конечное число состояний (отсюда и конечный автомат). Последнее состояние, отмеченное двойной линией, называется принимающим состоянием. У автомата может быть любое число принимающих состояний. Если после чтения входных данных автомат оказывается в принимающем состоянии, вход распознаётся как корректная последовательность символов.

Есть два типа конечных автоматов — детерминированный (ДКА) и недетерминированный (НКА). Главное различие между ними в том, что у ДКА каждый вход однозначно определяет состояние, в которое нужно перейти (отсюда «детерминированный»). Тогда как у НКА некоторые входы могут допускать выбор из нескольких результирующих состояний (отсюда «недетерминированный»).

Кроме того, ДКА может менять состояние только после чтения входа, а НКА можно построить так, что он сможет перейти в некоторое новое состояние вообще без чтения входа. Существуют алгоритмы преобразования одного типа КА в другой. НКА и ДКА эквивалентны по выразительной силе, и любой ДКА — частный случай НКА.

Иногда сканер может попасть в неоднозначную ситуацию. Мы знаем, что любой из операторов =, /=, *=, += распознаётся как корректный токен, но как сканер узнаёт, распознавать ли строку += как один токен += или как токен +, за которым идёт токен =? Такая неоднозначность разрешается правилом побеждает самое длинное совпадение, так что строка += распознаётся как один токен, интерпретируемый во время выполнения как оператор присваивания со сложением.

Реализация ДКА

ДКА можно реализовать как табличный или как написанный вручную сканер. Табличные сканеры обычно порождаются специализированными инструментами вроде Flex. Поскольку у ДКА каждый вход однозначно определяет состояние перехода и он никогда не откатывается назад, ДКА — предпочтительная модель для реализации в порождаемых сканерах. Обычный процесс состоит в преобразовании лексической спецификации (регулярной грамматики или регулярного выражения) в НКА, а затем НКА преобразуется в ДКА.

схема процесса: лексическая спецификация → НКА → ДКА → реализация

Однако большинство коммерческих и open-source компиляторов используют написанные вручную сканеры. Такой сканер быстрее порождаемого, потому что при реализации можно убрать некоторые накладные расходы, неизбежные в порождаемом сканере. Именно такой тип сканера реализован в компиляторе TypeScript. При написании сканера вручную обычно нет нужды в явном преобразовании грамматики/regex в ДКА, поскольку алгоритм сканирования можно реализовать вручную прямо по лексической спецификации. Такая рукописная реализация естественным образом начинает работать как ДКА.

И табличные, и рукописные сканеры работают похожим образом, эмулируя ДКА. Они многократно читают следующий символ на входе и эмулируют переход ДКА, вызванный этим символом. После чтения входа сканер проверяет, есть ли возможные переходы по этому входу. Если переход найден, он выполняется, и сканер оказывается в новом состоянии. Если доступных переходов нет, сканер проверяет, является ли текущее состояние принимающим. Если так, сканер распознаёт слово и возвращает лексему и её синтаксическую категорию вызывающей процедуре. Иначе сканер определяет, проходил ли он через принимающее состояние по пути к текущему. Если принимающее состояние встречалось, сканер откатывает своё внутреннее состояние (текущую позицию символа) к той точке и сообщает об успехе. Иначе он сообщает об ошибке.

Реализация сканера в TypeScript

Реализацию сканера TypeScript можно посмотреть в файле scanner.ts. Основная логика, эмулирующая ДКА чтением входа и переходом в следующее состояние, реализована в методе scan. Суть реализации — бесконечный цикл while, который проверяет входной символ, обрабатывает все возможные переходы по этому символу, устанавливает текущую позицию и возвращает класс токена, если тот распознан:

const pos;
while (true) {
    tokenPos = pos;
    if (pos >= end) {
        return token = SyntaxKind.EndOfFileToken;
    }
    let ch = text.charCodeAt(pos);
    switch(ch) {
        case CharacterCodes.exclamation:
            ...
            pos++;
            return token = SyntaxKind.ExclamationToken;
        case CharacterCodes.openParen:
            ...
            pos++;
            return token = SyntaxKind.OpenParenToken;
        ...

Поскольку он эмулирует ДКА, сканер никогда не откатывается назад.

Посмотрим на примере. ECMAScript, среди прочего, определяет такие отдельные знаки пунктуации:

Punctuator ::
    !  !=  !==  -  --  -=

Это правило легко преобразуется в регулярные выражения:

/!==|!=|!|--|-=|-/

ДКА для знаков пунктуации: !, !=, !==, -, --, -=

Обратите внимание, что все состояния, кроме начального, — принимающие. Именно это нам и говорят грамматика и регулярное выражение.

TypeScript реализует показанный выше ДКА так:

case CharacterCodes.exclamation:
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        if (text.charCodeAt(pos + 2) === CharacterCodes.equals) {
            pos += 3;
            return token = SyntaxKind.ExclamationEqualsEqualsToken;
        }
        pos += 2
        return token = SyntaxKind.ExclamationEqualsToken;
    }
    pos++;
    return token = SyntaxKind.ExclamationToken;
case CharacterCodes.plus:
    if (text.charCodeAt(pos + 1) === CharacterCodes.plus) {
        pos += 2;
        return token = SyntaxKind.PlusPlusToken;
    }
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        pos += 2
        return token = SyntaxKind.PlusEqualsToken;
    }
    pos++;
    return token = SyntaxKind.PlusToken;

Как видно из реализации TS и из ДКА, сканер старается сопоставить самую длинную возможную строку.

Обработка ключевых слов

Мы уже видели, что ECMAScript определяет ключевые слова вроде const, let, if в отдельной категории Keyword. Один способ их распознавать — задать для них явное регулярное выражение и сгенерировать соответствующие пути в ДКА. Однако, поскольку ключевые слова — подмножество всех идентификаторов, как задано грамматикой:

Identifier:
    IdentifierName but not ReservedWord

есть альтернативная стратегия — классифицировать ключевые слова как идентификаторы и проверять, является ли идентификатор ключевым словом. Именно этот подход и использует сканер TypeScript. Он держит все ключевые слова вместе с другими литеральными токенами в отображении textToToken, и как только идентификатор распознан, использует это отображение, чтобы получить корректный класс токена, который может оказаться, а может и не оказаться ключевым словом:

default:
    if (isIdentifierStart(ch, languageVersion)) {
        pos++;
        while (isIdentifierPart(ch = text.charCodeAt(pos))) pos++;
        tokenValue = text.substring(tokenPos, pos);
        return token = getIdentifierToken();
    }

function getIdentifierToken(): SyntaxKind {
    if (...) {
        return token = textToToken.get(tokenValue);
    }
    return token = SyntaxKind.Identifier;
}

Хотите узнать больше?

Я пишу вторую часть, в которой разбираю теорию контекстно-свободных грамматик, построение AST и алгоритмы реализации парсера. Эта вторая часть покажет, как реализован парсер TypeScript и какие алгоритмы он использует.

А вот несколько очень хороших источников, которые я рекомендую, чтобы получить больше информации по темам, объяснённым здесь:

Stanford CS143 (Compilers)
Engineering: A Compiler