Простий вступ до компіляторів. Частина 1: лексичний аналіз і сканер

Моя подорож у світ компіляторів почалася, коли я спробував з’ясувати, як насправді працює компіляція Angular AOT, яка базується на статичному аналізі коду. Після деякого налагодження я дізнався, що він значною мірою покладається на компілятор TypeScript, тому квест почав його реверсивну інженерію. Що цікаво, так це те, що більшість компіляторів реалізовано з використанням тих самих принципів, загальновідомих як теорія компіляторів. Гарне розуміння цієї теорії є незамінним, якщо ви намагаєтесь зрозуміти внутрішні особливості компілятора.

Ця стаття є першою в серії, яка підсумовує все, про що я дізнався під час зворотного проектування компілятора TypeScript. Тут я опишу поняття, важливі для розуміння першого етапу кожного компілятора — лексичного аналізу. Стаття містить мінімальний мінімум теорії та формалізму, але вона все одно виявилася переважно теоретичною. В останньому розділі я покажу, як реалізовано сканер TypeScript, і надаю відповідні посилання.

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

Стаття досить об’ємна, тому її не можна читати за один раз. Прочитайте його по частинах і дайте час, щоб концепції осіли у вашій голові. Якщо ви завжди хотіли навчитися читати специфікацію ECMAScript або зрозуміти, як працює компілятор (сканер), ця стаття для вас.

Загальні етапи

Компілятори — це комп’ютерні програми, які перекладають програму, написану однією мовою, у програму іншою мовою. Компілятор повинен спочатку зрозуміти програму на вихідній мові, яку він приймає як вхідні дані, а потім зіставити її функціональні можливості з програмою на цільовій мові. Через різну природу цих двох завдань доцільно розділити функціональні можливості компілятора на два основні блоки: інтерфейс і бек-енд. Перший зосереджується на тому, щоб зрозуміти програму на вихідній мові, тоді як другий зосереджується на перетворенні її в програму на цільовій мові.

Кожен блок складається з послідовності кількох фаз, причому кожна стадія отримує вхідні дані від попередньої стадії, модифікує їх і створює власне представлення вихідної програми та передає її до наступної фази. Інтерфейс складається з трьох основних етапів, які називаються лексичним, синтаксичним і семантичним аналізом. На першому етапі вихідний код береться як потік символів і визначає окремі слова (токени), такі як імена змінних, ключові слова та знаки розділових знаків. На другому етапі визначається правильність синтаксичної організації програми та створюється абстрактне синтаксичне дерево (AST). Семантичний аналіз перевіряє, чи відповідає AST правилам мови (перевірка типу, розпізнавання імен).

Ця стаття присвячена першому етапу лексичного аналізу та його основному діючому сканеру символів, він же розпізнавач.

Формальні мови та граматика

Перш ніж перейти до реалізації сканера, важливо трохи поговорити про природні та формальні мови та їх граматику. Природні мови, такі як англійська чи французька, використовуються переважно для спілкування та еволюціонували природним шляхом. З іншого боку, формальні мови — це мови, розроблені людьми для конкретних застосувань — мови програмування для вираження обчислень, математичні записи для позначення зв’язків між числами тощо.

І природні, і формальні мови можуть бути описані граматикою. Граматика — це набір правил, які описують, як об’єднати послідовність символів, таких як символи, слова (лексеми) або речення (висловлювання), дійсні відповідно до синтаксису мови. Граматика природних мов неймовірно складна і відкривається шляхом емпіричного дослідження. З іншого боку, граматика формальних мов (формальна граматика) зазвичай досить проста і визначається так, як нам потрібно. Залежно від того, для якого типу символів ми хочемо визначити правила, ми можемо виділити кілька типів граматики.

Лексична граматика описує словниковий запас мови: лексеми, які можуть зустрічатися у вихідному коді. Наприклад, JavaScript використовує як \, так і d, але окрема послідовність \d не є дійсним маркером. Це може відбуватися всередині регулярного виразу або рядкового літералу; сам по собі він створює синтаксичну помилку:

\d
Uncaught SyntaxError: Invalid or unexpected token

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

var const
Uncaught SyntaxError: Unexpected token const

Це структурно незаконний оператор відповідно до синтаксичної граматики ECMAScript, тому компілятор не очікує, що маркер const слідуватиме за маркером var у операторі, який ми написали раніше. Також зверніть увагу на різницю в повідомленнях про помилку неочікувані та недійсні.

Лексичний розбір

