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
Программирование в среде Turbo Pascal 7.0
Базовый конспект лекций
Санкт-Петербург
АННОТАЦИЯ
Данная работа представляет собой курс лекций по языку программирования Паскаль. В ней рассмотрен процесс создания программы для MS-DOS или Windows 2000/XPс самых первых шагов (разработка алгоритма) и до получения результата. Описана работа в популярной среде программирования Turbo Pascal 7.0; дано введение в структурное программирование.
Курс программирования излагается во втором семестре студентам I курса на всех факультетах Санкт-Петербургского государственного горного института (технического университета).
Таблиц – 9, рисунков – 28.
The summary
The paper is description of program language Pascal. Full process of creation program from development of algorithm before reached result is considered in it. Popular environment of programming Turbo Pascal 7.0 is described; introduction to structured programming is given.
The course of programming is stated in the first semester to the students of the second rate on all faculties of St.-Petersburg state mining institute (technical university).
