KockaAdmiralac: Ispravljen SELECT(2)

2022-12-04T14:35:08Z

Ispravljen SELECT(2)

← Старија измена		Верзија на датум 4. децембар 2022. у 16:35
Ред 66:		Ред 66:
	#: SELECT(1) = {f}		#: SELECT(1) = {f}
	# <S> → ε		# <S> → ε
	#: SELECT(2) = {a}		#: SELECT(2) = {─┤}
	# <A> → <A> <A> d		# <A> → <A> <A> d
	#: SELECT(3) = {f}		#: SELECT(3) = {f}
Ред 77:		Ред 77:
	#: SELECT(1) = {f}		#: SELECT(1) = {f}
	# <S> → ε		# <S> → ε
	#: SELECT(2) = {a}		#: SELECT(2) = {─┤}
	# <A> → f <A'>		# <A> → f <A'>
	#: SELECT(3) = {f}		#: SELECT(3) = {f}

KockaAdmiralac: Trajanje

2022-12-01T11:19:12Z

Trajanje

← Старија измена		Верзија на датум 1. децембар 2022. у 13:19
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
	'''Drugi kolokvijum 2019. godine''' održan je 2. decembra. Postavka roka dostupna je [http://ir4pp1.etf.rs/Rokovi/2019-2020/pp1-1920-k1k2.zip sa stranice predmeta] (arhiva).		'''Drugi kolokvijum 2019. godine''' održan je 2. decembra i trajao je 90 minuta. Postavka roka dostupna je [http://ir4pp1.etf.rs/Rokovi/2019-2020/pp1-1920-k1k2.zip sa stranice predmeta] (arhiva).

	== 1. zadatak ==		== 1. zadatak ==

KockaAdmiralac: Moja rešenja K2 2019

2022-12-01T10:59:50Z

Moja rešenja K2 2019

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

{{tocright}}
'''Drugi kolokvijum 2019. godine''' održan je 2. decembra. Postavka roka dostupna je [http://ir4pp1.etf.rs/Rokovi/2019-2020/pp1-1920-k1k2.zip sa stranice predmeta] (arhiva).

== 1. zadatak ==
=== Postavka ===
<div class="abc-list">
# Kojoj gramatici odgovara dati rekurzivni prepoznavač napisan na pseudojeziku?
# Nalaženjem SELECT skupova proveriti da li je gramatika iz tačke a) tipa LL(1).
# Ukoliko već nije, transformisati gramatiku iz tačke a) da bude LL(1).
</div>
<pre>
glavni program:
INP = prvi ulazni simbol
call PROCS;
if (INP <> '─┤')
then REJECT;
else ACCEPT;
end if;
end;

procedure PROCS:
case INP of
'c', 'f': {
call PROCA;
if (INP <> 'a')
then REJECT;
else call ADVANCE;
end if;
}
'─┤': /* ništa */ return;
'a', 'd': REJECT;
end case;
end procedure;

procedure PROCA:
case INP of
'c': {
call PROCA;
call PROCA;
if (INP <> 'd')
then REJECT;
else ADVANCE;
end if;
}
'f': call PROCB;
'a', 'd', '─┤': REJECT;
end case;
end procedure;

procedure PROCB:
case INP of
'c': ADVANCE;
'f': ADVANCE;
'a', 'd', '─┤': REJECT;
end case;
end procedure;
</pre>

=== Rešenje ===
Ovaj rekurzivni prepoznavač odgovara gramatici sa mrtvim neterminalom <A>. Ako bismo izbacili mrtve neterminale, dobili bismo gramatiku koja izgleda ovako:
# <S> → <A> a
# <S> → ε
# <A> → f
Ipak, ovo verovatno nije ono što je bio očekivani odgovor na ovu stavku. Bolja formulacija prve stavke bi bila "Kada bi se gramatika tehnikom rekurzivnog spusta prebacila u kod parsera, dobija se sledeći izvorni kod. Odrediti izvornu gramatiku." U ovom slučaju dobija se gramatika koja izgleda ovako:
# <S> → <A> a
#: SELECT(1) = {f}
# <S> → ε
#: SELECT(2) = {a}
# <A> → <A> <A> d
#: SELECT(3) = {f}
# <A> → f
#: SELECT(4) = {f}
Četvrta smena ove gramatike može biti samo f, zato što se PROCB iz originalnog parsera ne poziva u slučaju da na ulazu dođe terminal c.

Ova gramatika nije LL(1) zbog prisustva leve rekurzije. Kada eliminišemo levu rekurziju, ova gramatika izgleda ovako:
# <S> → <A> a
#: SELECT(1) = {f}
# <S> → ε
#: SELECT(2) = {a}
# <A> → f <A'>
#: SELECT(3) = {f}
# <A'> → <A> d <A'>
#: SELECT(4) = {f}
# <A'> → ε
#: SELECT(5) = {a}
Na ovaj način se SELECT skupovi smena ne preklapaju, i zato je ova gramatika LL(1).

== 2. zadatak ==
=== Postavka ===
Za datu gramatiku sa neterminalima S i A:
# <S> → <A>
# <S> → b c <A> c
# <A> → b
<div class="abc-list">
# Popuniti sadržaje stanja karakterističnog LR(0) automata na datoj slici (ne popunjavati unutar {})
# Popuniti predikcione skupove {} unutar stanja na slici da bi se dobio karakteristični LALR(1) automat.
# Popuniti kontrolnu tabelu SLR(1) parsera.
# Popuniti kontrolnu tabelu LALR(1) parsera
</div>

=== Rešenje ===
[[Датотека:PPR K2 2019 zadatak 2 automat.svg|thumb|Dijagram iz stavki a i b zadatka.]]
{| class="wikitable"
|+ Kontrolna tabela SLR(1) parsera
! Stanje !! b !! c !! ─┤
|-
| ∇ || SHIFT || ||
|-
| b3b4 || || '''S/R konflikt''' || REDUCE(3)
|-
| <S>0 || || || SHIFT
|-
| ─┤0 || || || ACCEPT
|-
| <A>1 || || || REDUCE(1)
|-
| c21 || SHIFT || ||
|-
| <A>2 || || SHIFT ||
|-
| c22 || || || REDUCE(2)
|-
| b3 || || REDUCE(3) || REDUCE(3)
|}
{| class="wikitable"
|+ Kontrolna tabela LALR(1) parsera
! Stanje !! b !! c !! ─┤
|-
| ∇ || SHIFT || ||
|-
| b3b4 || || SHIFT || REDUCE(3)
|-
| <S>0 || || || SHIFT
|-
| ─┤0 || || || ACCEPT
|-
| <A>1 || || || REDUCE(1)
|-
| c21 || SHIFT || ||
|-
| <A>2 || || SHIFT ||
|-
| c22 || || || REDUCE(2)
|-
| b3 || || REDUCE(3) ||
|}

== 3. zadatak ==
=== Postavka ===
Data je gramatika koja opisuje niz koji se sastoji od jednog ili više celih brojeva razdvojenih zarezima. Datoj gramatici dodeliti atribute i akcije ukoliko je potrebno tako da startni neterminal <niz> ima sintetizovani atribut u kome se nalazi duzina[sic] najduze[sic] neopadajuće sekvence u nizu. Smatrati da terminal BROJ ima sintetizovani atribut sa vrednošću tog broja. Za svaki uvedeni atribut potrebno je naznačiti njegov tip.
# <niz> → BROJ , <niz>
# <niz> → BROJ

=== Rešenje ===
Uvode se tri sintetizovana atributa, maksimalna dužina neopadajućeg niza brojeva (<math>ml</math>), trenutna dužina neopadajućeg niza brojeva (<math>l</math>) i prvi broj u nizu (<math>n</math>).
# <niz>ml,l,n → BROJval , <niz>ml1,l1,n1
#: <math>l \leftarrow (l_1 + 1) \cdot (val \leq n_1) + 1 \cdot (val > n_1)</math>
#: <math>ml \leftarrow l \cdot (l > ml_1) + ml_1 \cdot (l \leq ml_1)</math>
#: <math>n \leftarrow val</math>
# <niz>ml,l,n → BROJval
#: <math>ml \leftarrow 1</math>
#: <math>l \leftarrow 1</math>
#: <math>n \leftarrow val</math>

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

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

KockaAdmiralac: Ispravljen SELECT(2)

KockaAdmiralac: Trajanje

KockaAdmiralac: Moja rešenja K2 2019