A
Alfabet to dowolny skończony ciąg symboli a1,a2,a3,…,an.
Analiza polega na rozłożeniu programu na części składowe i stworzeniu jego reprezentacji pośredniej.
Analiza hierarchiczna to analiza,w której znaki lub symbole leksykalne są grupowane hierarchicznie w zagnieżdżone struktury mające wspólne znaczenie. W tym etapie następuje sprawdzenie,czy ułożenie tokenów nie łamie reguł danego języka programowania.
Analiza leksykalna ->Analiza liniowa
Analiza liniowa to analiza,w której strumień znaków,składający się na program wejściowy,jest wczytywany i grupowany w symbole leksykalne,tzw. tokeny,czyli ciągi znaków mających razem określone znaczenie.
Analizy semantyczna to analiza,w której przeprowadzane są pewne testy mające zapewnić,że składniki programu pasują do siebie pod względem znaczenia.
Analiza składniowa ->Analiza hierarchiczna
Automat nad alfabetem A to system A=(S,f),w którym S –jest dowolnym skończonym zbiorem zwanym zbiorem stanów,a f:S x A → S –jest funkcją przejść.
Automatem deterministyczny AD to piątka AD = <N,V,M,S,Z>,gdzie:
N –zbiór stanów (alfabet nieterminalny automatu)
V- zbiór wejść (alfabet terminalny automatu)
M –funkcja przejścia automatu tj M:(N x V) &rorr;N (określenie dla danego stanu oraz wejścia stanu nowego do jakiego następuje przejście automatu
S –zbiór stanów początkowych automatu (ustalone symbole nieterminalne)
Z –zbiór stanów końcowych (niepusty zbiór symboli nieterminalnych)
Automat niedeterministyczny AN to piątka AN = <N,V,M,S,Z>,gdzie:
N –zbiór stanów (alfabet nieterminalny automatu)
V- zbiór wejść (alfabet terminalny automatu)
M –relacja przejścia automatu tj M:(N x V) ->2^N (określenie dla danego stanu oraz wejścia stanów nowych do jakich może nastąpić przejście automatu
S –zbiór stanów początkowych automatu (ustalone symbole nieterminalne)
Z –zbiór stanów końcowych (niepusty zbiór symboli nieterminalnych)
Automat skończony składa się ze skończonego zbioru stanów i zbioru przejść pomiędzy stanami.
J
Język to system zorganizowanych znaków,symboli wraz z regułami posługiwania się nimi.
Język bezkontekstowy to język,który można wygenerować za pomocą gramatyki bezkontekstowej,która po lewej stronie reguł produkcji ma pojedynczy symbol nieterminalny,po prawej zaś dowolne słowa. Postać:A → γ
Język kontekstowy to język,który można wygenerować za pomocą gramatyki kontekstowej,której produkcje są postaci α A β → α γ β,gdzie α i β są dowolnymi słowami,A symbolem nieterminalnym,γ –niepustym słowem.
Język naturalny (etniczny) to język powstały w procesie ewolucji biologicznej lub społecznej.
Język regularny to język,który można wygenerować za pomocą gramatyki liniowej – takiej,która po lewej stronie reguł ma pojedynczy symbol nieterminalny,po prawej zaś słowa zawierające co najwyżej jeden symbol nieterminalny.
Język rekurencyjnie przeliczalny to język,dla którego istnieje gramatyka typu 0,której produkcje są postaci α → β,gdzie α i β są dowolnymi słowami.
Język sztuczny (formalny) to ściśle określony system znaków wraz z regułami postępowania z tymi symbolami,a także regułami ich interpretowania.
H
Hierarchia Chomsky’ego ->Klasyfikacja Chomsky’ego
K
Klasyfikacja Chomsky’ego –podział gramatyk na cztery klasy wprowadzony przez Noama Chomsky’ego.
Kompilacja to proces translacji kodu w języku źródłowym na kod w języku wynikowym.
Kompilator (ang. compiler) to program, który czyta kod napisany w jednym języku (języku źródłowym) i tłumaczy go na równoważny kod w innym języku (języku wynikowym) z jednoczesnym wykrywaniem ewentualnych błędów popełnionych w trakcie programowania.
Ł
Łańcuch –>Słowo
D
Determinizacja to proces przejścia z niedeterministycznego automatu skończonego do odpowiadającego mu deterministycznego automatu skończonego.
Długość słowa to liczba symboli znajdująca się w łańcuchu.
Domknięcie nieskończone języka L,co oznaczamy L*,nazywamy nowy język otrzymany w wyniku złożenia L*=df=∪∞i=0Li
Domknięcie dodatnie języka L,co oznaczamy L+,nazywamy nowy język otrzymany w wyniku złożenia L+=df=∪∞i=1Li
Drzewo syntaktyczne graficzny sposób zapisu rozbioru zdań,służący początkowo do opisu języków naturalnych.
G
Gramatyki bezkontekstowe – to gramatyki,które generują języki bezkontekstowe. Są rozpoznawalne przez automaty ze stosem.
Gramatyka formalna to sposób opisu języka formalnego. Aby określić gramatykę formalną trzeba zdefiniować zbiór symboli nieterminalnych,zbiór symboli terminalnych,zbiór reguł produkcji określających w jaki sposób wyprowadzane są słowa oraz symbol początkowy.
Gramatyki kontekstowe – to gramatyki,które generują języki kontekstowe. Są rozpoznawalne przez automaty liniowo ograniczone.
Gramatyki regularne –to gramatyki,które generują języki regularne. Są rrozpoznawalne przez automaty skończone
Gramatyki rekurencyjnie przeliczalne – to gramatyki,które generują języki rekurencyjnie przeliczalne. Odpowiadają maszynom Turinga.
Gramatyka wieloznaczna to gramatyka,której język zawiera przynajmniej jedno zdanie wieloznaczne. Gramatyka nie zawierająca zdania wieloznacznego to gramatyka jednoznaczna.
M
Metajęzyk to język służący do opisu innego języka.
Metoda generacyjna to metoda rozbioru zdań,w której analizę rozpoczynamy od wyróżnionego symbolu gramatyki,stosując kolejno odpowiednie produkcje do najbardziej na lewo położonego symbolu nieterminalnego.
Metoda redukcyjna to metoda rozbioru zdań,w której poprzez kolejne redukcje analizowanej na danym etapie formy zdaniowej dochodzimy ostatecznie do symbolu wyróżnionego gramatyki.
N
Notacja BNF (ang Backus-Naur Form) to metoda definiowania języka formalnego. Jest powszechnie wykorzystywana w informatyce do zapisu składni języków programowania.
P
Potęga złożeniowa n języka L,co oznaczamy Ln,gdzie n≥0,nazywamy n-krotne złożenie języka n = L…L (n)
Możemy to także określić następująco:
L0={ε}
Ln=LLn-1
Pragmatyka to zespół reguł i zaleceń mówiących o tym,jak stosować składnię i semantykę języka. Bada relacje pomiędzy językiem i jego użytkownikami,pozwala na tworzenie różnych form lingwistycznych o zbliżonym znaczeniu semantycznym i mówi,które z tych form lepiej jest wybrać.
R
Rozbiór formy β do α to ciąg numerów produkcji stosowanych w kolejnych krokach aby zredukować formę β do α.
Rozbiór kanoniczny to rozbiór,który zawsze rozpoczyna się od lewej strony redukowanej formy zdaniowej,tzn. w pierwszej kolejności redukowane są lewostronne symbole formy.
S
Semantyka to opis znaczenia przypisywanego zdaniom poprawnym,czyli odniesienie wygenerowanych zdań do rzeczywistości. Semantyka bada także relacje pomiędzy podstawowym znaczeniem wyrazu,a jego użyciem w konkretnej wypowiedzi.
Składnia ->Syntaktyka
Słowo to dowolny skończony ciąg z powtórzeniami elementów z alfabetu V.
Symbol pusty to łańcuch nie zawierający żadnego symbolu. Oznaczany literą ε.
Symbol terminalny to symbol,który buduje język właściwy,występuje w generowanym słowie języka.
Symbol nieterminalny to symbol pomocny przy budowie języka,nie może wystąpić w generowanym słowie języka.
Syntaktyka (składnia) to opis reguł konstrukcji języka pozwalających na zbudowanie wszystkich zdań uznanych za poprawne dla tego języka.
T
Translator to program,lub zespół programów,tłumaczący program źródłowy na równoważny mu program docelowy.
Z
Zdanie wieloznaczne to zdanie,dla którego istnieje więcej niż jedno drzewo syntaktyczne wyprowadzania takiego zdania.
Złożenie języków L1 i L2 to L1L2 ={xy:x ∈ L1 ∧ y ∈ L2}
