Projekt kompilatora - analiza semantyczna

Dowiedzieliśmy się, jak parser konstruuje drzewa parsowania w fazie analizy składni. Zwykłe drzewo parsowania skonstruowane w tej fazie jest generalnie bezużyteczne dla kompilatora, ponieważ nie zawiera żadnych informacji o tym, jak ocenić drzewo. Produkcje gramatyki bezkontekstowej, która czyni reguły języka, nie uwzględniają sposobu ich interpretacji.

Na przykład

E → E + T

Z powyższą produkcją CFG nie jest związana żadna reguła semantyczna i nie może pomóc w nadaniu sensu produkcji.

Semantyka

Semantyka języka nadaje znaczenie jego konstrukcjom, takim jak tokeny i struktura składni. Semantyka pomaga w interpretacji symboli, ich typów i relacji między nimi. Analiza semantyczna ocenia, czy struktura składni skonstruowana w programie źródłowym ma jakiekolwiek znaczenie, czy nie.

CFG + semantic rules = Syntax Directed Definitions

Na przykład:

int a = “value”;

nie powinien powodować błędu w fazie analizy leksykalnej i składniowej, ponieważ jest poprawny leksykalnie i strukturalnie, ale powinien generować błąd semantyczny, ponieważ rodzaj przypisania jest inny. Reguły te są wyznaczane przez gramatykę języka i oceniane w analizie semantycznej. W analizie semantycznej należy wykonać następujące zadania:

Rozdzielczość zakresu
Sprawdzanie typu
Sprawdzanie związane z tablicą

Błędy semantyczne

Wspomnieliśmy o niektórych błędach semantycznych, które analizator semantyczny powinien rozpoznać:

Niezgodność typów
Niezadeklarowana zmienna
Niewłaściwe użycie zastrzeżonego identyfikatora.
Wielokrotna deklaracja zmiennej w zakresie.
Dostęp do zmiennej spoza zakresu.
Rzeczywista i formalna niezgodność parametrów.

Gramatyka atrybutów

Gramatyka atrybutów jest specjalną formą gramatyki bezkontekstowej, w której pewne dodatkowe informacje (atrybuty) są dołączane do jednego lub większej liczby nieterminali w celu dostarczenia informacji kontekstowych. Każdy atrybut ma dobrze zdefiniowaną dziedzinę wartości, taką jak liczba całkowita, zmiennoprzecinkowa, znak, ciąg znaków i wyrażenia.

Gramatyka atrybutów jest medium dostarczającym semantykę do gramatyki bezkontekstowej i może pomóc w określeniu składni i semantyki języka programowania. Gramatyka atrybutów (widziana jako drzewo parsowania) może przekazywać wartości lub informacje między węzłami drzewa.

Example:

E → E + T { E.value = E.value + T.value }

Prawa część CFG zawiera reguły semantyczne, które określają, jak należy interpretować gramatykę. Tutaj wartości nieterminalowe E i T są sumowane, a wynik jest kopiowany do nieterminalowego E.

Atrybuty semantyczne mogą być przypisane do ich wartości z ich domeny w czasie analizy i oceniane w czasie przypisywania lub warunków. Na podstawie sposobu, w jaki atrybuty uzyskują swoje wartości, można je ogólnie podzielić na dwie kategorie: atrybuty zsyntetyzowane i atrybuty dziedziczone.

Zsyntetyzowane atrybuty

Te atrybuty pobierają wartości z wartości atrybutów ich węzłów podrzędnych. Aby to zilustrować, przyjmijmy następującą produkcję:

S → ABC

Jeśli S pobiera wartości z węzłów potomnych (A, B, C), to mówi się, że jest to atrybut zsyntetyzowany, ponieważ wartości ABC są syntetyzowane do S.

Podobnie jak w naszym poprzednim przykładzie (E → E + T), węzeł macierzysty E pobiera wartość ze swojego węzła potomnego. Zsyntetyzowane atrybuty nigdy nie pobierają wartości ze swoich węzłów nadrzędnych ani żadnych węzłów siostrzanych.

Dziedziczone atrybuty

W przeciwieństwie do atrybutów zsyntetyzowanych, odziedziczone atrybuty mogą przyjmować wartości od rodzica i / lub rodzeństwa. Jak w następnej produkcji,

S → ABC

A może pobierać wartości z S, B i C. B może przyjmować wartości z S, A i C. Podobnie C może przyjmować wartości z S, A i B.

Expansion : Gdy nieterminal jest rozszerzany do terminali zgodnie z regułą gramatyczną

Reduction: Kiedy terminal jest zredukowany do odpowiadającego mu nieterminala zgodnie z regułami gramatycznymi. Drzewa składniowe są analizowane z góry na dół i od lewej do prawej. Ilekroć następuje redukcja, stosujemy odpowiadające jej reguły semantyczne (akcje).

Analiza semantyczna wykorzystuje tłumaczenia ukierunkowane na składnię do wykonywania powyższych zadań.

Analizator semantyczny otrzymuje AST (Abstract Syntax Tree) z poprzedniego etapu (analiza składni).

Analizator semantyczny dołącza informacje o atrybutach do AST, które są nazywane Attributed AST.

Atrybuty to dwie wartości krotki, <nazwa atrybutu, wartość atrybutu>

Na przykład:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Do każdej produkcji dołączamy regułę semantyczną.

SDT przypisywane S.

Jeśli SDT używa tylko zsyntetyzowanych atrybutów, nazywa się to SDT z atrybutem S. Te atrybuty są oceniane za pomocą SDT z atrybutem S, które mają swoje działania semantyczne zapisane po produkcji (po prawej stronie).

Jak pokazano powyżej, atrybuty w SDT z atrybutem S są oceniane w analizie oddolnej, ponieważ wartości węzłów nadrzędnych zależą od wartości węzłów potomnych.

SDT przypisane L.

Ta forma SDT wykorzystuje zarówno atrybuty zsyntetyzowane, jak i odziedziczone, z zastrzeżeniem niepobierania wartości od prawego rodzeństwa.

W SDT z przypisanym atrybutem L, nieterminal może pobierać wartości ze swoich węzłów nadrzędnych, potomnych i rodzeństwa. Jak w następnej produkcji

S → ABC

S może przyjmować wartości z A, B i C (zsyntetyzowane). A może przyjmować wartości tylko z S. B może przyjmować wartości z S i A. C może uzyskać wartości z S, A i B. Żaden nieterminal nie może uzyskać wartości od rodzeństwa po jego prawej stronie.

Atrybuty w L-przypisanych SDT są oceniane metodą analizy najpierw w głąb i od lewej do prawej.

Możemy wywnioskować, że jeśli definicji przypisuje się S, to jest ona również przypisywana L, ponieważ definicja z atrybutem L obejmuje definicje z atrybutem S.