Програмски преводиоци 1/К2 2020 - Историја измена

KockaAdmiralac: Ispravka da se u petoj smeni množi sa 10

2022-12-03T14:00:47Z

Ispravka da se u petoj smeni množi sa 10

← Старија измена		Верзија на датум 3. децембар 2022. у 16:00
Ред 61:		Ред 61:
	# <id> → <id> <terminal>		# <id> → <id> <terminal>
	# <id> → SLOVO		# <id> → SLOVO
	# <konstanta><sub>v</sub> → <konstanta><sub>v1</sub> CIFRA<sub>v2</sub>		# <konstanta><sub>v</sub> → <konstanta><sub>v<sub>1</sub></sub> CIFRA<sub>v<sub>2</sub></sub>
	#: v ~~← v1~~ + v2		#: <math>v \leftarrow 10v_1 + v_2</math>
	# <konstanta><sub>v</sub> → CIFRA<sub>v1</sub>		# <konstanta><sub>v</sub> → CIFRA<sub>v<sub>1</sub></sub>
	#: v ~~← v1~~		#: <math>v \leftarrow v_1</math>
	# <element><sub>v</sub> → <id>		# <element><sub>v</sub> → <id>
	#: v ← 0		#: <math>v \leftarrow 0</math>
	# <element><sub>v</sub> → <konstanta><sub>v1</sub>		# <element><sub>v</sub> → <konstanta><sub>v<sub>1</sub></sub>
	#: v ~~← v1~~		#: <math>v \leftarrow v_1</math>
	# <lista><sub>v</sub> → <lista><sub>v1</sub>, <element><sub>v2</sub>		# <lista><sub>v</sub> → <lista><sub>v<sub>1</sub></sub>, <element><sub>v<sub>2</sub></sub>
	#: v ~~← v1~~ + v2		#: <math>v \leftarrow v_1 + v_2</math>
	# <lista><sub>v</sub> → <element><sub>v1</sub>		# <lista><sub>v</sub> → <element><sub>v<sub>1</sub></sub>
	#: v ~~← v1~~		#: <math>v \leftarrow v_1</math>
	# <S><sub>v</sub> → <lista><sub>v1</sub>;		# <S><sub>v</sub> → <lista><sub>v<sub>1</sub></sub>;
	#: v ~~← v1~~		#: <math>v \leftarrow v_1</math>

	== 2. zadatak ==		== 2. zadatak ==

KockaAdmiralac: Ispravljeni epsilon simboli

2022-12-02T20:38:26Z

Ispravljeni epsilon simboli

← Старија измена		Верзија на датум 2. децембар 2022. у 22:38
Ред 34:		Ред 34:
	# <id'> → <terminal> <id'>		# <id'> → <terminal> <id'>
	#: SELECT(4) = FIRST(<terminal>) = {SLOVO, CIFRA}		#: SELECT(4) = FIRST(<terminal>) = {SLOVO, CIFRA}
	# <id'> → E		# <id'> → ε
	#: SELECT(5) = FOLLOW(<id'>) = FOLLOW(<id>) = FOLLOW(<element>) = FIRST(<lista'>) ∪ FOLLOW(<lista'>) = {","} ∪ FOLLOW(<lista>) = {",", ";"}		#: SELECT(5) = FOLLOW(<id'>) = FOLLOW(<id>) = FOLLOW(<element>) = FIRST(<lista'>) ∪ FOLLOW(<lista'>) = {","} ∪ FOLLOW(<lista>) = {",", ";"}
	# <konstanta> → CIFRA <konstanta'>		# <konstanta> → CIFRA <konstanta'>
Ред 40:		Ред 40:
	# <konstanta'> → CIFRA <konstanta'>		# <konstanta'> → CIFRA <konstanta'>
	#: SELECT(7) = {CIFRA}		#: SELECT(7) = {CIFRA}
	# <konstanta'> → E		# <konstanta'> → ε
	#: SELECT(8) = FOLLOW(<konstanta'>) = {",", ";"}		#: SELECT(8) = FOLLOW(<konstanta'>) = {",", ";"}
	# <element> → <id>		# <element> → <id>
Ред 50:		Ред 50:
	# <lista'> → , <element> <lista'>		# <lista'> → , <element> <lista'>
	#: SELECT(12) = {","}		#: SELECT(12) = {","}
	# <lista'> → E		# <lista'> → ε
	#: SELECT(13) = {";"}		#: SELECT(13) = {";"}
	# <S> → <lista>;		# <S> → <lista>;
Ред 82:		Ред 82:
	# <A> → c <B>		# <A> → c <B>
	# <B> → f <S> c		# <B> → f <S> c
	# <B> → Ɛ		# <B> → ε
	<div class="abc-list">		<div class="abc-list">
	# Da li se sekvenca <code>fcffcfcf</code> može prepoznati opisanom gramatikom? Prikazati postupak.		# Da li se sekvenca <code>fcffcfcf</code> može prepoznati opisanom gramatikom? Prikazati postupak.

