ONP bez stosu

Jestem w trakcie pisania prostego "kompilatora" i natknąłem się na problem:
Dotychczas mój ewaluator (to chyba poprawne określenie ;)) działał na zasadzie odwrotnej notacji polskiej; tzn.zamieniałem wyrażenie na ONP, a potem je po kolei ewaluowałem, więc np.z 2+2*2robiło się 2 2 2 * +, a potem zamiana na bytecode:

ipush(2)
ipush(2)
ipush(2)
ipop(ei2)
ipop(ei1)
mul(ei1, ei2)
ipush(ei1)
ipop(ei2)
ipop(ei1)
ipush(ei1)

w tej chwili na stosie lądowała wartość 6
(oczywiście przy wyłączonej optymalizacji; dodałem prosty optymalizator który na żywo obliczał wyrażenia stałe, chodzi mi o pokazanie sposobu działania).
W kwestii wytłumaczenia:
ipush(int) - wrzucenie liczby typu int/integer na stos (dodatnia lub ujemna)
ipop(rejestr) - pobranie liczby typu int/integer ze stosu i wrzucenie jej do rejestru
mul(rejestr, wartość) - pomnożenie rejestru przez wartość i wrzucenie wyniku do rejestru
Rejestry dla liczb typu int to: ei1, ei2, ei3 oraz ei4.
Natomiast wracając do tematu: z tego co zauważyłem, "prawdziwe" kompilatory zrobiłyby to na zasadzie:

mov(ei1, 2)
mov(ei2, 2)
mul(ei1, ei2)
add(ei1, 2)

I to jest moje pytanie: jak mając wyrażenie w formie 2+2*2 lub 2 2 2 * + wykonać zamianę kod podany powyżej?
ONP opiera się na stosie, podczas gdy z tego co zauważyłem, kompilatory korzystają z niego rzadko (a w każdym razie w prostych programach).

Wirtualna maszyna Javy jest ZTCP maszyną stosową, więc jeśli generowałbyś bajtkod Javowy to maszyna Javy już by sobie zoptymalizowała to do wydajnej postaci.

Kompilatory kodu natywnego raczej w ogóle nie używają ONP, raczej stosują SSA (static single assignment), potem uwspólnianie wyrażeń, redukcja siły operatorów, itd a na koniec chyba jeszcze alokacja rejestrów za pomocą algorytmów kolorowania grafów.

Tutaj coś ciekawego znalazłem:
http://wazniak.mimuw.edu.pl/index.php?title=Metody_realizacji_j%C4%99zyk%C3%B3w_programowania

Patryk27 napisał(a):

Tutaj coś ciekawego znalazłem:
http://wazniak.mimuw.edu.pl/index.php?title=Metody_realizacji_j%C4%99zyk%C3%B3w_programowania

A nie przyszło ci do głowy by redukować do listy, a potem ewaluować?

To co masz na dole :

mov(ei1, 2)
mov(ei2, 2)
mul(ei1, ei2)
add(ei1, 2)

To po prostu : (zapis lispowy)
(+ (* 2 2) 2)

Widać wyraźnie, że w przy takim zapisie wykonuje się najpierw wyrażenie najbardziej zagnieżdżone (w wyrażeniach zachowuje się kolejność działań)

Np.: ( ^ - potęga )

1 + a * 2 + b * ( 3 - c * 2 ^ 2 ) - 8

1 + ( a * 2 ) + ( b * (3 - ( c * (2 ^ 2) ) ) ) - 8

Co się przekłada na:
(+ (* (- (* (^ 2 2) c) 3) b) (* a 2) 1 -8) najpierw najbrdziej zagnieżdżone, potem mniej a na końcu liczby (ogranicza to ilość pushów na stos w przypadku napotkania nawiasu)
tak by nie było sytuacji, np. : (+ 3 (* 2 3) 2) (trójka z przodu).
Zaczynamy wtedy od najbardziej zagnieżdżonego czyli od pierwszego

 Pseudo kod:
1a. e1 = 2
1b. e2 = 2
1c. e1 = e1 ^ e2
3. e1 = e1 * c
5. e1 = e1 - 3
7. e1 = e1 * b
-tutaj kolejne wyrazenie w nawiasie --+
8. push e1                            |
-znow zaczynamy od gory               |
9. e1 = a                             |
10. e2 = 2                            |
11. e1 = e1 * e2                      |
12. pop e2                            | 
-poza nawiasem -----------------------+
13. e1 = e1 + e2
14. e1 = e1 + 1
15. e1 = e1 + (- 8)
koniec wyrażenia 
zwróc e1

