Kompilator wyrażeń arytmetycznych
-- Sebastian Pawlak, 2003.
Program dla wyrażeń arytmetycznych
(opisanych zadaną gramatyką) generuje optymalny (minimalna ilość
wykorzystanej pamięci) kod "asemblera".
Mój program działa według następującego, ogólnego schematu:
1. Wczytaj wyrażenie.
2. Skonwertuj wyrażenie do Odwrotnej Notacji Polskiej.
3. Rozbij wyrażenie na wyrażenia cząstkowe (np. x0=a*b, x0=3+x0).
4. Stwórz tabelę pomocną przy optymalizacji.
5. Optymalizuj wyrażenia na podstawie tabeli.
6. Generuj kod w "asemblerze" (dostępne mnemoniki: MOV, ADD, MUL).
Warta uwagi jest funkcja konwertująca wyrażenie w notacji nawiasowej do
wyrażenia w Odwrotnej Notacji Polskiej. Oto algorytm konwersji wykorzystujący
stos. Uwaga: "znacznik" to spacja.
Krok 1 - Jeżeli nie ma więcej znaków w ciągu wejściowym, to realizuj krok 6;
w przeciwnym razie przeczytaj następny element (nawias, operator lub
argument) i nazwij go x.
Krok 2 - Jeżeli x jest argumentem, to zapisz go w ciągu wyjściowym, umieść po
nim znacznik i przejdź do realizacji kroku 1.
Krok 3 - Jeżeli x jest nawiasem otwierającym, wpisz go na stos i realizuj krok 1.
Jeżeli x jest nawiasem zamykającym, przejdź do realizacji kroku 4,
a w przeciwnym razie - kroku 5.
Krok 4 - Jeżeli na wierzchu stosu nie ma nawiasu otwierającego, to wycofaj ten
obiekt ze stosu wpisując go do ciągu wyjściowego, a zaraz za nim wpisz
znacznik i przejdź do wykonywania kroku 4. Jeżeli na wierzchołku stosu
jest nawias otwierający, to wycofaj go ze stosu i przejdź do realizacji
kroku 1.
Krok 5 - W przypadku gdy priorytet elementu wierzchołkowego stosu jest większy
lub równy priorytetowi x, wycofaj element z wierzchołka stosu, wpisz go
do ciągu wyjściowego, a potem wpisz za nim znacznik i powtórz krok 5.
W przeciwnym razie połóż x na wierzchołek stosu i wróć do wykonywania
kroku 1.
Krok 6 - Opróżnij stos po jednym elemencie wpisując każdy z nich do ciągu
wyjściowego i wstawiając między nimi znaczniki i to już koniec.
Założenia:
1. Wyrażenie jest postaci i:=wyrażenie. "i" to identyfikator (jedna wielka lub
mała litera). "wyrażenie" to wyrażenie artymetyczne bez spacji, np.
a*(b+23). Zmiennych, używanych w wyrażeniu, tyczą się te same zasady co
identyfikatorów.
2. Zakładam, że wejściowe wyrażenie jest poprawne.
3. Dostępne są operatory "*" (iloczyn) i "+" (suma). Iloczyn ma wyższy
priorytet niż suma.
Po uruchomieniu programu należy wpisać wyrażenie arytmetyczne.
Można także wywołać program przekierowując na niego strumień:
echo "i:=a+b" | ./a.out
Kod programu w plikach main.c, stos.c i stos.h
Oto przykładowy wynik pracy z programem:
Podaj wyrazenie arytmetyczne bez spacji (np. i:=a+b*(2+c)): Zmienne moga miec dlugosc jednego znaku (litera duza lub mala). i:=a+a+2*(a+b)+b*b Wynik konwersji do Odwrotnej Notacji Polskiej: a a + 2 a b + * + b b * + Wynik rozbicia na wyrazenia czastkowe: x0 = a + a x1 = b + a x2 = x1 * 2 x3 = x2 + x0 x4 = b * b x5 = x4 + x3 Tabela optymalizacji: x0 x1 x2 x3 x4 x5 0 - - - - - - 1 v - - - - - 2 v v - - - - 3 v - v - - - 4 - - - v - - 5 - - - v v - -- - - - - - v Wynik optymalizacji: x0 = a + a x1 = b + a x1 = x1 * 2 x0 = x1 + x0 x1 = b * b x0 = x1 + x0 Generowanie kodu (MNEMONIK arg1, arg2 <=> arg2 op= arg1): MOV a, x0 ADD a, x0 MOV b, x1 ADD a, x1 MUL 2, x1 ADD x1, x0 MOV b, x1 MUL b, x1 ADD x1, x0 MOV x0, i
Kod źródłowy pliku "stos.h":
/* Implementacja stosu. */ #ifndef STOS_H #define STOS_H void push(unsigned long int); unsigned long int pop(void); int ileElementow(void); #endif
Kod źródłowy pliku "stos.c":
/* Implementacja stosu.
*/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "stos.h"
#define MAX_STOS 1024 /* maksymalny rozmiar stosu */
unsigned long int stos[MAX_STOS];
int sp = 0; /* wskaznik kolejnego wolnego miejsca na stosie */
/* Wstawianie elementu na stos. */
void push(unsigned long int element)
{
if (sp < MAX_STOS)
stos[sp++] = element;
else
printf("push: Przepelnienie stosu!\n");
}
/* Pobieranie elementu ze stosu. */
unsigned long int pop(void)
{
if (sp > 0)
return stos[--sp];
return 0;
}
/* Zwraca liczbe elementow na stosie */
int ileElementow(void)
{
return sp;
}
Kod źródłowy pliku "main.c":
/*************************************
* Kompilator wyrazen arytmetycznych *
* z optymalizacja. *
* Sebastian Pawlak, s1222 *
*************************************/
/* Identyfikator i wszystkie zmienne moga miec dlugosc jednego
* znaku (litery duze lub male).
* Wartosci liczbowe musza byc naturalne.
* Rozroznia sie operatory: * iloczyn, + suma
* Dwa najstarsze bity liczby sa zarezerwowane na flagi - tak
* wiec max wartosc liczby wynosi 2^(8*sizeof(unsigned long)-2).
*/
#include <stdio.h>
#include <string.h> /* dla strlen() */
#include <stdlib.h> /* dla atol() */
#include <ctype.h> /* dla isalnum() */
#include "stos.h"
#define MAX 1024 /* maksymalna dlugosc wyrazenia (OdwNotPl) w znakach */
void konwerterONP(char *, char *);
int wyrazeniaCzastkowe(char *);
void optymalizacja(int);
void generowanieKodu(int, char);
int main(void)
{
char wyrazenie[MAX], wyrazenieONP[MAX], *wsk;
int liczbaWyrazen;
printf("Podaj wyrazenie arytmetyczne bez spacji (np. i:=a+b*(2+c)):\n");
printf("Zmienne moga miec dlugosc jednego znaku (litera duza lub mala).\n");
fscanf(stdin, "%s", wyrazenie);
if (!(wsk = strstr(wyrazenie, ":="))) {
fprintf(stderr, "main: Blad - brak :=\n");
exit(-1);
}
konwerterONP(wyrazenieONP, wsk + 2 /* omin := */);
printf("\nWynik konwersji do Odwrotnej Notacji Polskiej: \n%s\n\n", wyrazenieONP);
printf("Wynik rozbicia na wyrazenia czastkowe:\n");
liczbaWyrazen = wyrazeniaCzastkowe(wyrazenieONP);
if (ileElementow()) {
printf("\nTabela optymalizacji:\n");
optymalizacja(liczbaWyrazen);
}
printf("\nGenerowanie kodu (MNEMONIK arg1, arg2 <=> arg2 op= arg1):\n");
generowanieKodu(liczbaWyrazen, wyrazenie[0]);
return 0;
}
/* Funkcja przeksztalca wyrazenie zapisane w notacji nawiasowej
* do wyrazenia w Odwrotnej Notacji Polskiej.
*
* Obslugiwane sa operatory: * +
*/
void konwerterONP(char *wynik, char *s)
{
char x, y;
while (x = *s++) { /* krok 1 */
if (isalnum(x)) { /* krok 2 */
/* kopiowanie calej liczby z wejscia na wyjscie */
do *wynik++ = x; while (x = *s, isalnum(x) && s++);
*wynik++ = ' ';
} else if (x == '(') /* krok 3 */
push((double)'(');
else if (x == ')') /* krok 4 */
while ((y = (char)pop()) != '(')
*wynik++ = y, *wynik++ = ' ';
else { /* krok 5 */
while (y = (char)pop(), y && (y == '*' || (y == '+' && x != '*')))
*wynik++ = y, *wynik++ = ' ';
push((double)y);
push((double)x);
}
}
while(x = (char)pop()) /* krok 6 */
*wynik++ = x, *wynik++ = ' ';
*wynik = '\0'; /* zakonczenie wyjsciowego lancucha znakow zerem */
}
/* maski bitowe */
#define ZMIENNA (1 << (8 * sizeof (unsigned long int) - 2))
#define ZMIENNA2 (2 << (8 * sizeof (unsigned long int) - 2))
#define LICZBA (3 << (8 * sizeof (unsigned long int) - 2))
#define MASKA (3 << (8 * sizeof (unsigned long int) - 2))
struct {
unsigned long int arg1, arg2;
int nr;
char op;
} wyrazenia[MAX];
/* Funkcja wypisuje argument na wyjscie.
* Rozroznia czy argument jest liczba, zmienna zywa czy zmienna tymczasowa */
void wypisz(unsigned long int l)
{
if ((l & MASKA) == LICZBA) /* liczba */
printf("%ld", l & ~LICZBA);
else if ((l & MASKA) == ZMIENNA) /* zmienna zywa */
printf("%c", (char)(l & ~ZMIENNA));
else if ((l & MASKA) == ZMIENNA2) /* zmienna tymczasowa */
printf("x%d", (char)(l & ~ZMIENNA2));
else fprintf(stderr, "wypisz: Blad!\n");
}
/* Funkcja rozbija podane wyrazenia na wyrazenia czastkowe
* postaci xN = arg1 op arg2.
*/
int wyrazeniaCzastkowe(char *s)
{
char element[MAX];
int nrZmiennej = 0;
unsigned long int arg1, arg2;
while (sscanf(s, "%s", element) != -1) {
s += strlen(element) + 1;
if (isdigit(element[0])) /* cyfra */
push(LICZBA | atol(element));
else if (isalpha(element[0])) /* litera */
push(ZMIENNA | element[0]);
else if (element[0] == '*') { /* iloczyn */
/* wypisanie wyrazenia na ekran */
printf("x%d = ", nrZmiennej);
wypisz(arg1 = pop());
printf(" * ");
wypisz(arg2 = pop());
printf("\n");
/* zapamietanie wyrazenia w tablicy */
wyrazenia[nrZmiennej].arg1 = arg1;
wyrazenia[nrZmiennej].arg2 = arg2;
wyrazenia[nrZmiennej].op = '*';
push(ZMIENNA2 | nrZmiennej++);
} else if (element[0] == '+') { /* suma */
/* wypisanie wyrazenia na ekran */
printf("x%d = ", nrZmiennej);
wypisz(arg1 = pop());
printf(" + ");
wypisz(arg2 = pop());
printf("\n");
/* zapamietanie wyrazenia w tablicy */
wyrazenia[nrZmiennej].arg1 = arg1;
wyrazenia[nrZmiennej].arg2 = arg2;
wyrazenia[nrZmiennej].op = '+';
push(ZMIENNA2 | nrZmiennej++);
} else {
fprintf(stderr, "wyrazeniaCzastkowe: Blad - nieznany znak!\n");
exit(-1);
}
}
/* sprawdzanie czy nie podano prostego wyrazenia typu i:=2 - bez operatorow */
if (((arg1 = pop()) & MASKA) == ZMIENNA || (arg1 & MASKA) == LICZBA) {
printf("x%d = ", nrZmiennej);
wypisz(arg1);
printf("\n");
wyrazenia[nrZmiennej++].arg1 = arg1;
} else push(arg1);
return nrZmiennej; /* liczba wyrazen czastkowych */
}
/* Funkcja tworzy tabele optymalizacji i generuja zoptymalizowane
* wyrazenia czastkowe.
*/
void optymalizacja(int liczbaWyrazen)
{
char tab[MAX][MAX] = { "\0" };
int i, j, k;
tab[liczbaWyrazen][liczbaWyrazen - 1] = 1; /* wynikowa zmienna tmp zywa */
for (i = liczbaWyrazen - 1; i >= 0; i--) {
for (j = 0; j < liczbaWyrazen - 1; j++) /* przepisz wiersz do gory tabeli */
tab[i][j] = tab[i + 1][j];
tab[i][i] = 0; /* zabij aktualna zmienna tmp uzywana po lewej stronie */
if ((wyrazenia[i].arg1 & MASKA) == ZMIENNA2) /* ozyw uzyw. po praw. str. zmienne tmp */
tab[i][wyrazenia[i].arg1 & ~ZMIENNA2] = 1;
if ((wyrazenia[i].arg2 & MASKA) == ZMIENNA2)
tab[i][wyrazenia[i].arg2 & ~ZMIENNA2] = 1;
}
/* wypisz tabele optymalizacji na wyjscie */
printf(" ");
for (i = 0; i < liczbaWyrazen; i++) /* wypisz nazwy zmiennych w naglowku tabeli */
printf("x%-4d", i);
printf("\n");
for (i = 0; i <= liczbaWyrazen; i++) {
if (i < liczbaWyrazen) /* numer wyrazenia - lewa pionowa kolumna tabeli */
printf("%2d ", i);
else printf("-- ");
for (j = 0; j < liczbaWyrazen; j++) /* "v" zywe, "-" nie zywe */
printf(" %c ", tab[i][j] ? 'v' : '-');
printf("\n");
}
/* tworzenie optymalnych wyrazen na podstawie tabeli */
wyrazenia[0].nr = 0;
for (i = 1; i < liczbaWyrazen; i++) {
for (j = 0; j < i; j++) {
for (k = i - 1; k >= 0; k--)
if (wyrazenia[k].nr == j)
break;
if (tab[i][k] == 0 || (tab[i][k] == 1 && tab[i + 1][k] == 0)) /* wolna zm. tmp */
break;
}
if (j < i) {
wyrazenia[i].nr = j;
/* z powodu zmiany zmiennej xN na inna xK (z powodu wolnego miejsca)
* nalezy wszystkie wystapienia zmiennej xN pozamieniac na xK
*/
for (k = i; k < liczbaWyrazen; k++) {
if ((wyrazenia[k].arg1 & MASKA) == ZMIENNA2 &&
(wyrazenia[k].arg1 & ~ZMIENNA2) == i)
wyrazenia[k].arg1 = ZMIENNA2 | j;
if ((wyrazenia[k].arg2 & MASKA) == ZMIENNA2 &&
(wyrazenia[k].arg2 & ~ZMIENNA2) == i)
wyrazenia[k].arg2 = ZMIENNA2 | j;
}
} else wyrazenia[i].nr = i;
}
printf("\nWynik optymalizacji:\n");
for (i = 0; i < liczbaWyrazen; i++) {
printf("x%d = ", wyrazenia[i].nr);
wypisz(wyrazenia[i].arg1);
printf(" %c ", wyrazenia[i].op);
wypisz(wyrazenia[i].arg2);
printf("\n");
}
}
/* Funkcja na podstawie optymalnych wyrazen czastkowych generuje kod
* w pseudo asemblerze.
* Drugi argument menemoniku stanowi wynik danej operacji:
* ADD arg1, arg2 <=> arg2 += arg1
*/
void generowanieKodu(int liczbaWyrazen, char e)
{
int i, k;
/* jesli mamy do czynienia z prostym wyrazeniem typu i:=2 - bez operatorow */
if (!ileElementow()) {
printf("MOV ");
wypisz(wyrazenia[liczbaWyrazen - 1].arg1);
printf(", %c\n", e);
return;
}
for (i = 0; i < liczbaWyrazen; i++) {
if ((wyrazenia[i].arg1 & MASKA) == ZMIENNA2 &&
(wyrazenia[i].arg1 & ~ZMIENNA2) == wyrazenia[i].nr)
k = 1; /* wyrazenie typu xN = xN op b <=> xN op= b */
else if ((wyrazenia[i].arg2 & MASKA) == ZMIENNA2 &&
(wyrazenia[i].arg2 & ~ZMIENNA2) == wyrazenia[i].nr)
k = 2; /* wyrazenie typu xN = b op xN <=> xN op= b */
else k = 0; /* wyrazenie typi xN = xK op b lub xN = b op xK lub
* xN = xK op xL lub xN = a op b */
if (k) { /* jesli wyrazenie typu k == 1 lub k == 2 */
printf("%s ", wyrazenia[i].op == '*' ? "MUL" : "ADD");
wypisz(k == 1 ? wyrazenia[i].arg2 : wyrazenia[i].arg1);
printf(", x%d\n", wyrazenia[i].nr);
} else { /* jesli wyrazenie typu k == 0 */
printf("MOV ");
wypisz(wyrazenia[i].arg1);
printf(", x%d\n", wyrazenia[i].nr);
printf("%s ", wyrazenia[i].op == '*' ? "MUL" : "ADD");
wypisz(wyrazenia[i].arg2);
printf(", x%d\n", wyrazenia[i].nr);
}
}
/* przepisanie wartosc ze zmiennej tmp ostatniego wyrazenia do id */
printf("MOV x%d, %c\n", wyrazenia[liczbaWyrazen - 1].nr, e);
}