Лексичний аналіз є першим етапом процесу з трьох частин, який використовує компілятор для розуміння вхідної програми. Роль лексичного аналізу полягає в тому, щоб розділити вихідний код програми на підрядки, які називаються лексемами, і класифікувати кожну лексему відповідно до її ролі (клас лексеми). Програма, яка виконує аналіз, називається сканером або лексичним аналізатором. Він зчитує потік символів і комбінує їх у лексеми за допомогою правил, визначених лексичною граматикою, яка також називається лексичною специфікацією. Якщо немає правил, які визначають певну послідовність символів, сканер повідомляє про помилку. Саме це сталося з нашим прикладом рядка \d, який спричинив синтаксичну помилку Invalid or unexpected token.

Сканер призначає категорію кожному розпізнаному маркеру. Перелік SyntaxKind TypeScript включає такі категорії, як Identifier, NumericLiteral, StringLiteral, ConstKeyword, LetKeyword і IfKeyword. Це назви реалізації; вони не відображають один до одного граматику ECMAScript.

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

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

Для категорій токенів, які використовує TypeScript, перегляньте перелік SyntaxKind, аж до коментаря // Parse tree nodes.

Лексичний аналізатор може бути реалізований для сканування всієї вихідної програми та отримання повної послідовності лексем або для виконання поступового сканування та розпізнавання однієї лексеми за раз. Сканер, який перетворює всю вихідну програму в масив токенів перед запуском аналізатора, є досить рідкісним, оскільки він марно споживає пам’ять. Таким чином, сканери зазвичай створюють токени лише за запитом синтаксичного аналізатора, що також стосується сканера 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'}

З let замість const першою категорією є SyntaxKind.LetKeyword. getTokenText() сканера повертає вихідний текст маркера. getTokenValue() повертає оброблене значення для підтримуваних типів токенів, наприклад рядок із інтерпретованими екранами; це не загальний засіб доступу до лексеми.

Звичайна граматика

Багато класів токенів можна описати звичайними мовами, найменш виразним класом в ієрархії Хомського. Цього достатньо для наведених нижче прикладів ідентифікатора та пунктуації, але не для довільно вкладеної структури програми. ECMAScript записує свої лексичні продукти у власній граматичній нотації; сама нотація не обмежена строго ліво- чи праволінійними правилами.

У наступній статті ми розглянемо контекстно-вільні граматики (тип 2), які можуть описувати вкладені структури програм. Необмежена та контекстно-залежна граматика є більш виразною, але загальний розбір для цих класів важчий. Тому синтаксис компілятора зазвичай описується за допомогою контекстно-вільних граматик плюс додаткові перевірки.

Більшість знайомств зі сканерами використовують регулярні вирази для визначення токенів. Тут ми використовуємо правила виробництва, щоб ви могли дотримуватися граматичної нотації 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 — це синтетична змінна, яка називається нетермінальним символом, що означає, що вона має виробництва та може бути замінена (процес заміни не завершується цим). Заміни зазвичай називають похідними. Продукти const і let, які має цей символ, називаються терміналами, оскільки вони не мають жодних похідних. Символи терміналу, які не мають жодних продукцій, є фактичними рядками, які можна знайти у вихідній програмі. Синтетичні нетермінальні символи використовуються в граматиці лише для визначення правил заміни та ніколи не розпізнаються у вихідній програмі як дійсні маркери. ECMAScript визначає багато інших продукцій для нетермінального символу Keyword, наприклад: if, else, for, do, while, function, class тощо.

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

non_terminal_symbol ::
  symbol1 symbol2  (production rule 1, Symbol1 followed by Symbol2)
  symbol3 symbol4  (production rule 2, Symbol3 followed by Symbol4)

Символ ліворуч від :: називається лівою стороною, а символ праворуч — правою стороною. Для звичайних і контекстно-вільних граматик ви можете мати лише нетермінальний символ у лівій частині правила виробництва. У правій частині можна вказати як термінали, так і нетермінали, однак звичайна граматика обмежена:

• тільки термінали
• або термінали та один нетермінал, який завжди знаходиться на початку (лінійний) або завжди в кінці (правий лінійний):

non_terminal_symbol ::
  terminal_symbol
non_terminal_symbol ::
  terminal_symbol non_terminal_symbol   (right-linear)
non_terminal_symbol ::
  non_terminal_symbol terminal_symbol   (left-linear)

Контекстно-вільна граматика є більш розслабленою та дозволяє будь-яку кількість терміналів і нетерміналів у правій частині. І RG, і CFG можуть мати будь-яку кількість чергувань (продукцій) для кожного лівого символу:

non_terminal_symbol ::
  production rule 1
  production rule 2
  ...
  production rule n

Існують також інші граматичні нотації, наприклад форма Бекуса–Наура (BNF), яка використовує такий синтаксис:

nonterminal_symbol ::= symbol1 | symbol2

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

Keyword ::= const | let

Інші альтернативні позначення замінюють ::= на ->, тому правило виглядає так:

Keyword -> const | let

