Wprowadzenie
Translacja sterowana składnią i zależności
kontekstowe Translacja sterowana składnią to translacja języków oparta o
gramatyki bezkontekstowe, w której
Języki formalne i techniki translacji - Wykład 11
z konstrukcjami języka wiązana jest pewna informacja poprzez
dołączenie atrybutów do symboli gramatyki reprezentujących te
konstrukcje;
Maciek Gębala
wartości atrybutów obliczane są przez tzw. reguły semantyczne
związane z produkcjami gramatyki.
8 maja 2013
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Definicje Definicje sterowane składnią
Definicje sterowane składnią są uogólnieniem gramatyki
Definicje sterowane składnią  ukrywają wiele szczegółów
bezkontekstowej przez związanie z każdym symbolem pewnego
implementacyjnych, nie wymagają jawnego określania kolejności
zbioru atrybutów.
obliczania reguł semantycznych.
Atrybuty dzielimy na syntetyzowane i dziedziczone.
Schematy translacji  wskazują kolejność wyliczania reguł
Wartości atrybutów w węz
le drzewa wyprowadzenia są
semantycznych, pokazują więcej szczegółów
określane przez reguły semantyczne związane z produkcją
implementacyjnych.
przypisaną do tego węzła.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Atrybuty Definicje S-atrybutowe i L-atrybutowe
Definicje S-atrybutowe
Gramatyka posiada tylko atrybuty syntetyzowane.
Z każdą produkcją gramatyki B X1X2 . . . Xn wiążemy zbiór reguł
semantycznych postaci b �! f (p1, p2, . . . , pk).
Definicje L-atrybutowe
b jest atrybutem syntetyzowanym symbolu B a p1, p2, . . . , pk są
Gramatyka posiada tylko atrybuty syntetyzowane lub atrybuty
atrybutami symboli X1, X2, . . . , Xn.
dziedziczone symbolu Xi w produkcji B X1X2 . . . Xn które zależą
b jest atrybutem dziedziczonym symbolu Xi a p1, p2, . . . , pk są
tylko od atrybutów symboli X1, X2, . . . , Xi-1 oraz atrybutu
atrybutami symboli B, X1, X2, . . . , Xn.
dziedziczonego symbolu B.
Każda definicja S-atrybutowa jest definicją L-atrybutową.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Przykład Translacja sterowana składnią w BISON-ie
Reguły semantyczne w BISON-ie są obliczane w trakcie
translacji.
Drzewo wyprowadzenia nie jest jawnie konstruowane. Porządek
wyliczania atrybutów jest narzucony przez samą metodę analizy.
Produkcja Reguły semantyczne
D TL L.dz �! T .typ
Zalety: prostota i efektywność translatora.
T int T .typ �! integer
Wady: możliwość przetwarzania tylko L-atrybutowych definicji
T real T .typ �! real
sterowanych składnią.
L L1, id L1.dz �! L.dz; id.typ �! L.dz
Realizując translację sterowaną składnią w BISON-ie
L id id.typ �! L.dz
bezpieczniej jest korzystać z mechanizmu atrybutów
wbudowanego w generator.
Używanie zmiennych globalnych może mieć efekty uboczne i nie
gwarantuje prawidłowej kolejności akcji wykonywanych przez
LR-parser.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Atrybuty  ogólne reguły Atrybuty  ogólne reguły
Z każdym symbolem w produkcji związany jest atrybut
Domyślny typ atrybutów można zmodyfikować za pomocą słowa
kluczowego umieszczanego w specyfikcji parsera.
A : X1 X2 X3 . . . Xn
Wewnątrz deklaracji można umieścić wszystkie
�! �! �! �! �!
potrzebne typy atrybutów.
W celu zadeklarowania typów symboli należy najpierw
Wartość atrybutu jednostki leksykalnej jest nadawana w
zdefiniować typ atrybutów za pomocą np.
analizatorze leksykalnym za pomocą zmiennej .
a następnie na podstawie tej definicji przypisać typ dla symboli
Zmienna jest domyślnie typu całkowitego ( ).
terminalnych
Akcje semantyczne możemy zapisać z wykorzystaniem
atrybutów.
i dla nieterminalnych
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Atrybuty  ogólne reguły Przykład  Gramatyka S-atrybutowa
Zmiana typów w parserze wymusza zmianę typów w skanerze:
dodanie definicji interfejsu
\
i odpowiednie nadawanie wartości tokenom
\
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Przykład  lekser Atrybuty dziedziczone
W BISON-ie można korzystać z atrybutów dziedziczonych, ale
definicje muszą być L-atrybutowe.
Wszystkie akcje związane z obliczeniem atrybutów nieterminali z
których korzystamy muszą być już wykonane i znajdować się na
stosie.
Atrybuty dziedziczone w BISON-ie oznaczane są niedodatnimi
indeksami, w kolejności od szczytu stosu (0) w głąb.
Typ pola unii do którego się odwołujemy powinien być wskazany
(w nawiasach trójkątnych).
\
Nie jest przeprowadzana kontrola poprawności sięgania po
atrybuty (na stosie).
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Przykład  Gramatyka L-atrybutowa Zależności kontekstowe
Zgodność programu z
ródłowego z regułami składniowymi i
semantycznymi języka programowania.
Kontrola zależności kontekstowych może być wykonywana
\
statycznie  podczas kompilacji programu
\ dynamicznie  podczas wykonywania programu wynikowego.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Kontrola statyczna System typów
System typów jest określany w definicji języka.
System typów języka może być również określony przez system
Kontrola zgodności typów.
reguł wiązania typów z odpowiednimi regułami języka (patrz
Sprawdzenie przepływu sterowania (czy instrukcje zostały użyte
SML).
w dopuszczalny sposób).
Zgodność programu z systemem typów języka jest sprawdzana
Sprawdzenie unikalności nazw deklaracji (czy użyte obiekty są
za pomocą kontrolera typów.
poprawnie zadeklarowane).
System typów jest nazywany silnym jeśli nie ma potrzeby
Sprawdzenie powtórzeń nazw (czy nazwy są poprawnie
sprawdzania typów w trakcie działania programu wynikowego.
powtórzone).
Język jest nazywany silnie utypowiony jeśli ma silny system
typów.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Wyrażenia określające typy Wyrażenia określające typy  funkcje
Typy podstawowe wbudowane w język  wyrażenia w gramatyce
Funkcje (procedury, podprogramy) są podstawową metodą
języka.
strukturalizacji programów.
Konstruktory typów  reguły pozwalające na tworzenie nowych
Funkcja przekształca elementy dziedziny (iloczyn kartezjański
typów na podstawie już istniejących.
argumentów) w elementy zbioru wartości funkcji.
Zestaw konstruktorów zależy od języka z
ródłowego.
Typ funkcji jest wyrażeniem zawierającym iloczyn kartezjański
Typowe konstruktory typów konstruują typy takie jak tablice,
dziedziny i typ wartości funkcji.
rekordy, wskaz
niki, funkcje, procedury.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Kontroler typów  tablica symboli Kontroler typów - operacje
Deklaracja zmiennej  dodajemy nowy symbol do tablicy z typem
czy zasięgiem występowania.
Tablica symboli zawiera informacje o każdym użytym symbolu.
(Błędy: brak miejsca w tablicy, redeklaracja zmiennej.)
Informacje przechowujemy w postaci atrybutów takich jak: typ,
Wyrażenia stałe  rekonstrukcja typu.
zasięg występowania, wartość, itp.
Identyfikator  sprawdzenie atrybutów w tablicy typów.
Reprezentacja tablicy musi być efektywna czasowo i pamięciowo.
Operator  sprawdzenie dla operatora czy typy jego argumentów
Musi zostać zapewniona efektywna obsługa blokowych
odpowiadają typowi operatora.
konstrukcji języka (konteksty lokalne).
Tablica  sprawdzenie czy indeks jest odpowiedniego typu.
Wskaz
nik  czy prawidłowo użyto wskaz
nika, rekonstrukcja jego
typu.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe
Kontroler typów - instrukcje Problemy
Sprawdzenie czy warunki logiczne są rzeczywiście typu
Przeciążanie funkcji i operatorów.
logicznego.
Funkcje polimorficzne.
Sprawdzenie czy przypisania są możliwe ze względu na system
typów.
Rekonstrukcje typów.
Uwzględnienie niejawnych konwersji typów.
Maciek Gębala Translacja sterowana składnią i zależności kontekstowe Maciek Gębala Translacja sterowana składnią i zależności kontekstowe