Zasady automatycznej translacji


Stos i odwrotna notacja polska (ONP) > Translacja wyrażeń arytmetycznych > Przykłady >


Translacja i translatory

Języki programowania niskiego czy też wysokiego poziomu mają na zadanie przetworzyć ogół algorytmów w nich zapisanych na taką postać aby maszyna cyfrowa była w stanie je wykonać tzn. dać takie efekty jakie programista zakłada tworząc dany program. Między tymi językami występuje jednak zasadnicza różnica : program zapisany w języku niskiego poziomu (w języku wewnętrznym) stanowi ciąg instrukcji dostępnych przez dany procesor czy też maszynę cyfrową i jest wykonywany bezpośrednio; natomiast program zapisany w językach wysokiego poziomu takich jak Pascal czy C ( w językach zewnętrznych) wymaga dodatkowo przetłumaczenia na ciąg instrukcji dostępnych przez maszynę która ma dany program wykonać. Owo tłumaczenie w pewnym stopniu przypomina tłumaczenie języków etnicznych, przy uwzględnieniu dodatkowych warunków jak: znajomość kultury, tradycji i historii danego języka. Podobnie tłumacząc programy zewnętrzne na wewnętrzne należy także uwzględnić dodatkowe elementy takie jak dane wejściowe do programu, które także muszą być przetłumaczone do tego stopnia aby spodziewany efekt końcowy programu zapisanego w języku zewnętrznym niczym się nie różnił od efektu działania samej maszyny.

Proces przekładu tekstów zapisanych w jednym języku na drugi nosi nazwę translacji. W przypadku gdy dany język wysokiego poziomu ma stosunkowo łatwą gramatykę, translacja może być wykonana samoczynnie przez maszynę cyfrową przy pomocy specjalnego programu translacji zwanego translatorem.

Wykorzystując translatory programiści mogą posługiwać się zewnętrznymi językami programowania, co znacznie ułatwia tworzenie oprogramowania, gdyż czas stracony na żmudnym pisaniu instrukcji w języku wewnętrznym zostaje ograniczony do wybrania odpowiednich procedur i funkcji z repertuaru danego języka wysokiego poziomu,
a sam programista może skupić się na rozwiązywaniu powstałych problemów implementacyjnych.

Translatory dzielimy zazwyczaj na dwie kategorie: kompilatory i interpretatory. Podział ten bardzo często nie ma miejsca w praktyce, gdyż buduje się translatory wykazujące jednocześnie cechy kompilatorów i interpretatorów.

Najogólniej, kompilator jest translatorem, operującym na całym tekście programu źródłowego generując tekst przekładu jako całość, podczas gdy interpreter operuje na poszczególnych jednostkach syntaktycznych programu źródłowego i generuje ich przekłady. Jeśli więc wykonywamy program początkowo zapisany w języku zewnętrznym to:

      używając kompilatora, możemy przystąpić do wykonania programu w postaci docelowej dopiero po zakończeniu translacji. Oznacza to, że uzyskany tekst będący przekładem tekstu źródłowego w całości wprowadzany jest do maszyny cyfrowej;

      używając interpretatora, możemy wykonywać przekłady poszczególnych jednostek syntaktycznych, nie czekając na cały proces translacji. Oznacza to, że cały czas operujemy na tekście źródłowym tłumacząc tylko te jednostki syntaktyczne, które są potrzebne aby poszczególny fragment programu mógł zadziałać.

W praktyce rzadko dokonuje się bezpośredniej translacji programów z języka zewnętrznego na język maszynowy. Najczęściej stosuje się proces pośredni to znaczy, najpierw dokonuje się translacji z języka zewnętrznego na język asemblerowy, a potem z języka asemblerowego na język maszynowy. Zastosowanie takiej dwuetapowej translacji niesie za sobą wiele zalet, a główna z nich jest możliwość łączenia poszczególnych części programów zapisanych w różnych językach zewnętrznych.

 



Stos i odwrotna notacja polska (ONP)

Bardzo ważnymi pojęciami bez których trudne byłoby zrozumienie zasad jakiejkolwiek translacji są : stos i odwrotna notacja polska (ONP).

STOS- jest to organizacja sekwencyjna pamięci operacyjnej maszyny cyfrowej. Stos działa jak pojemnik określonych jednostek, przy czym pobieranie elementów w nim zgromadzonych odbywa się w kolejności odwrotnej do magazynowania. Jest to tak zwana struktura LIFO (last-in-first-out co oznacza “ ten co ostatni przyszedł pierwszy odchodzi”). Dla stosu określa się dwie podstawowe operacje:

  • dos(a)- dopisz na stosie - w wyniku wykonania tej operacji jednostka a zostaje umieszczona na szczycie stosu (staje się pierwszym elementem stosu)
  • ods(a)- odczytaj ze stosu - w wyniku wykonania tej operacji jednostka a zostaje wydana na zewnątrz stosu.

