WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
1
Wstęp do Teorii Języków
i
Automatów
J
J
A
A
N
N
R
R
O
O
S
S
E
E
K
K
I
I
N
N
S
S
T
T
Y
Y
T
T
U
U
T
T
I
I
N
N
F
F
O
O
R
R
M
M
A
A
T
T
Y
Y
K
K
I
I
U
U
N
N
I
I
W
W
E
E
R
R
S
S
Y
Y
T
T
E
E
T
T
U
U
J
J
A
A
G
G
I
I
E
E
L
L
L
L
O
O
Ń
Ń
S
S
K
K
I
I
E
E
G
G
O
O
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
2
1.W
STĘP
Konstrukcja
translatorów jest nadal ważną elementem umiejętności informatycznych,
wymaganych od informatyków, dlatego potrzebna jest podstawowa wiedza z teorii języków
formalnych i automatycznego rozpoznawania składni. Wiedza ta pozwoli konstruktorowi
translatora na lepsze zrozumienie poszczególnych etapów translacji i może pomóc
programować systematyczniej i efektywniej.
Przedstawione w tym materiale podstawy teorii języków formalnych, w szczególności
języków regularnych i automatów skończonych jak również języków bezkontekstowych i
automatów ze stosem mają bezpośrednie zastosowanie w konstrukcji takich modułów
kompilatora jak analizator leksykalny czy analizator składniowy.
Oprócz analizy leksykalnej i analizy składniowej w miarę dobre podstawy teoretyczne
można znaleźć do opisu semantyki języków, głównie za sprawą prac D. Knutha,
poświęconym gramatyką atrybutowanym.
1
Niestety programowanie wielu elementów translatora, takich jak tablice symboli,
generacja kodu wynikowego czy gospodarka pamięcią w czasie generacji kodu, wymaga od
programisty znajomości metod i systemów komputerowych, które powstają w zespołach
programistów w toku prac prowadzonych nad konstruowaniem kompilatorów dla
konkretnych języków.
W poniższym materiale zebrano zarówno dobrze znane w literaturze podstawy
teoretyczne
2
z zakresu teorii języków i automatów jak i praktyczne metody stosowane przy
konstrukcji kompilatorów
3
1
Knuth, D.E. ‘Semantics of context-free languages’
2
Aho, A. V. , Ullman J. D. , ‘The theory of parsing, translation and compiling’ vol. 1: Parsing, vol. 2:
Compiling.
3
D. Gries, ‘Konstrukcja translatorów dla maszyn cyfrowych’
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
3
W szczególności szczegółowy opis materiału obejmuje:
- Języki formalne, gramatyki i ich klasyfikacja,
- Wyrażenia regularne.
- Automaty
skończenie stanowe.
- Automaty ze stosem.
- Struktura
kompilatora.
2. J
ĘZYKI FORMALNE
Definicja 2.1
Językiem formalnym nazywamy każdy system, w którym stosując dobrze określone
reguły należące do ustalonego zbioru - możemy uzyskać wszystkie napisy (zdania) w tym
języku.
Różnica pomiędzy językiem etnicznym a językiem formalnym polega na tym, że dla
języków etnicznych nie znamy zbioru reguł, których stosowanie powiłoby otrzymać
wszystkie zdania tych języków.
Prowadzone od dawna prace nad językami etnicznymi, doprowadziły do opracowania już
reguł pozwalających uzyskiwać pewne podzbiory wszystkich zdań tych języków.
Wśród różnych aspektów języków formalnych takich jak:
1. syntaktyka (składnia)
2. semantyka
3. pragmatyka.
Najłatwiej można sformalizować składnię języka, która identyfikuje się z gramatyką języka.
Udowodniono, że nie dla każdego języka formalnego da się zbudować gramatykę.
Na przykład nie istnieje gramatyka dla języka składającego się ze wszystkich twierdzeń
arytmetyki, bowiem nie istnieje metoda stwierdzenia, czy dowolna hipoteza arytmetyczna
należy do języka, czy też nie.
Z praktycznego punktu widzenia najbardziej interesujące wydają się być takie języki dla,
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
4
których istnieją gramatyki - należą do nich języki programowania.
Formalna
składnia języka to zbiór reguł, które pozwalają generować syntaktycznie
poprawne zdania rozważanego języka.
Przykładowo dla pewnego podzbioru języka polskiego możemy przyjąć następujący zbiór
reguł:
1. <ZDANIE> Æ <GRUPA_PODMIOTU> <GRUPA_ORZECZENIA>
2. <GRUPA_PODMIOTU> Æ <PODMIOT_ROZWINIĘTY>
3. <PODMIOT_ROZWINIĘTY> Æ
<OKREŚLENIE_PODMIOTU><PODMIOT_ZASADNICZY>
4. <GRUPA_ORZECZENIA> Æ
<OKREŚLENIE_ORZECZENIA><ORZECZENIE_IMIENNE>
5. <ORZECZENIE_IMIENNE> Æ <ŁĄCZNIK><ORZECZNIK>
6. <ŁĄCZNIK< Æ jest
7. <ORZECZNIK> Æ piekarzem
8. | wiewiórką
9. <OKREŚLENIE_ORZECZNIKA> Æ <DOPEŁNIENIE>
10. | <OKOLICZNIK>
11. <DOPEŁNIENIE> Æ <DOPEŁNIENIE_BLIŻSZE>
12. | <DOPEŁNIENIE_DALSZE>
13. <PODMIOT_ZASADNICZY> Æ Janek
14. <OKREŚLENIE_PODMIOTU> Æ <PRZYDAWKA>
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
5
15. <OKOLICZNIK> Æ <OKOLICZNIK_CZASU>
16. <OKOLICZNIK_CZASU> Æ od dawna
17. | dzisiaj
18. <PRZYDAWKA> Æ wysoki
19. | wesoły
W tych regułach w nawiasach < > występują tzw. symbole nieterminalne - czyli nazwy
pewnych części zdań, które należy zastąpić przez symbole terminalne np. Janek, od dawna,
dzisiaj ......
Zastępowanie takie nazywane wywodzeniem wymaga niekiedy stosowania całego łańcucha
reguł, np.:
<ZDANIE> Æ
(1)
<GRUPA_PODMIOTU><GRUPA_ORZECZENIA>Æ
(2)
<PODMIOT_ROZWINIĘTY> <GRUPA_ORZECZENIA> Æ
(4)
<PODMIOT_ROZWINIĘTY> <OKREŚLENIE_ORZECZENIA>
<ORZECZENIE_IMIENNE> Æ
(3)
<OKREŚLENIE_PODMIOTU> <PODMIOT_ZASADNICZY>
<OKREŚLENIE_ORZECZENIA> <ORZECZENIE_IMIENNE> Æ
(14)
<PRZYDAWKA> <PODMIOT_ZASADNICZY> <OKREŚLENIE_ORZECZENIA>
<ORZECZENIE_IMIENNE> Æ
(18)
wysoki <PODMIOT_ZASADNICZY> <OKREŚLENIE_ORZECZENIA>
<ORZECZENIE_IMIENNE>Æ
(13)
wysoki Janek <OKREŚLENIE_ORZECZENIA><ORZECZENIE_IMIENNE> Æ
(10)
wysoki Janek <OKOLICZNIK> <ORZECZENIE_IMIENNE> Æ
(15)
wysoki Janek <OKOLICZNIK_CZASU><ORZECZENIE_IMIENNE> Æ
(17)
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
6
wysoki Janek dzisiaj <ORZECZENIE_IMIENNE> Æ
(5)
wysoki Janek dzisiaj <ŁĄCZNIK><ORZECZNIK> Æ
(6)
wysoki Janek dzisiaj jest <ORZECZNIK> Æ
(7)
wysoki Janek dzisiaj jest piekarzem
U
WAGI
Stosując podane reguły można jednak równie dobrze wygenerować zdanie: " wysoki Janek
od dawna jest wiewiórką - czyli zdanie syntaktycznie poprawne, aczkolwiek mało
sensowne.
W innym przypadku, gdybyśmy zastosowali regułę: <OKREŚLENIE_ORZECZENIA> Æ
<DOPEŁNIENIE> , nie wygenerujemy żadnego słowa, gdyż dla nieterminali
<DOPEŁNIENIE_BLIŻSZE> oraz <DOPEŁNIENIE_DALSZE> nie zostały określone
reguły, pozwalające na zastąpienie ich przez symbole terminale - w takim przypadku mówimy
o niekompletności podanego zbioru reguł.
Niektóre reguły mogą mieć postać, w której po prawej stronie strzałki ( Æ ) występuje pusty
ciąg symboli (
ε), np. <OKREŚLENIE_ORZECZENIA> Æ ε , pozwala to wzbogacić zbiór
generowanych zdań.
Jak widać same tylko reguły syntaktyczne gramatyki formalnej nie gwarantują
sensowności otrzymywanych zdań, aczkolwiek zdania te mogą być syntaktycznie poprawne.
Sensowność zdań języka - czyli jego semantykę, dużo trudniej ująć w sformalizowane reguły.
Badania nad sformalizowaniem semantyki języków programowania należą do
najciekawszych i najważniejszych problemów informatyki. Ich zasadnicza trudność polega na
tym, że chcąc wyrazić sens jakiegoś zdania posługujemy się zazwyczaj jakimś innym
językiem, którego semantyka również wymaga definicji itd.
Aby znaleźć jakieś wyjście, przyjmujemy, że zadany jest pewien ustalony zbiór zdań o
semantyce nie wymagającej dalszych wyjaśnień - aksjomatów. Zbiór ten tworzy język
formalny, używany do wyjaśnienia semantyki zdań w innych językach. Autorem wielu prac
korzystających z takiego podejścia jest D. Knuth.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
7
Najtrudniej sformalizować trzeci podstawowy aspekt języka tzw. pragmatykę.
Pragmatyka języka obejmuje zalecenia dotyczące używania różnych poprawnych form
lingwistycznych o zbliżonym znaczeniu semantycznym.
UWAGA
Oprócz problemu generowania wszystkich zdań danego języka na podstawie zadanego zbioru
reguł, rozważa się również problem dualny:
" Jak stwierdzić czy pewien napis jest zdaniem w danym języku".
Problem ten jest zasadniczy dla języków programowania, gdyż do niego właśnie ( w pewnym
przybliżeniu) sprowadza się zadanie określenia formalnej, a przynajmniej syntaktycznej
poprawności programów.
3. S
YMBOLE I SŁOWA
Definicja 3.1
Alfabetem nazywamy dowolny, niepusty zbiór elementów zwanych symbolami.
Słowem nazywamy dowolny, skończony ciąg symboli (konkatenacja)
symboli.
Przez
ε
oznaczamy słowo puste, które nie zawiera żadnego symbolu.
Przez | w |
- oznaczamy długość słowa, czyli liczbę symboli w słowie
w.
Tak więc
A=
{a, b, c} - alfabet
Słowa: a, b, c, ab, aaca, ... | a | = 1, | abc | = 3, oraz |
ε | = 0.
Niech w = ab i u = bc , przez konkatenację słów: w i u oznaczamy słowo
wu = abbc.
Zauważmy, że
ε w = w ε = w dla dowolnego słowa w.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
8
Definicja 3.2
Jeśli W i U
-
oznaczają zbiory słów nad pewnym alfabetem, to
złożeniem zbiorów słów nazywamy zbiór:
WU =
{ wu : w ∈W, u∈U}
Definicja 3.3
Potęgę słowa ‘
w’
definiujemy następująco:
w
0
=
ε , w
1
= w, w
2
= ww, w
n
= w ... w ,
n - razy
Definicja 3.4
Potęgę alfabetu A definiujemy podobnie:
A
0
=
{ε}, A
1
= A , A
2
= AA, A
n
= AA
n-1
, n>0
Oraz
A
+
= A
∪ A
2
∪ ... ∪ A
n
∪ ...
A
*
= A
0
∪ A
+
Np.
A =
{a, b}
A
+
= { a, b, ab, ba, aa, bb, aab, ... } – zbiór wszystkich słów nad alfabetem A.
A
*
= {
ε, a, b, ab, ba, aab, ...} = {ε} ∪ A
+
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
9
4. G
RAMATYKI
Definicja 4.1
Gramatyką nazywamy czwórkę:
G = ( N,
∑, P, S )
, gdzie:
N-skończony, niepusty zbiór symboli nieterminalnych ( pomocniczych ),
∑-skończony, niepusty zbiór symboli terminalnych ( końcowych ),
przy czym: N
∩ ∑ = ∅ .
Sumę obu zbiorów oznaczamy: V = N ∪ ∑ .
P - skończony zbiór reguł ( produkcji ): P
⊂ V
*
N V
*
× V
*
,
Dowolną regułę (α, β)∈P , zapisujemy w postaci: α→β, mówimy, że α-jest
lewą stroną produkcji (poprzednik) β- stroną prawą (następnik).
S
∈ N - symbol startowy, (głowa) gramatyki.
Obecnie zdefiniujemy relację wywodu (
⇒) w gramatyce G: ( ⇒) ∈
V
*
× V
*
.
Definicja 4.2
Niech u, w
∈ V
*
- słowa, mówimy, że słowo u wywodzi słowo w ,
(u
⇒w), jeśli istnieją słowa: x, y ∈ V
*
oraz produkcja: (
α → β ) ∈ P taka, że u =
x
α y , w = x β y.
Przechodnie domknięcie relacji wywodu (
⇒) - oznaczamy ( ⇒
+
), a zwrotne i przechodnie
domknięcie - przez (
⇒
*
).
Definicja 4.3
Językiem generowanym przez gramatykę G nazywamy zbiór:
L(G) = { w
∈ ∑
*
: S
⇒
*
w }
Dla dowolnego słowa należącego do L(G) - ciąg numerów produkcji użytych do
wygenerowania słowa nazywamy - wywodem, przy czym - dla gramatyk bezkontekstowych,
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
10
gdy w kolejnych krokach wywodzenia będziemy zawsze stosować produkcję do skrajnie
lewego symbolu nieterminalnego - wówczas taki wywód nazywamy - lewostronnym, jeśli
zaś wybierzemy produkcję zawsze do skrajnie prawego symbolu nieterminalnego - wówczas
taki wywód nazywamy - prawostronnym.
5. K
LASYFIKACJA GRAMATYK
Nakładając stopniowo coraz większe ograniczenia na postać produkcji A.N. Chomsky
4
-
dokonał podziału gramatyk, definiując cztery typy gramatyk a co za tym idzie cztery klasy
języków formalnych.
Gramatyki klasy 0 - (G
0
) - na ich produkcje nie nakłada się żadnych
restrykcji.
Gramatyki klasy 1 - (G
1
) zwane też gramatykami kontekstowymi,
których produkcje mają postać: α A β → α b β , przy czym: α, β ∈ V
*
,
A ∈ N, b ∈ V
*
.
Gramatyki klasy 2 - (G
2
) zwane też gramatykami bezkontekstowymi,
których produkcje mają postać: A → α , przy czym: A ∈ N, α ∈ V
*
.
Gramatyki klasy 3 - (G
3
) zwane też gramatykami regularnymi, których
produkcje mają postać: ( A → a ∨ A → a B ) albo ( A → a ∨ A → B a )
, przy czym: a ∈ ∑ , B ∈ N.
4
A.N. Chomsky - ur. 1928, amerykański logik i lingwista
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
11
Uwaga
G
3
⊂ G
2
⊂ G
1
⊂ G
0
- gramatyka klasy ' i ' jest jednocześnie gramatyką klasy ' j ' , dla 0
≤
j
≤ i . Inaczej mówiąc - każda gramatyka regularna jest gramatyką bezkontekstową, każda
gramatyka bezkontekstowa jest gramatyką kontekstową, itd.
Odwrotne twierdzenie nie jest prawdziwe, można podać przykłady zbiorów słów
wywiedlnych w gramatyce klasy ' i ', dla których nie można skonstruować gramatyki wyższej
klasy.
Klasyczny przykład:
Niech słowo w = aa ... a bb ... b cc ... c
k l m
Jeśli nie nakładamy żadnych ograniczeń na wartości: k, l, m - to można zbudować gramatykę
regularną generującą powyższe słowa o następujących produkcjach:
S
→ a S | a V ,
V
→ b V | b U ,
U
→ c U | c
Jeśli chcemy, by k = m, to nie można zbudować gramatyki regularnej generującej podane
słowa, natomiast można określić gramatykę bezkontekstową o następujących produkcjach:
S
→ a S c | a V c, V → V b | b
Jeśli chcemy by, k = m = l - to do generacji takich słów musimy użyć gramatyki
kontekstowej lub gramatyki klasy 0, np.
S
→ a b c | a S U c , c U → U c , b U → b b .
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
12
6.
N
IESKRACALNOŚĆ GRAMATYKI
Jeśli w definicji gramatyk klas 1, 2 i 3 przyjmiemy, że po prawej stronie produkcji nie
występuje słowo puste (
ε) - wówczas gramatyki te nazwiemy nieskracalnymi, to znaczy, że
zastosowanie produkcji do ciągu symboli daje w wyniku ciąg symboli nie krótszy od
wyjściowego.
Nieskracalność gramatyki ułatwia rozstrzygnięcie problemu, czy zadany skończony ciąg
symboli terminalnych -
w
, jest wywiedlny z głowy gramatyki.
Istotnie, rozważmy wszystkie produkcje, w których poprzednikiem jest głowa
gramatyki - S, następniki tych produkcji nazwiemy wnioskami pierwszego poziomu. Jeśli
wśród tych wniosków są ciągi symboli terminalnych o długości takiej jak zadany ciąg - to
możemy sprawdzić czy wśród nich znajduje się ciąg
w.
Jeśli nie, to do wniosków pierwszego poziomu, liczących nie więcej niż 'k' elementów,
stosujemy wszystkie produkcje, których poprzedniki znajdują się wśród elementów wniosków
pierwszego poziomu.
Postępując analogicznie - uzyskujemy wnioski poziomu drugiego, trzeciego, itd. Ze
skończoności zbioru produkcji i nieskracalności gramatyki wynika, że opisywany proces musi
się skończyć albo napotkaniem ciągu - w, albo wyczerpaniem wszystkich możliwości.
Wniosek
Tak więc dla gramatyk co najmniej kontekstowych można zbudować algorytm,
rozstrzygający - czy dowolne słowo nad alfabetem terminalnym należy do języka
generowanego przez gramatykę.
Języki mające tę własność nazywamy językami obliczalnymi , a ich gramatyki -
gramatykami rozstrzygalnymi.
Oprócz problemu o rozstrzygalności gramatyki - interesuje nas zazwyczaj także sposób w jaki
dane słowo wywodzi się z głowy gramatyki.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
13
Przykład.
Rozważmy gramatykę: G
1
= ( N,
∑, P, S )
Gdzie:
N = { S }, ∑ = { ( , ), +, *, a, b, c }
P = { 1. S Æ ( S )
2. S Æ S * S
3. S Æ S + S
4. S Æ a
5. S Æ b
6. S Æ c }
Gramatyka G
1
jest gramatyką bezkontekstową, L(G
1
) - jest językiem prostych wyrażeń
algebraicznych trzech zmiennych: a, b, c.
Weźmy słowo: w = a + b * c - należące do L(G
1
).
Zauważmy, że słowo - w, można wywieść lewostronnie - na dwa sposoby:
S
⇒
(2)
S * S
⇒
(3)
S + S * S
⇒
(4)
a + S * S
⇒
(5)
a + b * S
⇒
(6)
a + b * c
S
⇒
(3)
S + S
⇒
(4)
a + S
⇒
(2)
a + S * S
⇒
(5)
a + b * S
⇒
(6)
a + b * c
Dla słowa - w, otrzymaliśmy zatem dwa drzewa wywodu:
S
S
S
*
S
+
S
a
b
c
(1)
S
S + S
S * S
a
b
c
(2)
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
14
Definicja 6.1
Gramatykę, w której dla pewnego słowa istnieje więcej niż jeden
wywód lewostronny lub więcej niż jeden wywód prawostronny - nazywamy
gramatyką niejednoznaczną.
Niejednoznaczność gramatyki jest na ogół przeszkodą przy ścisłym formułowaniu
semantyki języka generowanego przez daną gramatykę. Zauważmy, że własność
jednoznaczności lub niejednoznaczności przypisujemy gramatyce, a nie generowanemu przez
nią językowi.
Zmieniając odpowiednio gramatykę niejednoznaczną - oczywiście bez naruszania
generowanego przez nią języka - możemy niekiedy otrzymać gramatykę jednoznaczną.
Istnieją jednak języki, dla których nie istnieją generujące je gramatyki jednoznaczne.
Takie języki nazywamy istotnie wieloznacznymi - na szczęście języki programowania nie
należą do tej grupy.
Udowodniono , że jednoznaczność jest problemem nierozstrzygalnym.
Oznacza to, że nie istnieje żaden algorytm, który dla dowolnej gramatyki mógłby w
sposób niezawodny i w skończonym czasie wykryć jednoznaczność lub niejednoznaczność
gramatyki.
Wszystko co można w tym zakresie czynić sprowadza się do formułowania dość
prostych - choć nie trywialnych - warunków, których spełnienie przez gramatykę gwarantuje
jej jednoznaczność.
W powyższym przykładzie gramatyki - niejednoznaczność oznacza, że w wyrażeniach
algebraicznych operacja mnożenia może być działaniem wykonywanym równie dobrze przed
jak i po dodawaniu.
Gramatyką jednoznaczną - generującą ten sam język jest gramatyka G
2
o produkcjach:
1. S Æ S + T
2. | T
3. T Æ T * F
4. | F
5. F Æ ( S )
6. | a
7. | b
8. | c
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
15
W tej gramatyce dane słowo w = a * b + c - posiada tylko jeden wywód
lewostronny lub tylko jeden wywód prawostronny - w konsekwencji - jedno drzewo wywodu.
Powyższa gramatyka jest nie tylko jednoznaczna ale również określa kolejność wykonywania
działań arytmetycznych mnożenia i dodawania.
7.
P
RZYKŁADY GRAMATYK
G
3
= ( { S, A }, { 0, 1 }, { S Æ 0 A 1, 0 A Æ 0 0 A 1, A Æ ε }, S )
Rozważmy następujące wywody:
S
⇒ 0 A 1 ⇒ 0 0 A 1 1 ⇒ 0 0 1 1
S
⇒ 0 A 1 ⇒ 0 0 A 1 1 ⇒ 0 0 0 A 1 1 1⇒ 0 0 0 1 1 1
Można pokazać przez indukcję, że L( G
3
) = { 0
n
1
n
, n
≥ 1 }
G
4
= ( N = { S, B, C }, ∑ = { a, b, c},
P = { S Æ a S B C | a b c , c B Æ B C , b B Æ b b ,
b C Æ b c , c C Æ c c }, S )
Zauważmy, że abc - najkrótsze słowo, należące do L(G
4
), oraz
S
⇒ a S B C ⇒ a a b c B C ⇒ a a b B C C ⇒ a a b b C C ⇒ a a b b c C ⇒ a a b b c c
Postępując analogicznie można pokazać, że L( G
4
) = { a
n
b
n
c
n
, n
≥ 1 }.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
16
G
5
= ( { S }, { a, b, c }, { S Æ a S a | b S b | c }, S )
Rozważmy wywód: S
⇒ a S a ⇒ a a S a a ⇒ a a b S b a a ⇒ a a b c b a a,
Stosując na przemian produkcje: S
⇒ a S a lub S ⇒ b S b - oraz na końcu S ⇒ c,
łatwo można zauważyć, że otrzymujemy słowa, w których po 'c' jest słowo, będące rewersem
słowa występującego przed 'c'. Tak więc: L( G
5
) = { w c w
←
| w
∈ { a, b }
*
}.
G
6
= ( { S, A }, { a, b } , { S Æ a A , A Æ A b }, S )
Nietrudno zauważyć, że L( G
6
) =
∅ - jest pusty, ponieważ nigdy nie otrzymamy
słowa składającego się tylko z symboli terminalnych.
G
7
: N = { < LICZBA>, <CZĘŚĆ_CAŁKOWITA>,
<CZĘŚĆ_UŁAMKOWA>, <NIE_ZERO>, <CIĄG_CYFR>, <CYFRA> }
∑ = {. , 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
P = { <LICZBA> Æ <CZĘŚĆ_CAŁKOWITA>
| <CZĘŚĆ_CAŁKOWITA> . <CZĘŚĆ_UŁAMKOWA>
<CZĘŚĆ_CAŁKOWITA> Æ 0
| <NIE_ZERO> <CIĄG_CYFR>
<NIE_ZERO>
Æ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<CIĄG_CYFR> Æ ε | <CYFRA> <CIĄG_CYFR>
<CYFRA>
Æ 0 | <NIE_ZERO>
<CZĘŚĆ_UŁAMKOWA> Æ <CYFRA> <CIĄG_CYFR> }
S = <LICZBA>
L( G
7
) - zawiera napisy odpowiadające nieujemnym liczbom rzeczywistym w zapisie
dziesiętnym
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
17
8. W
YRAŻENIA I ZBIORY REGULARNE
Wyrażenia regularne odgrywają istotną rolę w teorii języków formalnych, gdyż
opisują podobnie jak gramatyki regularne bardzo ważną - z praktycznego punktu widzenia -
klasę języków, mianowicie - język symboli leksykalnych, takich jak: liczby, identyfikatory,
operatory i symbole specjalne - występujące w językach programowania.
Definicja 8.1
Niech ∑ - alfabet skończony. Zbiór regularny nad alfabetem ∑
definiujemy następująco:
∅ - zbiór pusty - jest zbiorem regularnym nad ∑,
{ε} - zbiór zawierający słowo puste-jest zbiorem regularnym nad ∑,
{a} - jest zbiorem regularnym nad ∑, dla każdego a∈∑,
Jeśli P i Q - są zbiorami regularnymi nad ∑ - to również zbiory:
P∪Q, P⋅Q oraz P
*
- są zbiorami regularnymi nad ∑,
Nic innego nie jest zbiorem regularnym nad ∑.
Inaczej mówiąc - pewien zbiór jest zbiorem regularnym nad
∑, tylko wtedy gdy jest bądź
zbiorem pustym, bądź jest równy {
ε}, lub jest równy {a} dla dowolnego a ∈ ∑, bądź może
być sumą, konkatenacją lub nieskończoną iteracją pewnych zbiorów regularnych.
Wygodnym sposobem definiowania zbiorów regularnych są wyrażenia regularne.
Definicja 8.2
Wyrażenie regularne nad alfabetem ∑ i zbiór regularny, który ono
wyznacza definiujemy następująco:
∅-jest wyrażeniem regularnym, wyznaczającym zbiór regularny - ∅
ε-jest wyrażeniem regularnym, wyznaczającym zbiór regularny-{ε },
Jeśli a∈∑, to a-jest wyrażeniem regularnym, wyznaczającym zbiór {a }
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
18
Jeśli p i q - są wyrażeniami regularnymi, wyznaczającymi zbiory
regularne: P i Q to ( p+q ), ( pq ) oraz ( p )
*
- są też wyrażeniami
regularnymi, wyznaczającymi odpowiednio zbiory: P∪Q, P⋅Q oraz P
*
Nic innego nie jest wyrażeniem regularnym.
Będziemy również wykorzystywać zapis p
+
dla skracania zapisu: pp
*
. Poniżej podano kilka
przykładów wyrażeń regularnych i wyznaczonych przez nie zbiorów regularnych.
Przykłady.
0 1 - jest wyrażeniem wyznaczającym zbiór: { 0 1 }
0
*
- jest wyrażeniem wyznaczającym zbiór: { 0 }
*
( 0 + 1 )
*
- jest wyrażeniem wyznaczającym zbiór: { 0, 1 }
*
- liczby w zapisie binarnym,
( 0 + 1 )
*
011 - jest wyrażeniem wyznaczającym zbiór ciągów składających się z 0 i 1,
zakończonych: 011
( 1 0 )
*
+ ( 0 1 )
*
- jest wyrażeniem wyznaczającym zbiór ciągów z 0 i 1, o równej liczbie
zer i jedynek.
( 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 )
+
- jest wyrażeniem wyznaczającym zbiór liczb
całkowitych nieujemnych.
( litera ) ( litera + cyfra + _ )
*
- jest wyrażeniem wyznaczającym zbiór identyfikatorów.
F
AKTY
1. Dla każdego zbioru regularnego nad pewnym alfabetem można podać co najmniej jedno
wyrażenie regularne - wyznaczające ten zbiór.
2. Istnieje nieskończenie wiele wyrażeń regularnych, wyznaczających dany zbiór regularny.
3. Dwa wyrażenia regularne są równoważne, gdy opisują ten sam zbiór regularny.
4. Zbiór A - jest zbiorem regularnym nad alfabetem
∑ wtedy i tylko wtedy, gdy jest
językiem regularnym, tzn. jeśli istnieje gramatyka regularna G - taka , że L(G)= A.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
19
8.1 Lemat o rozrastaniu dla zbiorów regularnych.
Innym z ważniejszych faktów dotyczących zbiorów regularnych jest lemat o rozrastaniu dla
zbiorów regularnych., który mówi, że dla słowa dostatecznie długiego, należącego do zbioru
regularnego - można wydzielić w nim podsłowo, które powtarzane dowolną ilość razy - da
nowe słowa, które będą należeć do danego zbioru regularnego.
L
EMAT
Niech L - jest zbiorem regularnym.
Istnieje liczba p > 0 taka, że jeśli w ∈ L i |w| ≥ p
to w = x y z , 0 < |y| ≤ p oraz x y
i
z ∈ L ∀ i ≥ 0.
Lemat ten jest pomocny przy dowodzeniu 'nie wprost' , że jakiś zbiór nie jest zbiorem
regularnym.
Udowodnimy teraz:
L
EMAT
.
Zbiór L = { 0
n
1
n
: n
≥1 } - nie jest zbiorem regularnym.
Dowód.
Hp. Załóżmy, że L - jest regularny,
A więc zgodnie z powyższym lematem, dla dostatecznie dużego n,
słowo w = 0
n
1
n
da się przedstawić w postaci konkatenacji słów: x, y, z ,
tzn: w = xyz i y
≠ε oraz ∀ i ≥0 xy
i
z ∈ L.
Tym czasem ponieważ y
≠ε - mogą zajść następujące przypadki:
1. y
∈0
+
lub y∈1
+
i wówczas słowo xy
0
z = xz ∉ L - 'xz' nie może zawierać tyle samo
zer co i jedynek.
2. y
∈0
+
1
+
- wówczas słowo xyyz ∉ L - np. x0101z ≠ 0
k
1
k
∀ k ≥ 0.
Tak więc otrzymujemy sprzeczność - ostatecznie zbiór L - nie może być regularny.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
20
9. A
UTOMAT SKOŃCZONY
a
w
A
q
wejście
głowica
aktualny stan
q
Automat
skończony, zwany również automatem skończenie stanowy jest jednym z
najprostszych systemów rozpoznających.
Zwykle składa się z wejścia zawierającego badane słowa, przy czym aktualnie czytany
symbol danego słowa wskazuje głowica, która przesuwa się w prawo o jeden symbol.
Wyposażony ponad to w funkcję przejścia - automat rozpoznając dane słowo -
rozpoczyna pracę w stanie początkowym, a następnie pod wpływem następnych symboli,
przechodzi do kolejnych stanów aż osiągnięty zostanie koniec słowa - wówczas jeśli automat
znajdzie się w którymś ze stanów końcowych - następuje akceptacja (rozpoznanie) danego
słowa - w przeciwnym przypadku, badane słowo nie jest akceptowane.
Definicja 9.1
Automat skończony (niedeterministyczny) jest piątką:
A = ( Q, ∑,
δ
, q
0
, F ),
Gdzie:
Q - skończony zbiór stanów automatu,
∑ - skończony zbiór symboli wejściowych (alfabet),
δ -
funkcja przejścia, przy czym:
δ
: Q × ∑ Æ
P
(Q) funkcja ta
odwzorowuje parę: ( stan, symbol ) w podzbiór stanów Q.
q
0
∈
Q - stan początkowy,
F ⊆
Q - zbiór stanów końcowych.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
21
Aby sformalizować opis działania automatu skończonego zdefiniujemy pojęcie konfiguracji
automatu i określimy relację: ‘
¬ ‘
na zbiorze konfiguracji.
Definicja 9.2
Konfiguracją automatu skończonego A = ( Q, ∑,
δ
, q
0
, F ), nazywamy parę:
(q, w)
∈ Q × ∑
*
,
przy czym:
(q
0
, w) - nazywamy konfiguracją początkową,
natomiast: (q, ε), gdy q∈F - nazywamy konfiguracją
końcową (akceptującą ).
Działanie automatu A określa relacja :
¬
na zbiorze konfiguracji, którą
definiujemy następująco:
( q, aw )
¬ ( q′, w )
⇔ q ′ ∈
δ
(q, a) dla każdego w
∈∑
*
i a
∈∑.
Oznacza to, że jeśli automat A znajduje się w stanie 'q' oraz głowica jest ustawiona na
symbolu 'a'- to automat wykona takt, w którym automat przejdzie do stanu ' q
′ ' i głowica
przesunie się o jedną pozycję w prawo.
Ponieważ automat jest niedeterministyczny - przejście może nastąpić do dowolnego ze
stanów należących do
δ
( q, a ).
Definicja 9.3
Język akceptowany przez automat skończony - L(A) definiujemy:
L(A)
=
{
w
∈∑
*
: ( q
0
, w )
¬
*
( q,
ε ), gdy q∈F }
P
RZYKŁAD
.
Rozważmy automat: A = ( { p, q, r }, { 0, 1 },
δ
, p, { r } )
przy czym funkcję przejścia
δ,
definiuje poniższa tabelka:
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
22
δ 0 1
p {q} {p}
q {r} {p}
r {r} {r}
Bardzo wygodnym sposobem reprezentacji automatu skończonego jest graf
skierowany, w którym stany automatu są reprezentowane przez węzły grafu - a funkcja
przejścia jest reprezentowana przez krawędzie etykietowane przez symbole alfabetu .
q
r
p
0
1
0, 1
0
1
stan koñcowy
stan początkowy
Dla słowa w = 01001
∈ L( A ) działanie automatu opisuje następująca sekwencja taktów:
( p, 01001)
¬
(
q, 1001 )
¬
( p, 001 )
¬
( q, 01 )
¬
( r, 1 )
¬
( r,
ε )
Definicja 9.4
Automat skończony A = ( Q, ∑,
δ
, q
0
, F), nazywamy automatem
deterministycznym jeśli zbiór:
δ
(q, a) zawiera co najwyżej jeden stan dla dowolnych q
∈
Q i a
∈ ∑.
Jeśli
δ
(q, a) zawsze zawiera dokładnie jeden stan - wówczas mówimy, że automat A jest z
pełni zdefiniowany.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
23
Twierdzenie 9.1
Dla każdego automatu skończonego niedeterministycznego -
A=(Q , ∑,
δ
, q
0
, F) można skonstruować deterministy automat -
A' = (Q', ∑,
δ'
, q
0
', F' ) taki, że L(A) = L(A')
Konstrukcja automatu deterministycznego A' przebiega w następujący sposób:
Q ' =
P
( Q ) - zbiór podzbiorów zbioru stanów Q
q
0
' = { q
0
}
F ' = { S: S
⊆ Q ∧ S ∩ F ≠ ∅ }
δ' (
S , a ) = S ' :
∀ S ⊆ Q i a ∈ ∑,
przy czym S ' = { p : p
∈
δ' (
q , a )
∧ q ∈ S }.
Łatwo pokazać, że dla tak skonstruowanego automatu A’ zachodzi, że L(A)=L(A’).
Pomiędzy automatami skończonymi a gramatykami regularnymi istnieje ścisły związek
mianowicie:
Lemat 9.1
Jeśli L ( A ) - jest językiem akceptowanym przez pewien
deterministyczny automat skończony - A = ( Q , ∑ ,
δ
, q
0
, F ) - to
istnieje gramatyka regularna G taka, że L(G) = L(A).
Dowód.
Niech A = ( Q ,
∑ ,
δ
, q
0
, F ) - będzie deterministycznym automatem skończonym.
Zbudujemy gramatykę G = { Q ,
∑ , P, q
0
} - przy czym zbiór produkcji wyznaczamy
następująco:
(1)
∀ q ∈ Q i a ∈ ∑ jeśli p =
δ (
q , a ) to P = P
∪ { q Æ a p }
(2)
∀ p ∈ F : P = P ∪ { p Æ ε }
Stosując indukcję matematyczną można pokazać, że
∀ w ∈ ∑ * , q
0
⇒ * w ⇔ ( q
0 ,
w )
¬
*
( p ,
ε ) , dla pewnego p ∈ F .
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
24
9.1 Minimalizacja automatów skończonych.
Dla automatów skończonych jednym z ważnych problemów jest minimalizacja liczby
stanów, prowadzi ona do bardziej efektywnych, równoważnych automatów (akceptujących
ten sam język).
Dla zadanego automatu skończonego usuwając tzw. stany nieosiągalne i
nierozróżnialne można wyznaczyć równoważny mu automat zredukowany - o mniejszej
liczbie stanów.
Poniżej podamy definicje stanów nieosiągalnych i nierozróżnialnych oraz automatu
zredukowanego.
D
EFINICJA
9.5
Niech A=( Q, ∑, δ, q
0
, F) – automat skończony, q
1
, q
2
∈ Q , q
1
≠ q
2
Mówimy, że słowo x∈∑
*
- rozróżnia stany q
1
i q
2
jeśli (q
1
, x ) ¬
*
(q
3
, ε) i
(q
2
, x ) ¬
*
(q
4
, ε) oraz q
3
∈F, q
4
∈Q\F lub q
3
∈ Q\F, q
4
∈F
(jeden ze stanów jest stanem końcowym a drugi nie).
Mówimy, że stany q
1
i q
2
są k-nierozróżnialne ( q
1
≡
k
q
2
) , jeśli nie istnieje
słowo x : |x| < k , rozróżniające stany q
1
i q
2.
Mówimy, że stany q
1
i q
2
są nierozróżnialne ( q
1
≡ q
2
) , jeśli nie są
rozróżnialne dla żadnego k > 0.
Stan q ∈Q nazywamy nieosiągalnym, jeśli nie istnieje słowo x takie,
że
(q
0
, x ) ¬
*
(q
, ε).
Automat nazywamy zredukowanym jeśli zbiór Q nie zawiera stanów
nieosiągalnych i nierozróżnialnych.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
25
Lemat 9.2
Niech A=( Q,
∑, δ, q
0
, F) – automat skończony, przy czym |Q| = n.
Stany q
1
i q
2
są nierozróżnialne ( q
1
≡ q
2
) wtedy i tylko wtedy gdy są n-2 - nierozróżnialne (
q
1
≡
n-2
q
2
).
Dowód wystarczalności warunku jest oczywisty, konieczność warunku wykazuje się
dowodząc, że zachodzi:
⊆ ≡
n-2
⊆ ≡
n-3
⊆ ... ⊆ ≡
2
⊆ ≡
1
⊆ ≡
0
.
Aby to wykazać, zauważmy, że dla dowolnych stanów mamy
:
q
1
i q
2
q
1
≡
0
q
2
⇔ oba stany q
1
i q
2
jednocześnie
należą lub nie należą do F.
q
1
≡
k
q
2
⇔ q
1
≡
k-1
q
2
oraz δ( q
1
, a) ≡
k-1
δ( q
2
, a) ∀ a ∈ ∑.
Relacja
≡
0
wyznacza dwie klasy równoważności : Q\F i F. Jeśli
≡
k+1
≠
≡
k
to liczba klas
równoważności w Q/
≡
k+1
jest przynajmniej o jeden większa niż liczba klas w Q/
≡
k
,
Oznacza to, że przynajmniej jedna klasa w Q/
≡
k
uległa rozdzieleniu na dwie podklasy w Q/
≡
k+1
.
Ponieważ każdy ze zbiorów Q\F i F zawiera co najwyżej n-1 elementów, można otrzymać co
najwyżej n-2 kolejnych jednoelementowych klas relacji.
Jeśli
≡
k+1
=
≡
k
dla pewnego ‘k’ to na podstawie (b) również
≡
k+1
=
≡
k+2
, tak więc relacja
≡
jest równa pierwszej relacji postaci
≡
k
, dla której zachodzi
≡
k+1
=
≡
k
.
Z powyższego lematu wynika wniosek: jeśli dwa stany można rozróżnić to je można
rozróżnić przy pomocy słowa, którego długość jest mniejsza niż liczność zbioru stanów Q.
Poniżej podamy algorytm minimalizacji automatu skończonego.
Algorytm (minimalizacja automatu).
Wejście: Automat skończony: A=( Q,
∑, δ, q
0
, F)
Wyjście: Zredukowany automat A’ równoważny automatowi A.
Metoda:
1. Usunąć ze zbioru stanów Q wszystkie stany nieosiągalne.
2. Wyznaczyć klasy równoważności relacji:
≡
0
,
≡
1
,
≡
2
,
... tak długo aż dla pewnego ‘k’
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
26
zbiory klas równoważności są równe ( Q/
≡
k+1
= Q/
≡
k
).
Za relację ‘
≡’ przyjąć relację ‘≡
k’
.
3. Wyznaczyć automat A’ =( Q’,
∑, δ’, q
0
’, F’ ), w którym
Q’ = Q /
≡ , zbiór klas równoważności relacji ‘≡’,
δ’([q], a ) = [p] , jeśli δ(q, a) = p,
q
0
’= [q
0
],
F’ = { [q], q
∈ F}.
Nie trudno pokazać, że tak otrzymany automat jest równoważny automatowi początkowemu.
Przykład 1.
Rozważmy automat: A = ({q0, q1, q2, q3, q4, q5}, {a, b},
δ ,q0, {q0, q5}), przy czym
funkcję
δ przedstawia poniższy graf.
Zbiór stanów nie zawiera stanów nieosiągalnych. Aby wyznaczyć automat zredukowany
wyznaczymy klasy równoważności kolejnych relacji:
Q /
≡ = {[q0, q5], [q1, q2, q3, q4]}
Q /
≡
1
= {[q0, q5], [q1, q4], [q2, q3]}
Q /
≡
2
= {[q0, q5], [q1, q4], [q2, q3]}
Tak więc graf automatu minimalnego ma następującą postać:
q0
q1
q2
q3
q4
q5
a
a
a
a
a
a
b
b
b
b
b
b
Graf automatu A
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
27
Przykład 2.
Rozważmy automat A = ({ q0, q1, q2, q3, q4, q5, q6}, {0, 1}, ,q0, {q3, q4}), którego
funkcję przejścia opisuje poniższy graf.
W powyższym automacie stany: q5 i q6 są nieosiągalne z q0, a więc można je usunąć,
ponadto wyznaczając klasy równoważności relacji ‘
≡’, łatwo widać, że pary stanów: q1 i q2
oraz q3 i q4 są nierozróżnialne, tzn. q1
≡q2 oraz q3 ≡q4.
Ostatecznie otrzymamy równoważny powyższemu automat minimalny postaci:
[q2,q3]
[q1,q4]
b
b
b
a
a
a
Automat zredukowany
[q0,q5]
q0
q1
q2
q3
q4
q5
q6
0
1
0
0
1
1
0
1
1
1
0
1
0
0
q0
[q1,q2]
[q3,q4]
0, 1
0
1
0
1
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
28
9.2 Przykłady automatów skończonych.
Automat akceptujący liczby binarne - o nieparzystej liczbie zer i parzystej liczbie jedynek.
Rozważmy automat A = ( { PP, NP., PN, NN }, { 0, 1 } ,
δ ,
PP, NP }, przy czym funkcja
przejścia jest zdefiniowana następująco:
δ
0 1
PP NP
PN
NP PP
NN
PN NN
PP
NN PN
NP
Poszczególne stany wyznaczają ciągi zero-jedynkowe, przy czym:
PP -stan, w którym rozpoznano ciąg - o parzystej liczbie zer i parzystej liczbie jedynek,
NP -stan, w którym rozpoznano ciąg - o nieparzystej liczbie zer i parzystej liczbie jedynek,
PN -stan, w którym rozpoznano ciąg - o parzystej liczbie zer i nieparzystej liczbie jedynek,
NN -stan, w którym rozpoznano ciąg - o nieparzystej liczbie zer i nieparzystej liczbie
jedynek.
PP - jest stanem początkowym i ponieważ automat ma akceptować liczby binarne o
nieparzystej liczbie zer i parzystej liczbie jedynek - NP - jest stanem końcowym .
Graficzną reprezentację automatu przedstawia poniższy graf:
PP
PN
PN
NN
0
0
0
0
1
1
1
1
NP
stan końcowy
stan początkowy
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
29
2. Automat akceptujący liczby całkowite - nieujemne , oraz nazwy identyfikatorów,
które zawierają: litery, cyfry i znak podkreślenia, przy czym pierwszym znakiem musi być
litera.
Rozważmy automat:
A = ( { q
0
, q
1
, q
2
}, { l, c, _ },
δ , q
0
, { q
1
, q
2
} ),
Przy czym:
l - jest dowolną literą alfabetu,
c - jest jedną z cyfr: 0, 1, 2, ... , 9,
δ -
definiuje poniższa tabela:
δ
l c _
q
0
q
2
q
1
q
1
q
1
q
2
q
2
q
2
q
2
Weźmy dowolną liczbę np. w = 123, akceptacja tej liczby przebiega następująco:
(q
0
, 123 )
¬
( q
1
, 23 )
¬
(q
1
, 3 ) ¬ (q
1
, ε)
Poniżej przedstawiono graf automatu:
q
q 1
q 2
c
l
c
l , c
akceptacja liczby
akceptacja
identyfikatora
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
30
3. Automat akceptujący:
liczby całkowite - nieujemne,
liczby rzeczywiste - w postaci wykładniczej: ( c )
+
. ( c )
+
E ( c )
+
( c )
+
. ( c )
+
E ( - ) ( c )
+
oraz ( c )
+
. ( c )
+
E ( + ) ( c )
+
liczby rzeczywiste - w postaci zwykłej, tzn. liczby postaci: ( c )
+
. ( c )
+
Rozważmy następujący automat:
q
q
q
q
0
1
2
3
q
q
q
4
5
6
c
.
c
E
+
c
c
c
c
c
akceptacja
liczby całkowitej
akceptacja
liczby rzeczywistej
A = ( {q
0
, q
1
, q
2,
q
3,
q
4,
q
5,
q
6
}, { E, +, - , . , c},
δ , q
0
, { q
1
, q
3,
q
6
} ),
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
31
10. A
UTOMAT ZE STOSEM
Podany po wyżej automat skończony akceptuje dość proste obiekty występujące w
językach programowania, takie jak: liczby, identyfikatory, operatory arytmetyczne itp. -
dające się opisać gramatykami regularnymi lub wyrażeniami regularnymi.
Do akceptacji konstrukcji językowych, takich jak instrukcje, deklaracje - potrzebny
będzie bardziej skomplikowany automat - zwany automatem ze stosem, który wykonuje
kolejny takt w zależności nie tylko od aktualnego stanu i czytanego symbolu, ale również od
symbolu na szczycie stosu.
Stos jest dodatkową pamięcią, w której automat pamięta informacje o przebiegu analizy
badanych słów.
Na przykład podczas analizy słów postaci: a
n
b
n
, automat będzie zapamiętywał na stosie
kolejne symbole ‘a’ , jeśli na wejściu będą pojawiać się symbole ‘b’ – automat będzie
zdejmował ze stosu symbole ‘a’.
Tak więc po zakończeniu analizy danego słowa a
n
b
n
stos będzie pusty.
a
w
A s
q
Z
stos
wejście
γ
Rys 10.1 Automat ze stosem
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
32
Definicja 10.1
Automatem ze stosem nazywamy: A
s
= ( Q,
∑, Γ, δ, q
0
, Z
0
, F ) , gdzie:
Q - skończony zbiór stanów,
∑ - skończony zbiór symboli wejściowych (alfabet),
Γ - skończony zbiór symboli na stosie (alfabet stosowy),
δ -
funkcja przejścia, przy czym:
δ
: Q
×(∑∪ε)×Γ Æ
P
( Q
×Γ
*
) funkcja ta odwzorowuje trójkę:
(stan, symbol wejściowy, symbol na stosie)
w podzbiór par: (stan, słowo nad Γ).
q
0
∈ Q - stan początkowy,
Z
0
∈ Γ - symbol początkowy na stosie,
F
⊆ Q - zbiór stanów końcowych.
Podobnie jak w przypadku automatu skończonego aby opisać działanie automatu ze stosem
zdefiniujemy najpierw konfigurację A
s
- automatu, a następnie relację
¬
na zbiorze
konfiguracji.
Definicja 10.2
Konfiguracją A
s
- automatu jest trójka: ( q
,
w
,
α
)
∈ Q × ∑
*
× Γ
*
,
gdzie: q - bieżący stan automatu
w - analizowane słowo, przy czym pierwszy z lewej symbol słowa 'w',
jest symbolem czytanym (wskazany przez głowice), jeśli w = ε - to
oznacza, że słowo zostało zbadane,
α - zawartość stosu, przy czym szczyt stosu wskazuje pierwszy z lewej
symbol słowa - α , jeśli α = ε - mówimy, że stos jest pusty.
Konfiguracja początkowa ma postać: ( q
0
, w, Z
0
) , w
∈∑
*
Konfiguracja końcowa ma postać: (q,
ε, γ) gdzie: q∈F ∧ γ∈
Γ
*
.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
33
Na zbiorze konfiguracji definiujemy relację:
¬
Definicja 10.3
( q , aw , Z
γ )
¬
( q
'
, w ,
β γ ) gdy ( q
'
,
β ) ∈
δ
( q, a, Z )
przy czym: q , q
'
∈ Q , a ∈ ∑ ∪ {ε} , w ∈ ∑
*
, Z
∈
Γ
,
β , γ ∈
Γ
*
.
Zapis:
¬
*
- oznacza zwrotne i przechodnie domknięcie relacji :
¬ .
Z
powyższej definicji relacji
¬ wynika, że automat ze stosem będąc w stanie: q ,
podczas gdy na szczycie stosu znajduje się symbol: Z - przejdzie do nowego stanu - q
'
,
przy czym jednocześnie może nastąpić przesunięcie głowicy czytającej aktualny symbol -
( a
≠ ε ) lub głowica pozostanie w tym samym miejscu - ( a = ε ).
Ponadto - na szczycie stosu następuje zastąpienie symbolu Z – słowem
β ∈
Γ
*
, w szczególnym przypadku, gdy
β = ε - symbol ze szczytu stosu jest usuwany.
Automat ze stosem rozpoczyna pracę w konfiguracji początkowej, a następnie -
wykonując kolejne takty (zgodnie z definicją funkcji przejścia) - może zakończyć analizę
słowa w stanie końcowym - co oznacza jego akceptację lub zatrzyma się, gdy dla trójki:
(aktualny stan, symbol wejściowy i symbol na szczycie stosu) , funkcja przejścia - nie będzie
określona.
Definicja 10.4
Językiem akceptowanym przez automat ze stosem - A
s
nazywamy
zbiór:
L( A
s
) = { w
∈∑
*
: (q
0
, w , Z
0
)
¬
*
( q ,
ε , γ ) , q ∈ F , γ ∈
Γ
*
}
Uwaga
Automat ze stosem - A
s
może kontynuować pracę - wykonując takty - nawet wtedy,
gdy zostanie przeczytane całe słowo 'w' , ale nie może wykonać następnego taktu, gdy stos
będzie pusty.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
34
Przykład 1.
A
s
= ( { q
0
, q
1
, q
2
} , { 0, 1 }, { Z
0
, 0 } , δ , q
0
, Z
0
, { q
0
} )
Przy czym funkcja
δ
jest określona następująco:
δ
(q
0
, 0 , Z
0
) = { (q
1 ,
0Z
0
) }
δ
(q
1
, 0 , 0 ) = { (q
1 ,
00) }
δ
(q
1
, 1 , 0 ) = { (q
2 ,
ε) }
δ
(q
2
, 1 , 0 ) = { (q
2 ,
ε) }
δ
(q
2
, ε , Z
0
) = { (q
0 ,
ε) }
Prześledzimy takty automatu dla słowa w = 0011
(q
0
, 0011 , Z
0
)
¬
(q
1
, 011 , 0Z
0
)
¬
(q
1
, 11 , 00Z
0
)
¬
(q
2
, 1 , 0Z
0
)
¬
(q
2
, ε , Z
0
)
¬
(q
0
, ε , ε )
Ogólnie można pokazać, że
(q
0
, 0 , Z
0
)
¬
(q
1
, ε , 0Z
0
)
(q
1
, 0
i
, 0Z
0
)
¬
i
(q
1
, ε , 0
i+1
Z
0
)
(q
1
, 1 , 0
i+1
Z
0
)
¬
(q
2
, ε , 0
i
Z
0
)
(q
2
, 1
i
, 0
i
Z
0
)
¬
i
(q
2
, ε , Z
0
)
(q
2
, ε , Z
0
)
¬
(q
0
, ε , ε )
Tak więc mamy, że
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
35
(q
0
, 0
n
1
n
, Z
0
)
¬
2 n + 1
(q
0
, ε , ε) , n ≥ 1
(q
0
, ε , Z
0
)
¬
0
(q
0
, ε , Z
0
)
Wniosek.
{ 0
n
1
n
, n ≥ 0 } ⊆ L(A
s
)
Dowód w drugą stronę jest trudniejszy.
Przykład 2.
Rozważmy automat ze stosem, akceptujący język L={w w
←
: w ∈ { a , b }
+
}
gdzie :
w
←
oznacza rewers słowa w.
A
s
= ( { q
0
, q
1
, q
2
} , { a, b }, { Z
0
, a, b } ,
δ
, q
0
, Z
0
, { q
2
} )
Przy czym funkcja przejścia ma postać:
(1)
δ
(q
0
, a , Z
0
) = { (q
0 ,
aZ
0
) }
(2)
δ
(q
0
, b , Z
0
) = { (q
0 ,
bZ
0
) }
(3)
δ
(q
0
, a , a ) = { (q
0 ,
aa) , (q
1 ,
ε) }
(4)
δ
(q
0
, a , b ) = { (q
0 ,
ab) }
(5)
δ
(q
0
, b , a ) = { (q
0 ,
ba) }
(6)
δ
(q
0
, b , b ) = { (q
0 ,
bb) , (q
1 ,
ε) }
(7)
δ
(q
1
, a , a ) = { (q
1 ,
ε) }
(8)
δ
(q
1
, b , b ) = { (q
1 ,
ε) }
(9)
δ
(q
1
, ε , Z
0
) = { (q
2 ,
ε) }
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
36
Zauważmy, że powyższy automat dla dowolnej konfiguracji: ( q
0
, aw , aγ ) może
wykonać jeden z dwóch taktów:
1. włożyć na szczyt stosu - jeszcze jeden symbol 'a'
2. usunąć ze stosu - symbol 'a'
Podobnie będzie dla konfiguracji: ( q
0
, bw , bγ ) - świadczy to o tym, że powyższy
automat jest niedeterministyczny.
Definicja10.5
Automat ze stosem A
s
= ( Q ,
∑ , Γ ,
δ
, q
0
, Z
0
, F ) nazywamy automatem
deterministycznym jeśli:
∀ q ∈ Q , ∀ Z ∈ Γ , ∀ a ∈ ∑ zachodzi, że
|
δ
(q, a, Z)|
≤ 1 ∧
δ
(q,
ε, Z)=∅ lub
|
δ
(q,
ε, Z)| ≤ 1 ∧
δ
(q, a, Z)=
∅
W automacie deterministycznym w każdej konfiguracji - możliwe jest co najwyżej jedno
przejście do konfiguracji następnej.
Język akceptowany przez deterministyczny automat ze stosem nazywamy językiem
deterministycznym.
Istnieją języki bezkontekstowe, które nie są deterministyczne, z drugiej strony
wiadomo, że wszystkie znane języki programowania - są deterministyczne i istnieją podklasy
gramatyk bezkontekstowych, np. LR(1), SLR(1), LALR(1), LL(1), gramatyki precedensyjne,
generujące języki programowania, dla których można skonstruować deterministyczne
automaty ze stosem.
Są one istotnym elementem kompilatorów języków programowania - tzw. analizatorami
składniowymi - parserami.
Podstawą do optymizmu przy konstrukcji kompilatorów języków programowania jest
następujące:
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
37
Twierdzenie.
Każdy deterministyczny język bezkontekstowy jest generowany przez pewną
gramatykę typu LR(1).
Przykład.
Rozważmy deterministyczny automat ze stosem:
A
s
= ( { q
0
, q
1
, q
2
} , { a, b, c }, { Z
0
, a, b } ,
δ
, q
0
, Z
0
, { q
2
} )
akceptujący język postaci: L = { wcw
←
: w ∈ { a, b }
+
}.
Funkcja przejścia jest zdefiniowana następująco:
δ
(q
0
, X, Y) = (q
0 ,
XY) , ∀ X ∈ {a, b} ∧ Y ∈ { Z
0
, a, b}
δ
(q
0
, c, Y) = (q
1 ,
Y) , ∀ Y ∈ {a, b}
δ
(q
1
, X, X) = (q
1 ,
ε) , ∀ X ∈ {a, b}
δ
(q
1
, ε, Z) = (q
2 ,
ε)
Zauważmy, że automat przepisuje analizowane symbole słowa - z wejścia na stos -
dopóki na wejściu nie pojawi się symbol 'c'. Po napotkaniu symbolu 'c' - automat zmienia
aktualny stan q
0
- na nowy stan q
1
, a następnie gdy kolejny symbol na wejściu jest równy
symbolowi na stosie - to ze stosu usuwa się dany symbol.
Tak więc automat akceptuje słowa, w których symbol 'c' tworzy jakby oś symetrii.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
38
11.S
TRUKTURA KOMPILATORA
Translatory
stanowią jedną z najważniejszych części systemów komputerowych - bez
nich programowano by w językach symbolicznych lub nawet w kodzie maszynowym.
Dlatego konstrukcja kompilatorów stała się ważną dziedziną w informatyce.
Translator - zwany niekiedy kompilatorem - jest programem, który tłumaczy program
w języku źródłowym na równoważny mu program w języku docelowym, którym jest język
symboliczny lub kod pewnej maszyny.
Interpreter - czyta program w języku źródłowym i wykonuje go. Różnica pomiędzy
kompilatorem a interpreterem polega na tym, że interpreter nie tworzy programu docelowego
do wykonania lecz wykonuje bezpośrednio każdą analizowaną instrukcję programu
źródłowego. Mówiąc dokładnie - interpreter analizuje kolejno instrukcje programu
źródłowego i tłumaczy je na jakąś postać wewnętrzną - a następnie interpretuje (wykonuje)
utworzony kod wewnętrzny.
Praca kompilatora składa się z dwóch faz:
1. analizy programu źródłowego, w której następuje rozłożenie programu źródłowego na
jego części podstawowe - z jednoczesnym sprawdzeniem jego poprawności składniowej i
semantycznej - na końcu tej fazy tworzony jest program w pewnej formie pośredniej
2. syntezy programu docelowego, w której opierając się na utworzonej formie pośredniej -
następuje najpierw przygotowanie do generacji programu docelowego a następnie
właściwa generacja kodu.
Podczas całego procesu kompilator tworzy struktury danych - tablice informacji, w których
zapamiętuje informacje o zmiennych, stałych, niektórych instrukcjach i procedurach - i
używa ich zarówno w czasie analizy jak i syntezy.
Poniżej przedstawiono strukturę logiczna kompilatora.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
39
program
źródłowy
Analizator
leksykalny
Analiza
Analizatory
Składni
i Semantyki
Przygotowanie
do
generacji kodu
Generacja
kodu docelowego
Synteza
Tablice
Tablica
symboli
Tablica
stałych
Tablica
' for '
Program
docelowy
Rys. 1 Struktura logiczna kompilatora
symbole
wewnętrzna
postać programu
KOMPILATOR
Obecnie zostaną pokrótce omówione poszczególne moduły kompilatora.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
40
10.1 Analizator leksykalny
Analizator leksykalny jest najprostszą częścią kompilatora - czyta on znaki programu
źródłowego kolejno od lewej do prawej i rozpoznaje właściwe symbole programu, zwane
atomami leksykalnymi.
Są to: liczby, łańcuchy znakowe, zmienne, słowa
zarezerwowane, operatory arytmetyczne i relacyjne, operator przypisania, symbole
jednoznakowe: (, ), ;, ,, . {, }, [, ] itd.
Podczas analizy - analizator leksykalny może usuwać komentarze, dołączać
identyfikatory lub liczby do tablicy informacji i wykrywać błędy w budowie atomów np.
błędne liczby.
Rozpoznane atomy leksykalne są przekazywane analizatorowi składniowemu - w
postaci par : (numer atomu, informacja semantyczna), przy czym informacja semantyczna -
jest istotna tylko dla takich atomów jak: identyfikatory, liczby, operatory addytywne,
multiplikatywne i relacyjne - dla których potrzebna jest dodatkowa informacja -
jednoznacznie identyfikująca dany atom.
Na
przykład dla identyfikatora lub liczby - informacją semantyczną jest adres do
tablicy symboli lub tablicy stałych.
Dla operatorów addytywnych, postaci: ‘+’ , ‘-’ , informacją semantyczną jest numer operatora
: 1 - dla ‘+’ 2 - dla ‘-’. Podobnie - dla operatorów multiplikatywnych: ‘*’ , ‘/’ , czy
relacyjnych: ‘<‘, ‘>‘ , ‘<=‘ , ‘>=‘ , ‘=‘ , ‘<>‘ .
Od strony formalnej - analizator leksykalny jest automatem skończonym nad
alfabetem, którego elementami są klasy symboli, tzn.: litery, cyfry i inne znaki, z których
zbudowane są atomy.
Automat rozpoznaje możliwie najdłuższy podciąg znaków, który może reprezentować
- poprawnie zbudowany atom leksykalny. W chwili gdy na wejściu znajdzie się znak, nie
należący do aktualnie rozpoznawanego atomu oraz dotychczas przeanalizowane znaki nie
mogą być poprawnym atomem - automat wykrywa błąd - 'niepoprawny atom'.
Automat ten zawiera:
- stan
początkowy, w którym rozpoczyna się rozpoznanie dowolnego atomu
- kilka stanach końcowych - po jednym dla każdego atomu - w których akceptuje się -
poszczególne atomy leksykalne
- kilka stanów błędnych, w których wykrywa się błędy w atomach.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
41
Pracą automatu steruje funkcja przejścia, która dla dowolnej pary:
(stan bieżący, klasa czytanego symbolu) - wyznacza następny stan.
10.2 Analizator składni i analizator semantyczny
Dwa wymienione analizatory wykonują pełne sprawdzenie poprawności syntaktycznej
i semantycznej programu. Podczas obu analiz następuje:
rozłożenie programu na jego części składowe,
zapisanie informacji o atomach leksykalnych w tablicach symboli ,
utworzenie pośredniej postaci programu.
Zwykle
analizatory są sterowane składnią programu to znaczy - podczas analizy
syntaktycznej - analizator składni
rozpoznaje jakąś konstrukcję języka źródłowego i
wywołuje tak zwaną procedurę semantyczną, która sprawdza poprawność semantyczną
rozpoznanej konstrukcji i zapamiętuje niezbędne informacje w tablicy symboli lub generuje -
odpowiadający jej kod w języku pośrednim.
Jeżeli na przykład zostanie rozpoznany identyfikator w liście deklaracji zmiennych, to
jedna z procedur semantycznych sprawdzi, czy nie został on zadeklarowany ponownie i
dołączy go do tablicy symboli - łącznie z wynikającymi z deklaracji charakterystykami,
takimi jak: typ czy rodzaj identyfikatora.
Natomiast po rozpoznaniu instrukcji podstawienia postaci:
‘identyfikator := wyrażenie’,
odpowiednia procedura semantyczna sprawdzi zgodność typów identyfikatora i wyrażenia, a
następnie wygeneruje odpowiadający jej kod w języku pośrednim i dołączy go do dotychczas
wygenerowanego kodu pośredniego.
Od strony formalnej składnię języka źródłowego opisuje gramatyka, będąca pewną
podklasą gramatyk bezkontekstowych, dla której możliwa jest konstrukcja
deterministycznego automatu ze stosem.
Najczęściej do opisu składni języków programowania wykorzystuje się takie podklasy
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
42
gramatyk bezkontekstowych jak:
1. gramatyki LL(1),
2. LR(1) - jej podklasy: SLR(1) i LALR(1)
3. gramatyki precedensyjne.
10.3 Tablice informacji
Podczas analizy programu źródłowego zbiera się i zachowuje do późniejszego użytku
informacje zawarte w deklaracjach zmiennych i procedur, jak również informacje zawarte w
pewnych instrukcjach, np. w pętlach ‘ for ‘.
Na
przykład przy każdym wystąpieniu nazwy - trzeba zachować informacje - jak ta
zmienna została zadeklarowana lub użyta w jakimś innym miejscu.
Informacje te gromadzi się w tablicy symboli, której organizacja powinna zapewnić na
efektywny do niej dostęp. W tablicy symboli zapamiętuje się oprócz samych nazw zmiennych
- również ich charakterystyki, takie jak: typ nazwy, adres przyporządkowany tej nazwie w
programie docelowym i inne informacje potrzebne do utworzenia przekładu programu w
języku docelowym.
Oprócz tablicy symboli dla zmiennych - w tablicach informacji pamięta się tablicę
stałych: liczbowych lub łańcuchach znaków - użytych w programie źródłowym, a także inne
informacje związane z niektórymi instrukcjami, jak na przykład - instrukcje ‘ for ‘ , dla
których trzeba pamiętać - sposób zagnieżdżenia i zmienne sterujące. Informacje te są nie
zbędne dla sprawdzenia poprawności semantycznej niektórych instrukcji.
Podobnie - w tablicy informacji pamięta się informacje o deklarowanych w
analizowanym programie - strukturach złożonych, takich jak tablice czy rekordy.
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
43
10.4 Język pośredni programu.
Proces analizy programu źródłowego kończy się wygenerowaniem równoważnego
programu w języku pośrednim, którym może być:
1. jedna z notatacji polskich ,
2. ciąg tetrad (czwórek), postaci:
(operator, argument_1, argument_2, wynik)
3. ciąg triad (trójek), postaci: (operator, argument_1, argument_2).
4. Język symboliczny przykładowej maszyny cyfrowej.
Na przykład dla instrukcji przypisania:
a := b + c * d ,
zostanie utworzony następujący ciąg czwórek:
( * , c, d, T1 )
( + , b, T1, T2)
( := , T2, 0, a),
gdzie: T1 i T2 - są zmiennymi roboczymi, użytymi przez kompilator.
Należy podkreślić, że w praktyce argumentami czwórek nie są nazwy symboliczne - lecz
wskaźniki do elementów tablicy symboli, w których znajdują się opisy argumentów.
10.5 Przygotowanie do generacji kodu.
Moduł ten dokonuje przeglądu utworzonego kodu pośredniego i przekształca go w
postać zoptymalizowaną - pozwalającą na skrócenie czasu wykonywania programu
docelowego.
Optymalizacja kodu pośredniego dotyczy przede wszystkim instrukcji pętli
programowych, gdzie istotnym jest by instrukcje wewnątrz pętli, które nie zależą od
zmiennych sterujących - były wykonywane poza pętlą.
Chodzi też o to, by znaleźć i usunąć z kodu pośredniego operacje zbędne, to znaczy operacje,
dla których można znaleźć w kodzie - wcześniej występujące - identyczne operacje (ten sam
kod i argumenty), przy czym ich argumenty nie uległy modyfikacji w żadnej operacji -
WSTĘP DO TEOR II JĘZYK ÓW I ATO MATÓW
44
pomiędzy wcześniejszą operacją identyczną i operacją zbędną.
Dla operacji zbędnych nie trzeba generować kodu docelowego - wystarczy tylko
zmienić wszystkie do nich odwołania - na odwołania do identycznych operacji
wcześniejszych.
10.6 Generowanie kodu docelowego.
Ostatnim etapem kompilacji jest przekształcenie ciągu operacji w kodzie pośrednim na
język maszynowy lub symboliczny danej maszyny cyfrowej. Jest to etap najbardziej zależny
od konkretnego systemu komputerowego i wymaga dobrej znajomości konkretnego
procesora, cyklu rozkazowego, listy dostępnych rozkazów i sposobów adresacji.
Na
przykład dla podanego ciągu czwórek moglibyśmy wygenerować ciąg rozkazów w
języku symbolicznym jakiejś maszyny, w następującej postaci:
Load 5, c
- pobranie ‘c’ do rejestru R5
Mult
4,
d
- wynik mnożenia w rejestrach R4, R5
Add
5,
b
- dodanie ‘b’ do wyniku mnożenia
Store 5, a
- zapamiętanie wyniku w ’a’.
Wszystkie cztery moduły kompilacji mogą być wykonywane w kolejności podanej na
rysunku 1, ale mogą być też bardziej splecione i wykonywane w sposób równoległy.
W typowym schemacie kompilacji centralną rolę odgrywa analizator syntaktyczny,
który analizując kolejne części programu źródłowego - wywołuje analizator leksykalny - gdy
potrzebuje nowego symbolu - a po rozpoznaniu jakiejś konstrukcji językowej - wywołuje
odpowiednią procedurę - analizatora semantycznego.
Procedura ta sprawdza poprawność
semantyczną tej konstrukcji i generuje odpowiadający jej - kod pośredni.
Po wygenerowaniu kodu pośredniego dla całego programu źródłowego - następuje
omówiony wcześniej proces syntezy.
Taki schemat kompilacji nosi nazwę - jednoprzebiegowego, przy czym trzeba
podkreślić, że nie wszystkie języki programowania mają strukturę umożliwiającą kompilacje
jednoprzebiegowe.