Programski prevodioci 1/K2 2019

Drugi kolokvijum 2019. godine održan je 2. decembra i trajao je 90 minuta. Postavka roka dostupna je sa stranice predmeta (arhiva).

1. zadatak

Postavka

1. Kojoj gramatici odgovara dati rekurzivni prepoznavač napisan na pseudojeziku?
2. Nalaženjem SELECT skupova proveriti da li je gramatika iz tačke a) tipa LL(1).
3. Ukoliko već nije, transformisati gramatiku iz tačke a) da bude LL(1).

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;

Rešenje

Ovaj rekurzivni prepoznavač odgovara gramatici sa mrtvim neterminalom <A>. Ako bismo izbacili mrtve neterminale, dobili bismo gramatiku koja izgleda ovako:

1. <S> → <A> a
2. <S> → ε
3. <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:

1. <S> → <A> a

   SELECT(1) = {f}

2. <S> → ε

   SELECT(2) = {a}

3. <A> → <A> <A> d

   SELECT(3) = {f}

4. <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:

1. <S> → <A> a

   SELECT(1) = {f}

2. <S> → ε

   SELECT(2) = {a}

3. <A> → f <A'>

   SELECT(3) = {f}

4. <A'> → <A> d <A'>

   SELECT(4) = {f}

5. <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:

1. <S> → <A>
2. <S> → b c <A> c
3. <A> → b

1. Popuniti sadržaje stanja karakterističnog LR(0) automata na datoj slici (ne popunjavati unutar {})
2. Popuniti predikcione skupove {} unutar stanja na slici da bi se dobio karakteristični LALR(1) automat.
3. Popuniti kontrolnu tabelu SLR(1) parsera.
4. Popuniti kontrolnu tabelu LALR(1) parsera

Rešenje

Dijagram iz stavki a i b zadatka.

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)

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.

1. <niz> → BROJ , <niz>
2. <niz> → BROJ

Rešenje

Uvode se tri sintetizovana atributa, maksimalna dužina neopadajućeg niza brojeva ($ml$), trenutna dužina neopadajućeg niza brojeva ($l$) i prvi broj u nizu ($n$).

1. <niz>_ml,l,n → BROJ_val , <niz>_ml1,l1,n1

   $l \leftarrow (l_1 + 1) \cdot (val \leq n_1) + 1 \cdot (val > n_1)$

   $ml \leftarrow l \cdot (l > ml_1) + ml_1 \cdot (l \leq ml_1)$

   $n \leftarrow val$

2. <niz>_ml,l,n → BROJ_val

   $ml \leftarrow 1$

   $l \leftarrow 1$

   $n \leftarrow val$