Програмски преводиоци 1/К2 2019

Други колоквијум 2019. године одржан је 2. децембра. Поставка рока доступна је са странице предмета (архива).

1. задатак

Поставка

1. Којој граматици одговара дати рекурзивни препознавач написан на псеудојезику?
2. Налажењем СЕЛЕЦТ скупова проверити да ли је граматика из тачке а) типа ЛЛ(1).
3. Уколико већ није, трансформисати граматику из тачке а) да буде ЛЛ(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;

Решење

Овај рекурзивни препознавач одговара граматици са мртвим нетерминалом <А>. Ако бисмо избацили мртве нетерминале, добили бисмо граматику која изгледа овако:

1. <С> → <А> а
2. <С> → ε
3. <А> → ф

Ипак, ово вероватно није оно што је био очекивани одговор на ову ставку. Боља формулација прве ставке би била "Када би се граматика техником рекурзивног спуста пребацила у код парсера, добија се следећи изворни код. Одредити изворну граматику." У овом случају добија се граматика која изгледа овако:

1. <С> → <А> а

   СЕЛЕЦТ(1) = {ф}

2. <С> → ε

   СЕЛЕЦТ(2) = {а}

3. <А> → <А> <А> д

   СЕЛЕЦТ(3) = {ф}

4. <А> → ф

   СЕЛЕЦТ(4) = {ф}

Четврта смена ове граматике може бити само ф, зато што се ПРОЦБ из оригиналног парсера не позива у случају да на улазу дође терминал ц.

Ова граматика није ЛЛ(1) због присуства леве рекурзије. Када елиминишемо леву рекурзију, ова граматика изгледа овако:

1. <С> → <А> а

   СЕЛЕЦТ(1) = {ф}

2. <С> → ε

   СЕЛЕЦТ(2) = {а}

3. <А> → ф <А'>

   СЕЛЕЦТ(3) = {ф}

4. <А'> → <А> д <А'>

   СЕЛЕЦТ(4) = {ф}

5. <А'> → ε

   СЕЛЕЦТ(5) = {а}

На овај начин се СЕЛЕЦТ скупови смена не преклапају, и зато је ова граматика ЛЛ(1).

2. задатак

Поставка

За дату граматику са нетерминалима С и А:

1. <С> → <А>
2. <С> → б ц <А> ц
3. <А> → б

1. Попунити садржаје стања карактеристичног ЛР(0) аутомата на датој слици (не попуњавати унутар {})
2. Попунити предикционе скупове {} унутар стања на слици да би се добио карактеристични ЛАЛР(1) аутомат.
3. Попунити контролну табелу СЛР(1) парсера.
4. Попунити контролну табелу ЛАЛР(1) парсера

Решење

Дијаграм из ставки а и б задатка.

Контролна табела СЛР(1) парсера

Стање	б	ц	─┤
∇	СХИФТ
б3б4		С/Р конфликт	РЕДУЦЕ(3)
<С>0			СХИФТ
─┤0			АЦЦЕПТ
<А>1			РЕДУЦЕ(1)
ц21	СХИФТ
<А>2		СХИФТ
ц22			РЕДУЦЕ(2)
б3		РЕДУЦЕ(3)	РЕДУЦЕ(3)

Контролна табела ЛАЛР(1) парсера

Стање	б	ц	─┤
∇	СХИФТ
б3б4		СХИФТ	РЕДУЦЕ(3)
<С>0			СХИФТ
─┤0			АЦЦЕПТ
<А>1			РЕДУЦЕ(1)
ц21	СХИФТ
<А>2		СХИФТ
ц22			РЕДУЦЕ(2)
б3		РЕДУЦЕ(3)

3. задатак

Поставка

Дата је граматика која описује низ који се састоји од једног или више целих бројева раздвојених зарезима. Датој граматици доделити атрибуте и акције уколико је потребно тако да стартни нетерминал <низ> има синтетизовани атрибут у коме се налази дузина^[сиц] најдузе^[сиц] неопадајуће секвенце у низу. Сматрати да терминал БРОЈ има синтетизовани атрибут са вредношћу тог броја. За сваки уведени атрибут потребно је назначити његов тип.

1. <низ> → БРОЈ , <низ>
2. <низ> → БРОЈ

Решење

Уводе се три синтетизована атрибута, максимална дужина неопадајућег низа бројева ($ml$), тренутна дужина неопадајућег низа бројева ($l$) и први број у низу ($n$).

1. <низ>_мл,л,н → БРОЈ_вал , <низ>_{мл1,л1,н1}

   $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. <низ>_мл,л,н → БРОЈ_вал

   $ml \leftarrow 1$

   $l \leftarrow 1$

   $n \leftarrow val$