2. Для следующих выражений в ПОЛИЗе дать обычную инфиксную
запись:
а) ab*c b) abc*/ c) ab+c*
d) ab+bc-/a+ e) a not b and not f) abca and or and
g) 2x+2x*<
3. Используя стек, вычислить следующие выражения в ПОЛИЗе:
а) 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 .
4. Записать в ПОЛИЗе следующие операторы языка Си и, используя стек, выполнить их при указанных начальных значениях переменных:
а) 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 .
5. Используя стек, выполнить следующие действия, записанные в ПОЛИЗе, при 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.
6. Записать в ПОЛИЗе следующие операторы Паскаля:
a) for I := E1 to E2 do S
b) case E of
c1: S1;
c2: S2;
....
cn: Sn
end;
c) repeat S1; S2; ... ;Sn until B;
7. Записать в ПОЛИЗе следующие фрагменты программ на Паскале:
a) case k of
1: 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 end
end
b) S:=0; for i:=1 to N do
begin d:=i*2; a:=a+d*((i-1)*N+5)
S:=-a*d+S
end
c) c:=a*b; while a<>b do
if a<b then b:=b-a else a:=a-b;
c:=c/a
8. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *, / и скобки ( ), где операции должны выполняться строго слева направо, но приоритет скобок сохраняется. Определить действия по переводу таких выражений в ПОЛИЗ.
9. Изменить приоритет операций отношения в М - языке (сделать его наивысшим). Построить соответствующую грамматику, отражающую этот приоритет. Написать синтаксический анализатор, обеспечить контроль типов, задать перевод в ПОЛИЗ.
10. Написать КС-грамматику, аналогичную данной,
E ® T {+T}
T ® F {*F}
F ® (E) | i
с той лишь разницей, что в новом языке будет допускаться унарный минус перед идентификатором, имеющий наивысший приоритет (например, a*-b+-c допускается и означает a*(-b)+(-c)).
В созданную грамматику вставить действия по переводу такого выражения в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Cи.
11. Дана грамматика, описывающая выражения:
E ® TE’ E’ ® +TE’ | e
T ® FT’ T’ ® *FT’ | e
F ® PF’ F’ ® ^PF’ | e
P ® (E) | i
Включить в эту грамматику действия по переводу этих выражений в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Си.
12. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *, /, ** и скобки ( ) с обычным приоритетом операций и скобок. Включить в эту грамматику действия по переводу этих выражений в префиксную запись (операции предшествуют операндам). Предложить интерпретатор префиксной записи выражений.
13. В грамматику, описывающую выражения, включить действия по переводу выражений из инфиксной формы (операция между операндами) в функциональную запись.
Например,
а+b ==> + (a, b)
a+b*c ==> + (a, * (b, c))
14. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу L1 в L2.
L1 = {1m 0n | n,m>0}
L2 = {1m-n | если m>n;
0 | если m<n;
e | если m=n}
(Эта задача аналогична задаче выдачи сообщений об ошибке в балансе скобок).
15. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.
L1 = {1n 0m 1m 0n | m,n > 0}
L2 = {1m 0n+m | m,n > 0}
16. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.
L1 = {bi | bi =(i)2, то есть bi -это двоичное представление числа i Î N}
17. Построить грамматику, описывающую целые двоичные числа (допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел в четверичную систему счисления.
Д. Грис. Конструирование компиляторов для цифровых вычислительных машин / Д. Грис. - М.: Мир, 1998.
1. Ф. Льюис, Д. Розенкранц, Р. Стирнз. Теоретические основы проектирования компиляторов / Ф. Льюис, Д. Розенкранц, Р. Стирнз. - М.: Мир, 1989.
2. А. Ахо, Дж. Ульман.Теория синтаксического анализа, перевода и компиляции, Том 1,2. / А. Ахо, Дж. Ульман. - М.: Мир, 1995.
3. Ф. Вайнгартен. Трансляция языков программирования / Ф. Вайнгартен. - М.: Мир, 1987.
4. И. Л. Братчиков. Синтаксис языков программирования / И. Л. Братчиков. - М.: Наука, 1985.
5. С. Гинзбург. Математическая теория контекстно-свободных языков / С. Гинзбург. - М.: Мир, 1980.
6. Дж. Фостер. Автоматический синтаксический анализ / Дж. Фостер. - М.: Мир, 1985.
7. В. Н. Лебедев. Введение в системы программирования / В. Н. Лебедев. - М.: Статистика, 1975.
8. Л. Бек. Введение в системное программное обеспечение / Л. Бек.- М.: Мир,1989.
9. Р. Хантер. Основные концепции компиляторов / Р. Хантер. - Вильямс, 2002.
10.А.В. Ахо, Дж. Д. Ульман. Компиляторы: принципы, технологии и инструменты / А.В. Ахо, Дж. Д. Ульман. Вильямс, 2001.
11.Д. Э. Кнут. Искусство программирования, том 3. Сортировка и поиск / Д. Э. Кнут. Вильямс, 2000.
12.Д.Э. Кнут.Искусство программирования, том 1. Основные алгоритмы / Д.Э. Кнут. Вильямс, 2000.
13.А. В. Ахо, Дж. Д. Ульман. Структуры данных и алгоритмы / А. В. Ахо, Дж. Д. Ульман. Вильямс, 2000.
А. В. Гордеев, А. Ю. Молчанов.Системное программное обеспечение / А. В. Гордеев, А. Ю. Молчанов. Питер, 2001
