Analiza leksykalna (analizator) w projektowaniu kompilatora z przykładem

Programy, które wykonują analizę leksykalną w projekcie kompilatora, nazywane są analizatorami leksykalnymi lub lekserami. Lekser zawiera tokenizator lub skaner. Jeśli analizator leksykalny wykryje, że token jest nieprawidłowy, generuje błąd. Rolą analizatora leksykalnego w projektowaniu kompilatora jest odczytywanie strumieni znaków z kodu źródłowego, sprawdzanie legalnych tokenów i przekazywanie danych do analizatora składni, gdy tego wymaga.

Przykład

How Pleasant Is The Weather?

Zobacz ten przykład analizy leksykalnej; Możemy tutaj łatwo rozpoznać, że istnieje pięć słów: How Pleasant, The, Weather, Is. Jest to dla nas bardzo naturalne, ponieważ potrafimy rozpoznać separatory, spacje i znaki interpunkcyjne.

 HowPl easantIs Th ewe ather?

Teraz sprawdź ten przykład, możemy to również przeczytać. Zajmie to jednak trochę czasu, ponieważ w nieparzystych miejscach umieszczone zostaną separatory. To nie jest coś, co przychodzi do ciebie natychmiast.

Podstawowe terminologie

Co to jest leksem?

Leksem to ciąg znaków zawarty w programie źródłowym zgodnie ze wzorcem pasującym do tokena. To nic innego jak instancja tokena.

Co to jest token?

Tokeny w projekcie kompilatora to ciąg znaków reprezentujący jednostkę informacji w programie źródłowym.

Co to jest wzór?

Wzorzec to opis, którego używa token. W przypadku słowa kluczowego, które pełni funkcję tokena, wzorcem jest ciąg znaków.

Analizator leksykalny Architecture: Jak rozpoznawane są tokeny

Głównym zadaniem analizy leksykalnej jest odczytanie znaków wejściowych w kodzie i utworzenie tokenów.

Analizator leksykalny skanuje cały kod źródłowy programu. Identyfikuje każdy token jeden po drugim. Skanery są zwykle implementowane w celu generowania tokenów tylko na żądanie parsera. Oto jak działa rozpoznawanie tokenów w projektowaniu kompilatora:

1. „Pobierz następny token” to polecenie wysyłane z parsera do analizatora leksykalnego.
2. Po otrzymaniu tego polecenia analizator leksykalny skanuje dane wejściowe, aż znajdzie następny token.
3. Zwraca token do Parsera.

Analizator leksykalny pomija białe znaki i komentarze podczas tworzenia tych tokenów. Jeśli wystąpi jakikolwiek błąd, analizator leksykalny skoreluje ten błąd z plikiem źródłowym i numerem wiersza.

Role analizatora leksykalnego

Analizator leksykalny realizuje poniższe zadania:

• Pomaga zidentyfikować token w tabeli symboli
• Usuwa białe spacje i komentarze z programu źródłowego
• Koreluje komunikaty o błędach z programem źródłowym
• Pomaga w rozwijaniu makr, jeśli zostaną znalezione w programie źródłowym
• Odczytaj znaki wejściowe z programu źródłowego

Przykład analizy leksykalnej, tokeny, nie-tokeny

Rozważ poniższy kod, który jest przekazywany do analizatora leksykalnego

#include <stdio.h>
    int maximum(int x, int y) {
        // This will compare 2 numbers
        if (x > y)
            return x;
        else {
            return y;
        }
    }

Przykłady utworzonych Tokenów

