Лексичний аналіз
Лексичний розбір — це процес перетворення послідовності символів в послідовність токенів (груп символів що відповідають певним шаблонам), та визначення їх типів. Програма, чи функція що виконує лексичний аналіз, називається лексичним аналізатором, токенізатором[1] чи сканером. Часто сканер є звичайною функцією що використовується парсером (синтаксичним аналізатором), для отримання наступного токена з потоку вхідних символів в процесі компіляції. Також часто лексичний аналіз використовують для підсвітки синтаксису певних мов.
Лексичний аналізатор формує першу фазу аналізу коду, що відбувається під час початкової стадії компіляції. Аналіз зазвичай відбувається за один прохід.
У старих мовах, таких як ALGOL, початкова стадія була замість реконструкції рядків, яка виконувала згортання[en] та видалення пробілів і коментарів (та мала парсери без сканерів, без окремих лексичних аналізаторів). Ці кроки зараз виконуються як частина лексичного аналізатора.
Лексичні аналізатори та парсери найчастіше використовуються для компіляторів, але можуть використовуватися для інших мовних засобів, таких як лінтерів. Лексичний аналіз можна розділити на два етапи: сканування, яке сегментує вхідний рядок у синтаксичні одиниці, які називаються лексемами, та класифікує їх у класи токенів; та обчислення, яке перетворює лексеми в оброблені значення.
Лексичні аналізатори, як правило, досить прості, причому більша частина складності відкладена на фази парсера або семантичного аналізу, та можуть бути згенеровані генераторами лексичних аналізаторів, особливо за допомогою lex[en], або похідних. Однак, лексичні аналізатори можуть іноді мати деяку складність, таку як обробка структури фрази, щоб полегшити вхідні дані, та спростити парсер, та можуть бути написані частково, або повністю, вручну, або для підтримки більшої кількості функцій, або для більшої продуктивності.
Лексичний розбирач є скінченним автоматом, перехід в певні стани якого викликає функції, які зазвичай повертають тип лексеми, і саму лексему (токен).
Токен[2] — це рядок літералів, впорядкованих відповідно до правил (наприклад, IDENTIFIER, NUMBER, COMMA). Процес утворення позначок з вихідного потоку називається видобуванням позначок (англ. tokenization) і розбирач впорядковує їх за відповідними типами. Лексичний аналізатор зазвичай нічого не робить з об'єднаннями позначок, це завдання припадає на синтаксичний аналізатор. Наприклад, типовий сканер розпізнає дужки як позначки, але саме синтаксичний аналізатор перевіряє відповідність '(' і ')' дужок.
Припустімо наступний вираз на C:
sum=3+2;
Переводиться в таку таблицю:
| Lexeme | Token type |
|---|---|
| sum | Утотожнювач |
| = | Оператор надання значення |
| 3 | Число |
| + | Оператор додавання |
| 2 | Число |
| ; | Завершення твердження |
Позначки часто визначаються за допомогою регулярних виразів, що зрозумілі генераторам лексичних розбирачів таким як lex. Лексичний розбирач (чи створений автоматично приладдям на кшталт lex або вручну) читає потік символів, визначає лексеми в потоці, і впорядковує їх як позначки.[3][4] Це називається «видобуванням позначок». Якщо розбирач натрапляє на непридатну позначку, він звітує про помилку.
Наступним кроком іде синтаксичний розбір. Звідти, витрактовані дані можуть бути завантажені в структури даних для загального використання, інтерпретації, компіляції.
Специфікація мови програмування часто містить набір правил, лексичну граматику[en], що визначає лексичний синтаксис. Лексичний синтаксис зазвичай є регулярною мовою, граматичні правила складаються з регулярних виразів; вони визначають набір можливих послідовностей символів (лексеми) токена. Лексичний аналізатор розпізнає рядки, та для кожного рядка, знайденого лексичною програмою, вирішує як обробити, найчастіше просто створюється токен.
Дві важливі загальні лексичні категорії — це пробіл[en] і коментарі. Вони також визначаються в граматиці і обробляються лексичним аналізатором, але можуть бути відкинуті (не виробляючи жодних токенів) та вважатися незначними, не більше, ніж розділення двох токенів (як у випадку if x замість ifx). Існують два важливі винятки з цього приводу. По-перше, у мовах, що дотримуються правила офсайду[en], які розмежовують блоки з відступами, початковий пробіл є значним, оскільки він визначає структуру блоків і, як правило, обробляється на рівні лексичного аналізатора. По-друге, в деяких випадках використання лексичних аналізаторів, коментарі та пробіли мають бути збережені — наприклад, деякі інструменти зневадження можуть надавати програмісту повідомлення, що показують вихідний код. У 1960-х роках, особливо для ALGOL, пробіли та коментарі були усунені як частина фази реконструкції рядків (початкова фаза аналізу кода, що виконує компілятор), але ця окрема фаза була усунена, і тепер вони обробляються лексичним аналізатором.
Токенізація — це процес розмежування та, можливо, класифікації секцій рядка вхідних символів. Потім отримані токени передаються іншій формі обробки. Процес можна розглядати як підзадачу парсингу вхідних даних.
(Примітка: Токенізація[en] в області комп'ютерної безпеки має інше значення.)
Наприклад, у рядку:
The quick brown fox jumps over the lazy dog
рядок не є неявно сегментованим на пробіли, як це зробить людина, котра спілкується звичайною мовою. Вхідні дані, 43 символи, повинні бути явно розділені на 9 токенів з даним розділювачем (тобто, відповідним до рядка " " або регулярному виразу /\s{1}/).
Ці токени можуть бути представлені в XML:
<sentence>
<word>The</word>
<word>quick</word>
<word>brown</word>
<word>fox</word>
<word>jumps</word>
<word>over</word>
<word>the</word>
<word>lazy</word>
<word>dog</word>
</sentence>
Або як s-вираз:
(sentence
(word The)
(word quick)
(word brown)
(word fox)
(word jumps)
(word over)
(word the)
(word lazy)
(word dog))
Коли клас токенів представляє більше ніж одну лексему, лексичний аналізатор часто зберігає достатню кількість інформації, щоб відтворити оригінальну лексему, щоб її можна було використовувати у семантичному аналізі. Парсер зазвичай отримує цю інформацію від лексичного аналізатора та зберігає її в абстрактному синтаксичному дереві. Це необхідно для того, щоб уникнути втрати інформації у випадку чисел та ідентифікаторів.
Токени ідентифікуються на основі конкретних правил лексичного аналізатора. Деякі методи, які використовуються для ідентифікації токенів, містять: регулярні вирази, спеціальні послідовності символів, які називаються флагом[en], спеціальні розділювальні символи, що називаються роздільниками та явно визначені за словником. Спеціальні символи, включаючи символи пунктуації, зазвичай використовуються лексичними аналізаторами для ідентифікації токенів через їх природне використання у письмових мовах та мовах програмування.
Токени часто класифікуються за вмістом символів або за контекстом у потоці даних. Категорії визначаються правилами лексичного аналізатора. Вони часто включають елементи граматики мови, що використовується в потоці даних. Мови програмування часто класифікують токени як ідентифікатори, оператори, символи групування або тип даних. Письмові мови зазвичай класифікують токени як іменники, дієслова, прикметники або знаки пунктуації. Категорії використовуються для подальшої обробки токенів або парсером, або іншими функціями у програмі.
Взагалі, лексичний аналізатор нічого не робить з комбінаціями токенів, ця задача залишається парсеру. Наприклад, типовий лексичний аналізатор розпізнає дужки як токени, але нічого не робить для того, щоб кожна «(» відповідала «)».
Коли лексичний аналізатор подає токени парсеру, він зазвичай представляє їх як перелічений список числових представлень. Наприклад, «Ідентифікатор» представлений як 0, «Оператор присвоєння» як 1, «Оператор додавання» як 2, і т. д.
Токени часто визначаються регулярними виразами, які розуміють генератори лексичних аналізаторів, такі як Lex[en]. Лексичний аналізатор (згенерований автоматично інструментом, подібним до lex, або написаний вручну) читає в потік символів, ідентифікує лексеми в потоці і класифікує їх у токени. Це називається токенізацією. Якщо лексичний аналізатор знаходить невірний токен, він повідомить про помилку. Наступним за токенізацією проводиться парсинг. Починаючи звідси, інтерпретовані дані можуть бути завантажені в структури даних для загального використання, інтерпретації або компіляції.
Перший етап, його називають сканером, зазвичай базується на скінченному автоматі. В ньому закодована інформація про можливі послідовності символів, які можуть міститися в будь-якому з токенів, які він обробляє (окремі екземпляри цих послідовностей символів називаються лексемами). Наприклад, цілочисельний токен може містити будь-яку послідовність цифрових символів. У багатьох випадках перший символ, що не є пробілом, може бути використаний для виведення наступного токена, далі наступні вхідні символи обробляються один за одним до досягнення символу, який не знаходиться в наборі символів, прийнятих для цього токена. У деяких мовах правила створення лексем є більш складними і можуть включати пошук з вертанням попередньо прочитаних символів. Наприклад, у C одного символу 'L' недостатньо, щоб відрізнити ідентифікатор, який починається з 'L', від рядкового літералу[en], який є послідовністю символів.
Лексема, однак, є лише рядком символів, відомих як певний тип (наприклад, строковий літерал, послідовність букв). Для того, щоб побудувати токен, лексичний аналізатор потребує другий етап, — оцінювання, який проходить по всім символам лексеми, щоб отримати значення. Тип лексеми в поєднанні з його значенням — це те, що правильно становить токен, який може бути наданий синтаксичному аналізатору. Деякі токени, такі як дужки, насправді не мають значень, і тому функція оцінювання для них може нічого не повертати: потрібний лише тип. Аналогічно, іноді оцінювачі можуть повністю приховати лексему від синтаксичного аналізатора, що є корисним для пробілів і коментарів. Оцінювачі для ідентифікаторів, як правило, прості (буквально представляють ідентифікатор), але можуть містити деяке згортання[en]. Оцінювачі цілочисельних літералів[en] можуть передавати рядок (відкладаючи оцінювання до фази семантичного аналізу), або можуть виконувати оцінювання власноруч, яке може бути залучено для різних основ або чисел з рухомою комою. Для простого літералу у лапках оцінювач має видалити лише лапки, але оцінювач для екранованого строкового літералу[en] містить лексичний аналізатор, який скасовує екранування послідовності.
Наприклад, у вихідному коді комп'ютерної програми, рядок
net_worth_future = (assets - liabilities);
може бути перетворений у наступний лексичний потік токенів; пробіли відхиляються, а спеціальні символи не мають значення:
IDENTIFIER net_worth_future EQUALS OPEN_PARENTHESIS IDENTIFIER assets MINUS IDENTIFIER liabilities CLOSE_PARENTHESIS SEMICOLON
У зв'язку з обмеженнями ліцензування існуючих парсерів, може виникнути необхідність створити лексичний аналізатор самостійно. Це можливо, якщо список токенів невеликий, але в цілому, лексичні аналізатори генеруються за допомогою автоматизованих інструментів. Ці інструменти зазвичай приймають регулярні вирази, які описують токени, дозволені у вхідному потоці. Кожен регулярний вираз пов'язаний з правилом виводу у лексичній граматиці мови програмування, яка оцінює лексеми, що відповідають регулярному виразу. Ці інструменти можуть генерувати вихідний код, який можна скомпілювати і виконати або побудувати таблицю переходів станів для кінцевого автомата (який підключений до коду шаблона для компіляції та виконання).
Регулярні вирази компактно зображують шаблони, за якими можуть слідувати символи в лексемах. Наприклад, для мови, що базується на англійський, токен IDENTIFIER може бути будь-яким англійським алфавітним символом або символом підкреслення, за яким слідує будь-яке число екземплярів ASCII символів та/або підкреслення. Це може бути компактно представлено рядком [a-zA-Z_][a-zA-Z_0-9]*. Це означає «будь-який символ a-z, A-Z або _, за яким слідує 0 або більше a-z, A-Z, _ або 0-9».
- ↑ Anatomy of a Compiler and The Tokenizer. www.cs.man.ac.uk. Архів оригіналу за 27 липня 2018. Процитовано 31 травня 2019.
- ↑ page 111, "Compilers Principles, Techniques, & Tools, 2nd Ed." (WorldCat) by Aho, Lam, Sethi and Ullman, as quoted in https://stackoverflow.com/questions/14954721/what-is-the-difference-between-token-and-lexeme [Архівовано 30 грудня 2016 у Wayback Machine.]
- ↑ Perl 5 Porters. perlinterp: Perl 5 version 24.0 documentation. perldoc.perl.org - Official documentation for the Perl programming language. perldoc.perl.org. Архів оригіналу за 18 жовтня 2018. Процитовано 26 січня 2017.
- ↑ Guy Coder (19 лютого 2013). What is the difference between token and lexeme?. Stack Overflow. Stack Exchange Inc. Архів оригіналу за 30 грудня 2016. Процитовано 26 січня 2017.
- Compiling with C# and Java, Pat Terry, 2005, ISBN 032126360X
- Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6
- Sebesta, R. W. (2006). Concepts of programming languages (Seventh edition) pp. 177. Boston: Pearson/Addison-Wesley.
- Yang, W.; Tsay, Chey-Woei; Chan, Jien-Tsai (2002). On the applicability of the longest-match rule in lexical analysis. Computer Languages, Systems & Structures. 28 (3): 273—288. doi:10.1016/S0096-0551(02)00014-0. NSC 86-2213-E-009-021 and NSC 86-2213-E-009-079. Архів оригіналу за 17 квітня 2022. Процитовано 30 травня 2019.
- Trim, Craig (23 січня 2013). The Art of Tokenization. Developer Works. IBM. Архів оригіналу за 30 травня 2019. Процитовано 30 травня 2019.
- Word Mention Segmentation Task [Архівовано 30 травня 2019 у Wayback Machine.], an analysis