ODWROTNA NOTACJA POLSKA (ONP) - mianem tym obdarzono jeden z wariantów beznawiasowego zapisu wyrażeń formalnych, wynalezionego przez polskiego logika Jana Łukasiewicza (1878-1956). W tym beznawiasowym zapisie symbole operandów poprzedzają bezpośrednio symbol operatora, na przykład wyrażenie a+b zapisujemy w ONP jako a b +.




Translacja wyrażeń arytmetycznych

Współczesne podejście translacji wyrażeń arytmetycznych polega na wydzieleniu dwu etapów translacji:

  •  translacja do ONP

  •  translacja ONP na język symboliczny

W celu zobrazowania translacji do ONP przyjmujemy, że źródłowy zapis wyrażeń arytmetycznych pojawia się na wejściu specjalnego automatu (Rrysunek 1). Na wyjściu uzyskamy zapis ONP tych wyrażeń, sam zaś automat wyposażony jest w pamięć stosową.:

Podczas translacji wyrażeń arytmetycznych szczególnej analizie poddawane są symbole operacji (+,-,*,itp.) zwane ogranicznikami ,stąd wprowadza się dodatkowo listę priorytetów ograniczników (tablica 1):

Ogranicznik

Priorytet

+ -

0

* / ÷

1

2

Tablica 1. Priorytety symbolów operacji (ograniczników)

 

Działanie automatu odbywa się według następującego algorytmu postępowania:

  1. Pobierz kolejny element (nazwę zmiennej, stałą lub ogranicznik) źródłowego wyrażenia arytmetycznego.

  2. Jeśli ten element jest nazwą zmiennej lub stałą, przekaż go natychmiast na wyjście; w przeciwnym wypadku, jeśli priorytet ogranicznika jest wyższy od priorytetu ogranicznika zajmującego szczyt stosu lub jeśli stos jest pusty, dopisz go na stos, jeśli wreszcie na szczycie stosu znajduje się ogranicznik o wyższym lub równym priorytecie - odczytaj go ze stosu i prześlij na wyjście, a ogranicznik z wejścia dopisz na stosie, chyba, że nowy ogranicznik zajmujący szczyt stosu w wyniku odczytania priorytetu ma priorytet nie mniejszy niż ogranicznik z wejścia. w takim przypadku należy kontynuować odczytywanie ze stosu
    i przesyłanie na wyjście aż do wystąpienia
    na szczycie stosu ogranicznika o priorytecie niższym od priorytetu ogranicznika nadchodzącego z wejścia.

  3. Jeśli wyrażenie źródłowe zostało wyczerpane, odczytaj wszystkie ograniczniki
    ze stosu na wyjście automatu.




Przykłady translacji wyrażeń arytmetycznych do postaci ONP i odwrotnie z postaci postfiksowej (ONP) na infiksową

Przykład 1:

Przykład 1 przedstawia poszczególne takty procesu translacji do ONP dla wybranego wyrażenia arytmetycznego.

Niech wyrażenie źródłowe ma postać: x + 3 * z ÷ k

Poszczególne takty translacji są następujące:

Takt

Wejście

Stos

Wyjście

1

x

 

x

2

+

+

 

3

3

+

3

4

*

+,*

 

5

z

+,*

z

6

÷

+,÷

*

7

k

+,÷

k

8

koniec

 

÷ ,+

Rysunek 2. Poszczególne takty procesu translacji wyrażenia do ONP dla przykładu 1

Na wyjściu uzyskamy wyrażenie ONP postaci: x, 3, z, *, k, ÷ , +

Dla uzyskania prawidłowej konwersji wyrażeń arytmetycznych uzupełniamy listę ograniczników o następujące symbole:

  • nawiasy ( )
  • operator negacji NEG (jako symbol operacji unarnej służący do zmiany znaku)
  • funkcje trygonometryczne (operatory jednoargumentowe)

 

Priorytety wyżej wymienionych ograniczników przedstawia tabela 2

Ogranicznik

Priorytet

(

0

+ - )

1

* / ÷ NEG

2

 

3

sin cos tg ctg

4

Tab.2. Priorytety rozszerzonych symbolów operacji (ograniczników)

