Analiza leksykalna – w informatyce proces rozdzielania programów źródłowych na jednostki logiczne (zwane leksemami) złożone z jednego lub więcej znaków, które łącznie mają jakieś znaczenie[1]. Przykładami leksemów mogą być słowa kluczowe (np. while), identyfikator lub liczba składająca się z cyfr. Rozdzielaniem programu źródłowego, na leksemy, zajmuje się lekser. Zazwyczaj lekser działa w parze z parserem, z którym wspólnie analizują składnię języków programowania, na przykład w kompilatorach, ale również w parserach HTML występujących w przeglądarkach internetowych.
Ściślej rzecz biorąc, lekser jest też rodzajem parsera. Składnia wielu języków programowania dzieli się na dwie części: składnię leksykalną (wewnętrzną konstrukcję tokenu), która jest przetwarzana przez lekser i składnię gramatyczną, która jest przetwarzana przez parser. Składnia leksykalna jest zazwyczaj wyrażeniem regularnym którego alfabet składa się z pojedynczych znaków kodu źródłowego. Składnia gramatyczna to zazwyczaj bezkontekstowy język, którego alfabet składa się z tokenów produkowanych przez lekser. Zwyczajowo analiza tekstu przebiega w wymienionych wyżej dwóch fazach, jednak lekser może być połączony z parserem w przetwarzaniu jednoprzebiegowym.
Token
[edytuj | edytuj kod]Token jest strukturą reprezentującą leksem i wprost go kategoryzującą[2], co ułatwia późniejszą pracę parserowi. Tokeny kategoryzuje się na komputerowy odpowiednik tego, co lingwiści określiliby mianem części mowy. Przykładowe kategorie to: identyfikator, operator przypisania, znacznik początku bloku. Proces tworzenia tokenów z wejściowego strumienia znakowego jest nazywany tokenizacją.
Rozważmy następujące wyrażenie z języka C:
int suma = 3 + 2;
Rezultatem procesu tokenizacji jest ta tabela:
Leksem | Kategoria |
---|---|
int | Identyfikator typu zmiennej |
suma | Identyfikator zmiennej |
= | Operator przypisania |
3 | Literał całkowitoliczbowy |
+ | Operator dodawania |
2 | Literał całkowitoliczbowy |
; | Znacznik końca wyrażenia |
Gramatyka leksykalna
[edytuj | edytuj kod]Specyfikacja języka programowania obejmuje szereg reguł które definiują składnię leksykalną. Składnia leksykalna jest zazwyczaj opisana za pomocą wyrażeń regularnych. Definiują one zbiór możliwych sekwencji znakowych które tworzą pojedyncze tokeny. Lekser przetwarza oddzielone znakami białymi ciągi znaków i dla każdego ciągu znaków podejmuje akcję zazwyczaj produkując token, bądź ogłasza błąd analizy leksykalnej.
Komentarze i białe znaki zajmują ważne miejsce analizie leksykalnej i muszą być opisane w gramatyce języka. Mogą być odrzucone na etapie analizy leksykalnej (nie tworzą tokenu). W większości języków są uważane za nieznaczące, jedynie separujące dwa tokeny. W niektórych językach (takich jak Python[3], YAML, ABC) rozpoznających bloki kodu za pomocą odpowiedniej głębokości wcięć białe znaki na początku każdej linii są znaczące. Komentarze są również czasem zachowywane, w celu późniejszej łatwiejszej analizy lub manipulacji kodu wynikowego (np. prezerwacja adnotacji w Java).
Przypisy
[edytuj | edytuj kod]- ↑ Hopcroft, Motwani i Ullman 2005 ↓, s. 80.
- ↑ Definicja tokenu – stackoverflow. (ang.).
- ↑ Analiza leksykalna w języku python – dokumentacja. (ang.).
Bibliografia
[edytuj | edytuj kod]- J.E. Hopcroft, R. Motwani, J.D. Ullman: Wprowadzenie do Teorii automatów, języków i obliczń. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 83-01-14502-1.