Програмски преводиоци 1/К2 2020

Drugi kolokvijum 2020. godine održan je 22. januara 2021. godine, zbog neodržavanja druge kolokvijumske nedelje u regularnom terminu. Postavka ovog roka je dostupna sa stranice predmeta (arhiva).

1. zadatak

Postavka

Posmatra se lista od jednog ili više identifikatora ili celobrojnih konstanti, razdvojenih zarezima, pri čemu se na kraju koristi ";". Ulazni simboli su SLOVO, CIFRA, "," i ";". Identifikatori počinju slovom, a u nastavku imaju nula ili više slova ili cifara. Konstante sadrže samo cifre, mogu počinjati nulom. Primer ispravne liste: 1, a, tt20r, 120;

1. Napisati gramatiku (u kojoj repetitivne konstrukcije treba da budu predstavljene levo rekurzivnim smenama) za opisane liste. Terminalni simboli su SLOVO, CIFRA, "," i ";". Gramatika ne sme biti dvosmislena.
2. Transformisati gramatiku iza tačke a) u LL(1) gramatiku, primenom standarnih transformacija. Izračunati selekcione skupove i proveriti da li je dobijena gramatika LL(1).
3. Dodati u gramatiku iz tačke a) atribute kojima se računa vrednost svake od konstanti koje se pojavljuju u ulaznoj listi, a takođe i zbir vrednosti svih konstanti u listi. Napomena: akcione simbole ne uvoditi, nisu potrebni.

Rešenje

Gramatika tražena u stavci pod a može da glasi ovako:

1. <terminal> → SLOVO
2. <terminal> → CIFRA
3. <id> → <id> <terminal>
4. <id> → SLOVO
5. <konstanta> → <konstanta> CIFRA
6. <konstanta> → CIFRA
7. <element> → <id>
8. <element> → <konstanta>
9. <lista> → <lista>, <element>
10. <lista> → <element>
11. <S> → <lista>;

Transformisana LL(1) gramatika sa selekcionim skupovima može da izgleda ovako:

1. <terminal> → SLOVO

   SELECT(1) = {SLOVO}

2. <terminal> → CIFRA

   SELECT(2) = {CIFRA}

3. <id> → SLOVO <id'>

   SELECT(3) = {SLOVO}

4. <id'> → <terminal> <id'>

   SELECT(4) = FIRST(<terminal>) = {SLOVO, CIFRA}

5. <id'> → E

   SELECT(5) = FOLLOW(<id'>) = FOLLOW(<id>) = FOLLOW(<element>) = FIRST(<lista'>) ∪ FOLLOW(<lista'>) = {","} ∪ FOLLOW(<lista>) = {",", ";"}

6. <konstanta> → CIFRA <konstanta'>

   SELECT(6) = {CIFRA}

7. <konstanta'> → CIFRA <konstanta'>

   SELECT(7) = {CIFRA}

8. <konstanta'> → E

   SELECT(8) = FOLLOW(<konstanta'>) = {",", ";"}

9. <element> → <id>

   SELECT(9) = {SLOVO}

10. <element> → <konstanta>

    SELECT(10) = {CIFRA}

11. <lista> → <element> <lista'>

    SELECT(11) = FIRST(<element>) = {SLOVO, CIFRA}

12. <lista'> → , <element> <lista'>

    SELECT(12) = {","}

13. <lista'> → E

    SELECT(13) = {";"}

14. <S> → <lista>;

    SELECT(14) = FIRST(<lista>) = FIRST(<element>) = {SLOVO, CIFRA}

Zbog toga što se ni za jednu smenu ne preklapaju SELECT skupovi, ovo je LL(1) gramatika.

Atributivno-translaciona gramatika sa pomenutim atributima bi, zato, mogla da izgleda ovako:

1. <terminal> → SLOVO
2. <terminal> → CIFRA
3. <id> → <id> <terminal>
4. <id> → SLOVO
5. <konstanta>_v → <konstanta>_v1 CIFRA_v2

   v ← v1 + v2

6. <konstanta>_v → CIFRA_v1

   v ← v1

7. <element>_v → <id>

   v ← 0

8. <element>_v → <konstanta>_v1

   v ← v1

9. <lista>_v → <lista>_v1, <element>_v2

   v ← v1 + v2

10. <lista>_v → <element>_v1

    v ← v1

11. <S>_v → <lista>_v1;

    v ← v1

2. zadatak

Postavka

Data je gramatika:

1. <S> → f <A> f
2. <A> → c <B>
3. <B> → f <S> c
4. <B> → Ɛ

1. Da li se sekvenca fcffcfcf može prepoznati opisanom gramatikom? Prikazati postupak.
2. Nacrtati karakteristični automat i kontrolnu tabelu LR(0) parsera (potisnu ne crtati).
3. Prikazati kontrolnu tabelu SLR(1) parsera. Da li postoje konflikti?

Rešenje

• 

  Stablo izraza u stavci pod a.

• 

  Karakteristični automat u stavci pod b.

Kontrolna tabela LR(0) parsera

Stanje	Operacija
∇	SHIFT
<S>0	SHIFT
─┤0	ACCEPT
f11	SHIFT
<A>1	SHIFT
f12	REDUCE(1)
c2	S/R konflikt
<B>2	REDUCE(2)
f3	SHIFT
<S>3	SHIFT
c3	REDUCE(3)

FOLLOW skupovi ove gramatike su:

• FOLLOW(<S>) = {─┤, c}
• FOLLOW(<A>) = {f}
• FOLLOW(<B>) = {f}

Kontrolna tabela SLR(1) parsera

Stanje	c	f	─┤
∇		SHIFT
<S>0			SHIFT
─┤0			ACCEPT
f11	SHIFT
<A>1		SHIFT
f12	REDUCE(1)		REDUCE(1)
c2		S/R konflikt
<B>2		REDUCE(2)
f3		SHIFT
<S>3	SHIFT
c3		REDUCE(3)