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

KockaAdmiralac: 2^c_1 -> 2^c

2022-12-04T21:25:53Z

2^c_1 -> 2^c

← Старија измена		Верзија на датум 4. децембар 2022. у 23:25
Ред 21:		Ред 21:
	#: <math>c \leftarrow c_1 + 1</math>		#: <math>c \leftarrow c_1 + 1</math>
	#: <math>v \leftarrow 2v_1 + v_2</math>		#: <math>v \leftarrow 2v_1 + v_2</math>
	#: <math>p \leftarrow p_1 + \frac{v_2}{2^~~{c_1}~~}</math>		#: <math>p \leftarrow p_1 + \frac{v_2}{2^c}</math>
	# <L><sub>v,p,c</sub> → <B><sub>v<sub>1</sub></sub>		# <L><sub>v,p,c</sub> → <B><sub>v<sub>1</sub></sub>
	#: <math>c \leftarrow 1</math>		#: <math>c \leftarrow 1</math>

KockaAdmiralac: U a1 može da se radi REDUCE po b

2022-12-03T15:21:24Z

U a1 može da se radi REDUCE po b

← Старија измена		Верзија на датум 3. децембар 2022. у 17:21
Ред 260:		Ред 260:
	\| ─┤<sub>0</sub> \|\| \|\| \|\| \|\| ACCEPT		\| ─┤<sub>0</sub> \|\| \|\| \|\| \|\| ACCEPT
	\|-		\|-
	\| a<sub>1</sub> \|\| \|\| \|\| \|\| REDUCE(3)		\| a<sub>1</sub> \|\| \|\| REDUCE(3) \|\| \|\| REDUCE(3)
	\|-		\|-
	\| <X><sub>x</sub> \|\| \|\| SHIFT \|\| \|\| REDUCE(1)		\| <X><sub>x</sub> \|\| \|\| SHIFT \|\| \|\| REDUCE(1)

KockaAdmiralac: Kratak komentar na dobijeni rezultat

2022-12-03T13:51:09Z

Kratak komentar na dobijeni rezultat

← Старија измена		Верзија на датум 3. децембар 2022. у 15:51
Ред 210:		Ред 210:
	\| b<sub>3</sub> \|\| REDUCE(3) \|\| REDUCE(3) \|\| REDUCE(3)		\| b<sub>3</sub> \|\| REDUCE(3) \|\| REDUCE(3) \|\| REDUCE(3)
	\|}		\|}
			Možemo videti da, uprkos korišćenju SLR(1) automata umesto LR(0), nismo uspeli da razrešimo S/R konflikte.

	== 4. zadatak ==		== 4. zadatak ==

KockaAdmiralac: Dodate tabele za treći i četvrti zadatak

2022-12-03T13:45:32Z

Dodate tabele za treći i četvrti zadatak

@@ Ред 190: / Ред 190: @@
 {| class="wikitable"
 |+ Kontrolna tabela SLR(1) parsera
-<!-- TODO -->
+! Stanje             !! a !! b !! ─┤
 |}
@@ Ред 202: / Ред 220: @@
 === Rešenje ===
 [[Датотека:PPR K2 2015 zadatak 4 automat.svg|thumb|Karakteristični automat u četvrtom zadatku.]]
 [[Категорија:Рокови]]
 [[Категорија:Програмски преводиоци 1]]

KockaAdmiralac: WIP, fali rešenje četvrtog zadatka i kontrolna tabela u trećem

2022-12-02T21:48:50Z

WIP, fali rešenje četvrtog zadatka i kontrolna tabela u trećem

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

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

== 1. zadatak ==
=== Postavka ===
<div class="abc-list">
# Dodati atribute i odgovarajuća pravila u datu gramatiku tako da startni simbol dobije atribut <code>val</code> koji predstavlja decimalnu vrednost binarnog broja opisanog gramatikom. Na primer, ako je ulazna sekvenca 101.101 onda <code>val</code> treba da ima vrednost 5.625. Simbol | nije terminalni simbol, već se koristi da razdvoji smene istog neterminala.
#* <S> → <L> . <L> | <L>
#* <L> → <L> | 
#* → 0 | 1
# Nacrtati atributivno stablo izvođenja za izraz 101.101.
</div>

=== Rešenje ===
[[Датотека:PPR K2 2015 zadatak 1 stablo.svg|thumb|Stablo izvođenja u prvom zadatku, stavci pod b.]]
# <S>val → <L>v1,p1,c1 . <L>v2,p2,c2
#: <math>val \leftarrow v_1 + p_2</math>
# <S>val → <L>v1,p1,c1
#: <math>val \leftarrow v_1</math>
# <L>v,p,c → <L>v1,p1,c1 v2
#: <math>c \leftarrow c_1 + 1</math>
#: <math>v \leftarrow 2v_1 + v_2</math>
#: <math>p \leftarrow p_1 + \frac{v_2}{2^{c_1}}</math>
# <L>v,p,c → v1
#: <math>c \leftarrow 1</math>
#: <math>v \leftarrow v_1</math>
#: <math>p \leftarrow \frac{v_1}{2}</math>
# v → 0
#: <math>v \leftarrow 0</math>
# v → 1
#: <math>v \leftarrow 1</math>

