Create
Learn
Share

Mgr

rename
kari565's version from 2016-11-05 20:02

Section

Question Answer
1. Formalna definicja gramatyki i językaGramatyka formalna - zbiór zasad produkcji ciągów znakowych w języku formalnym. Gramatyka składa się z czterech elementów (N, Sigma, P, S), gdzie: N - skończony zbiór symboli nieterminalnych (istnieją dla nich zasady zmieniające je na inne symbole) , Sigma - skończony zbiór symboli terminalnych (nie istnieją dla nich zasady zmieniające je na inne symbole), rozłączny ze zbiorem N, P - skończony zbiór reguł, S - symbol należący do zbioru N, zwany symbolem startowym Wyprowadzenie bezpośrednie v -> w - mamy z nim do czynienia, jeżeli istnieje produkcja bezpośrednio v do w. Wyprowadzenie pośrednie v -> w - mamy z nim do czynienia, jeżeli istnieją produkcje, których seria będzie prowadzić do wyprowadzenia v do w Język formalny - Dowolny zbiór słów nad skończonym alfabetem. Język jest wyprowadzany przez gramatykę. Wiele gramatyk może wyprowadzać ten sam język
2. Gramatyki jednoznaczne i wieloznacznegramatyka jednoznaczna - gramatyka, w której każde słowo ma tylko jedno drzewo wyprowadzenia. gramatyka niejednoznaczna - gramatyka nie spełniająca definicji gramatyki jednoznacznej
3. Klasyfikacja gramatykgramatyka typu 0 (rekurencyjnie przeliczalna) - każda gramatyka formalna mieści się w definicji gramatyki rekurencyjnie przeliczalnej. Są to gramatyki, nie posiadające żadnych restrykcji. Są one tożsame z maszyną Turinga. gramatyka typu 1 (kontekstowa) - gramatyka posiadająca zasady w postaci: alfa A beta --> alfa gamma beta, gdzie A jest znakiem nieterminalnym a alfa, beta, gamma jest znakiem ciągiem znaków terminalnych i nieterminalnych. alfa i beta mogą być puste, ale gamma musi być niepusta. Gramatyki te nazywane są kontekstowymi, ponieważ elementy alfa i beta występują po obu stronach wyprowadzenia - są tzw. "kontekstem". Gramatyki kontekstowe są  tożsame z automatem liniowo ograniczonym. gramatyka typu 2 (bezkontekstowa) - gramatyka posiadająca reguły o postaci A --> gamma, gdzie A jest nieterminalne a gamma jest ciągniem znaków terminalnych i nieterminalnych. Języki programowania są opisywane gramatykami tego typu. Są równoważne niedeterministycznym automatom ze stosem. gramatyka typu 3 (regularna) - gramatyka posiadająca reguły w takiej postaci, że po lewej i prawej stronie może znajdować się tylko jeden nieterminal. Gramatyka taka może być lewo, lub prawostronna. Gramatyki te są równoznaczne automatom skończonym.
4. Problem rozbioru gramatycznegoProblem rozbioru gramatycznego polega na próbie stwierdzenia czy dany ciąg symboli terminalnych jest słowem należącym do danego języka. Jeżeli dla danego słowa można zbudować drzewo rozbioru w danej gramatyce to słowo należy do języka generowanego przez tę gramatykę.Istnieją dwa algorytmy budowania drzewa: Top-Down (wyprowadzenie / wyprowadzanie lewostronne / analiza zstępująca) - drzewo budowane jest w kolejności od korzenia ku liściom Bottom-Up (redukowanie / wyprowadzenie prawostronne / analiza wstępująca) - drzewo budowane jest w kolejości od liści do korzenia Rozbiór gramatyczny jest wykonywany przez analizator składni (analizator syntaktyczny, parser).
5. Analiza leksykalnaAnaliza leksykalna stanowi pierwszą fazę kompilacji. Analizator leksykalny jest odpowiedzialny za przetwarzanie strumienia danych wejściowych i rozpoznawanie ciągów zbudowanych zgodnie z pewnymi zasadami (symbole leksykalne, tokeny). Symbolami leksykalnymi języka źródłowego są jego elementarne konstrukcje takie, jak: słowa kluczowe, liczby, identyfikatory i operatory. Analiza leksykalna może istotnie uprościć implementację następnej fazy kompilatora usuwając z wejścia nieistotne elementy takie, jak białe znaki (czyli spacje, tabulatory i nowe linie) oraz komentarze. Elementy te służą zwykle poprawie zrozumiałości kodu i nie mają wpływu na semantykę programu. Po przeprowadzeniu analizy leksykalnej, symbole leksykalne są przesłane na wejście analizatora składniowego.
6. Analiza syntaktyczna metodami wyprowadzaniaFaza analizy składniowej (analizy syntaktycznej) bada, czy jednostki leksykalne tworzą poprawne konstrukcje danego języka źródłowego. Analiza syntaktyczna metodą wyprowadzania (analiza zstępująca / top-down) to sposób analizy w której punktem początkowym jest korzeń drzewa wyprowadzania. Wychodząc od korzenia "zstępuje się" w dół drzewa zgodnie z regułami danej gramatyki tak długo aż osiągniemy zdanie podane na wejściu, bądź stwierdzimy, że dane zdanie nie może być wygenerowane przez daną gramatykę. Przykłady metod wprowadzenia: parser Ungera, przeszukiwanie wszerz, przeszukiwanie w głąb, metoda LL.
7. Analiza syntaktyczna metodami redukowania.Analiza syntaktyczna metodami redukowania (analiza wstępująca / bottom-up), jest to sposób analizy w którym punktem początkowym jest gotowe zdanie. Wychodząc z podanego zdania "wstępuje" się w górę drzewa wyprowadzenia tak długo, aż osiągnie się symbol startowy. W momencie osiągnięcia symbolu startowego wiemy, że zdanie może być generowane przez gramatykę i znamy wyprowadzenia zdania. Przykłady metod redukowania: algorytm CYK, algorytm Earleye, metody LR.
8. Wewnętrzne postaci programu źródłowegoPodstawowymi postaciami są: czwórki, trójki, drzewa, notacja polska. Czwórki – w tej postać wyrażenie jest zapisane za pomocą czterech elementów: (znak, operand1, operand2, wynik). Charakterystyczną cechą czwórek jest fakt, że zapisuje je się je w kolejności wykonywania działań. Minusem tej notacji jest istnienie bardzo wielu zmiennych pomocniczych. Przykładowo dla Operacji A*B, notacja czwórki może przyjąć postać (*, A, B, T), gdzie T jest zmienną pod którą zostanie podstawiony wynik. Wyrażenia bardziej skomplikowane zostaną zapisane za pomocą serii czwórek, np. wyrażenie A+B*C, będzie się składać z czwórek: (*, B, C, T1) oraz (+, A, T1, T2) Trójki - w tej postaci wyrażenie jest zapisane za pomocą trzech elementów: (znak, operand1, operand2) - z tym, że operandem może być dowolna wcześniej zapisana trójka (każda trójka musi posiadać swój indeks, poprzez który można ją "wstawić" do innej trójki). Podobnie jak w przypadku czwórek zapisuje się je w kolejności wykonywania działania, ale nie występuje tu potrzeba zapisywania zmiennych tymczasowych. Przykładowo dla operacji A*B notacja trójki przyjmie postać (1)(*,A,B), gdzie (1) jest indeksem. Bardziej skomplikowane wyrażenie: A+B*C zostanie zapisane w trójkami: (1)(*,B,C) oraz (2) (+,A,(1)) Drzewa - wyrażenie zapisane w postaci drzewa, którego węzłami są zmienne bądź operatory. Zmienne tworzą liście drzewa, natomiast operatory posiadają potomków, które są operandami tych operatorów. Notacja polska - (notacja przyrostkowa) wymyślona przez Łukasiewicza, reprezentująca wyrażenia w sposób jasno określający kolejność działań, bez wykorzystywania nawiasów. W notacji polskiej operatory występują bezpośrednio po argumentach. Przykładowo dla wyrażenia A*B notacja polska ma postać A B *, natomiast dla wyrażenia A + B * C, będzie miała postać A B C * +
9. Zadania analizy semantycznejPo zakończeniu faz analizy leksykalnej i analizy składniowej kompilator przechodzi do analizy semantycznej. Zadaniem tej fazy jest sprawdzenie programu źródłowego pod względem semantycznej zgodności z definicją języka źródłowego. Przy okazji zbierane są informacje potrzebne w kolejnej fazie – generacji kodu. Proces analizy semantycznej dodaje informację o tym co tak naprawdę znaczą poszczególne tokeny. Sprawdzane są takie rzeczy jak: 1. Typy danych (np. czy typ zmiennej zgadza się z przypisywaną wartością) 2. Powiązania obiektów (wiązanie zmiennych i nazw funkcji z ich definicjami) 3. Przypisania (np. czy zmienna została zainicjowana przed próbą użycia) 4. Kontrola nazw (np. czy nazwy się nie duplikują, bądź czy są poprawne) Analiza sematyczna następuje po fazie parsowania i przed fazą generowania kodu.
10. Generowanie przekładuGenerowanie przekładu to inaczej wygenerowanie właściwego kodu asemblera na podstawie wyniku analizy syntaktycznej i semantycznej. Generowanie przekładu na podstawie wyrażenia arytmetycznego wygląda w ten sposób, że wyrażenie zostaje przedstawione np. w postaci czwórek. Każda z czwórek jest przeglądana i na jej podstawie generowany jest przekład. Na podstawie wartości każdej czwórki wybierane są docelowe instrukcje, które zostaną wygenerowane. Np. przy operacji dodawania zostanie wygenerowana instrukcja ADD, przy odejmowaniu SUB, itd. W procesie generowania przekładu dba się , aby nie generować niepotrzebnych instrukcji takich jak LOAD - jeżeli np. jedna z potrzebnych wartości znajduje się już w akumulatorze. Uwzględnia się specyfikę języka programowania aby dobrać najefektywniejszy przekład.
11. Techniki optymalizacji przekładuIstnieje wiele rodzajów optymalizacji wykonywanych przez kompilator. Mogą one być zależne bądź nie od konkretnego języka programowania lub maszyny. Podstawowa klasyfikacja optymalizacji: 1. Peehole optimization - optymalizacja na gotowym kodzie asemblerowym, przeglądanych jest po kilku instrukcji na raz i sprawdzane jest, czy nie da się ich zastąpić innymi (np. krótszą ilością instrukcji, albo instrukcjami mniej kosztownymi obliczeniowo). Np mnożenie przez 2 można zastąpić przesunięciem bitowym. 2. Optymalizacja lokalna – badane są bloki podstawowe pod kątem możliwości optymalizacji. Blok podstawowy nie zawiera instrukcji sterujących, więc analiza takiego bloku jest stosunkowo prosta, ale nie można w niej zastosować optymalizacji związanych ze skokami. 3. Optymalizacja globalna – badane są całe funkcje, optymalizacje takie w przeciwieństwie do optymalizacji lokalnej, są dużo bardziej skomplikowane. 4. Optymalizacje pętli - analiza bloków pętli i wykonywanie na nich optymalizacji, np. wyszukiwanie niezmienników pętli i obliczanie ich jednorazowo przed samym wejściem do pętli. 5. Optymalizacja całego programu - analiza całości programu. Dostarcza największej liczby informacji, można zastosować bardzo zaawansowane optymalizacje, przykładowo optymalizacja typu function inline, gdzie zastępuje się wywołania danej funkcji, jej treścią.
12. Definicja przetwarzania równoległego i rozproszonego, różnica miedzy przetwarzaniem równoległym a rozproszonymPrzetwarzanie równoległe - program jest podzielony na kilka wątków i przynajmniej część z nich jest wykonywana w tym samym czasie. W przetwarzaniu równoległym wątki współdzielą pamięć. Przetwarzanie rozproszone - wątki składające się na program mogą być wykonywane na kilku fizycznych maszynach. W przetwarzaniu rozproszonym wątki komunikują się ze sobą przez sieć.
13. Rodzaje zależności danych1. Zależność prosta (odczyt po zapisie) - w jednej instrukcji dokonujemy przypisania do danej zmiennej, aby w kolejnej instrukcji tą zmienną odczytać (np. a = b; c = a;). 2. Zależność odwrotna (zapis po odczycie) - w jednej instrukcji odczytujemy zmienną by w następnej dokonać na niej zapisu (np. a = b; b = c;). 3. Zależność po wyjściu (zapis po zapisie) - w jednej instrukcji zapisujemy do danej zmiennej, a w kolejnej nadpisujemy tą wartość kolejnym przypisaniem (np. a = b; a = c;). 4. Zależność na wejściu (odczyt po odczycie) - nie wpływa na poprawność aplikacji (a=b; c=b;).
14. Podstawowe transformacje pętliTransformacja FAN - poszczególne iteracje dzieli się pomiędzy różne wątki aby na końcu zebrać wyniki i połączyć je. Takiej transformacji można dokonać jeśli brak jest zależności pomiędzy iteracjami, natomiast zależności między instrukcjami w iteracji nie są przeszkodą do zastosowania tej transformacji. Poziom równoległości jest równy liczbie zrównoleglonych pętli. Transformacja PAR - poszczególne instrukcje (grupy instrukcji) w ramach każdej iteracji są dzielone pomiędzy różnymi wątkami, a na koniec każdej iteracji występuje synchronizacja barierowa. Poziom równoległości jest równy liczbie niezależnych instrukcji. Transformacja PIPE - poszczególne iteracje są wykonywane równolegle, z jednym ważnym zastrzeżeniem, że wykonanie iteracji jest opóźnione względem siebie, tak, że pierwszy wątek zakończy wykonywanie wszystkich instrukcji, które powodują zależność między iteracjami. Najpierw wykonywane są obliczenia dotyczące początku zależności, a dopiero później obliczenia dotyczące końca zależności.
15. Przyspieszenie i efektywność, prawa Amdahl’a i Gustaffson’aPrzyspieszenie to stosunek czasu wykonania obliczeń na jednym procesorze do czasu wykonania obliczeń na wielu procesorach. Wzór: S(P) = t(1)/t(P) Efektywność - Stosunek przyspieszenia do liczby procesorów. Wzór: E(P) = S(P)/P Prawo Amdahla - określa teoretyczne maksymalne przyśpieszenie wykonywanego programu poprzez jego zrównoleglenie. Wynika z niego, że wzrost wydajności jest ograniczony częścią obliczeń, która musi być wykonywana sekwencyjnie. Prawo Amdal'a wyraża się wzorem: 1/(S+(1-S)/N) ,gdzie S - cząstka obliczeń, która musi być wykonywana sekwencyjnie (ułamek), N - liczba procesorów na których będzie wykonywał się zrównoleglony kod Prawo Gustafsona - każdy wystarczająco duży problem może być efektywnie zrównoleglony. Przyśpieszenie w prawie Gustafsona wyraża się wzorem: S(P) = P - alfa * (P-1) gdzie: P - liczba procesorów, S – przyśpieszenie, alfa - część programu, która musi się wykonywać sekwencyjnie
16. Paradygmaty programowania równoległego i rozproszonego (programowanie równoległości danych).Model równoległości danych Model SPMD (pierwotnie dla maszyn SIMD). Zrównoleglenie poprzez przypisanie danych poszczególnym procesorom. Implementacja powinna umożliwiać efektywną realizację programów, tak dla systemów z pamięcią wspólną, jak i dla środowisk przesyłania komunikatów bez pamięci wspólnej
memorize

Recent badges