Działanie automatu uzupełniamy następującymi regułami:

  Ogranicznik “(” jest dopisywany do stosu bez jakiegokolwiek odczytywania stosu.

  Ogranicznik “)” nie jest dopisywany na stos, pojawienie się jednak tego ogranicznika na wejściu powoduje odczytanie ze stosu i przesłanie na wyjście wszystkich kolejnych ograniczników aż do pojawienia się ogranicznika “(”.

  Ogranicznik “(” ze szczytu stosu zostaje usunięty bez przekazywania na wyjście, jeśli aktualnym symbolem na wejściu jest “)”.

Pojawienie się nawiasu zamykającego “)” na wejściu automatu powoduje wyprowadzenie na wejście wszystkich ograniczników z wnętrza pary nawiasów aż do nawiasu otwierającego “(” oraz likwidację tego nawiasu.

 

Przykład 2:

Przykład 2 przedstawia proces translacji z uwzględnieniem powyższych reguł.

Niech wyrażenie źródłowe ma postać: b * c ( d - e*k )

Poszczególne takty translacji są następujące:

Takt

Wejście

Stos

Wyjście

1

b

 

b

2

*

*

 

3

c

*

c

4

*,

 

5

(

*, , (

 

6

d

*, , (

d

7

-

*, , (,-

 

8

e

*, , (,-

e

9

*

*, , (,-,*

 

10

k

*, , (,-,*

k

11

)

*,

*,-

12

koniec

 

,*

Rysunek 3. Poszczególne takty procesu translacji wyrażenia do ONP dla przykładu 2

Na wyjściu uzyskamy wyrażenie ONP postaci: b, c, d, e, k, *, -, ,*

 

Przykład 3:

Przykład 3 przedstawia translację krótkiego wyrażenia arytmetycznego z funkcjami trygonometrycznymi.

Niech wyrażenie źródłowe ma postać: sinx + cosy + tgz

Poszczególne takty translacji są następujące:

Takt

Wejście

Stos

Wyjście

1

sin

sin

 

2

x

sin

x

3

+

+

sin

4

cos

+, cos

 

5

y

+, cos

y

6

+

+

cos, +

7

tg

+, tg

 

8

z

+, tg

z

9

koniec

 

tg, +

Rysunek 4. Poszczególne takty procesu translacji wyrażenia do ONP dla przykładu 3

Na wyjściu uzyskamy wyrażenie ONP postaci: x , sin, y, cos, +, z, tg, + ,

 Nic nie stoi na przeszkodzie by procesowi translacji poddać wyrażenia arytmetyczne zawierające operacje logiczne i warunkowe. W tym celu należy odpowiednio rozszerzyć ilość priorytetów, a także chcąc odzwierciedlić składnie: if..then..else należy wprowadzić odpowiednie oznaczenia, które będą sygnalizowały konieczność wykonania skoku warunkowego lub bezwarunkowego. Operacje te zapisujemy w postaci SW (k) i SB (k), gdzie SW- oznacza then, a SB else. Dla translacji wyrażeń arytmetycznych z elementami logicznymi koniecznym jest wprowadzenie dwóch różnych pojęć priorytetów: priorytet porównawczy (p.p) i priorytet stosowy (p.s.). gdzie: priorytet porównawczy dla danego ogranicznika oznacza moc rozładowania stosu, a priorytet stosowy moc blokowania stosu. W praktyce oznacza to, że jeżeli na wejściu automatu pojawi się symbol operacji (ogranicznik) to celem ewentualnego odczytania symboli ze stosu porównujemy priorytet porównawczy tego symbolu z priorytetem stosowym symboli operacji na stosie.

Uzupełniona tablica priorytetów ograniczników wraz z uwzględnieniem pojęć: priorytet stosowy i porównawczy kształtuje się następująco:

Ogranicznik

p. stosowy

p. porównawczy

(, if

0

nie dotyczy

then

0

1

else

1

2

), ;

nie dotyczy

1

3

3

4

4

5

5

6

6

-

7

7

< =

8

8

+-

9

9

* / ÷ NEG

10

10

11

11

Tablica 3. Uzupełniona lista ograniczników z uwzględnieniem elementów logicznych

 

Algorytm konwersji zostaje uzupełniony o nowe reguły związane z elementami logicznymi: if..then...else:

  1. Gdy na wejściu pojawi się ogranicznik “then”, wówczas, oprócz wszystkich ograniczników wyprowadzanych ze stosu na wyjście ze względu na ich priorytety, zostaje także usunięty ze szczytu stosu ogranicznik “if” ( konstrukcja if - then jest analogiczna do pary nawiasów ( ) w wyrażeniach arytmetycznych). Na wyjście automatu zostaje wyprowadzona operacja SW z pustym nawiasem SW( ), zaś ogranicznik “then” zostaje dopisany do stosu wraz z numerem, pod jakim występuje w zapisie ONP operacja SW( ).

  2. Gdy na wejściu pojawia się ogranicznik “else”, powoduje on wyprowadzenie wszystkich symboli na wyjście automatu aż do momentu pojawienia się ma stosie ogranicznika “then”. Na wyjście zostaje wpisana niekompletna operacja SB(), operacja SW( ) będąca na wyjściu zostaje uzupełniona przez wpisanie do nawiasu numeru pozycyjnego z zapisu ONP, a sam ogranicznik “else” zostaje dopisany do stosu wraz z numerem pozycyjnym SB( ) w zapisie ONP.

  3. Gdy podczas wyprowadzania ograniczników ze stosu natrafimy na “else”, wówczas uzupełniamy odpowiedni nawias operacji SB( ) odpowiadającej danemu “else”, zaś sam ogranicznik else zostaje zlikwidowany tzn. nie jest wyprowadzany na wyjście automatu.

 

Przykład 4:

Przykład 4 obrazuje translację wyrażeń zawierających elementy logiczne.

Niech wyrażenie na wejściu ma postać: y + ( if a>0 then 3 else a )

Poszczególne takty konwersji przedstawia rysunek 5.

Takt

Wejście

Stos

Wyjście

Numer pozycyjny

w ONP

1

y

 

y

1

2

+9

+9

   

3

(

+9 (0

   

4

if

+9 (0 if0

   

5

a

+9 (0 if0

a

2

6

>8

+9 (0 if0 >8

   

7

0

+9 (0 if0 >8

0

3

8

then1

+9 (0 then50

>

SW()

po takcie 10 - SW(8)

4

5

9

3

+9 (0 then50

3

6

10

else2

+9 (0 else71

SB()

po takcie 12- SB(9)

7

11

a

+9 (0 else71

a

8

12

)1

+9

   

13

;

 

+

9

Górne indeksy przy then i else oznaczają numer pozycyjny instrukcji SW i SB w ONP, zaś indeksy dolne oznaczają priorytet stosowy lub porównawczy danego ogranicznika.

 

Etap drugi translacji wyrażeń arytmetycznych polega na wygenerowaniu programu w języku symbolicznym (docelowym). Proces ten także korzysta z pamięci stosowej a sam algorytm postępowania wymaga przyjęcia pewnych oznaczeń :

ð i - i = 0, 1, ....   są to kolejne pozycje stosu; 
język docelowy pozwala na występowanie dwu typów instrukcji:  ð i := Z  ð i : = ð i op ð i+1  gdzie Z jest nazwą zmiennej lub stałą, a op jest symbolem operacji.

 

Proces translacji zapisu ONP na język docelowy przebiega według następującego algorytmu:

  1. Ustalamy i=0, k=1

  2. Odczytujemy k-ty element ONP : Ek

  3. Jeśli Ek jest nazwą zmiennej lub stała, generuje się operacja ð i:=Ek i następuje zwiększenie i o 1 i:= i +1; jeśli Ek jest symbolem operacji op NEG, generuje się operacja ð i-2 := ð i-2 op ð i-1 oraz następuje zmniejszenie i o 1 i := i - 1; jeśli Ek = NEG, następuje wygenerowanie operacji ði-1 := - ð i-1

  4. Jeśli Ek nie był ostatnim symbolem wyrażenia w ONP, to k:= k + 1 i przechodzimy do punktu 2.

Sposób translacji wyrażenia ONP na język symboliczny przedstawia przykład 5.

 

Przykład 5:

Niech wyrażenie arytmetyczne ma postać: ( a + b ) / ( k (-c) )

Postać ONP tego wyrażenia jest następująca: a, b, +, k, c, NEG, /

 

i

k

 

0

1

1: ð 0:= a

1

2

2: ð i:= b

2

3

3: ð 0:= ð 0 +ð i

1

4

4: ð i:= k

2

5

5: ð 2:= c

3

6

6: ð 2:= -ð 2

3

7

7: ð i:= ð i ð 2

2

8

8: ð 0:= ð o / ð 1

1

9

9: brak symboli w wyrażeniu ONP -koniec algorytmu

Wiadomości zawarte w tym rozdziale przedstawiają nam drogę od zrodzenia się algorytmu, aż po wykonanie programu na maszynie cyfrowej co schematycznie przestawia rysunek 6