KockaAdmiralac: +transparent-svg

2022-11-29T23:10:59Z

+transparent-svg

← Старија измена		Верзија на датум 30. новембар 2022. у 01:10
Ред 90:		Ред 90:

	=== Rešenje ===		=== Rešenje ===
	<gallery widths="500" heights="500">		<gallery widths="500" heights="500" class="transparent-svg">
	PPR K2 2020 zadatak 2 stavka a.svg \| Stablo izraza u stavci pod a.		PPR K2 2020 zadatak 2 stavka a.svg \| Stablo izraza u stavci pod a.
	PPR K2 2020 zadatak 2 stavka b.svg \| Karakteristični automat u stavci pod b.		PPR K2 2020 zadatak 2 stavka b.svg \| Karakteristični automat u stavci pod b.

KockaAdmiralac: Rešenje i drugog zadatka

2022-11-29T23:10:33Z

Rešenje i drugog zadatka

@@ Ред 90: / Ред 90: @@
 === Rešenje ===
 [[Категорија:Рокови]]
 [[Категорија:Програмски преводиоци 1]]

KockaAdmiralac: Rešenje samo prvog zadatka zasad

2022-11-29T11:56:13Z

Rešenje samo prvog zadatka zasad

Нова страница

{{tocright}}
'''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 [http://ir4pp1.etf.rs/Rokovi/2020-2021/pp1-2021-k1k2-si.zip 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;
<div class="abc-list">
# 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.
# 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).
# 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.
</div>

=== Rešenje ===
Gramatika tražena u stavci pod a može da glasi ovako:
# <terminal> → SLOVO
# <terminal> → CIFRA
# <id> → <id> <terminal>
# <id> → SLOVO
# <konstanta> → <konstanta> CIFRA
# <konstanta> → CIFRA
# <element> → <id>
# <element> → <konstanta>
# <lista> → <lista>, <element>
# <lista> → <element>
# <S> → <lista>;

Transformisana LL(1) gramatika sa selekcionim skupovima može da izgleda ovako:
# <terminal> → SLOVO
#: SELECT(1) = {SLOVO}
# <terminal> → CIFRA
#: SELECT(2) = {CIFRA}
# <id> → SLOVO <id'>
#: SELECT(3) = {SLOVO}
# <id'> → <terminal> <id'>
#: SELECT(4) = FIRST(<terminal>) = {SLOVO, CIFRA}
# <id'> → E
#: SELECT(5) = FOLLOW(<id'>) = FOLLOW(<id>) = FOLLOW(<element>) = FIRST(<lista'>) ∪ FOLLOW(<lista'>) = {","} ∪ FOLLOW(<lista>) = {",", ";"}
# <konstanta> → CIFRA <konstanta'>
#: SELECT(6) = {CIFRA}
# <konstanta'> → CIFRA <konstanta'>
#: SELECT(7) = {CIFRA}
# <konstanta'> → E
#: SELECT(8) = FOLLOW(<konstanta'>) = {",", ";"}
# <element> → <id>
#: SELECT(9) = {SLOVO}
# <element> → <konstanta>
#: SELECT(10) = {CIFRA}
# <lista> → <element> <lista'>
#: SELECT(11) = FIRST(<element>) = {SLOVO, CIFRA}
# <lista'> → , <element> <lista'>
#: SELECT(12) = {","}
# <lista'> → E
#: SELECT(13) = {";"}
# <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:
# <terminal> → SLOVO
# <terminal> → CIFRA
# <id> → <id> <terminal>
# <id> → SLOVO
# <konstanta>v → <konstanta>v1 CIFRAv2
#: v ← v1 + v2
# <konstanta>v → CIFRAv1
#: v ← v1
# <element>v → <id>
#: v ← 0
# <element>v → <konstanta>v1
#: v ← v1
# <lista>v → <lista>v1, <element>v2
#: v ← v1 + v2
# <lista>v → <element>v1
#: v ← v1
# <S>v → <lista>v1;
#: v ← v1

== 2. zadatak ==
=== Postavka ===
Data je gramatika:
# <S> → f <A> f
# <A> → c 
# → f <S> c
# → Ɛ
<div class="abc-list">
# Da li se sekvenca <code>fcffcfcf</code> može prepoznati opisanom gramatikom? Prikazati postupak.
# Nacrtati karakteristični automat i kontrolnu tabelu LR(0) parsera (potisnu ne crtati).
# Prikazati kontrolnu tabelu SLR(1) parsera. Da li postoje konflikti?
</div>

=== Rešenje ===

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]