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

Други колоквијум 2022. године одржан је 5. децембра. Трајао је 100 минута и поставка рока није тренутно доступна са странице предмета.

1. задатак

Поставка

На основу дате потисне и контролне табеле ЛР(0) парсера:

1. Нацртати карактеристични аутомат овог парсера.
2. Одредити граматику коју овај парсер парсира.
3. Одредити ФОЛЛОW скупове ове граматике. Уколико овај парсер постане СЛР(1), да ли ће бити конфликата?

Контролна и потисна табела ЛР(0) парсера

Стање	<Е>	ид	(	)	+	─┤	Акција
∇	<Е>x1	идx					СХИФТ
<Е>x1					+3	─┤0	СХИФТ
─┤0							АЦЦЕПТ
идx			(2				СХИФТ/РЕДУЦЕ(1)
(2	<Е>x2	идx					СХИФТ
<Е>x2				)2	+3		СХИФТ
+3		ид3					СХИФТ
)2							РЕДУЦЕ(2)
ид3							РЕДУЦЕ(3)

Решење

Карактеристични ЛР(0) аутомат из ставке а првог задатка.

Граматика коју овај аутомат парсира је:

1. <Е> → ид
2. <Е> → ид ( <Е> )
3. <Е> → <Е> + ид

ФИРСТ и ФОЛЛОW скупови ове граматике су:

• ФИРСТ(<Е>) = {ид}
• ФОЛЛОW(<Е>) = {")", "+", ─┤}

У ЛР(0) аутомату, у стању ид_x дешава се С/Р конфликт. У СЛР(1) парсеру, за сваки терминал се акција одређује посебно. За терминал ( ће се обављати СХИФТ, док ће за ФОЛЛОW(<Е>), односно за знакове ), + и ─┤, обављати РЕДУЦЕ(1). Због овога у СЛР(1) парсеру неће бити конфликата.

2. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Допунити парсер или граматику испод на одговарајући начин на местима означеним са ????. Уколико се у ову граматику додају следеће две смене:

• <С> → б <С>
• <Б> → <Б> ф

да ли граматика остаје ЛЛ(1) (образложити зашто да или зашто не) и уколико не остаје трансформисати тако да буде ЛЛ(1).

Граматика:

1. <С> → а <А> е <Б>
2. <С> → ????
3. <А> → б <С> д
4. <А> → ε
5. <Б> → ц ????
6. <Б> → ????

Парсер:

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;

Решење

Крајња граматика је:

1. <С> → а <А> е <Б>
2. <С> → <А> <Б>
3. <А> → б <С> д
4. <А> → ε
5. <Б> → ц <С>
6. <Б> → ε

3. задатак

Поставка

Дата је граматика која описује бинарно стабло:

1. <трее>_{wидтх,левел} → <ноде>
2. <ноде> → <ноде> ИД <ноде>
3. <ноде> → НУЛЛ

У граматици, између левог и десног детета неког чвора долази идентификатор тог чвора, док уколико чвор нема дете на месту његовог подстабла пише НУЛЛ. Кроз наслеђени атрибут level прослеђује се број одређеног нивоа стабла (корен има ниво 0), а потребно је направити атрибутивно-транслациону граматику која у атрибут width корена уписује ширину стабла на том нивоу. За сваки атрибут написати улогу и да ли је синтетизован или наслеђен.

Решење

Уводе се три атрибута:

• Наслеђени атрибут curr који представља тренутни ниво на којем се налази чвор.
• Наслеђени атрибут aim који представља тражени ниво на којем се мери ширина.
• Синтетизовани атрибут width који представља до тада израчунату ширину стабла на задатом нивоу.

Са њима, атрибутивно-транслациона граматика изгледа овако:

1. <трее>_{wидтх,левел} → <ноде>_{цурр,аим,wидтх1}

   $aim \leftarrow level$

   $curr \leftarrow 0$

   $width \leftarrow width_1$

2. <ноде>_{цурр,аим,wидтх} → <ноде>_ц1,а1,w1 ИД <ноде>_ц2,а2,w2

   $a_1 \leftarrow aim$

   $a_2 \leftarrow aim$

   $c_1 \leftarrow curr + 1$

   $c_2 \leftarrow curr + 1$

   $width \leftarrow (curr = aim) + w_1 + w_2$

3. <ноде>_{цурр,аим,wидтх} → НУЛЛ

   $width \leftarrow (curr = aim)$