И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901), страница 7
Текст из файла (страница 7)
пара вида (номер_класса,номер_в_классе). Нам придется расширить набор лексем:1. будем считать, что новые операции (!, !F, R, W) относятся к классуограничителей, как и все другие операции модельного языка;2. для ссылок на номера элементов ПОЛИЗа введем лексемы класса 0,т.е.
(0,p) - лексема, обозначающая p-ый элемент в ПОЛИЗе;3. для того, чтобы различать операнды-значения-переменных иоперанды-адреса-переменных (например, в ПОЛИЗе оператораприсваивания), операнды-значения будем обозначать лексемамикласса 4, а для операндов-адресов введем лексемы класса 5.Будем считать, что генерируемая программа размещается в массиве P,переменная free - номер первого свободного элемента в этом массиве:#define MAXLEN_P 10000struct lex{int class;int value;}struct lex P [ MAXLEN_P];int free = 0;Для записи очередного элемента в массив P будем использоватьфункцию put_lex:void put_lex (struct lex l){P [ free++] = l;}Кроме того, введем модификацию этой функции - функцию put_lex5,которая записывает лексему в ПОЛИЗ, изменяя ее класс с 4-го на 5-й (ссохранением значения поля value):void put_lex5 (struct lex l){l.class = 5; P [ free++] = l;}Пусть есть функцияstruct lex make_op(char *op),котораяпосимвольномуизображениюоперацииopнаходитвтаблицеограничителей соответствующую строку и формирует лексему вида (2,i), где i номер найденной строки.Генерация внутреннего представления программы будет проходить во времясинтаксического анализа параллельно с контролем контекстных условий, поэтомудля генерации можно использовать информацию, "собранную" синтаксическим исемантическим анализаторами; например, при генерации ПОЛИЗа выражений можновоспользоватьсясодержимымстека,скоторымработаетсемантическийанализатор.Кроме того, можно дополнить функции семантического анализа действиями погенерации:void checkop_p (void){char *op; char *t1; char *t2; char *res;t2 = spop(); op = spop(); t1 = spop();res = gettype (op,t1,t2);if (strcmp (res, "no")){spush (res);put_lex (make_op (op));} /* дополнение! - операцияop заносится в ПОЛИЗ */else ERROR();}Тогда грамматика, содержащая действия по контролю контекстныхусловий и переводу выражений модельного языка в ПОЛИЗ, будет такой:E → E1 | E1 [=|>|<] <spush (TD[curr_lex.value])> E1<checkop_p()>E1 → T {[+|-|or] <spush (TD[curr_lex.value])>T <checkop_p()>}T → F {[*|/|and] <spush (TD[curr_lex.value])>F <checkop_p()>}F → I <checkid(); put_lex (curr_lex)> |N <spush("int"); put_lex (curr_lex)> |[true|false] <spush ("bool"); put_lex (curr_lex)> |not F <checknot(); put_lex (make_op ("not"))> | (E)Действия, которыми нужно дополнить правило вывода оператораприсваивания, также достаточно очевидны:S → I <checkid(); put_lex5 (curr_lex)> :=E <eqtype(); put_lex (make_op (":="))>При генерации ПОЛИЗа выражений и оператора присваивания элементымассива P заполнялись последовательно.
Семантика условногооператора if E then S1 else S2 такова, что значения операндов дляопераций безусловного перехода и перехода "по лжи" в моментгенерации операций еще неизвестны:if (!E) goto l2; S1; goto l3; l2: S2; l3:...Поэтому придется запоминать номера элементов в массиве P,соответствующих этим операндам, а затем, когда станут известны ихзначения, заполнять пропущенное.Пусть есть функцияstruct lex make_labl (int k),которая формирует лексему-метку ПОЛИЗа вида (0,k).Тогда грамматика, содержащая действия по контролю контекстных условийпереводу условного оператора модельного языка в ПОЛИЗ, будет такой:иS → if E <eqbool(); pl2 = free++; put_lex (make_op ("!F"))>then S <pl3 = free++; put_lex (make_op ("!")); P[pl2] = make_labl (free) >else S < P[pl3] = make_lable (free) >Замечание: переменные pl2 и pl3 должны быть локализованы в процедуре S, иначевозникнет ошибка при обработке вложенных условных операторов.Аналогично можно описать способ генерации ПОЛИЗа других операторов модельногоязыка.Интерпретатор ПОЛИЗа для модельного языкаПольская инверсная запись была выбрана нами в качестве языкавнутреннего представления программы, в частности, потому, чтозаписаннаятакимобразомпрограммаможетбытьлегкопроинтерпретирована.Идея алгоритма очень проста: просматриваем ПОЛИЗ слева направо;если встречаем операнд, то записываем его в стек; если встретили знакоперации, то извлекаем из стека нужное количество операндов ивыполняем операцию, результат (если он есть) заносим в стек и т.д.Итак, программа на ПОЛИЗе записана в массиве P; пусть она состоит изN элементов-лексем.
Каждая лексема - это структураstruct lex {int class; int value;},возможные значения поля class:1. - лексемы-метки (номера элементов в ПОЛИЗе)2. - логические константы true либо false (других лексем - служебныхслов в ПОЛИЗе нет)3. - операции (других лексем-ограничителей в ПОЛИЗе нет)4. - целые константы5. - лексемы-идентификаторы (во время интерпретации будетиспользоваться значение)6. - лексемы-идентификаторы (во время интерпретации будетиспользоваться адрес).Считаем, что к моменту интерпретации распределена память подконстанты и переменные, адреса занесены в поле address таблиц TID иTNUM, значения констант размещены в памяти.В программе-интерпретаторе будем использовать некоторые переменныеи функции, введенные нами ранее.void interpreter(void) {int *ip;int i, j, arg;for (i = 0; i<=N; i++){curr_lex = P[i];switch (curr_lex.class) {case 0: ipush (curr_lex.value); break;/* метку ПОЛИЗ - в стек */case 1: if (eq ("true")) ipush (1);else ipush (0); break;/* логическое значение - в стек */case 2: if (eq ("+")) {ipush (ipop() + ipop()); break};/* выполнили операцию сложения, результат - в стек*/if (eq ("-")){arg = ipop(); ipush (ipop() - arg); break;}/* аналогично для других двухместных арифметическихи логических операций */if (eq ("not")) {ipush (!ipop()); break;};if (eq ("!")) {j = ipop(); i = j-1; break;};/* интерпретация будет продолжена с j-го элементаПОЛИЗа */if (eq ("!F")) {j = ipop(); arg = ipop();if (!arg) {i = j-1}; break;};/* если значение arg ложно, то интерпретация будетпродолжена с j -го элемента ПОЛИЗа, иначе порядокне изменится */if (eq (":=")) {arg = ipop(); ip = (int*)ipop();*ip = arg; break;};if (eq ("R")) {ip = (*int) ipop();scanf("%d", ip); break;};/* "R" - обозначение операции ввода */if (eq ("W")) {arg = ipop();printf ("%d", arg); break;};/* "W" - обозначение операции вывода */case 3: ip = TNUM [curr_lex.value].address;ipush(*ip); break;/* значение константы - в стек */case 4: ip = TID [curr_lex.value].address;ipush(*ip); break;/* значение переменной - в стек */case 5: ip = TID [curr_lex.value}.address;ipush((int)ip); break;/* адрес переменной - в стек */} /* конец switch */} /* конец for */}Задачи.63.
Представить в ПОЛИЗе следующие выражения:а) a+b-c b) a*b+c/ac) a/(b+c)*a d) (a+b)/(c+a*b)e) a and b or c f) not a or b and ag) x+y=x/y h ) (x*x+y*y < 1) and (x > 0)64. Для следующих выражений в ПОЛИЗе дать обычную инфикснуюзапись:а ) ab*c b) abc*/ c) ab+c*d) ab+bc-/a+ e) a not b and not f) abca and or andg ) 2x+2x*<65. Используя стек, вычислить следующие выражения в ПОЛИЗе:а) xy*xy/+ при x = 8, y = 2 ;b) a2+b/b4*+ при a = 4, b = 3 ;c) ab not and a or not при a = b = true ;d) xy*0 > y2x- < and при x = y = 1 .66.
Записать в ПОЛИЗе следующие операторы языка Си и, используястек, выполнить их при указанных начальных значениях переменных:а) if (x != y) x = x+1 ; при x = 3 ;b) if (x > y) x = y ; else y = x ; при x = 5, y = 7;c) while (b > a) {b = b-a;} ; при a = 3, b = 7;d) do {x = y; y = 2;} while (y > 9); при y = 2;e) S = 0; for (i = 1; i <= k; i = i + 1) {S = S + i*i;} при k = 3 ;f) switch (k) {case 1: a = not a; break;case 2: b = a or not b ;case 3: a = b ;}при k = 2, a = b = false .67. Используя стек, выполнить следующие действия, записанные вПОЛИЗе, при x = 9, y = 15 (считаем,что элементы ПОЛИЗаперенумерованы с 1).z, x, y, *, :=, x, y, <>, 30, !F, x, y, <, 23, !F, y, y, x, -, :=, 6, !, x, x, y, -,:=, 6, !, z, z, x, /, :=Описать заданные действия на Си, не используя оператор goto.68.
Записать в ПОЛИЗе следующие операторы Паскаля:a) for I := E1 to E2 do Sb) case E ofc1: S1;c2: S2;....cn: Snend;c) repeat S1; S2; ... ;Sn until B;69. Записать в ПОЛИЗе следующие фрагменты программ на Паскале:a) case k of1: begin a:=not(a or b and c); b:=a and c or b end;2: begin a:=a and (b or not c); b:= not a end;3: begin a:=b or c or not a; b:==b and c or a endendb) S:=0; for i:=1 to N dobegin d:=i*2; a:=a+d*((i-1)*N+5)S:=-a*d+Sendc) c:=a*b; while a<>b doif a<b then b:=b-a else a:=a-b;c:=c/a70.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
