Kihagyás

Választható projektfeladatok

Mindegyik feladat egyszemélyes, azaz önálló megoldást kell rá adni. A nyelvtan fál(ok)nak és az esetlegesen mellékelt egyéb forrásfájloknak fordulnia kell, az előállt elemző futtatható kell, hogy legyen. A feladat megvalósítására több hét áll rendelkezésre, így a "Nem volt időm befejezni." nem kifogás. Az elemzés megvalósítása nem elegendő, a leadott kötelező programnak számolnia is kell. Egy hibásan, hiányosan működő, de működő program kevesebb pontot ér, de elfogadható, egy csak elemzést végző program, mégha tökéletes is, nem. (A saját AST építés már működésnek számít.)

A programok értékelésére nincs javítókulcs. Vannak bizonyos szempontok, pl:

  • Fordul-e, fut-e, több-e mint egy puszta elemzés?
  • Mennyire teljes, a kiírásnak mennyire felel meg?
  • Black-box szinten megfelelő-e, jó eredményt ad-e?
  • Szakmailag mennyire jó a megoldás? Megfelelő-e a nyelvtan, megfelelő-e az AST (ha van), jók-e a szemantikus akciók? Mennyire jó a számolás módja, mennyire illeszkedik a fordítóprogramok alapelveihez?

Ezen szempontok alapján a gyakorlatvezető saját szakmai tapasztalata alapján fogja értékelni a leadott munkákat.

[PR01] Szkript nyelv megvalósítása AST generálással.

A nyelv utasításai (amelyek ;-vel záródnak) a következők legyenek:

  • Egy kifejezés a következő operátorokkal/műveletekkel, megfelelő precedenciákkal: +, -, *, /, (, ), ABS(), ?:, =, ==, <, >. Az utolsó 3 logikai kifejezés értéke 0 ha nem igaz, 1 ha igaz.
  • Legyen benne print(...) utasítás, ami a paraméterül kapott kifejezést, vagy kifejezéseket kiírja.
  • Legyen benne scan(...) utasítás, ami a paraméterül kapott változók értékét olvassa be.
  • A kifejezés levelében lehet szám (egész és tizedes tört is), lehet változónév (ha eddig nem volt neki érték adva, akkor az értéke legyen 0), és lehet TIME is, ami az aktuális idő (a UNIX idő, azaz az 1970 óta eltelt másodpercek száma).
  • Lehessen benne változókat deklarálni int vagy double típusokkal (csak ez a kettő). Nem deklarált változók használata vagy változó újradeklarálása esetén keletkezzen hiba. A változók globálisak, függetlenül attól, hol lettek deklarálva.
  • A változódeklaráció is utasítás olyan szempontból, hogy ha nem fut le, akkor nem jön létre az adott változó. Lehessen változót törölni a del utasítással.
  • Lehessen benne for és while ciklus C szerű szintaktikával.
  • Legyen benne if és switch-case-default utasítás is.
  • Legyen megjegyzési lehetőség.
Példa input #1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int starttime;
int sum;
int x;
starttime = TIME;
sum = 0;
for (x=0; x<10; x=x+1) {
  sum = sum + x;
}
print(sum);
print(TIME - starttime);
Példa input #2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Ez az input fuggvenyeben futhat helyesen
# vagy okozhat futasi hibat
int x;
scan(x);
while(x>0) {
    switch(x) {
        case 1: int y; scan(y); break;
        case 2: del y;
        case 3: x = 5; break;
        default: x = 10;
    }
    scan(x);
}
print(x+y);

Az elemző csak felépítse az AST-t, a végrehajtás pedig ezen az AST-n egy külön fázisban történjen.

[PR02] Táblázatkezelő megvalósítása AST generálással.

A program bemenetként egy CSV fájlt várjon, ahol az egyes cellákban vagy számok, vagy stringek, vagy kifejezések lehetnek. Kimentként ki kell számolnia az összes kifejezést és HTML táblázatba kiírni a kiszámoltakat. A kifejezést tartalmazó cellák = jellel kezdődnek. Egy kifejezésben lehet:

  • Egyszerű (egész vagy tizedestört) szám, vagy szöveg idézőjelek között.
  • A számokra legyen értelmezve a 4 alapművelet zárójelezéssel, precedenciával.
  • A szövegnél a + operátor konkatenációt jelentsen. Ha sztringet kell számmal összefűzni, akkor a szám értéke szövegesen fűződjön hozzá. Pl. "Eredemény="+(2+2) értéke "Eredmény=4" legyen.
  • Tartalmazhat cellahivatkozást is. (Pl. A1 az első cella értékét jelenti.) Körkörös hivatkozásba ne halljon bele -- detektálja valahogy.
  • Tartalmazhat SUM(...) kifejezést, ami paraméterül egy cellatartományt vár kezdőcella:végcella formában.
  • Tartalmazhat IND(...) kifejezést, ami paraméterül egy sztring értéket vár, ami egy cellahivatkozás, és ennek a cellának az értékét adja vissza.