У цьому відношенні ECMAScript використовує власний довільний формат, який пояснюється вище. Подробиці граматичної нотації описано в розділі Граматична нотація, і я настійно рекомендую його прочитати. Ось деякі важливі частини:

Символи терміналів … відображаються шрифтом фіксованої ширини, символи нетерміналів – курсивом… Одна або кілька альтернативних правих сторін для нетерміналу йдуть у наступних рядках… Визначення нетерміналу вводиться назвою нетермінала, після якої йде одна або більше двокрапок. ECMAScript використовує подвійну двокрапку для позначення лексичної граматики та одну двокрапку для синтаксичної граматики.

Застосування правил виробництва

Правило виробництва застосовується до символу шляхом заміни одного входження лівої частини правила виробництва правою частиною цього правила виробництва. Це трохи багатослівно, тому розглянемо приклад. Припустимо, ви хочете визначити мову зарезервованих слів. Граматика такої мови буде починатися з нетермінального символу ReservedWord. ECMAScript визначає для нього наступні версії:

ReservedWord ::
  Keyword
  FutureReservedWord
  NullLiteral
  BooleanLiteral

але давайте зараз обмежимося лише Keyword:

ReservedWord ::
  Keyword

Раніше ми визначили граматику для Keyword так:

Keyword ::
    const
    let

Замінюючи ReservedWord на Keyword, а потім вибираючи одну з його продукцій, наша спрощена граматика генерує const або let. Ця мова скінченна: вона містить два рядки. Граматики мов програмування зазвичай описують нескінченну кількість можливих програм, навіть якщо кожна окрема програма є кінцевою.

У нашій граматиці вище ReservedWord називається символом початку, оскільки це символ, з якого ми почали генерувати рядки. Граматика ECMAScript визначає кілька стартових символів і називає їх символами цілі. Пізніше в статті я поясню, чому це потрібно.

Процес, який дозволив нам почати з початкового символу ReservedWord і дійти до рядка const або let, називається виведенням. Похідний рядок для граматики — це послідовність застосування граматичних правил, яка перетворює початковий символ у рядок. Виведення доводить, що рядок належить до мови граматики. Наприклад, ми знаємо, що 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, які використовуються у відповідних позиціях назви ідентифікатора. Я не буду вдаватися в подробиці, але якщо вам цікаво, прочитайте Дійсні імена змінних JavaScript у 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
    IdentifierReference
    …
    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.

Цей спосіб специфікації граматики має особливу властивість: замінивши кожен нетермінал (окрім кореневого) його правою частиною, ви можете звести його до єдиного виробництва для кореня, лише з терміналами на правій стороні. Цей скорочений вираз можна легко перетворити на регулярний вираз (регулярний вираз). Наприклад, для IdentifierChars ми матимемо наступне:

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

Використання оператора повторення в регулярних граматичних правилах замість рекурсивних структур не є традиційним. Якщо граматику вказано за допомогою стандартної нотації з рекурсивними структурами, механічне перетворення граматики в регулярні вирази не є тривіальним: вам спочатку потрібно перетворити граматику в недетермінований кінцевий автомат (NFA, пояснення нижче), а потім перетворити NFA в регулярні вирази. Однак часто набагато легше придумати еквівалентний регулярний вираз, застосувавши «логічне мислення».

Як звичайна граматика, так і регулярний вираз можуть описувати послідовність символів, взятих із фіксованого набору, і можуть використовуватися як взаємозамінні. З цієї причини регулярні вирази зазвичай використовуються для визначення лексичної специфікації замість звичайної граматики. Наприклад, це стосується генераторів лексичних аналізаторів (сканерів), таких як Flex.

Кінцевий автомат

Окрім звичайної граматики та регулярних виразів, існує ще один спосіб визначення лексичної специфікації — кінцеві автомати (FA). Усі вони є просто трьома різними формалізмами для виконання принципово однакових речей — розпізнавання наборів символів. Основна причина того, що у нас є три способи зробити те саме, полягає в тому, що вони були розроблені незалежно. Однак FA надає найкращу розумову модель для опису реалізації сканера, і ми будемо використовувати її для цієї мети.

Автомат можна пояснити за допомогою посимвольного алгоритму розпізнавання слів. Припустимо, ми хочемо розпізнати маркер const. Нам потрібно написати код, який перевіряє c, потім o, потім n і так далі, доки ми не досягнемо останнього символу t. Якщо ми зобразимо кожен крок програми у вигляді діаграми переходів, ми матимемо такі стани.

Кожен автомат має стани, зображені у вигляді кіл на діаграмі. У цій статті я буду говорити лише про автомат, який має скінченну кількість станів (отже, скінченний автомат). Останній стан, позначений подвійною лінією, називається приймаючим станом. Автомат може мати будь-яку кількість приймаючих станів. Якщо після читання вхідних даних автомат потрапляє в стан прийняття, вхідні дані розпізнаються як дійсна послідовність символів.

