KockaAdmiralac: Falilo povećavanje nivoa

2022-12-05T23:29:38Z

Falilo povećavanje nivoa

← Старија измена		Верзија на датум 6. децембар 2022. у 01:29
Ред 146:		Ред 146:
	#: <math>a_1 \leftarrow aim</math>		#: <math>a_1 \leftarrow aim</math>
	#: <math>a_2 \leftarrow aim</math>		#: <math>a_2 \leftarrow aim</math>
	#: <math>c_1 \leftarrow curr</math>		#: <math>c_1 \leftarrow curr + 1</math>
	#: <math>c_2 \leftarrow curr</math>		#: <math>c_2 \leftarrow curr + 1</math>
	#: <math>width \leftarrow (curr = aim) + w_1 + w_2</math>		#: <math>width \leftarrow (curr = aim) + w_1 + w_2</math>
	# <node><sub>curr,aim,width</sub> → NULL		# <node><sub>curr,aim,width</sub> → NULL

KockaAdmiralac: Rekonstrukcija današnjeg roka sa rešenjem prvog i trećeg zadatka

2022-12-05T23:12:38Z

Rekonstrukcija današnjeg roka sa rešenjem prvog i trećeg zadatka

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

{{tocright}}
'''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:
<div class="abc-list">
# Nacrtati karakteristični automat ovog parsera.
# Odrediti gramatiku koju ovaj parser parsira.
# Odrediti FOLLOW skupove ove gramatike. Ukoliko ovaj parser postane SLR(1), da li će biti konflikata?
</div>
{| class="wikitable"
|+ 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 ===
[[Датотека:PPR K2 2022 zadatak 1 automat.svg|thumb|Karakteristični LR(0) automat iz stavke a prvog zadatka.]]
Gramatika koju ovaj automat parsira je:
# <E> → id
# <E> → id ( <E> )
# <E> → <E> + id
FIRST i FOLLOW skupovi ove gramatike su:
* FIRST(<E>) = {id}
* FOLLOW(<E>) = {")", "+", ─┤}
U LR(0) automatu, u stanju idx 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 ==
{{delimično rešeno}}
=== 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>
* → 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:
# <S> → a <A> e 
# <S> → ????
# <A> → b <S> d
# <A> → ε
# → c ????
# → ????
Parser:<ref>Na kolokvijumu je rečeno da pozivi poput <code>call A</code> imaju isto značenje kao <code>call PROCA</code>.</ref>
<pre>
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;
</pre>

=== Rešenje ===
Krajnja gramatika je:
# <S> → a <A> e 
# <S> → <A> 
# <A> → b <S> d
# <A> → ε
# → c <S>
# → ε

== 3. zadatak ==
=== Postavka ===
Data je gramatika koja opisuje binarno stablo:
# <tree>width,level → <node>
# <node> → <node> ID <node>
# <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 <code>level</code> prosleđuje se broj određenog nivoa stabla (koren ima nivo 0), a potrebno je napraviti atributivno-translacionu gramatiku koja u atribut <code>width</code> 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 <code>curr</code> koji predstavlja trenutni nivo na kojem se nalazi čvor.
* Nasleđeni atribut <code>aim</code> koji predstavlja traženi nivo na kojem se meri širina.
* Sintetizovani atribut <code>width</code> koji predstavlja do tada izračunatu širinu stabla na zadatom nivou.
Sa njima, atributivno-translaciona gramatika izgleda ovako:
# <tree>width,level → <node>curr,aim,width1
#: <math>aim \leftarrow level</math>
#: <math>curr \leftarrow 0</math>
#: <math>width \leftarrow width_1</math>
# <node>curr,aim,width → <node>c1,a1,w1 ID <node>c2,a2,w2
#: <math>a_1 \leftarrow aim</math>
#: <math>a_2 \leftarrow aim</math>
#: <math>c_1 \leftarrow curr</math>
#: <math>c_2 \leftarrow curr</math>
#: <math>width \leftarrow (curr = aim) + w_1 + w_2</math>
# <node>curr,aim,width → NULL
#: <math>width \leftarrow (curr = aim)</math>

== Napomene ==
<references />

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

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

KockaAdmiralac: Falilo povećavanje nivoa

KockaAdmiralac: Rekonstrukcija današnjeg roka sa rešenjem prvog i trećeg zadatka