Programski prevodioci 1/K2 2022

Drugi kolokvijum 2022. godine održan je 5. decembra. Trajao je 100 minuta i postavka roka nije trenutno dostupna sa stranice predmeta.

1. zadatak

Postavka

Na osnovu date potisne i kontrolne tabele LR(0) parsera:

1. Nacrtati karakteristični automat ovog parsera.
2. Odrediti gramatiku koju ovaj parser parsira.
3. Odrediti FOLLOW skupove ove gramatike. Ukoliko ovaj parser postane SLR(1), da li će biti konflikata?

Kontrolna i potisna tabela LR(0) parsera

Stanje	<E>	id	(	)	+	─┤	Akcija
∇	<E>x1	idx					SHIFT
<E>x1					+3	─┤0	SHIFT
─┤0							ACCEPT
idx			(2				SHIFT/REDUCE(1)
(2	<E>x2	idx					SHIFT
<E>x2				)2	+3		SHIFT
+3		id3					SHIFT
)2							REDUCE(2)
id3							REDUCE(3)

Rešenje

Karakteristični LR(0) automat iz stavke a prvog zadatka.

Gramatika koju ovaj automat parsira je:

1. <E> → id
2. <E> → id ( <E> )
3. <E> → <E> + id

FIRST i FOLLOW skupovi ove gramatike su:

• FIRST(<E>) = {id}
• FOLLOW(<E>) = {")", "+", ─┤}

U LR(0) automatu, u stanju id_x dešava se S/R konflikt. U SLR(1) parseru, za svaki terminal se akcija određuje posebno. Za terminal ( će se obavljati SHIFT, dok će za FOLLOW(<E>), odnosno za znakove ), + i ─┤, obavljati REDUCE(1). Zbog ovoga u SLR(1) parseru neće biti konflikata.

2. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Dopuniti parser ili gramatiku ispod na odgovarajući način na mestima označenim sa ????. Ukoliko se u ovu gramatiku dodaju sledeće dve smene:

• <S> → b <S>
• <B> → <B> f

da li gramatika ostaje LL(1) (obrazložiti zašto da ili zašto ne) i ukoliko ne ostaje transformisati tako da bude LL(1).

Gramatika:

1. <S> → a <A> e <B>
2. <S> → ????
3. <A> → b <S> d
4. <A> → ε
5. <B> → c ????
6. <B> → ????

Parser:

glavni program:
    INP = NEXTCHAR();
    call PROCS;
    /* ???? */
end;

procedure PROCS:
    case INP of
        ????: goto P1;
        ????: goto P2;
        default: REJECT();
    end case;
    P1: INP = NEXTCHAR();
        /* ???? */
        call A;
        /* ???? */
    P2: call A;
        call S;
        return;
end procedure;

procedure PROCA:
    case INP of
        ????: goto P3;
        ????: goto P4;
        default: REJECT();
    end case;
    P3: INP = NEXTCHAR();
        /* ???? */
    P4: /* ???? */
end procedure;

procedure PROCB:
    case INP of
        ????: goto P5;
        ????: goto P6;
        default: REJECT();
    end case;
    P5: INP = NEXTCHAR();
        /* ???? */
        call PROCS;
    P6: return;
end procedure;

Rešenje

Krajnja gramatika je:

1. <S> → a <A> e <B>
2. <S> → <A> <B>
3. <A> → b <S> d
4. <A> → ε
5. <B> → c <S>
6. <B> → ε

3. zadatak

Postavka

Data je gramatika koja opisuje binarno stablo:

1. <tree>_width,level → <node>
2. <node> → <node> ID <node>
3. <node> → NULL

U gramatici, između levog i desnog deteta nekog čvora dolazi identifikator tog čvora, dok ukoliko čvor nema dete na mestu njegovog podstabla piše NULL. Kroz nasleđeni atribut level prosleđuje se broj određenog nivoa stabla (koren ima nivo 0), a potrebno je napraviti atributivno-translacionu gramatiku koja u atribut width korena upisuje širinu stabla na tom nivou. Za svaki atribut napisati ulogu i da li je sintetizovan ili nasleđen.

Rešenje

Uvode se tri atributa:

• Nasleđeni atribut curr koji predstavlja trenutni nivo na kojem se nalazi čvor.
• Nasleđeni atribut aim koji predstavlja traženi nivo na kojem se meri širina.
• Sintetizovani atribut width koji predstavlja do tada izračunatu širinu stabla na zadatom nivou.

Sa njima, atributivno-translaciona gramatika izgleda ovako:

1. <tree>_width,level → <node>_{curr,aim,width1}

   $aim \leftarrow level$

   $curr \leftarrow 0$

   $width \leftarrow width_1$

2. <node>_{curr,aim,width} → <node>_c1,a1,w1 ID <node>_c2,a2,w2

   $a_1 \leftarrow aim$

   $a_2 \leftarrow aim$

   $c_1 \leftarrow curr + 1$

   $c_2 \leftarrow curr + 1$

   $width \leftarrow (curr = aim) + w_1 + w_2$

3. <node>_{curr,aim,width} → NULL

   $width \leftarrow (curr = aim)$