KockaAdmiralac: Izmena da bude konzistentnije sa pravilima leve faktorizacije

2022-12-02T15:16:36Z

Izmena <broj'> da bude konzistentnije sa pravilima leve faktorizacije

← Старија измена		Верзија на датум 2. децембар 2022. у 17:16
Ред 21:		Ред 21:
	# <niz'> → , <broj> <niz'>		# <niz'> → , <broj> <niz'>
	#: SELECT(2) = {","}		#: SELECT(2) = {","}
	# <niz'> → E		# <niz'> → ε
	#: SELECT(3) = {-\|}		#: SELECT(3) = {-\|}
	# <broj> → BIT <broj'>		# <broj> → BIT <broj'>
	#: SELECT(4) = {BIT}		#: SELECT(4) = {BIT}
	# <broj'> → ~~BIT~~ <broj'>		# <broj'> → <broj>
	#: SELECT(5) = {BIT}		#: SELECT(5) = {BIT}
	# <broj'> → E		# <broj'> → ε
	#: SELECT(6) = {",", -\|}		#: SELECT(6) = {",", -\|}
	Neterminalu <niz> možemo dodati atribut koji broji koliko je neparnih brojeva bilo u njemu, dok neterminalu <broj> možemo dodati atribute koji kažu da li je taj broj paran (<math>p</math>, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja (<math>e</math>). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako:		Neterminalu <niz> možemo dodati atribut koji broji koliko je neparnih brojeva bilo u njemu, dok neterminalu <broj> možemo dodati atribute koji kažu da li je taj broj paran (<math>p</math>, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja (<math>e</math>). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako:
Ред 34:		Ред 34:
	# <niz'><sub>n</sub> → , <broj><sub>p,e</sub> <niz'><sub>n<sub>1</sub></sub>		# <niz'><sub>n</sub> → , <broj><sub>p,e</sub> <niz'><sub>n<sub>1</sub></sub>
	#: <math>n \leftarrow n_1 + p</math>		#: <math>n \leftarrow n_1 + p</math>
	# <niz'>_n → E		# <niz'>_n → ε
	#: <math>n \leftarrow 0</math>		#: <math>n \leftarrow 0</math>
	# <broj><sub>p,e</sub> → BIT<sub>v</sub> <broj'><sub>p<sub>1</sub>,e<sub>1</sub></sub>		# <broj><sub>p,e</sub> → BIT<sub>v</sub> <broj'><sub>p<sub>1</sub>,e<sub>1</sub></sub>
	#: <math>p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1</math>		#: <math>p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1</math>
	#: <math>e \leftarrow 0</math>		#: <math>e \leftarrow 0</math>
	# <broj'><sub>p,e</sub> → ~~BIT<sub>v</sub>~~ <broj'><sub>p<sub>1</sub>,e<sub>1</sub></sub>		# <broj'><sub>p,e</sub> → <broj><sub>p<sub>1</sub>,e<sub>1</sub></sub>
	#: <math>p \leftarrow ~~e_1 \cdot v + (1 - e_1) \cdot~~ p_1</math>		#: <math>p \leftarrow p_1</math>
	#: <math>e \leftarrow 0</math>		#: <math>e \leftarrow e_1</math>
	# <broj'><sub>p,e</sub> → ε		# <broj'><sub>p,e</sub> → ε
	#: <math>p \leftarrow 0</math>		#: <math>p \leftarrow 0</math>

KockaAdmiralac: Ispravljen FOLLOW skup za A i dodate dve REDUCE smene u kontrolnu tabelu; ažurirana potisna tabela sa stanjima iz ispravljenog dijagrama

2022-12-02T15:10:22Z

Ispravljen FOLLOW skup za A i dodate dve REDUCE smene u kontrolnu tabelu; ažurirana potisna tabela sa stanjima iz ispravljenog dijagrama

← Старија измена		Верзија на датум 2. децембар 2022. у 17:10
Ред 204:		Ред 204:
	* FIRST(<A>) = {c}		* FIRST(<A>) = {c}
	* FIRST(<S>) = FIRST(<A>) = {c}		* FIRST(<S>) = FIRST(<A>) = {c}
	* FOLLOW(<A>) = FIRST(<S>) ∪ {b} = {b, c}		* FOLLOW(<A>) = FIRST(<S>) ∪ FOLLOW(<S>) ∪ {b} = {─┤, b, c}
	* FOLLOW(<S>) = FOLLOW(<A>) ∪ FIRST(<S>) ∪ {─┤} = {─┤, b, c}		* FOLLOW(<S>) = FOLLOW(<A>) ∪ FIRST(<S>) ∪ {─┤} = {─┤, b, c}
	{\| class="wikitable"		{\| class="wikitable"
Ред 224:		Ред 224:
	\|-		\|-
	! <A><sub>x</sub>		! <A><sub>x</sub>
	\| <S><sub>1</sub> \|\| \|\| b<sub>3</sub> \|\| \|\|		\| <S><sub>1</sub> \|\| <A><sub>x</sub> \|\| b<sub>3</sub> \|\| c<sub>4</sub> \|\|
	\|-		\|-
	! b<sub>3</sub>		! b<sub>3</sub>
	\| <S><sub>3</sub> \|\| \|\| \|\| \|\|		\| <S><sub>3</sub> \|\| <A><sub>x</sub> \|\| \|\| c<sub>4</sub> \|\|
	\|-		\|-
	! <S><sub>3</sub>		! <S><sub>3</sub>
Ред 237:		Ред 237:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Kontrolna tabela SLR(1) parsera		\|+ Kontrolna tabela SLR(1) parsera
	! Stanje !! b !! c !! ─┤		! Stanje !! b !! c !! ─┤
	\|-		\|-
	\| ∇ \|\| REDUCE(2) \|\| '''S/R konflikt''' \|\| REDUCE(2)		\| ∇ \|\| REDUCE(2) \|\| '''S/R konflikt''' \|\| REDUCE(2)
	\|-		\|-
	\| <S><sub>0</sub> \|\| \|\| \|\| SHIFT		\| <S><sub>0</sub> \|\| \|\| \|\| SHIFT
	\|-		\|-
	\| ─┤<sub>0</sub> \|\| \|\| \|\| ACCEPT		\| ─┤<sub>0</sub> \|\| \|\| \|\| ACCEPT
	\|-		\|-
	\| c<sub>4</sub> \|\| REDUCE(4) \|\| REDUCE(4) \|\|		\| c<sub>4</sub> \|\| REDUCE(4) \|\| REDUCE(4) \|\| REDUCE(4)
	\|-		\|-
	\| <A><sub>x</sub> \|\| '''S/R konflikt''' \|\| '''S/R konflikt''' \|\| REDUCE(2)		\| <A><sub>x</sub> \|\| '''S/R konflikt''' \|\| '''S/R konflikt''' \|\| REDUCE(2)
	\|-		\|-
	\| b<sub>3</sub> \|\| REDUCE(2) \|\| '''S/R konflikt''' \|\| REDUCE(2)		\| b<sub>3</sub> \|\| REDUCE(2) \|\| '''S/R konflikt''' \|\| REDUCE(2)
	\|-		\|-
	\| <S><sub>3</sub> \|\| REDUCE(3) \|\| REDUCE(3) \|\|		\| <S><sub>3</sub> \|\| REDUCE(3) \|\| REDUCE(3) \|\| REDUCE(3)
	\|-		\|-
	\| <S><sub>1</sub> \|\| REDUCE(1) \|\| REDUCE(1) \|\| REDUCE(1)		\| <S><sub>1</sub> \|\| REDUCE(1) \|\| REDUCE(1) \|\| REDUCE(1)
	\|}		\|}

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

KockaAdmiralac: Moja rešenja K2 2017

2022-12-01T16:38:20Z

Moja rešenja K2 2017

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

{{tocright}}
'''Drugi kolokvijum 2017. godine''' održan je 2. decembra i trajao je 90 minuta. Postavka roka dostupna je [http://ir4pp1.etf.rs/Rokovi/2017-2018/si4pp1-1718-k1k2.zip sa stranice predmeta] (arhiva).

== 1. zadatak ==
=== Postavka ===
Data je gramatika koja opisuje niz brojeva u brojnom sistemu sa osnovom dva (niz binarnih vrednosti). Brojevi su razdvojeni zarezom. Broj se sastoji od jednog ili više bitova.
# <niz> → <niz> , <broj>
# <niz> → <broj>
# <broj> → BIT <broj>
# <broj> → BIT
<div class="abc-list">
# Gramatiku transformisati u LL(1) gramatiku.
# Gramatiku dobijenu pod a) dopuniti atributima tako da startni neterminal <niz> sadrži sintetizovani atribut koji predstavlja ukupan broj neparnih vrednosti u nizu. Terminal BIT ima sintetizovani atribut koji može biti 1 ili 0 u zavisnosti od vrednosti bita.
# Na osnovu gramatike dobijene pod b) formirati parser rekurzivnog spusta.
</div>

=== Rešenje ===
Gramatika transformisana u LL(1) zajedno sa SELECT skupovima glasi ovako:
# <niz> → <broj> <niz'>
#: SELECT(1) = {BIT}
# <niz'> → , <broj> <niz'>
#: SELECT(2) = {","}
# <niz'> → E
#: SELECT(3) = {-|}
# <broj> → BIT <broj'>
#: SELECT(4) = {BIT}
# <broj'> → BIT <broj'>
#: SELECT(5) = {BIT}
# <broj'> → E
#: SELECT(6) = {",", -|}
Neterminalu <niz> možemo dodati atribut koji broji koliko je neparnih brojeva bilo u njemu, dok neterminalu <broj> možemo dodati atribute koji kažu da li je taj broj paran (<math>p</math>, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja (<math>e</math>). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako:
# <niz>n → <broj>p,e <niz'>n1
#: <math>n \leftarrow n_1 + p</math>
# <niz'>n → , <broj>p,e <niz'>n1
#: <math>n \leftarrow n_1 + p</math>
# <niz'>_n → E
#: <math>n \leftarrow 0</math>
# <broj>p,e → BITv <broj'>p1,e1
#: <math>p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1</math>
#: <math>e \leftarrow 0</math>
# <broj'>p,e → BITv <broj'>p1,e1
#: <math>p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1</math>
#: <math>e \leftarrow 0</math>
# <broj'>p,e → ε
#: <math>p \leftarrow 0</math>
#: <math>e \leftarrow 1</math>
Parser rekurzivnog spusta za ovu gramatiku bi glasio:
<syntaxhighlight lang="cpp">
char input;

int terminal(char t) {
if (input == t) {
input = advance();
// Za dobijanje vrednosti terminala BIT.
return getInputValue();
} else {
reject();
}
}

void parse() {
int n;
input = advance();
niz(n);
terminal(EOF);
}

void niz(int& n) {
switch (input) {
case BIT:
int p;
int e;
broj(p, e);
int n1;
niz1(n1);
n = n1 + p;
break;
default: reject();
}
}

void niz1(int& n) {
switch (input) {
case ',':
terminal(',');
int p;
int e;
broj(p, e);
int n1;
niz1(n1);
n = n1 + p;
break;
case EOF:
n = 0;
break;
default: reject();
}
}

void broj(int& p, int& e) {
switch (input) {
case BIT:
e = 0;
int v = terminal(BIT);
int p1;
int e1;
broj1(p1, e1);
p = p1;
if (e1) {
p = v;
}
break;
default: reject();
}
}

void broj1(int& p, int& e) {
switch (input) {
case BIT:
e = 0;
int v = terminal(BIT);
int p1;
int e1;
broj1(p1, e1);
p = p1;
if (e1) {
p = v;
}
break;
case ',':
case EOF:
p = 0;
e = 1;
break;
default: reject();
}
}
</syntaxhighlight>

== 2. zadatak ==
=== Postavka ===
Jedna bezbednosna agencija na osnovu zakona o obelodanjivanju informacija objavila je delove dosijea poznatog kompjuterskog stručnjaka sa sledećim LALR(1) karakterističnim automatom u kome su neka stanja namerno zasenčena:
<div class="abc-list">
# Navesti sadržaje svih zasenčenih stanja.
# Napisati originalnu gramatiku na osnovu koje je konstruisan dati automat.
# Napisati KONTROLNU tabelu LALR(1) parsera. Potisnu ne pisati (negativni poeni).
# Koje je finalno stanje na vrhu steka parsera i finalni rezultat parsiranja ulazne sekvence: cacbd─┤
</div>

=== Rešenje ===
[[Датотека:PPR K2 2017 zadatak 2 automat.svg|thumb|Karakteristični automat iz stavkе pod a drugog zadatka.]]
Originalna gramatika glasi:
# <S> → a b <A>
# <S> → <A> <C>
# <A> → a <C> b
# <A> → ε
# <C> → c <A>
# <C> → d
{| class="wikitable"
|+ Kontrolna tabela LALR(1) parsera
! Stanje !! a !! b !! c !! d !! ─┤
|-
| ∇ || SHIFT || || REDUCE(4) || REDUCE(4) ||
|-
| <A>2 || || || SHIFT || SHIFT ||
|-
| <S>0 || || || || || SHIFT
|-
| <C>2 || || || || || REDUCE(2)
|-
| ax || || SHIFT || SHIFT || SHIFT ||
|-
| d6 || || REDUCE(6) || || ||
|-
| <C>3 || || SHIFT || || ||
|-
| b3 || || || REDUCE(3) || REDUCE(3) || REDUCE(3)
|-
| ─┤0 || || || || || ACCEPT
|-
| b1 || SHIFT || || || || REDUCE(4)
|-
| <A>1 || || || || || REDUCE(1)
|-
| a3 || || || SHIFT || SHIFT ||
|-
| c5 || SHIFT || REDUCE(4) || || ||
|-
| <A>5 || || REDUCE(5) || || ||
|}
Na kraju parsiranja date sekvence na vrhu steka je stanje <A>5, i sekvenca se odbija.

== 3. zadatak ==
=== Postavka ===
Na osnovu zadate beskontekstne gramatike, u kojoj se simbol ε koristi za opis praznih smena, konstruisati SLR(1) parser konfiguracionom metodom i odrediti FIRST i FOLLOW skupove.
# <S> → <A> <S>
# <S> → ε
# <A> → <A> b <S>
# <A> → c

=== Rešenje ===
[[Датотека:PPR K2 2017 zadatak 3 automat.svg|thumb|Karakteristični automat iz trećeg zadatka.]]
FIRST i FOLLOW skupovi su sledeći:
* FIRST(<A>) = {c}
* FIRST(<S>) = FIRST(<A>) = {c}
* FOLLOW(<A>) = FIRST(<S>) ∪ {b} = {b, c}
* FOLLOW(<S>) = FOLLOW(<A>) ∪ FIRST(<S>) ∪ {─┤} = {─┤, b, c}
{| class="wikitable"
|+ Potisna tabela SLR(1) parsera
! Stanje
! <S> !! <A> !! b !! c !! ─┤
|-
! ∇
| <S>0 || <A>x || || c4 ||
|-
! <S>0
| || || || || ─┤0
|-
! ─┤0
| || || || ||
|-
! c4
| || || || ||
|-
! <A>x
| <S>1 || || b3 || ||
|-
! b3
| <S>3 || || || ||
|-
! <S>3
| || || || ||
|-
! <S>1
| || || || ||
|}
{| class="wikitable"
|+ Kontrolna tabela SLR(1) parsera
! Stanje !! b !! c !! ─┤
|-
| ∇ || REDUCE(2) || '''S/R konflikt''' || REDUCE(2)
|-
| <S>0 || || || SHIFT
|-
| ─┤0 || || || ACCEPT
|-
| c4 || REDUCE(4) || REDUCE(4) ||
|-
| <A>x || '''S/R konflikt''' || '''S/R konflikt''' || REDUCE(2)
|-
| b3 || REDUCE(2) || '''S/R konflikt''' || REDUCE(2)
|-
| <S>3 || REDUCE(3) || REDUCE(3) ||
|-
| <S>1 || REDUCE(1) || REDUCE(1) || REDUCE(1)
|}

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

← Старија измена		Верзија на датум 4. децембар 2022. у 18:37
Ред 185:		Ред 185:
	\| a<sub>3</sub> \|\| \|\| \|\| SHIFT \|\| SHIFT \|\|		\| a<sub>3</sub> \|\| \|\| \|\| SHIFT \|\| SHIFT \|\|
	\|-		\|-
	\| c<sub>5</sub> \|\| SHIFT \|\| REDUCE(4) \|\| \|\| \|\|		\| c<sub>5</sub> \|\| SHIFT \|\| REDUCE(4) \|\| \|\| \|\| REDUCE(4)
	\|-		\|-
	\| <A><sub>5</sub> \|\| \|\| REDUCE(5) \|\| \|\| \|\| REDUCE(5)		\| <A><sub>5</sub> \|\| \|\| REDUCE(5) \|\| \|\| \|\| REDUCE(5)

← Старија измена		Верзија на датум 3. децембар 2022. у 16:08
Ред 187:		Ред 187:
	\| c<sub>5</sub> \|\| SHIFT \|\| REDUCE(4) \|\| \|\| \|\|		\| c<sub>5</sub> \|\| SHIFT \|\| REDUCE(4) \|\| \|\| \|\|
	\|-		\|-
	\| <A><sub>5</sub> \|\| \|\| REDUCE(5) \|\| \|\| \|\|		\| <A><sub>5</sub> \|\| \|\| REDUCE(5) \|\| \|\| \|\| REDUCE(5)
	\|}		\|}
	Na kraju parsiranja date sekvence na vrhu steka je stanje <A><sub>5</sub>, i sekvenca se odbija.		Na kraju parsiranja date sekvence na vrhu steka je stanje <A><sub>5</sub>, i sekvenca se odbija.

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

KockaAdmiralac: -nepotrebna dodela

KockaAdmiralac: broj1 sad poziva broj

KockaAdmiralac: Parser sad koristi ažuran

KockaAdmiralac: Dodat REDUCE(4) za -| u c5

KockaAdmiralac: Dodat REDUCE(5) u 5 kontrolnu tabelu

KockaAdmiralac: Izmena da bude konzistentnije sa pravilima leve faktorizacije

KockaAdmiralac: Ispravljen FOLLOW skup za A i dodate dve REDUCE smene u kontrolnu tabelu; ažurirana potisna tabela sa stanjima iz ispravljenog dijagrama

KockaAdmiralac: Moja rešenja K2 2017

← Старија измена		Верзија на датум 4. децембар 2022. у 20:22
Ред 118:		Ред 118:
	switch (input) {		switch (input) {
	case BIT:		case BIT:
	~~e = 0;~~
	int p1;		int p1;
	int e1;		int e1;

← Старија измена		Верзија на датум 4. децембар 2022. у 20:20
Ред 121:		Ред 121:
	int p1;		int p1;
	int e1;		int e1;
	~~broj1~~(p1, e1);		broj(p1, e1);
	p = p1;		p = p1;
	e = e1;		e = e1;

← Старија измена		Верзија на датум 4. децембар 2022. у 20:15
Ред 119:		Ред 119:
	case BIT:		case BIT:
	e = 0;		e = 0;
	~~int v = terminal(BIT);~~
	int p1;		int p1;
	int e1;		int e1;
	broj1(p1, e1);		broj1(p1, e1);
	p = p1;		p = p1;
	~~if (~~e1~~) {~~		e = e1;
	~~p = v~~;
	}
	break;		break;
	case ',':		case ',':