Példa input #1
1
2
12;=35.5+6*2;=A1+B1
"szöveg";"másik szöveg";=A2+B2+C1
Példa input #2
1
2
3
4
12;=(35.5+6*2)/A1;=SUM(A1:B2)
"szöveg";"másik szöveg";=A3+C1
=C3;;=C2*A1;"B2"
=IND("A1")+IND(IND("D3"))+IND(D3)

[PR03] Bájtkód generálás és futtatás.

A program inputként kifejezéseket kap a négy alapművelettel, hatványozással, zárójelezéssel és értékadással, ahol a változók m[x] nevűek. (Kezdetben mindegyik változó értéke 0). Legyen benne read(x) utasítás, ami az m[x] változó értékét olvassa be. Ebből kell ANTLR nyelvtan segítségével saját bájtkódot (a bájtkód itt általános fogalom, nem (kizárólag) a Java Bytecode-ot jelenti) generálni. A bájtkód specifikációjában (milyen kódú opkód milyen utasítást jelent) szabad kezed van, és abban is, hogy az azt futtató virtuális gépet milyen nyelven implementálod -- azaz annak nem kell ANTLR-rel készülnie, viszont bájtkód jellege kell, hogy legyen (assembly-szerű lineáris memóriával vagy regiszterekkel, veremgép, stb.; akár konkrét assembly vagy java bájtkód). Lényeg, hogy a generált kód a virtuális gépen futtatva kiírja a konzolra az összes kifejezés értékét. A "fordítás" közben lehet optimalizálást végezni.

Példa input #1
1
2
m[1]=12+3*5
23-(5-1)+2*m[1+0*99]
Példa input #2
1
2
3
read(0)
read(m[0])
m[2*m[0]]=(m[0]+m[1])*m[m[0]]

[PR04] Polinom-számológép.

A program képes valós együtthatós polinomokkal (polinomtörtekkel) számolni.

  • Egy polinom <a_n x^n + ... + a_1 x + a_0> alakban adható meg, ahol
  • az x egy foglalt nyelvi elem
  • n tetszőleges egész szám lehet
  • a_n ... a_0 valós együttható értékek (literálok)
  • a 0 együtthatójú tag elhagyható
  • az x^1 jelölés írható x alakban is
  • az x^0 jelölés pedig elhagyható (ekkor csak az a_0 együttható szerepel a polinom megadásában).
  • Polinom-változóknak p = <kifejezés> alakban lehet értéket adni, ahol
  • p egy polynom p;-ként deklarált változó,
  • a <kifejezés> egy polinom-kifejezés.
  • Polinomokkal a következő műveletek végezhetők:
  • +, -, *, /, % (utóbbi kettő maradékos polinom-osztás hányadosa és maradéka, mindkettő polinom),
  • zárójelezés ( és ) segítségével, valamint
  • kiértékelés <kifejezés>[X] alakban, ahol X tetszőleges valós szám lehet, és
  • a kiértékelés művelet magas prioritású.
  • A program show utasítása kiírja a megadott kifejezés értékét (ha az polinom, akkor a polinomot).
  • A programban lehetnek valós típusú változók (number), amelyek a polinomokban együtthatóként használhatók.
Példa input #1
1
2
3
4
5
6
7
8
polynom p_1, p_2;
number a;
a = 3 - 2 * 1;
p_1 = <x - a>;
p_2 = <x+1x^0>;
show((p_1 * p_2)[3]);
show(p_1 * p_2[2]);
show((<x^2 + 2x + 1> / <1x^1 + 1>)[p_1[2]]);
Példa input #2
1
2
3
4
5
polynom a, b, c;
a = <x - 1>;
b = <x + 1x^0>;
c = a / b + <2x + 2>[3];
show(c);

Utolsó frissítés: 2022-05-13 09:39:25