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);
}
w3cw3c
automatyka przemysłowa