Zauważyłeś pewien schemat?

To samo jeszcze raz dla 2 + 2 * 2

zapis w postaci NP z nawiasami (lista)
(+ (* 2 2) 2)

zaczynamy od najbardziej zngnieżdżonego nawiasu
e1 = 2
e2 = 2
e1 = e1 * e2
e1 = e1 + 2

Podążyłem za radą @RaveStar:
Parser wyrażeń najpierw zamienia wyrażenie na ONP (2+2*2 -> 2 2 2 * +), a potem na formę: 2 2 * 2 +, która jest już bardziej "oczywista", co do którego rejestru wrzucić.
W tym wypadku mamy:
2: idzie do rejestru ei1: mov(ei1, 2)
2: idzie do rejestru ei2: mov(ei2, 2)
*: mnożymy oba rejestry: mul(ei1, ei2), wynik jest w ei1
2: skoro w ei1 mamy wynik ostatniego działania, liczbę należy zapisać do ei2: mov(ei2, 2)
+: dodajemy oba rejestry: add(ei1, ei2), wynik jest w ei1
Ostatecznie:

mov(ei1, 2)
mov(ei2, 2)
mul(ei1, ei2)
mov(ei2, 2)
add(ei1, ei2)

I wynik w ei1 :)

---

Zobaczymy jak sprawdzi się w praktyce ;)

---

Edit: właśnie dokończyłem pisanie, działa świetnie nawet z bardziej zaawansowanymi działaniami typu: `10+(10*(2+2*2)-20)` W tym wypadku zostaje to zamienione na `2 2 * 2 + 10 * 20 - 10 + `, a kod wyjściowy: ``` mov(ei1, 2) mov(ei2, 2) mul(ei1, ei2) mov(ei2, 2) add(ei1, ei2) mov(ei2, 10) mul(ei1, ei2) mov(ei2, 20) sub(ei1, ei2) mov(ei2, 10) add(ei1, ei2) ``` Czyli nie jest najgorzej ;) Dorobi się różne optymalizacje i będzie śmigało aż miło :]

Jak zamienić wyrażenie zwykłe na ONP i inne:

http://www.seas.gwu.edu/~csci133/fall04/133f04toRPN.html

http://en.wikipedia.org/wiki/Shunting_yard_algorithm

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Witam ;)

Ostatecznie postanowiłem (i zaimplementowałem) binary expression tree.
Tj.:

1. zamieniam wyrażenie na ONP
2. ONP zamieniam na drzewo

---

Przykładowe drzewo wygenerowane dla wyrażenia `2+2*2`:  (`L` to lewa gałąź, `P` to prawa gałąź, `e_*` to odpowiednie tokeny) Oraz wygenerowany bytecode: ``` mov(ei1, 2) mov(ei2, 2) mul(ei1, ei2) ipush(ei1) mov(ei1, 2) ipop(ei2) add(ei1, ei2) ipush(ei1) ``` Idealnie nie jest, ale po włączeniu optymalizacji kod jest znacznie krótszy (w tym wypadku zostałoby same `ipush(6)`, ponieważ dodatkowo potem wywoływana jest funkcja `println`, której parametrem jest właśnie to wyrażenie). Te dodatkowe push'e tworzone są, aby przypadkiem w pewnym momencie nie napisać jakiegoś wyniku czymś innym. Akurat w tym prostym kodzie nie są one potrzebne, ale i tak są z jakiegoś powodu dodawane :P A teraz nieco trudniej: `(2+3)*func(10, func(func(2, 5), 2))` Wygenerowane drzewo:  Oraz bytecode (bez optymalizacji): ``` ipush(10) ipush(2) ipush(5) call(:__function_func) ipush(2) call(:__function_func) call(:__function_func) mov(ei1, 2) mov(ei2, 3) add(ei1, ei2) ipush(ei1) ipop(ei1) ipop(ei2) mul(ei1, ei2) ```

---

Cała implementacja zajmuje obiektowo około 900 linijek (w tej chwili `838` wraz z komentarzami); wrzuciłbym kod źródłowy, ale jest on ściśle związany z samym kompilatorem i prawdę mówiąc niewiele pewnie byście zrozumieli (nie mówiąc o jego skompilowaniu). W najbliższym czasie spróbuję zaimplementować to wszystko od nowa, aby nie było aż tak zależne od pozostałych modułów mojego kompilatora i postaram się wrzucić Wam kod ;)