Tabela symboli - Symbol table

W informatyce , wykorzystując stół symbol jest struktura danych używana przez język tłumacza , takich jak kompilator lub interpreter , gdzie każdy identyfikator (lub symbol) w programie w kodzie źródłowym jest związany z informacji odnoszących się do jego zgłoszenia lub wyglądu w źródle. Innymi słowy, wpisy tablicy symboli przechowują informacje związane z odpowiednim symbolem wpisu.

Tło

Tablica symboli może istnieć tylko w pamięci podczas procesu translacji lub może być osadzona w wyniku translacji, na przykład w pliku obiektowym ABI do późniejszego wykorzystania. Na przykład może być używany podczas interaktywnej sesji debugowania lub jako zasób do formatowania raportu diagnostycznego podczas lub po wykonaniu programu.

Opis

Minimalna informacja zawarta w tablicy symboli używanych przez tłumacza obejmuje nazwę symbolu oraz jego lokalizację lub adres. W przypadku kompilatora ukierunkowanego na platformę z koncepcją relokowalności, będzie on również zawierał atrybuty relokacji (bezwzględne, relokowalne itp.) oraz potrzebne informacje o relokacji dla relokowalnych symboli. Tabele symboli dla języków programowania wysokiego poziomu mogą przechowywać typ symbolu: łańcuch, liczbę całkowitą, zmiennoprzecinkową itp., jego rozmiar, wymiary i granice. Nie wszystkie te informacje są zawarte w pliku wyjściowym, ale można je podać do wykorzystania podczas debugowania . W wielu przypadkach, symbol jest odsyłacz informacje są przechowywane z lub związane z tablicy symboli. Większość kompilatorów drukuje niektóre lub wszystkie te informacje w tablicy symboli i wykazach odsyłaczy na końcu tłumaczenia.

Realizacja

Dostępnych jest wiele struktur danych do implementacji tabel. Drzewa, listy liniowe i listy samoorganizujące się mogą być używane do implementacji tablicy symboli. Dostęp do tablicy symboli uzyskuje się w większości faz kompilatora, począwszy od analizy leksykalnej , a skończywszy na optymalizacji.

Kompilator może używać jednej dużej tablicy symboli dla wszystkich symboli lub używać oddzielnych, hierarchicznych tablic symboli dla różnych zakresów . Na przykład w języku o określonym zakresie, takim jak Algol lub PL/I, symbol „p” można zadeklarować oddzielnie w kilku procedurach, być może z różnymi atrybutami. Zakresem każdej deklaracji jest sekcja programu, w której odwołania do "p" prowadzą do tej deklaracji. Każda deklaracja reprezentuje unikalny identyfikator „p”. Tablica symboli musi mieć pewne sposoby rozróżniania odniesień do różnych „p”.

Powszechną strukturą danych używaną do implementacji tablic symboli jest tablica mieszająca . Czas wyszukiwania w tablicach mieszających jest niezależny od ilości elementów przechowywanych w tablicy, więc jest to efektywne dla dużej ilości elementów. Upraszcza również klasyfikację literałów w formacie tabelarycznym, włączając klasyfikację do obliczania klucza skrótu.

Ponieważ analizator leksykalny spędza dużą część swojego czasu na przeglądaniu tablicy symboli, czynność ta ma decydujący wpływ na ogólną szybkość kompilatora. Tablica symboli musi być zorganizowana w taki sposób, aby wpisy można było znaleźć tak szybko, jak to możliwe. Tabele haszujące są zwykle używane do organizowania tabeli symboli, w której słowo kluczowe lub identyfikator jest haszowane w celu utworzenia indeksu tablicy. Kolizje są nieuniknione w tabeli mieszającej, a częstym sposobem ich obsługi jest przechowywanie synonimu w następnym wolnym miejscu w tabeli.

Aplikacje