Існує два типи скінченних автоматів — детермінований (DFA) і недетермінований (NFA). Найбільша різниця між ними полягає в тому, що для DFA кожен вхід унікально визначає стан, до якого потрібно перейти (отже, детермінований). Тоді як з NFA деякі вхідні дані можуть дозволити вибір результуючих станів (отже, недетермінованих).

Крім того, DFA може змінювати стан лише після читання вхідних даних, але NFA може бути побудований так, що він може змінювати стан на якийсь новий стан без читання будь-яких вхідних даних взагалі. Існують алгоритми для перетворення одного типу FA в інший. NFA і DFA еквівалентні за своєю виразною силою, і будь-який DFA є окремим випадком NFA.

Іноді сканер може стикатися з неоднозначною ситуацією. Ми знаємо, що будь-який із наведених нижче операторів =, /=, *=, += розпізнається як дійсний маркер, але як сканер дізнається, чи розпізнати рядок += як один маркер += чи як маркер +, за яким слідує маркер =? Цей вид неоднозначності вирішується за допомогою правила перемагає найдовший збіг, тому рядок += розпізнається як один маркер, який інтерпретується як оператор призначення додавання під час виконання.

Впровадження DFA

DFA може бути реалізований як керований таблицею або ручний кодований сканер. Табличні сканери зазвичай створюються спеціалізованими інструментами, такими як Flex. Оскільки за допомогою DFA кожен вхід унікально визначає стан, до якого потрібно перейти, і він ніколи не повертається назад, DFA є кращою моделлю для реалізації в створених сканерах. Звичайний процес складається з перетворення лексичної специфікації (звичайної граматики або регулярного виразу) на NFA, а потім NFA перетворюється на DFA.

TypeScript використовує рукописний сканер. Це дозволяє здійснювати конкретну оптимізацію без явного створення таблиці DFA. Згенерований сканер також може бути ефективним; продуктивність залежить від граматики та реалізації, а не від універсальної переваги рукописного коду.

Як керовані таблицею, так і сканери з ручним кодуванням функціонують подібним чином, емулюючи DFA. Вони неодноразово читають наступний символ у вхідних даних і емулюють перехід DFA, викликаний цим символом. Після зчитування введення сканер перевіряє, чи можливі переходи за допомогою введення. Якщо перехід знайдено, він виконується, і сканер переходить у новий стан. Якщо доступних переходів немає, сканер перевіряє, чи є поточний стан прийнятним. Якщо це так, сканер розпізнає слово та повертає лексему та її синтаксичну категорію до процедури виклику. В іншому випадку сканер визначає, чи пройшов він через стан прийняття на шляху до поточного стану. Якщо виявлено стан прийняття, сканер повертає свій внутрішній стан (поточну позицію символу) до цієї точки та повідомляє про успіх. В іншому випадку він повідомляє про помилку.

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

Реалізацію сканера TypeScript можна побачити у файлі scanner.ts. Основна логіка, яка емулює DFA шляхом читання вхідних даних і переходу до наступного стану, реалізована в методі scan. Суть реалізації полягає в нескінченному циклі while, який перевіряє вхідний символ, обробляє всі можливі переходи від цього символу, встановлює поточну позицію та повертає клас маркера, якщо його розпізнають:

let pos = 0;
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;
        ...

DFA дотримується одного шляху переходу, але сканер все ще може зберігати та відновлювати позиції або повторно сканувати маркер, коли аналізатор надає більше контексту. TypeScript використовує таке повторне сканування для конструкцій, включаючи літерали регулярних виразів.

Давайте розглянемо приклад. Серед іншого ECMAScript визначає наступні окремі знаки пунктуації:

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

Це правило можна легко перетворити на регулярні вирази:

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

Зауважте, що всі стани, за винятком початкового, є приймаючими. Це саме те, що говорять нам граматика та регулярні вирази.

TypeScript реалізує наведений вище DFA наступним чином:

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.minus:
    if (text.charCodeAt(pos + 1) === CharacterCodes.minus) {
        pos += 2;
        return token = SyntaxKind.MinusMinusToken;
    }
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        pos += 2
        return token = SyntaxKind.MinusEqualsToken;
    }
    pos++;
    return token = SyntaxKind.MinusToken;

Як ви можете бачити з реалізації TS і DFA, сканер намагається знайти найдовший із можливих рядків.

Обробка ключових слів

Ми вже бачили, що ECMAScript визначає такі ключові слова, як const, let, if у власній категорії Keyword. Одним із способів розпізнати їх було б визначити для них явний регулярний вираз і створити відповідні шляхи для DFA. Однак, оскільки ключові слова є підмножиною всіх ідентифікаторів, як визначено граматикою:

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 (компілятори)
• Інженерна справа: компілятор