LL(1)-грамматика составного оператора
Пример оператора :
begin
if a1>5 then z := 0; goto 55
else x, y := 0; z := 1
end;
i := 1; S := 0;
while i < 10 do
S := S + i; i := i + 1
end;
55 : M := z + S * (c ^2 –1)
end
| 1 | <SSP> ® begin <SOP> end | begin |
| 2 | <SOP> ® <OP> <PSOP> | CN goto if while ID |
| 3 4 | <PSOP> ® ; <OP> <PSOP> ® e | ; else end |
| 5 | <OP> ® <MT> <NOP> | CN goto if while ID |
| 6 7 | <MT> ® e ® CN <PMT> : | goto if while ID CN |
| 8 9 | <PMT> ® e ® , CN <PMT> | : , |
| 10 11 12 13 | <NOP> ® goto CN ® if <US> then <SOP> <ELE> end ® while <US> do <SOP> end ® ID <PSI> := <W> | goto if while ID |
| 14 15 | <PSI> ® e ® , ID <PSI> | := , |
| 16 17 | <ELE> ® else <SOP> ® e | else end |
| 18 19 | <US> ® not <OTN> ® <OTN> | not ID CN ( |
| 20 | <OTN> ® <W> <ZS> <W> | ID CN ( |
| 21 22 23 | <ZS> ® < ® > ® = | < > = |
| 24 | <W> ® <S> <PW> | ID CN ( |
| 25 26 27 | <PW> ® + <S> <PW> ® – <S> <PW> ® e | + – ) ] < > = then do end else ; |
| 28 | <S> ® <M> <PS> | ID CN ( |
| 29 30 31 | <PS> ® * <M> <PS> ® / <M> <PS> ® e | * / + – ) ] < > = then do end else ; |
| 32 | <M> ® <PR> <PM> | ID CN ( |
| 33 34 | <PM> ® ^ <PR> <PM> ® e | ^ * / + – ) ] < > = then do end else ; |
| 35 36 37 | <PR> ® ID ® CN ® ( <W> ) | ID CN ( |
|
|
|
Обозначения в грамматике:
<SSP> – составной оператор,
<SOP> – список операторов,
<PSOP> – продолжение списка операторов,
<OP> – оператор,
<MT> – метки,
<PMT> – продолжение меток,
<NOP> – непомеченный оператор,
<PSI> – продолжение списка идентификаторов,
<ELE> – else–ветвь или пусто ( e ),
<US> – условие,
<OTN> – отношение,
<ZS> – знак сравнения,
<W> – выражение,
<PW> – продолжение выражения,
<S> – слагаемое,
<PS> – продолжение слагаемого,
<M> – множитель,
<PM> – продолжение множителя,
<PR> – простейшее (операнд).
_________________________
Приложение 7
LL(1)-грамматика составного оператора с включенными действиями
| 1 | <PRG> ® begin <SOP> end [19] | begin |
| 2 | <SOP> ® <OP> <PSOP> | CN goto if while ID |
| 3 4 | <PSOP>® ; <OP> <PSOP> ® e | ; else end |
| 5 | <OP> ® <MT> <NOP> | CN goto if while ID |
| 6 7 | <MT> ® e ® CN [20] <PMT> : | goto if while ID CN |
| 8 9 | <PMT> ® e ® , CN [20] <PMT> | : , |
| 10 11 12 13 | <NOP> ® goto CN [9] ® if <US> [10] then <SOP> <ELE>[12] end ® while [16] <US> [17] do <SOP> [18] end ® ID [13] <PSI> := <W> [15] | goto if while ID |
| 14 15 | <PSI> ® e ® , ID [14] <PSI> | := , |
| 16 17 | <ELE> ® else [11] <SOP> ® | else end |
| 18 19 | <US> ® not <OTN> [7] ® <OTN> | not ID CN ( |
| 20 | <OTN> ® <W> <ZS> [1] <W> [8] | ID CN ( |
| 21 22 23 | <ZS> ® < ® > ® = | < > = |
| 24 | <W> ® <S> <PW> | ID CN ( |
| 25 26 27 | <PW> ® + <S> [2] <PW> ® – <S> [3] <PW> ® e | + – ) ] < > = then do end else ; |
| 28 | <S> ® <M> <PS> | ID CN ( |
| 29 30 31 | <PS> ® * <M> [4] <PS> ® / <M> [5] <PS> ® e | * / + – ) ] < > = then do end else ; |
| 32 | <M> ® <PR> <PM> | ID CN ( |
| 33 34 | <PM> ® ^ <PR> <PM> [6] ® e | ^ * / + – ) ] < > = then do end else ; |
| 35 36 37 | <PR> ® ID [1] ® CN [1] ® ( <W> ) | ID CN ( |
|
|
|
|
|
|
Действия в грамматике:
[1] – сохранить в RSt распознанную ЛЕ;
[2] – сформировать в МИ команду сложения add по двум элементам RSt, для результата выделить временную переменную, сохранить её в RSt;
[3] – сформировать в МИ команду вычитания sub по двум элементам RSt, для результата выделить временную переменную, сохранить её в RSt;
[4] – сформировать в МИ команду умножения mul по двум элементам RSt, для результата выделить временную переменную, сохранить её в RSt;
|
|
|
[5] – сформировать в МИ команду деления div по двум элементам RSt, для результата выделить временную переменную, сохранить её в RSt;
[6] – сформировать в МИ команду возведения в степень exp по двум элементам RSt, для результата выделить временную переменную, сохранить её в RSt;
[7] – сформировать в МИ команду изменения знака inv по одному элементу RSt, для результата выделить временную переменную, сохранить её в RSt;
[8] – сформировать в МИ команду сравнения cmp’u’ по трем элементам RSt (код операции преобразовать из внутренней формы во внешнюю), для результата выделить временную переменную, сохранить её в RSt;
[9] – сформировать в МИ команду безусловного перехода jmp на распознанную константу-метку;
[10] – сформировать в МИ команду условного перехода по ложь j_false по одному элементу RSt (по результату <U>) на очередную внутреннюю метку и сохранить её в RSt ;
[11] – сформировать в МИ команду безусловного перехода jmp на очередную внутреннюю метку, разместить в МИ метку из RSt, сохранить в RSt использованную в команде jmp метку;
[12] – разместить в МИ метку из RSt;
[13] – сохранить ID в RSt, установить внутренний счетчик переменных Cnt = 1 ;
[14] – сохранить ID в RSt, нарастить внутренний счетчик переменных Cnt = Cnt + 1 ;
[15] – сформировать операцию присваивания mov верхнего элемента RSt для Cnt переменных из RSt;
[16] – разместиь в МИ очередную внутреннюю метку и сохранить её в RSt ( как метку начала цикла );
[17] – сформировать в МИ команду условного перехода по ложь j_false по одному элементу RSt на очередную внутреннюю метку и сохранить её в RSt (как метку выхода из цикла );
[18] – извлечь из RSt метку (выхода из цикла) и временно сохранить в переменной VMET, сформировать в МИ команду безусловного перехода jmp на метку из RSt (метку начала цикла), разместить в МИ сохранённую в VMET метку;
[19] – сформировать в МИ команду завершения программы end ;
[20] – распознанную константу отметить в таблице констант как метку и разместить в МИ как метку.
____________________
Приложение 8
Дата добавления: 2018-04-05; просмотров: 286; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!