Leksem	żeton
int	słowo kluczowe
maksymalny	identyfikator
(	OperaTor
int	słowo kluczowe
x	identyfikator
,	OperaTor
int	słowo kluczowe
Y	identyfikator
)	OperaTor
{	OperaTor
If	słowo kluczowe

Przykłady nietokenów

Typ	Przykłady
Komentarz	// To porówna 2 liczby
Dyrektywa przedprocesorowa	#włączać
Dyrektywa przedprocesorowa	#zdefiniuj NUM 8,9
Macro	LICZBY
Biała przestrzeń	/n /b /t

Błędy leksykalne

Sekwencja znaków, której nie można zeskanować do żadnego prawidłowego tokena, jest błędem leksykalnym. Ważne fakty dotyczące błędu leksykalnego:

• Błędy leksykalne nie są zbyt częste, ale skaner powinien sobie z nimi poradzić
• Błędy ortograficzne w identyfikatorach, operatorach i słowach kluczowych są uważane za błędy leksykalne
• Generalnie błąd leksykalny wynika z pojawienia się jakiegoś nielegalnego znaku, najczęściej na początku tokena.

Odzyskiwanie błędów w analizatorze leksykalnym

Oto kilka najpopularniejszych technik odzyskiwania po błędach:

• Usuwa jeden znak z pozostałych danych wejściowych
• W trybie paniki kolejne znaki są zawsze ignorowane, aż do momentu, gdy dotrzemy do dobrze uformowanego żetonu
• Wstawiając brakujący znak do pozostałych danych wejściowych
• Zastąp znak innym znakiem
• Transponuj dwa znaki seryjne

Analizator leksykalny a parser

Analizator leksykalny	Parser
Skanuj program wejściowy	Wykonaj analizę składni
Identyfikuj tokeny	Utwórz abstrakcyjną reprezentację kodu
Wstaw tokeny do tabeli symboli	Zaktualizuj wpisy w tabeli symboli
Generuje błędy leksykalne	Generuje drzewo analizy kodu źródłowego

Po co oddzielać leksykalny i parser?

• Prostota projektu: Ułatwia proces analizy leksykalnej i analizy składni poprzez eliminację niepożądanych tokenów
• Aby poprawić wydajność kompilatora: Pomaga poprawić wydajność kompilatora
• Specjalizacja: można zastosować specjalistyczne techniki w celu usprawnienia procesu analizy leksykalnej
• Przenośność: jedynie skaner wymaga komunikacji ze światem zewnętrznym
• Większa przenośność: cechy specyficzne dla urządzenia wejściowego ograniczone do leksykonu

Zalety analizy leksykalnej

• Metoda analizatora leksykalnego jest używana przez programy takie jak kompilatory, które mogą wykorzystywać przeanalizowane dane z kodu programisty do utworzenia skompilowanego binarnego kodu wykonywalnego
• Jest używany przez przeglądarki internetowe do formatowania i wyświetlania strony internetowej za pomocą przeanalizowanych danych JavaScript, HTML, CSS
• Oddzielny analizator leksykalny pomaga skonstruować wyspecjalizowany i potencjalnie wydajniejszy procesor do zadania

Wady analizy leksykalnej

• Musisz spędzić dużo czasu na czytaniu programu źródłowego i partycjonowaniu go w formie tokenów
• Niektóre wyrażenia regularne są dość trudne do zrozumienia w porównaniu z regułami PEG lub EBNF
• Opracowanie i debugowanie leksykonu i jego opisów tokenów wymaga więcej wysiłku
• Do wygenerowania tabel leksykalnych i skonstruowania tokenów wymagane jest dodatkowe obciążenie środowiska wykonawczego

Podsumowanie

• Analiza leksykalna jest pierwszą fazą projektowania kompilatora
• Leksemy i Tokeny to ciąg znaków zawarty w programie źródłowym zgodnie ze wzorcem dopasowania tokena
• Zaimplementowano analizator leksykalny umożliwiający skanowanie całego kodu źródłowego programu
• Analizator leksykalny pomaga zidentyfikować token w tabeli symboli
• Sekwencja znaków, której nie można zeskanować do żadnego prawidłowego tokena, jest błędem leksykalnym
• Usuwa jeden znak z pozostałych danych wejściowych. Przydatna metoda odzyskiwania po błędzie
• Analizator leksykalny skanuje program wejściowy, podczas gdy parser przeprowadza analizę składni
• Ułatwia proces analizy leksykalnej i analizy składni poprzez eliminację niechcianych tokenów
• Analizator leksykalny jest używany przez przeglądarki internetowe do formatowania i wyświetlania strony internetowej za pomocą analizowanych danych z JavsScript, HTML, CSS
• Największą wadą korzystania z analizatora leksykalnego jest to, że wymaga dodatkowego narzutu w czasie wykonywania, wymaganego do wygenerowania tabel leksykalnych i skonstruowania tokenów