[nastava:2004] - RE: prevodioci - 4. domaci by "Predrag Gojic" <pgojic@EUnet.yu>

	Verovatno si mislio na 3. zadatak.
Slican zadatka je bio 2001/02.


Pozdrav,
Pedja


Naći L atributivno translacionu LL(1) gramatiku koja opisuje niz iskaza dodele oblika:
	promenljiva = izraz ;
Identifikatori promenljivih su jednoslovni. Izraz se sastoji od promenljivih i operatora sabiranja i oduzimanja, a može sadržati i zagrade.
Napisati parser, na programskom jeziku po izboru, koji radi na principu rekurzivnog spusta i koji dati niz iskaza prevodi u niz iskaza u formi:
	promenljiva = jednostavan_izraz
gde jednostavan izraz predstavlja ili promenljivu ili dve promenljive povezane jednim operatorom. Po potrebi se uvode privremene promenljive koje se označavaju sa $1, $2, itd.

1.	<S> → idn = <E>s {genExp}a,b,c
 		a←n, b←”=”, c←s
2.	<E>s → <T>s1 <E’>z,s2 {genExp}a,b,c,d,e
 		(s,a) ←newTemp, b←”=”, c←s1, d←z, e←s2
3.	<E’>z,s → + <T>s1 <E’>z2,s2 {genExp}a,b,c,d,e
 		(s,a) ←newTemp, b←”=”, c←s1, d←z2, e←s2, z←”+”
4.	<E’>z,s → – <T>s1 <E’>z2,s2 {genExp}a,b,c,d,e
 		(s,a) ←newTemp, b←”=”, c←s1, d←z2, e←s2, z←”–”
5.	<E’>z,s → ε
 		(z,s) ←NULL
6.	<T>p → ( <E>s )
 		p←s
7.	<T>p → idn
 		p←n

Listing programa
#include <fstream.h>
#include <iostream.h>
#include <stdlib.h>

struct Par{
    char klasa, vred;
    Par(char k, char v) {klasa=k; vred=v;}
    void ispis(ofstream &oo) { oo<<"("<<klasa<<","<<vred<<") ";}
};

struct Atribut{
    char klasa;
    int broj;
    static int count;
    Atribut() {}
    void newTemp() { klasa='$'; broj=count++;}
};

int Atribut::count=0;

ostream & operator<<(ostream& oo, Atribut& a) {
    oo<<a.klasa;
    if(a.klasa=='$') oo<<a.broj;
    return oo;
}
Par* nextToken(ifstream &in) {
    char p;
    do {
        p=(char)in.get();
    }while (p==' '||p=='\n');
    if (p==EOF) return new Par('$', 0);
    if (p=='+'||p=='-'||p=='('||p==')'||p=='=') return new Par(p,0);
    else if (p>='A'&&p<='z') return new Par('v',p);
    else {
        cout<<"LA: nedozvoljen ulazni simbol: "<<p<<endl;
        exit(1);
    }
}

void accept() { cout<<"OK."<<endl; }
void reject() {
    cout<<"Greska u parsiranju!"<<endl;
    exit(1);
}

Par* procS(Par*, ifstream&);
Par* procE(Par*, ifstream&, Atribut&);
Par* procEE(Par*, ifstream&, Atribut&, Atribut&);
Par* procT(Par*, ifstream&, Atribut&);

Par* procS(Par *p, ifstream& in) {
    Atribut n, s;
    if (p->klasa=='v') {
        n.klasa=p->vred;
        p=nextToken(in);
    }
    else reject();
    if (p->klasa=='=') p=nextToken(in);
    else reject();
    p=procE(p,in,s);
    cout<<n<<'='<<s<<endl;
    return p;
}

Par* procE(Par *p, ifstream& in,Atribut &s){
    Atribut tp, te1, te2;
    switch (p->klasa){
        case 'v': case '(': goto s21;
        default: reject();
    }
  s21:
    p=procT(p,in,tp);
    p=procEE(p,in,te1,te2);
    s.newTemp();
    cout<<s<<'='<<tp<<te1<<te2<<endl;
    return p;
}

Par* procEE(Par *p, ifstream& in, Atribut &znak, Atribut &s){
    Atribut tp, te1, te2;
    switch (p->klasa) {
        case '+': znak.klasa='+';goto s3;
        case '-': znak.klasa='-';goto s4;
        case '$': case ')': goto s5;
        default: reject();
    }
  s3:
    p=nextToken(in);
    p=procT(p,in,tp);
    p=procEE(p,in,te1,te2);
    s.newTemp();
    cout<<s<<'='<<tp<<te1<<te2<<endl;
    return p;
  s4:
    p=nextToken(in);
    p=procT(p,in,tp);
    p=procEE(p,in,te1,te2);
    s.newTemp();
    cout<<s<<'='<<tp<<te1<<te2<<endl;
    return p;
  s5:
    znak.klasa=s.klasa=0;
    return p;
}

Par* procT(Par *p, ifstream& in, Atribut &s) {
    Atribut tp;
    switch (p->klasa) {
        case '(': goto s6;
        case 'v': goto s7;
    }
  s6:
    p=nextToken(in);
    p=procE(p,in,tp);
    s.klasa=tp.klasa; s.broj=tp.broj;
    if (p->klasa==')') p=nextToken(in);
    else reject();
    return p;
  s7:
    s.klasa=p->vred;
    p=nextToken(in);
    return p;
}

int main (int argc, char *argv[]) {
    ifstream in(argv[1]);
    Par *p= nextToken(in);
    p=procS(p,in);
    if (p->klasa=='$') accept();
    else reject();
}



> -----Original Message-----
> From: v.i@verat.net [mailto:v.i@verat.net] 
> Sent: 28 September 2004 19:40
> To: nastava@titan.etf.bg.ac.yu
> Subject: [nastava] prevodioci - 4. domaci
> 
> 
> Ljudi, meni nesto sistemski nije jasno u ovom 4. zadatku. 
> Covek trazi da se napravi parser na principu rekurzivnog 
> spusta (dakle top-down, deterministicki parser sa jednim 
> predikcionim simbolom, kao kod njega u
> zbirci) za gramatiku koja opisuje regularne izraze sa +,-,*,/ 
> i !, pritom postujuci asocijativnost i prioritete.
> 
> Ovakva gramatika ima direktnu levu rekurziju, dakle nemoze se 
> seterministicki parsirati gorepomenutim nacinom, sto je i 
> pokazano u zbirci.
> 
> Jer ja nesto previdjam, ili je postavka malo pogresna?
> 
> Ideje? Komentari?
> 
> Pozdrav!
> 
> -----------------------------------------------------------------
> unsubscribe:
>    minimalist@titan.etf.bg.ac.yu?subject=unsubscribe%20nastava
> -----------------------------------------------------------------
>