== 2. zadatak ==
=== Postavka ===
Data je gramatika:
* <S> → ( <L> ) | a
* <L> → <L> , <S> | <S>
<div class="abc-list">
# Da li je gramatika pogodna za parsiranje na bazi rekurzivnog spusta? Obrazložiti odgovor. Ako nije pogodna, izvršiti transformaciju gramatike u ekvivalentnu koja se može koristiti za rekurzivni spust.
# Izračunati poništivost, FIRST, FOLLOW i SELECT skupove za gramatiku dobijenu u tački a).
# Dodati u gramatiku attribute, pravila i akcije da se izračuna i ispiše na izlazu najveća dubina ugneždavanja zagrada u ulaznoj sekvenci. Na primer, ako je u ulaznoj sekvenci ...(...(..)..)..(..).. onda je najveća dubina 2.
# Napraviti parser na bazi rekurzivnog spusta za gramatiku dobijenu u tački c). Napomena: ako preskočite tačku c) onda za gramatiku dobijenu u tački a).
</div>

=== Rešenje ===
Data gramatika nije pogodna za parsiranje na bazi rekurzivnog spusta jer nije LL(1) (sadrži levu rekurziju). Transformisanjem dobija se sledeća gramatika:
# <S> → ( <L> )
#: SELECT(1) = {"("}
# <S> → a
#: SELECT(2) = {"a"}
# <L> → <S> <L'>
#: SELECT(3) = {"(", "a"}
# <L'> → , <S> <L'>
#: SELECT(4) = {","}
# <L'> → E
#: SELECT(5) = FOLLOW(<L'>) = {")"}
FIRST i FOLLOW skupovi u ovoj gramatici glase ovako:
* FIRST(<S>) = {"(", "a"}
* FIRST(<L>) = FIRST(<S>) = {"(", "a"}
* FIRST(<L'>) = {","}
* FOLLOW(<L>) = {")"}
* FOLLOW(<L'>) = FOLLOW(<L>) = {")"}
* FOLLOW(<S>) = {─┤} ∪ FIRST(<L'>) ∪ FOLLOW(<L>) = {─┤, ",", ")"}
Atributivno-translaciona gramatika iz tačke c bi glasila ovako:
# <S>d → ( <L>d1 )
#: <math>d \leftarrow d_1 + 1</math>
# <S>d → a
#: <math>d \leftarrow 0</math>
# <L>d → <S>d1 <L'>d2
#: <math>d \leftarrow \max(d_1, d_2)</math>
# <L'>d → , <S>d1 <L'>d2
#: <math>d \leftarrow \max(d_1, d_2)</math>
# <L'>d → ε
#: <math>d \leftarrow 0</math>
Na osnovu toga, parser ove gramatike bi mogao da izgleda ovako:
<syntaxhighlight lang="cpp">
char input;

void terminal(char t) {
if (input == t) {
input = advance();
} else {
reject();
}
}

void parse() {
input = advance();
int depth;
S(depth);
}

void S(int& depth) {
switch (input) {
case 'a':
terminal('a');
depth = 0;
break;
case '(':
terminal('(');
int d1;
L(d1);
depth = d1;
terminal(')');
default: reject();
}
}

void L(int& depth) {
switch (input) {
case '(':
case 'a':
int d1;
int d2;
S(d1);
L1(d2);
depth = max(d1, d2);
break;
default: reject();
}
}

void L1(int& depth) {
switch (input) {
case ',':
terminal(',');
int d1;
int d2;
S(d1);
L1(d2);
depth = max(d1, d2);
break;
case ')':
depth = 0;
break;
default: reject();
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Na osnovu date gramatike konstruisati LR(0) prepoznavač ručki, kao i kontrolnu i potisnu tabelu SLR(1) parsera. Dati kratak komentar na dobijeni rezultat.
* <S> → <A> 
* <A> → a 
* → <S> b
* → ε

=== Rešenje ===
[[Датотека:PPR K2 2015 zadatak 3 automat.svg|thumb|Karakteristični automat u trećem zadatku.]]
FIRST i FOLLOW skupovi u ovoj gramatici su:
* FIRST(<A>) = {"a"}
* FIRST(<S>) = FIRST(<A>) = {"a"}
* FIRST() = FIRST(<S>) = {"a"}
* FOLLOW(<S>) = {─┤, "b"}
* FOLLOW(<A>) = FIRST() u FOLLOW(<S>) = {─┤, "a", "b"}
* FOLLOW() = FOLLOW(<A>) u FOLLOW(<S>) = {─┤, "a", "b"}
{| class="wikitable"
|+ Potisna tabela SLR(1) parsera
! Stanje
! <S> !! <A> !! !! a !! b !! ─┤
|-
! ∇
| <S>0 || <A>1 || || a2 || ||
|-
! <S>0
| || || || || || ─┤0
|-
! ─┤0
| || || || || ||
|-
! a2
| <S>3 || <A>1 || 2 || a2 || ||
|-
! 2
| || || || || ||
|-
! <A>1
| <S>3 || <A>1 || 1 || a2 || ||
|-
! 1
| || || || || ||
|-
! <S>3
| || || || || b3 ||
|-
! b3
| || || || || ||
|}
{| class="wikitable"
|+ Kontrolna tabela SLR(1) parsera

|}

== 4. zadatak ==
=== Postavka ===
Na osnovu date gramatike konstruisati LR(0) automat, kontrolnu i potisnu tabelu LALR(1) parsera.
* <S> → a <X>
* <X> → <X> b <X> c
* <X> → ε

=== Rešenje ===
[[Датотека:PPR K2 2015 zadatak 4 automat.svg|thumb|Karakteristični automat u četvrtom zadatku.]]

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