Plik obiektowy będzie zawierał tablicę symboli zawartych w nim identyfikatorów, które są widoczne z zewnątrz. Podczas łączenia różnych plików obiektowych, linker zidentyfikuje i rozwiąże te odniesienia do symboli. Zazwyczaj wszystkie niezdefiniowane symbole zewnętrzne będą wyszukiwane w jednej lub kilku bibliotekach obiektów . Jeśli zostanie znaleziony moduł, który definiuje ten symbol, z którym jest powiązany wraz z pierwszym plikiem obiektowym, a wszelkie niezdefiniowane identyfikatory zewnętrzne są dodawane do listy identyfikatorów do wyszukania. Ten proces trwa do momentu rozwiązania wszystkich odwołań zewnętrznych. Jest to błąd, jeśli jeden lub więcej pozostaje nierozwiązanych na końcu procesu.

Podczas inżynierii wstecznej pliku wykonywalnego, wiele narzędzi odwołuje się do tablicy symboli, aby sprawdzić, jakie adresy zostały przypisane zmiennym globalnym i znanym funkcjom. Jeśli tablica symboli została usunięta lub wyczyszczona przed przekształceniem w plik wykonywalny, narzędziom będzie trudniej określić adresy lub zrozumieć cokolwiek na temat programu.

Przykład

Rozważmy następujący program napisany w C :

// Declare an external function
extern double bar(double x);

// Define a public function
double foo(int count)
{
    double sum = 0.0;

    // Sum all the values bar(1) to bar(count)
    for (int i = 1; i <= count; i++)
        sum += bar((double) i);
    return sum;
}

Kompilator AC, który analizuje ten kod, będzie zawierał co najmniej następujące wpisy w tablicy symboli:

Ponadto tablica symboli będzie również zawierać wpisy wygenerowane przez kompilator dla wartości wyrażeń pośrednich (np. wyrażenie rzutujące izmienną pętli na a doublei wartość zwracaną wywołania function bar()), etykiety instrukcji i tak dalej.

Przykład: SysV ABI

Przykład tabeli symboli można znaleźć w specyfikacji SysV Application Binary Interface (ABI), która określa sposób rozmieszczenia symboli w pliku binarnym, tak aby różne kompilatory, linkery i programy ładujące mogły konsekwentnie znajdować i pracować z symbole w skompilowanym obiekcie.

SysV ABI jest zaimplementowany w narzędziu nm GNU binutils . Ten format wykorzystuje posortowane pole adresu pamięci, pole „typu symbolu” i identyfikator symbolu (nazywany „Nazwą”).

Typy symboli w SysV ABI (i danych wyjściowych nm) wskazują naturę każdego wpisu w tablicy symboli. Każdy typ symbolu jest reprezentowany przez pojedynczy znak. Na przykład, wpisy tablicy symboli reprezentujące zainicjowane dane są oznaczone znakiem "d", a wpisy tablicy symboli dla funkcji mają typ symbolu "t" (ponieważ kod wykonywalny znajduje się w sekcji tekstowej pliku obiektowego). Dodatkowo, wielkość typu symbolu wskazuje rodzaj powiązania: małe litery wskazują, że symbol jest lokalny, a wielkie litery wskazują na powiązanie zewnętrzne (globalne).

Przykład: tablica symboli Pythona

Język programowania Python zawiera obszerną obsługę tworzenia i manipulowania tablicami symboli. Właściwości, które można przeszukiwać to, czy dany symbol jest wolna zmienna lub zmienna związana , czy jest to zakres blok lub zakres globalny , czy jest on importowany i jakie obszaru nazw należy.

Przykład: dynamiczne tablice symboli

Niektóre języki programowania pozwalają na manipulowanie tablicą symboli w czasie wykonywania, dzięki czemu symbole mogą być dodawane w dowolnym momencie. Przykładem takiego języka jest rakieta .

Zarówno LISP, jak i języki programowania Scheme pozwalają na skojarzenie dowolnych, ogólnych właściwości z każdym symbolem.

Język programowania Prolog jest zasadniczo językiem manipulacji tablicami symboli; symbole nazywane są atomami , a relacje między symbolami można przeanalizować. Podobnie OpenCog zapewnia dynamiczną tablicę symboli, zwaną przestrzenią atomową , która jest używana do reprezentacji wiedzy .

Zobacz też

• Symbol debugowania

Bibliografia