«Е.А. Роганов Основы информатики и программирования Учебное пособие для студентов программистских специальностей Москва 2001 ББК 22.18 УДК 519.6 Р59 Е.А. Роганов. Основы информатики и программирования: Учебное пособие ...»

Указание. Продифференцировав по x равенство Pn (x) = x·Pn1 (x)+ an и подставив затем x = t, получите соотношения P0 (t) = 0 и Pn (t) = t · Pn1 (t) + Pn1 (t), которые помогут построить индуктивное расширение исходной функции.

Задача 3.8. Напишите программу, определяющую правильность формулы над алфавитом из четырех символов X = {(, ), t, +}. Формула считается правильной, если она может быть получена с помощью следующей НФБН: e t | (e + e).

Указание. Рассмотрите следующее индуктивное расширение F = определены следующим образом:

f1 () = может быть продолжена до правильной формулы, f2 () = разность числа левых и правых скобок в, f3 () = последний элемент.

Задача 3.9. Напишите программу, определяющую номер f последнего элемента, равного x0, в последовательности целых чисел. В том случае, если число x0 в последовательности не встречается, положите f = 0.

Полным решением задач, приведенных ниже, не может считаться только текст правильно написанной программы. Во всех случаях необходимо изложение теоретической части решения и описание соответствия между переменными программы и обозначениями, использованными при теоретическом исследовании.

1. Задачи на рекурсию. При решении задач из этого раздела необходимо обосновать как то, почему программа заканчивает работу, так и то, почему после ее завершения будет получен требуемый результат.

Задача 4.1. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення сложность которой не должна превосходить (log b), таковы:

Q = (a ZM b ZM b 0), R = (z = ab). Числа a и b в программе изменять нельзя.

Задача 4.2. Напишите программу, печатающую значение многочлена степени n 0 в заданной точке x0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, также как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

Задача 4.3. Напишите рекурсивную программу, печатающую значение производной многочлена степени n 0 в заданной точке x 0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, так же как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

Указание. Пусть Pn (x) = a0 xn + a1 xn1 +... + an1 x + an. Продифференцируем по x равенство Pn (x) = x · Pn1 (x) + an и подставим затем x = x0. Мы получим следующие соотношения:

P0 (x0 ) = 0, Pn (x0 ) = x0 · Pn1 (x0 ) + Pn1 (x0 ).

Воспользовавшись ими и формулами P0 (x0 ) = a0, Pn (x0 ) = x0 · Pn1 (x0 ) + an, легко определить рекурсивную функцию неотрицательного целого аргумента g : ZM ZM ZM, g(n) = (Pn (x0 ), Pn (x0 )) для вычисления которой и пишется программа.

2. Проектирование цикла при помощи инвариантa. При решении задач из этого раздела необходимо построить и доказать правильность построенной программы вида "S0;while(e)S;", а при отсутствии в условии задачи явно заданных инварианта цикла и ограничивающей функции объяснить предварительно, каким образом они были получены.

Задача 4.4. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення а сложность которой не должна превосходить (log b), таковы: Q = (a личины a и b изменять не разрешается, следует использовать инвариант I = (y 0 z + xy = ab) и ограничивающую функция h = y.

Задача 4.5. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой проR = (z = ab ).

При написании программы величины a и b изменять не разрешается, следует использовать инвариант I = (y 0 z · xy = ab ) и ограничивающую функцию h = y.

Задача 4.6. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Вот более точная формулировка пред- и постусловия:

написании программы величину n изменять нельзя.

Задача 4.7. Напишите программу (линейный поиск), определяющую первое вхождение заданного целого числа x в заданный массив b[0..m 1] целых чисел (m > 0). Известно, что x находится в массиве b. Значения элементов массива b и число x в программе изменять нельзя.

Задача 4.8. Напишите программу, находящую сумму s элементов заданного целочисленного массива b[0..n 1], элементы которого и величину n изменять нельзя. Точные пред- и постусловия: Q = (n > 0), Задача 4.9. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Точные пред- и постусловия требуемой программы, времення сложность которой не должна превосходить (log n), таковы:

написании программы величину n изменять нельзя.

Задача 4.10. Найдите минимальное число, содержащееся в каждом из трех упорядоченных по возрастанию массивов целых чисел, в предположении, что таковое существует.

Задача 4.11. Напишите программу, печатающую n-ое число Фибоначчи (f0 = 0, f1 = 1, fk = fk1 + fk2 для k > 1). При написании программы используйте Q = (n ZM n > 0), R = (a = fn ), изменять нельзя.

Задача 4.12. Напишите программу, находящую частное q и остаток r от деления x на y, не использующую операций умножения и деления. При написании программы положите Q = (x ZM y ZM x 0 y > 0), §4. Все задачи главы Величины x и y в программе изменять не разрешается.

Задача 4.13. Напишите программу, находящую наибольший общий делитель gcd(X, Y ) двух целых положительных чисел X и Y, не использующую операций умножения и деления и не изменяющую величин X и Y.

При написании программы положите Q = (X ZM Y ZM X > 0Y > 0), R = (x = y = gcd(X, Y )), I = (0 < x 0 < y gcd(x, y) = gcd(X, Y )), h = x + y 2 · gcd(x, y).

Указание. Воспользуйтесь следующими свойствами наибольшего общего делителя двух чисел не равных одновременно нулю (не забудьте научиться доказывать все эти свойства):

gcd(x, y) = gcd(x, y x) = gcd(x y, y), gcd(x, y) = gcd(x, y + x) = gcd(x + y, y), gcd(x, x) = x, gcd(x, y) = gcd(y, x), gcd(x, 0) = gcd(0, x) = x.

Задача 4.14. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Вот более точная формулировка пред- и постусловия:

При написании программы величину n изменять нельзя. Для построения инварианта удалите из постусловия конъюнктивный член a 2 n. Оцените временню сложность получившейся программы и сравните ее со сложностью программы, построенной в задаче 2.1.

Задача 4.15. Напишите программу, определяющую первое вхождение заданного целого числа x в заданный массив массивов b[0..m 1][0..n 1] целых чисел (m > 0, n > 0). Значения элементов массива b и числа x, m и n в программе изменять нельзя. В момент завершения должно быть либо b[i][j] = x, либо, если числа x в массиве нет, i = m. Точные преди постусловия требуемой программы таковы: Q = (m > 0 n > 0), R = ((0 i < m 0 j < n x = b[i][j]) (i = m x b[0..m 1][0..n 1])).

Указание. Используйте инвариант, утверждающий, что x не находится в уже проверенных строках b[0..i 1] и среди уже проверенных элементов b[i][0..j 1] текущей строки i. В качестве ограничивающей функции возьмите h = (m i) · n j + m i.

Задача 4.16. Напишите программу (бинарный или двоичный поиск), определяющую для упорядоченного по неубыванию массива b[0..n 1] целых чисел и заданного целого числа x позицию i, в которую может быть вставлено это число без нарушения упорядоченности массива. Точные пред- и постусловия требуемой программы, времення сложность коа торой не должна превосходить (log n), таковы: Q = (x ZM n При написании программы величины x, n и элементы массива b изменять не разрешается, для построения инварианта используйте метод замены константы переменной.

Задача 4.17. Напишите программу, печатающую факториал введенного неотрицательного целого числа, изменять которое нельзя. Для построения инварианта используйте метод замены константы переменной.

Задача 4.18. Напишите программу, находящую наибольшее целое число, являющееся степенью двойки, не превосходящее заданного натурального числа n ZM, изменять которое в программе нельзя.

Указание. Сначала выпишите формальную спецификацию программы, а затем постройте инвариант с помощью метода устранения конъюнктивного члена.

Задача 4.19. Напишите программу, находящую сумму s элементов заданного целочисленного массива b[0..n 1], элементы которого и величину n изменять нельзя. Точные пред- и постусловия: Q = (n > 0), R= s= b[j]. Инвариант постройте методом замены константы 0 в постусловии R новой переменной i.

Задача 4.20. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Точные пред- и постусловия требуемой программы, времення сложность которой не должна превосходить (log n), таковы:

написании программы величину n изменять нельзя, а инвариант следует построить методом замены константы a на переменную b в конъюнктивном члене a2 n постусловия R.

Задача 4.21. Напишите программу, находящую наименьшее значение x ZM в заданном массиве целых чисел b[0..n 1], где n > 0. Значения элементов массива b и число n в программе изменять нельзя, Q = (n §4. Все задачи главы b[j + p]))), инвариант постройте методом замены константы n на переменную i.

Задача 4.23. Напишите программу, находящую число m 1 площадок в упорядоченном по неубыванию массиве b[0..n 1] целых чисел.

Площадкой мы называем последовательность нескольких равных значений. Значения элементов массива b и число n > 0 в программе изменять нельзя.

Указание. Воспользуйтесь формулировкой предыдущей задачи.

Задача 4.24. Напишите программу, печатающую значение многочлена степени n 0 в заданной точке x0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, так же как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя. Для построения инварианта используйте метод замены константы переменной.

3. Схема вычисления инвариантной функции. При решении задач из этого раздела необходимо указать множества X, Y и XP, функцию F и преобразование T (см. определение инвариантной функции). Должна быть объяснена программная реализация преобразования T и доказана правильность построенной программы вида "S0;while(e)S;S1;".

Задача 4.25. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Воспользуйтесь следующими свойствами наибольшего общего делителя (не забудьте научиться доказывать все эти свойства):

gcd(x, y) = gcd(x, y x) = gcd(x y, y), gcd(x, y) = gcd(x, y + x) = gcd(x + y, y), gcd(x, x) = x, gcd(x, y) = gcd(y, x), gcd(x, 0) = gcd(0, x) = x.

Задача 4.26. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення а сложность которой не должна превосходить (log b), таковы: Q = (a чины a и b изменять не разрешается. Воспользуйтесь тем, что функция F : ZM ZM ZM ZM, F (x, y, z) = z + xy является инвариантной относительно преобразования T : ZM ZM ZM ZM ZM ZM, задаваемого формулой T (x, y, z) = Задача 4.27. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Воспользуйтесь следующим свойством наибольшего общего делителя (докажите его!):

gcd(x, y) = Здесь операция x%y позволяет найти остаток от деления x на y.

Задача 4.28. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: Q = (a ZM b ZM a > 0 b 0), R1 = (z = ab ).

При написании программы величины a и b изменять не разрешается. Воспользуйтесь тем, что функция F : ZM ZM ZM ZM, F (x, y, z) = zxy является инвариантной относительно преобразования T : Z M ZM ZM ZM ZM ZM, задаваемого формулой T (x, y, z) = (x, y 1, xz).

Задача 4.29. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Программа должна иметь временню сложность поу рядка (log max(x, y)) и не использовать операций деления и нахождения остатка от деления (допустимо деление пополам, реализуемое с помощью операции сдвига). Воспользуйтесь следующими свойствами наибольшего общего делителя (докажите их!):

gcd(2x, 2y) = 2gcd(x, y), gcd(2x, 2y + 1) = gcd(x, 2y + 1).

Указание. Воспользуйтесь инвариантностью функции F (x, y, z) = z · gcd(x, y) относительно следующего преобразования T :

T (x, y, z) = (x, y/2, z), если x нeчетно, а y четно, Не забудьте доказать T -инвариантность функции F.

4. Задачи на индуктивные функции. При решении задач из этого раздела необходимо выяснить, является ли индуктивной заданная функция f. В случае ее индуктивности следует предъявить отображение G, иначе нужно построить индуктивное расширение F исходной функции и предъявить G для него. В последнем случае нужно также указать отображение и исследовать построенное расширение на минимальность (минимальность не является обязательным условием). Завершить решение следует написанием программы, реализующей однопроходный алгоритм, §4. Все задачи главы с указанием соответствия между программными переменными и обозначениями, использованными в теоретической части решения. Необходимо объяснить, как в программе реализуется вычисление f или F на пустой (или ее заменяющей) цепочке, как именно реализовано перевычисление функции при удлинении цепочки, и как находится (F ()) в случае использования индуктивного расширения.

Задача 4.30. Напишите программу, определяющую значение в целой точке t многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

Задача 4.31. Напишите программу, вводящую последовательность целых чисел, и печатающую количество ее максимальных элементов.

Задача 4.32. Напишите программу, определяющую номер f первого элемента, равного x0, в последовательности целых чисел. В том случае, если число x0 в последовательности не встречается, положите f равным нулю.

Задача 4.33. Напишите программу, вводящую последовательность вещественных чисел, и печатающую среднее арифметическое ее элементов (для непустой последовательности).

Задача 4.34. Напишите программу, определяющую количество вхождений образца abcd в последовательность символов.

Задача 4.35. Напишите программу, определяющую количество минимальных элементов в последовательности неположительных целых чисел.

Указание. В данном случае для доопределения индуктивного расширения на пустой цепочке нет необходимости использовать величины Integer.MIN_VALUE или Integer.MAX_VALUE.

Задача 4.36. Напишите программу, определяющую дисперсию не пустой последовательности действительных чисел. Дисперсией d последоn вательности x1, x2,..., xn называется величина F = (s2, s1, s0 ) является индуктивной.

Задача 4.37. Напишите программу, определяющую значение в целой точке t многочлена, заданного последовательностью его целых коэффициентов (в порядке возрастания степеней).

Задача 4.38. Напишите программу, определяющую значение в целой точке t производной многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

Указание. Продифференцировав по x равенство Pn (x) = x·Pn1 (x)+ an и подставив затем x = t, получите соотношения P0 (t) = 0 и Pn (t) = t · Pn1 (t) + Pn1 (t), которые помогут построить индуктивное расширение исходной функции.

Задача 4.39. Напишите программу, определяющую значение в целой точке t производной многочлена, заданного последовательностью его целых коэффициентов (в порядке возрастания степеней).

Задача 4.40. Напишите программу, определяющую значение в целой точке t второй производной многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

Задача 4.41. Напишите программу, определяющую правильность формулы над алфавитом из четырех символов X = {(, ), t, +}. Формула считается правильной, если она может быть получена с помощью следующей НФБН: e t | (e + e).

Указание. Рассмотрите следующее индуктивное расширение F = определены следующим образом:

f1 () = может быть продолжена до правильной формулы, f2 () = разность числа левых и правых скобок в, f3 () = последний элемент.

Задача 4.42. Напишите программу, определяющую номер f последнего элемента, равного x0, в последовательности целых чисел. В том случае, если число x0 в последовательности не встречается, положите f = 0.

§4. Все задачи главы Задача 4.43. Напишите программу, определяющую число локальных максимумов в последовательности целых чисел. Элемент называется локальным максимумом, если у него нет соседа большего, чем он сам. Например, в любой одноэлементной последовательности всегда ровно один локальный максимум.

Задача 4.44. Напишите программу, определяющую среднюю длину связной возрастающей подпоследовательности в последовательности целых чисел.

Задача 4.45. Напишите программу (быстрое возведение в степень), возводящую целое число a в целую неотрицательную степень b, времення сложность которой не должна превосходить (log b).

Указание. Рассмотрите эту функцию f, как функцию на пространстве последовательностей над алфавитом {0, 1}. В качестве последовательности нужно взять инвертированное представление числа b в двоичной системе счисления. Данная последовательность получается естественным образом последняя цифра числа b есть "b&1", предпоследняя получается по той же формуле после сдвига вправо ("b>>>=1;") и так далее. Индуктивное расширение F исходной функции f легко находится, что и позволяет написать требуемую программу.

Задача 4.46. Напишите программу, определяющую количество вхождений образца abab в последовательность символов.

Задача 4.47. Напишите программу, определяющую значение в целой точке t k-ой производной многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

Применение ООП к разработке программных Несмотря на то, что язык Java является объектно-ориентированным, до сих пор при разработке программ мы по существу пользовались парадигмой директивного программирования целью было создание кода, воздействующего должным образом на данные. Этот подход хорош при решении небольших задач, но порождает множество трудноразрешимых проблем при попытке создания больших программных систем.

Одной из альтернатив директивному программированию является объектно-ориентированное программирование, которое действительно помогает справиться с нелинейно растущей сложностью программ при увеличении их объема. Не следует, однако, делать вывод, что использование парадигмы объектно-ориентированного программирования гарантирует успешное решение всех проблем.

Для того чтобы стать профессионалом в программировании, необходимы талант, способность к творчеству, интеллект, знания, логика, умение строить и использовать абстракции и, самое главное, опыт.

§ 1. Основы объектно-ориентированного В этом параграфе мы продолжим знакомство с базисными концепциями объектно-ориентированного программирования, начатое еще в первой главе книги. Сначала будут обсуждены общие для различных языков программирования понятия ООП, а затем их реализация в языке Java.

Следует знать, что курс объектно-ориентированного программирования читается студентам-старшекурсникам в течение целого семестра, и поэтому материал, изложенный ниже, представляет собой лишь самое начальное введение в мир ООП. Значительно более полное изложение многих вопросов, связанных с объектно-ориентированными дизайном, проектированием и программированием, содержится в книге [2], а в третьей главе книги [13] можно найти очень ясное описание всех объектноориентированных аспектов языка Java.

158 Глава III. Применение ООП к разработке программных проектов 1. Основные концепции ООП. Объектно-ориентированное программирование или ООП (object-oriented programming) методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является реализацией определенного типа, использующая механизм пересылки сообщений и классы, организованные в иерархию наследования.

Центральный элемент ООП абстракция. Данные с помощью абстракции преобразуются в объекты, а последовательность обработки этих данных превращается в набор сообщений, передаваемых между этими объектами. Каждый из объектов имеет свое собственное уникальное поведение. С объектами можно обращаться как с конкретными сущностями, которые реагируют на сообщения, приказывающие им выполнить какието действия.

ООП характеризуется следующими принципами (по Алану Кею):

• все является объектом;

• вычисления осуществляются путем взаимодействия (обмена данными) между объектами, при котором один объект требует, чтобы другой объект выполнил некоторое действие; объекты взаимодействуют, посылая и получая сообщения; сообщение это запрос на выполнение действия, дополненный набором аргументов, которые могут понадобиться при выполнении действия;

• каждый объект имеет независимую память, которая состоит из • каждый объект является представителем класса, который выражает общие свойства объектов данного типа;

• в классе задается функциональность (поведение объекта); тем самым все объекты, которые являются экземплярами одного класса, могут выполнять одни и те же действия;

• классы организованы в единую древовидную структуру с общим корнем, называемую иерархией наследования; память и поведение, связанное с экземплярами определенного класса, автоматически доступны любому классу, расположенному ниже в иерархическом дереве.

Определение 1.1. Абстрагирование (abstraction) метод решения задачи, при котором объекты разного рода объединяются общим понятием (концепцией), а затем сгруппированные сущности рассматриваются как элементы единой категории.

Абстрагирование позволяет отделить логический смысл фрагмента программы от проблемы его реализации, разделив внешнее описание (интерфейс) объекта и его внутреннюю организацию (реализацию).

§1. Основы объектно-ориентированного программирования Определение 1.2. Инкапсуляция (encapsulation) техника, при которой несущественная с точки зрения интерфейса объекта информация прячется внутри него.

Определение 1.3. Наследование (inheritance) свойство объектов, посредством которого экземпляры класса получают доступ к данным и методам классов-предков без их повторного определения.

Наследование позволяет различным типам данных совместно использовать один и тот же код, приводя к уменьшению его размера и повышению функциональности.

Определение 1.4. Полиморфизм (polymorphism) свойство, позволяющее использовать один и тот же интерфейс для различных действий;

полиморфной переменной, например, может соответствовать несколько различных методов.

Полиморфизм перекраивает общий код, реализующий некоторый интерфейс, так, чтобы удовлетворить конкретным особенностям отдельных типов данных.

Определение 1.5. Класс (class) множество объектов, связанных общностью структуры и поведения; абстрактное описание данных и поведения (методов) для совокупности похожих объектов, представители которой называются экземплярами класса.

Определение 1.6. Объект (object) конкретная реализация класса, обладающая характеристиками состояния, поведения и индивидуальности, синоним экземпляра.

Как это уже отмечалось в самом начале курса, Java лишь один из объектно-ориентированных языков. Другим активно используемым профессиональными программистами языком ООП, с который мы познакомимся в следующем семестре, является C++. В дальнейшем нам предстоит знакомство с такими представителями этого семейства, как Smalltalk, Delphi Pascal и CLOS.

Следует иметь в виду, что в разных объектно-ориентированных языках для обозначения одних и тех же концепций ООП используются слегка отличающиеся друг от друга термины (см. стр. 186).

2. Классы и объекты в языке Java. Для знакомства с базовым для объекно-ориентированного программирования понятием класса, рассмотрим класс R2Point, задающий точку на плоскости.

Пример программы.

160 Глава III. Применение ООП к разработке программных проектов //Класс, описывающий точку (Point) на плоскости (R2).

class R2Point { // Переменные экземпляра, задающие координаты точки.

private double x, y;

// Конструктор с параметрами.

public R2Point(double x, double y) { // Метод экземпляра - расстояние до начала координат.

public double dist0() { return Math.sqrt(x*x + y*y);

Для того, чтобы создать экземпляр этого класса, в программе следует предварительно объявить переменную типа R2Point, а затем воспользоваться оператором new. Объявление переменной можно совмещать с созданием нового объекта, что демонстрируется в следующей программе, находящей расстояние от точки до начала координат.

R2Point p = new R2Point(1.,2.);

double d = p.dist0();

Этот пример объясняет, почему такой стиль записи называют объектно-ориентированным: при вызове метода в центре внимания находится объект p, а не метод dist0. Этот метод не нуждается в аргументе объект, над которым производится данное действие, уже указан в данной конструкции. Именно по этой причине внутри метода dist0 можно работать с величинами x и y, принадлежащими конкретному экземпляру объекта. Имена x и y в теле метода dist0 являются сокращениями от this.x и this.y соответственно, где ключевое слово this является указателем на тот экземпляр класса, с которым должен работать метод.

Часто нет необходимости явно использовать этот неявный аргумент любого метода экземпляра, однако иногда это необходимо. Примером является конструктор класса R2Point.

Конструктор это метод, имеющий имя, совпадающее с именем класса. Две основные задачи конструктора заключаются в выделении памяти под вновь создаваемый объект и его инициализация. В рассматриваемом нами примере точки на плоскости совершенно бессмысленно пытаться как-либо работать с объектом (точкой), у которого не заданы координаты.

Поэтому конструктор объекта типа R2Point, который вызывается с помощью метода new, должен записать в переменные конкретного экземпляра §1. Основы объектно-ориентированного программирования его координаты. В том случае, если в качестве имен аргументов конструктора выбраны x и y (а это вполне естественный выбор), для обеспечения доступа к переменным экземпляра необходимо использование ключевого слова this. В объявлении конструктора не разрешается указывать возвращаемый тип (хотя неявно всегда возвращается объект this), а в его теле нельзя использовать оператор return.

Если в некоторой задаче необходимо создавать новые объекты типа R2Point, вводя их координаты с клавиатуры, то может возникнуть желание реализовать это непосредственно в конструкторе.

Пример программы.

//Класс, описывающий точку (Point) на плоскости (R2).

class R2Point{ // Переменные экземпляра, задающие координаты точки.

private double x, y;

// Конструктор с параметрами.

public R2Point(double x, double y) { // Еще один конструктор, позволяющий вводить // координаты вновь создаваемой точки с клавиатуры.

public R2Point() throws Exception { x = Xterm.inputDouble("x -> ");

y = Xterm.inputDouble("y -> ");

// Метод класса - расстояние до начала координат.

public static double dist0(R2Point a) { return Math.sqrt(a.x*a.x + a.y*a.y);

// Метод экземпляра - расстояние до начала координат.

public double dist0() { return Math.sqrt(x*x + y*y);

Такой класс выглядит на первый взгляд весьма странно в нем разные методы имеют одинаковые имена. Компилятор, однако, может различить их. Признак, по которому это происходит количество и типы аргументов у различных методов. Так, если оператор new для объекта R2Point имеет два аргумента, то вызывается первый из конструкторов, а если аргументов нет второй.

Вторым интересным моментом в этом примере является иллюстрация использования метода класса. Первый из двух методов dist0 описан с 162 Глава III. Применение ООП к разработке программных проектов ключевым словом static, что и делает его методом класса. Такой метод не может быть вызван от конкретного объекта с помощью оператора точка, ему не передается указатель this на экземпляр, а само это ключевое слово не может быть использовано в его теле. Приведенная ниже программа находит расстояние от точки p до начала координат двумя различными эквивалентными методами.

R2Point p = new R2Point(1.,2.);

double d1 = p.dist0();

double d2 = R2Point.dist0(p);

Могут существовать и переменные класса это такие переменные, которые всегда имеются ровно в одном экземпляре, независимо от того как много имеется объектов данного класса. Для их описания также применяется ключевое слово static.

Обычно класс содержит целый ряд методов, как экземпляра, так и класса, набор которых определяется конкретной задачей. Вот как выглядит описание класса R2Point, которое будет использовано в следующем параграфе в реальном проекте.

Пример программы.

//Класс, описывающий точку (Point) на плоскости (R2).

class R2Point { private double x, y;

public R2Point(double x, double y) { public R2Point() throws Exception { x = Xterm.inputDouble("x -> ");

y = Xterm.inputDouble("y -> ");

public static double dist(R2Point a, R2Point b) { return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

public static double area(R2Point a, R2Point b, R2Point c) { return 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));

public static boolean equal(R2Point a, R2Point b) { return a.x==b.x && a.y==b.y;

public static boolean isTriangle(R2Point a, R2Point b, R2Point c) { public boolean inside(R2Point a, R2Point b) { §1. Основы объектно-ориентированного программирования public boolean light(R2Point a, R2Point b) { double s = area(a, b, this);

return s < 0.0 || ( s == 0.0 && ! inside(a, b));

Рассмотрим задачу на реализацию класса с заданными свойствами.

Задача 1.1. Реализуйте класс R2Vector, позволяющий выполнять над векторами на плоскости следующие операции: сложение, вычитание, умножение на число и вычисление скалярного произведения.

Ее решение, приведенное ниже, в комментариях не нуждается.

Текст программы.

class R2Vector { private double x, y;

public R2Vector(double x, double y) { public R2Vector() throws Exception { x = Xterm.inputDouble("x -> ");

y = Xterm.inputDouble("y -> ");

public static R2Vector plus(R2Vector a, R2Vector b) { return new R2Vector(a.x+b.x, a.y+b.y);

public static R2Vector minus(R2Vector a, R2Vector b) { return new R2Vector(a.x-b.x, a.y-b.y);

public static R2Vector mult(R2Vector a, double k) { return new R2Vector(k*a.x, k*a.y);

public static double product(R2Vector a, R2Vector b) { return a.x*b.x + a.y*b.y;

Одним из достоинств объектно-ориентированного подхода является возможность использования уже существующих типов для порождения новых с автоматическим наследованием уже имеющихся свойств. Язык 164 Глава III. Применение ООП к разработке программных проектов Java реализует эту возможность с помощью двух механизмов расширения или наследования классов (ключевое слово extends) и реализации интерфейсов (ключевое слово implements).

Примером использования первого из этих механизмов является следующий программный фрагмент.

Пример расширения класса.

class Stack { private static final int DEFSIZE = 16;

private char[] array;

public Stack() { array = new char[DEFSIZE];

public final void push(char c) { public final char pop() { return array[--head];

public class Compf extends Stack { private void processSymbol(char c) { case ’+’: case ’-’: case ’*’: case ’/’:

public Compf() { public final void compile(String str) { for(int i = 0; i < str.length(); i++) processSymbol(str.charAt(i));

§1. Основы объектно-ориентированного программирования Класс Stack (стек символов) в данном случае используется в качестве базового для нового класса Compf (стековый компилятор формул), называемого в этом случае дочерним или выведенным. Все те методы, которые были реализованы в базовом классе (или суперклассе) Stack могут быть использованы и для объектов типа Compf, что и делается в методе processSymbol. Принято говорить, что между классами Stack и Compf возникает отношение наследования.

В языке Java каждый существующий класс неявно наследует класс Object, что превращает последний в суперкласс любого класса. Сам же класс Object является единственным классом, не имеющим суперкласса.

Если изобразить иерархию классов графически, то получится дерево с корнем Object.

При вызове конструктора выведенного класса всегда происходит вызов (явный или неявный) конструктора его непосредственного базового класса. В случае явного вызова это реализуется с помощью оператора super(), который должен быть первым оператором конструктора. В случае отсутствия явного вызова компилятор самостоятельно вставляет вызов конструктора суперкласса без параметров. Таким образом, при создании нового объекта всегда реализуется цепочка вызовов конструкторов всех родительских классов (вплоть до Object).

Перед завершением рассмотрения примера отметим, что используемые в реальном проекте классы Stack и Compf существенно отличаются от рассмотренных нами сейчас. Это замечание в полной мере применимо и к следующему примеру механизма создания новых типов использованию интерфейсов.

Пример реализации интерфейса.

// Интерфейс, задающий новый тип - фигуру.

interface Figure { // Периметр фигуры.

public double perimeter();

// Площадь фигуры.

public double area();

// Класс "нульугольник", реализующий интерфейс фигуры.

class Void implements Figure { public double perimeter() { public double area() { Глава III. Применение ООП к разработке программных проектов // Класс "одноугольник", реализующий интерфейс фигуры.

class Point implements Figure { private R2Point p;

public Point(R2Point p) { public double perimeter() { public double area() { // Класс "двуугольник", реализующий интерфейс фигуры.

class Segment implements Figure { private R2Point p, q;

public Segment(R2Point p, R2Point q) { public double perimeter() { return 2.0 * R2Point.dist(p, q);

public double area() { // Класс "многоугольник", реализующий интерфейс фигуры.

class Polygon extends Deq implements Figure { private double s, p;

public Polygon(R2Point a, R2Point b, R2Point c) { ; // Значительное упрощение.

public double perimeter() { public double area() { §1. Основы объектно-ориентированного программирования Интерфейс Figure определяет геометрическую фигуру, которая характеризуется периметром и площадью. При этом конкретными реализациями этой абстрактной идеи могут быть нульугольник (пустое множество), одноугольник (точка), двуугольник (отрезок) и многоугольник. Каждый из этих классов имеет свою особую внутреннюю структуру: одноугольник содержит координаты его единственной точки, двуугольник двух его концевых точек, а класс Polygon (многоугольник) вообще выведен из класса Deq, что позволяет ему хранить координаты всех его вершин. Каждый из этих классов обеспечивает свои варианты реализации для всех методов, имеющихся в описании интерфейса.

Когда в программе, работающей с объектом типа Figure, вызывается метод area() для этого объекта, то реально произойдет вызов метода именно того класса, к которому принадлежит данный объект. Это гарантируется с помощью специального механизма, известного как динамический поиск метода. Подобное свойство имеет, к сожалению, и негативную сторону динамический поиск метода медленнее непосредственного вызова. По этой причине там, где это возможно, программист должен дать компилятору право применить непосредственный вызов метода.

Динамический поиск метода никогда не используется в следующих ситуациях:

• для методов, объявленных с ключевым словом static;

• для методов, объявленных с ключевым словом private;

• для методов, объявленных с ключевым словом final;

• для всех методов final-класса.

Поясним смысл этих и некоторых других ключевых слов языка Java, которые были использованы в приведенных выше примерах. Ключевое слово final, примененное к методу, запрещает переопределять его в выведенных классах. Применение его к полю данных превращает эти данные в неизменяемые (константу). Особенно часто для этой цели используется комбинация двух ключевых слов static final. Будучи примененным к описанию класса, final запрещает использование данного класса в качестве базового.

Квалификаторы доступа private, protected и public определяют доступность данных или метода, реализуя возможность инкапсуляции.

Только методы, описанные с использованием ключевого слова public, являются общедоступными. Именно они определяют интерфейс объекта.

Все внутренние данные объекта, как правило, описываются с квалификатором private, что запрещает работу с ними извне объекта. Ключевое слово protected обеспечивает работу с так описанными компонентами 168 Глава III. Применение ООП к разработке программных проектов методам выведенных классов. Во всех рассмотренных выше примерах интерфейс объекта (его public-компоненты и методы) был отделен пустой строкой от компонент, являющихся его внутренней реализацией (private и protected данные и методы).

Теперь мы в состоянии полностью объяснить программу Здравствуй, мир!, с которой в самом начале книги началось знакомство с языком Java.

Текст программы.

public class Hello { public static void main(String[] args) { System.out.println("Здравствуй, мир!");

Общедоступный (public) статический (static) метод main класса Hello, с которого начинается выполнение программы, получает в качестве аргумента массив строк args, не возвращая после своего завершения никакого результата (являясь void-методом). Выполнение main сводится к вызову метода println с аргументом "Здравствуй, мир!" для объекта, на который ссылается поле (компонента) out объекта System.

3. Контейнеры. ООП предоставляет программисту богатейшие возможности по созданию новых типов данных, часть из которых была проиллюстрирована в предыдущей секции. Сейчас мы рассмотрим еще один важный механизм применение контейнеров.

Определение 1.7. Контейнерные классы (container classes) классы, которые используются как структуры данных, содержащие набор элементов.

Пакет java.util предоставляет интерфейс Enumeration и классы Vector, Stack, Dictionary, Hashtable и BitSet, предназначенные для решения сформулированной задачи при программировании на языке Java.

По целому ряду причин мы не будем использовать классы этого пакета в нашем курсе.

Стандартная библиотека (STL) языка C++ содержит более широкий набор так называемых стандартных контейнеров. Используемые нами в данной секции имена классов и методов будут в значительной мере напоминать имена из этой стандартной библиотеки, более подробное знакомство с которой предусмотрено в рамках последующего курса Методы хранения и обработки информации.

Определение 1.8. Основными контейнерами являются вектор (vector), перечисление (enumeration), динамический вектор (dynamic §1. Основы объектно-ориентированного программирования vector), стек (stack), очередь (queue), дек (deq), множество (set), однои двусвязные списки (lists).

Из приведенного выше перечня выделяются вектор и перечисление это структуры, не являющиеся динамическими. Последнее означает, что их размер определяется в момент создания и не может быть изменен в дальнейшем.

Использование векторов (так называют массивы) нам уже хорошо знакомо, а пример работы с перечислением приведен ниже. В нем применяется интерфейс Enumeration, очень похожий на тот, что определен в пакете java.util. Этот интерфейс задает новый тип объекта контейнер, который содержит внутри себя набор других объектов и позволяет извлекать из него эти объекты один за другим (в неизвестном порядке), предварительно выясняя, осталось ли в нем что-либо.

Пример интерфейса.

interface Enumeration { // Есть ли еще элементы?

public boolean hasMoreElements();

// Взять следующий элемент.

public Object nextElement();

// Реализация перечисления для работы с целыми числами.

class Enum implements Enumeration { // Вектор, в котором хранятся числа.

private int[] values;

// Количество уже извлеченных чисел.

private int current;

// Конструктор.

public Enum(int[] values) { this.values = values;

public boolean hasMoreElements() { return current < values.length;

public Object nextElement() { return new Integer(values[current++]);

// Тестовая программа для работы с перечислением.

public static void main(String[] args) { for (int i=0; i= array.length) throw new Exception();

array[tail=forward(tail)] = val;

public int pop() throws Exception { public int front() throws Exception { if(empty()) throw new Exception();

public static void main(String[] args) throws Exception { QueueTest q = new QueueTest(5);

switch (Xterm.inputInt("Action [01234] -> ")) { q.push(Xterm.inputInt("Push int: ")); break;

System.out.println("Pop int " + q.pop()); break;

System.out.println("Front = " + q.front()); break;

System.out.println("Wrong action, ignore");

§1. Основы объектно-ориентированного программирования Рис. 6. Реализация ограниченной очереди Основная идея, используемая в этой реализации сворачивание вектора в кольцо, что реализуется с помощью метода forward, вычисляющего индекс элемента, следующего за данным. При этом следующим за последним элементом массива считается его самый первый элемент (с индексом 0).

Графическая иллюстрация этой реализации приведена на рисунке 6.

Переменная size здесь содержит количество элементов в очереди, head индекс самого первого элемента в (непустой) очереди, а tail последнего ее элемента. Первая из этих трех переменных необходима для того, чтобы отличить пустую очередь от полностью заполненной.

Если не сворачивать вектор, то после выполнения n (где n длина вектора) последовательных пар операций push и pop над изначально пустой очередью она по-прежнему будет пуста, но положение указателей head и tail сделает невозможным добавление в нее новых элементов.

Интерфейс Queue был изменен так, чтобы попытка добавить элемент в полностью заполненную очередь также приводила к возникновению исключительной ситуации. Реализация на базе циклического вектора не приводит к автоматическому возникновению исключительной ситуации, связанной с выходом за границу массива, как это было в предыдущем примере. Поэтому здесь приходится возбуждать исключительную ситуацию явным образом с помощью оператора throw.

Также как и для стека, реализация очереди является достаточно эффективной все методы имеют константную сложность (1).

Непрерывно можно реализовать практически любую структуру данных. Ряд упражнений на это приведен в конце параграфа. Обратите, в частности, внимание на две реализации ограниченного множества на базе вектора, основанные на последовательном и двоичном поиске элементов.

182 Глава III. Применение ООП к разработке программных проектов Рис. 7. Идея ссылочной реализации односвязного списка Любая непрерывная реализация на базе вектора множества или, скажем, трех стеков, имеет, однако, существенный недостаток некоторые из методов имеют линейную сложность ((n)), ибо требуют массовых сдвига части элементов вектора. Как правило, это неприемопераций лемо высокая времення эффективность реализации обычно является обязательным условием.

Существенно повысить эффективность можно, используя ссылочные реализации. Особенно изящно это удается сделать в языках программирования, допускающих указатели (например C++), но и язык Java позволяет применять данный прием. Следующее определение относится именно к языкам, не допускающим использования указателей.

Определение 1.10. Реализация на базе вектора называется ссылочной, если все элементы контейнера хранятся в одном векторе, а другой вектор вектор ссылок, определяет реально содержащиеся в имитируемой структуре элементы и их порядок (если он существует).

Иногда (например, в случае двусвязного списка) ссылочная реализация требует использования двух векторов ссылок.

Типичным примером ссылочной реализации является реализация односвязного списка.

Задача 1.4. Постройте ссылочную реализацию ограниченного односвязного списка целых чисел на базе вектора с применением двух векторов ссылок и оцените эффективность полученной программы.

Элементы списка будут размещаться в массиве array, а второй массив next будем использовать для ссылок. Лучше всего представлять себе элементы списка в виде бусинок на ниточке. При этом все элементы §1. Основы объектно-ориентированного программирования Рис. 8. Ссылочная реализация односвязного списка массива, не содержащиеся в списке, нанизаны на другую нитку. Для того чтобы упростить работу с пустым и полностью заполненным списком, полезно завести два фиктивных элемента, к которым прикрепляются концы этих двух нитей (см. рис. 7). По историческим причинам будем называть эти элементы нилом списка и нилом свободного места соответственно, разместив их в двух дополнительных элементах массива ссылок next.

Добавление элемента в список при этом сводится к тому, что элемент (бусинку) надо снять с одной нити и переместить на другую. Удаление из списка производится точно также, только нити меняются местами.

Для реализация этой идеи в i-м элементе массива ссылок необходимо хранить индекс элемента, следующего за ним (собственно в списке или в списке свободных элементов). В частности, пустому списку соответствует ситуация, изображенная на рисунке 8.

В приведенной ниже программе конструктор списка L1ListTest заносит необходимые значения в массив next, используя метод link, обеспечивающий связывание двух элементов. Все остальные методы класса имеют константную сложность (1).

Текст программы.

interface L1List { boolean empty();

void toFront();

boolean end();

void forward() throws Exception;

int after() throws Exception;

void insert(int val) throws Exception;

int erase() throws Exception;

class L1ListTest implements L1List { Глава III. Применение ООП к разработке программных проектов // массив элементов.

private int[] array;

// массив ссылок.

private int[] next;

// "нил" списка.

private int nilList;

// "нил" свободного места.

private int nilFree;

// индексы элементов до и после указателя.

private int before, after;

// связать два элемента, заданные индексами.

private void link(int first, int second) { // захватить место.

private int mallocIndex() { int index = next[nilFree];

link(nilFree, next[index]);

// освободить место.

private void freeIndex(int index) { link(index, next[nilFree]);

link(nilFree, index);

public L1ListTest(int size) { link(nilList, nilList);

for (int i=0; i= 0 ? index : array.length - 1;

public Deq(int size) { array = new R2Point[size];

public Deq() { this(DEFSIZE);

public int length() { public void pushFront(R2Point p) { array[head=backward(head)] = p;

public void pushBack(R2Point p) { array[tail=forward(tail)] = p;

Глава III. Применение ООП к разработке программных проектов public R2Point popFront() { public R2Point popBack() { public R2Point front() { public R2Point back() { // Интерфейс, задающий новый тип - фигуру.

interface Figure { public double perimeter();

public double area();

public Figure add(R2Point p);

// Класс "нульугольник", реализующий интерфейс фигуры.

class Void implements Figure { public double perimeter() { public double area() { public Figure add(R2Point p) { return new Point(p);

// Класс "одноугольник", реализующий интерфейс фигуры.

class Point implements Figure { private R2Point p;

public Point(R2Point p) { public double perimeter() { public double area() { public Figure add(R2Point q) { if (!R2Point.equal(p,q)) return new Segment(p, q);

// Класс "двуугольник", реализующий интерфейс фигуры.

class Segment implements Figure { private R2Point p, q;

public Segment(R2Point p, R2Point q) { public double perimeter() { return 2.0 * R2Point.dist(p, q);

public double area() { public Figure add(R2Point r) { if (R2Point.isTriangle(p, q, r)) // Класс "многоугольник", реализующий интерфейс фигуры.

class Polygon extends Deq implements Figure { private double s, p;

private void grow(R2Point a, R2Point b, R2Point t) { p -= R2Point.dist(a, b);

s += Math.abs(R2Point.area(a, b, t));

public Polygon(R2Point a, R2Point b, R2Point c) { Глава III. Применение ООП к разработке программных проектов pushFront(a); pushBack(c);

pushFront(c); pushBack(a);

p = R2Point.dist(a, b) + R2Point.dist(b, c) s = Math.abs(R2Point.area(a, b, c));

public double perimeter() { public double area() { public Figure add(R2Point t) { // Ищем освещенные ребра, просматривая их одно за другим.

for (i=length(); i>0 && !t.light(back(),front()); i--) // УТВЕРЖДЕНИЕ: либо ребро [back(),front()] освещено из t, // Удаляем все освещенные ребра из начала дека.

for (x = popFront(); t.light(x, front()); x = popFront()) // Удаляем все освещенные ребра из конца дека.

for (x = popBack(); t.light(back(), x); x = popBack()) // Завершаем обработку добавляемой точки.

p += R2Point.dist(back(), t) + R2Point.dist(t, front());

// Класс "выпуклая оболочка".

class Convex { private Figure fig;

§3. Проект Компилятор формул public Convex() { public void add(R2Point p) { public double area() { return fig.area();

public double perimeter() { return fig.perimeter();

// Тест для выпуклой оболочки.

class ConvexTest { public static void main(String[] args) throws Exception { Convex convex = new Convex();

convex.add(new R2Point());

В данном параграфе изучаются простейшие вопросы теории компиляции, рассматриваются языки простейших арифметических формул и стекового калькулятора, а также задача автоматического перевода с первого на второй.

Первым вариантом компилятора средства для автоматического перевода программ, является рекурсивный компилятор формул достаточно простой, но обладающий рядом недостатков.

Другой, значительно более общий подход к решению этой задачи, осуществляется во втором программном проекте стековом компиляторе формул. Этот проект, кроме реализации компилятора, предусматривает также и реализацию интерпретатора арифметических формул. Исходные тексты упомянутых программ в значительной мере оптимизированы, а для облегчения работы над проектами используется утилита make.

Дополнительная информация о различных подходах к реализации компиляторов может быть найдена в книге [9].

220 Глава III. Применение ООП к разработке программных проектов 1. Стековый калькулятор. Стековый калькулятор, как это следует из его названия, представляет из себя некоторый объект, использующий хорошо известный нам контейнер стек. С формальной точки зрения стековый калькулятор это класс, реализующий следующий интерфейс.

Интерфейс стекового калькулятора.

interface StackCalc { // Добавить число в стек.

void push(int val);

// Сложить.

int add() throws Exception;

// Вычесть.

int sub() throws Exception;

// Умножить.

int mul() throws Exception;

// Разделить.

int div() throws Exception;

// Показать вершину стека.

int top() throws Exception;

Методы push и top хорошо известны и комментариев не требуют, а семантика остальных четырех такова: из стека извлекаются (с помощью метода pop) два верхних числа, над ними выполняется указанная в названии метода арифметическая операция, а результат кладется обратно в стек (с помощью метода push). При этом в качестве первого аргумента арифметической операции берется тот из двух извлеченных элементов, который был положен в стек раньше другого. Если в момент вызова одного из этих четырех методов глубина стека меньше двух, возникает исключительная ситуация. При реализации данного интерфейса на базе ограниченного вектора выполнение метода push также может привести к исключительной ситуации, связанной с переполнением стека.

Стековый калькулятор можно использовать для вычисления значений различных арифметических выражений типа 5(7 + 8) + 25. Нужно только написать предварительно программу для вычисления значения.

С целью сокращения длины подобной программы будем записывать последовательность вызываемых методов в строку, разделяя их просто пробелом. Названия методов арифметических операций заменим на соответствующие им знаки действий (+, -, * и /), вместо вызова метода push с аргументом val будем записывать только его аргумент, а завершающий любую программу вызов метода top вообще включать в такую сокращенную запись программы не будем.

§3. Проект Компилятор формул С использованием этих сокращений программа для вычисления выражения 5(7 + 8) + 25 примет вид 5 7 8 + * 25 +. Рисунок 17 показывает последовательность состояний стека стекового калькулятора при выполнении этой программы.

В рассмотренном примере программа для стекового калькулятора была написана по исходной формуле 5(7 + 8) + 25 нами. Основной задачей этого параграфа является реализация компилятора программы, которая сможет осуществлять преобразование формулы в программу для калькулятора автоматически.

С формальной точки зрения компилятор представляет собой программную реализацию некоторой функции, действующей из множества цепочек одного языка L1 (в рассматриваемом случае это язык арифметических формул) в множество цепочек другого L2 (язык программ стекового калькулятора) таким образом, что L1 семантика цепочек и () L2 совпадает. Говоря другими словами, компилятор (часто называемый также транслятором) реализует перевод с одного языка на другой с сохранением смысла.

Напомним некоторые важнейшие определения, связанные с языками и грамматиками, которые были рассмотрены в §3 первой главы.

Пусть некоторый алфавит, N метаалфавит, т.е. какой-то другой алфавит, не пересекающийся с ( N = ). Элементы метаалфавита N называются метасимволами. Грамматикой G называется набор (, N, P, S), где множество символов, N множество метасимволов, тасимвол, ( N ) произвольная цепочка над объединением двух алфавитов, и для каждого N встречается хотя бы одно правило с в левой части (до стрелочки), а S N так называемый стартовый метасимвол.

Содержательно каждое правило грамматики имеет смысл подстановки. Например, строка означает возможность замены метасимвола на цепочку. Начав со стартового символа и пользуясь различными правилами грамматики, мы можем получать различные цепочки из символов, которые называются выводимыми цепочками.

222 Глава III. Применение ООП к разработке программных проектов Заметим, что если в цепочке встречается метасимвол, то ее можно преобразовать дальше, применив одно из правил грамматики с этим метасимволом в левой части. Если же метасимволов в цепочке не осталось, то процесс ее преобразования закончен и больше с цепочкой ничего сделать нельзя. По этой причине обычные символы (из алфавита ) часто называют терминалами, а метасимволы (из N ) нетерминалами.

Языком L(G), порожденным грамматикой G, называется множество всех терминальных выводимых цепочек.

Для задания грамматики часто используют очень наглядную форму представления, называемую нормальной формой Бэкуса-Наура (НФБН).

Набор правил P задают при этом в виде совокупности правил со стрелочками, перечисляющими все возможные цепочки, на которые может быть заменен каждый из метасимволов грамматики в процессе вывода, а стартовым метасимволом считается тот, который присутствует в левой части самого первого правила.

Возьмем в качестве алфавита множество, состоящее из четырех знаков арифметических операций (+,, и /) и 26-и идентификаторов от a до z, которыми будут обозначаться произвольные целые числа:

Тогда язык будет представлять из себя все возможные программы для стекового калькулятора, включая и неправильные. Например, пустая цепочка означает вызов единственного метода pop, что приведет к возникновению исключительной ситуации. Принадлежащая этому языку цепочка 2 + также соответствует некорректной программе, ибо в момент вызова метода add в стеке будет содержаться только один элемент.

Для описания языка правильных программ для стекового калькулятора можно воспользоваться следующей грамматикой GS.

Именно язык L(GS ) мы и будем рассматривать, как язык правильных программ для стекового калькулятора.

2. Грамматики языка правильных арифметических формул.

Разобравшись с языком программ стекового калькулятора, на который мы будем осуществлять перевод, попробуем теперь формально описать язык правильных арифметических формул, с которого этот перевод будет производиться. Для простоты ограничимся случаем, когда в формулах §3. Проект Компилятор формул фигурируют только односимвольные переменные, запрещено использование унарных операций, а символ, обозначающий умножение, не может быть опущен.

В качестве алфавита возьмем то же самое множество, что и раньше, состоящее из двух круглых скобок (открывающей и закрывающей), четырех знаков арифметических операций (+,, и /) и 26-и идентификаторов от a до z, которыми будут обозначаться произвольные целые числа:

В качестве метаалфавита рассмотрим множество из трех нетерминалов:

где символ будет обозначать формулу, имя переменной, а арифметическую операцию.

Множество правил P грамматики G1 = (, N, P, S) зададим так:

Стартовым метасимволом этой грамматики является нетерминал, а примером вывода в ней может служить следующий вывод формулы x + y:

Для формулы x + y z существует два существенно различных множества эквивалентных между собой цепочек вывода, каждому из которых соответствует свое дерево вывода. Эти деревья изображены на рисунке и отличаются друг от друга порядком появления в формуле операций + 224 Глава III. Применение ООП к разработке программных проектов и. Хотя в результате различных выводов получается одна и та же формула, вычисления по ним дадут различные результаты. В одном случае выражение x + y z трактуется как (x + y) z, а в другом как x + (y z).

Таким образом, грамматика G1 хотя и задает язык правильных арифметических формул, не отражает старшинства операций (приоритетов).

Тот же самый язык может быть задан с помощью иной грамматики G 2, в которой этот недостаток устранен.

Множество нетерминалов для этой грамматики будет состоять из четырех метасимволов F, T, M и V, обозначающих соответственно формулу, терм, множитель и имя переменной. Множество правил P грамматики G2 зададим так:

По ряду причин чуть позже нам понадобятся другие грамматики рассматриваемого языка.

Грамматика G0 отличается от только что рассмотренной G2 порядком следования нетерминалов в правой части первых двух правил:

Важные свойства именно этой грамматики определяют ее обозначение. Именно грамматика G0 языка правильных арифметических формул будет использоваться в целом ряде последующих учебных курсов.

Еще один вариант грамматики (назовем ее G3 ) таков:

Фигурные скобки в этой записи означают повторение фрагмента, в них стоящего, нуль или более раз. Таким образом, первое правило этой грамматики означает, что метасимвол F может быть преобразован в T, Докажите самостоятельно, что все приведенные выше грамматики задают один и тот же язык правильных арифметических формул.

§3. Проект Компилятор формул 3. Рекурсивный компилятор формул. Как уже было отмечено в предыдущей секции, грамматика G1 не подходит для использования ее в качестве базовой при реализации компилятора формул из-за отсутствия в ней учета приоритета операций. Поэтому поставим перед собой задачу реализовать компилятор, т.е. программу, осуществляющую автоматический перевод с сохранением семантики, с языка L(G2 ) на язык L(GS ) программ стекового калькулятора.

Задача 3.1. Напишите программу (компилятор формул), которая для любой правильной арифметической формулы (элемента языка L(G 2 )), данной ей на вход, выдает семантически эквивалентную ей программу стекового калькулятора (элемент языка L(GS )).

Сначала даже не ясно, как подступиться к такой задаче. Однако ее разрешимость сомнения вызывать не должна существуют же компиляторы с огромного множества языков программирования, включая язык Java!

Ключом к решению задачи является использование грамматик, задающих входной и выходной языки. Существует вполне естественное соответствие между грамматиками G2 и GS : в них обеих имеются ровно по одному правилу, порождающему каждую из четырех арифметических операций и правило, порождающее имя переменной (переменная является одним из способов задания числа).

Для любой цепочки входного языка рассмотрим ее вывод в грамматике G2, а затем заменим правила входной грамматики, используемые на каждом шаге вывода, на соответствующие им правила выходной грамматики GS. В результате у нас получится цепочка выходного языка, которая будет иметь тот же самый смысл, что и входная цепочка.

Попробуем реализовать данную общую идею, применив рекурсию. Это определяет имя компилятора, который будет построен рекурсивный компилятор формул.

Будем трактовать поставленную задачу следующим образом: реализовать класс RecursCompf с методом compile, получающим в качестве аргумента исходную формулу (цепочку языка L(G2 )) в виде массива символов, который компилирует эту формулу и печатает получившийся результат (цепочку языка L(GS ). Метод main, предназначенный для тестирования получившейся программы реализуем в отдельном классе RecursCompfTest. Для ввода/вывода информации будем использовать методы класса Xterm, а весь исходный текст программы разместим в одном файле, который будет иметь имя RecursCompfTest.java.

После завершения работы над программой она должна вести себя примерно так:

226 Глава III. Применение ООП к разработке программных проектов [roganov@msiu compf]$ java RecursCompfTest Введите формулу -> a Введите формулу -> a-b abВведите формулу -> (a-b)*(a+b) ab-ab+* Приступим собственно к решению. Создадим отдельный метод для обработки каждого из четырех метасимволов грамматики G 2. Для компиляции формулы (метасимвола F ) будем использовать метод compileF, терма compileT, множителя compileM, а имени переменной метод compileV. Так как любая цепочка входного языка представляет из себя формулу, что соответствует метасимволу F грамматики G2, то ее компиляция, выполняемая методом compile, должна сводится к вызову метода compileF.

В соответствии с первым правилом грамматики G2 формула всегда начинается с терма. Таким образом, первое действие, которое должен выполнить метод compileF, это вызвать метод compileT. Опять таки в соответствии с грамматикой далее возможны три различных варианта:

либо формула на этом заканчивается (сводится просто к терму), либо за знаками сложения или вычитания (два варианта) следует еще одна формула.

Теперь уже в соответствии с грамматикой GS можно сделать вывод о том, как должна происходить работа метода compileF в каждом из этих трех случаях. В первом из них делать ничего не надо, а в двух остальных следует сначала обработать формулу, следующую за знаком операции, а затем напечатать символ, ей соответствующий (+ или -).

Обратите внимание, что при такой реализации метод compileF не пытается откомпилировать всю полученную методом compile формулу целиком им обрабатывается только некоторая ее часть, соответствующая одному метасимволу F в процессе ее вывода.

Для того чтобы можно было реализовать описанную идею, необходимо конкретизировать форму представления исходной формулы. Так как метод compile получает ее в виде массива символов str, вполне естественно сделать этот массив private-компонентой класса RecursCompf, доступной всем его методам и с помощью еще одной private-компоненты index отслеживать ту часть формулы, которая уже обработана. Обработка завершается, когда достигается конец формулы, длина которой равна str.length.

Этого вполне достаточно для реализации метода compileF:

private void compileF() { §3. Проект Компилятор формул if (index >= str.length) return;

if (str[index] == ’+’){ if (str[index] == ’-’){ Обработка терма совершенно аналогична обработке формулы это следует из грамматик G2 и GS, поэтому метод compileT пишется мгновенно:

private void compileT() { if (index >= str.length) return;

if (str[index] == ’*’){ if (str[index] == ’/’){ Множитель M в грамматике G2 является либо заключенной в скобки формулой, либо именем переменной. В первом случае необходимо пропустить открывающую скобку, затем вызвать метод compileF и пропустить закрывающую скобку, а во втором достаточно просто вызвать метод обработки имени переменной:

private void compileM() { if (str[index] == ’(’) { } else compileV();

228 Глава III. Применение ООП к разработке программных проектов Последний из оставшихся методов является самым простым обработка имени переменной сводится к печати этого имени (и перемещению указателя index):

private void compileV() { Xterm.print("" + str[index++] + " ");

Полный текст построенной программы приведен в последней секции параграфа, а мы сейчас попробуем ответить на стандартный для рекурсивных программ вопрос: почему эта программа заканчивает работу?

Потенциально опасными в данном случае являются методы compileF и compileT, которые являются рекурсивными. Перед каждым таким рекурсивным вызовом, однако, обработанная часть исходной формулы увеличивается (возрастает значение переменной index), что, в силу конечности длины исходной формулы, и гарантирует завершение работы программы в целом.

Сделаем одно небольшое чисто технологическое замечание. Хотя построенная нами реализация и является достаточно простой, программа в целом использует три различных файла (RecursCompfTest.java, RecursCompf.java и Xterm.java), размещенных в двух директориях (каталогах). Хорошим средством для автоматизации работы над сложными программными проектами является утилита make, которая позволяет значительно облегчить труд программиста в процессе написания и отладки большой программы (на любом языке).

В специальном управляющем файле, обычно именуемом Makefile, необходимо указать те конечные и промежуточные цели, которые должны быть достигнуты в процессе работы над проектом. В нашем случае такими целями являются запуск итоговой программы, ее компиляция и удаление class-файлов. Каждой цели в управляющем файле дается уникальное имя, после которого ставится двоеточие и перечисляются те файлы, от которых данная цель зависит, а в следующей строке после обязательного символа табуляции записывается действие, которое должно быть выполнено для достижения цели.

Когда утилита make запускается с указанием одной из перечисленных в управляющем файле целей в виде ее аргумента, то все необходимые действия для достижения цели выполняются автоматически. При этом выясняется, не изменились ли некоторые из файлов, от которых зависит цель.

Если это произошло, то все промежуточные цели, от них зависящие, также будут заново перестроены. При запуске make без указания аргумента в качестве цели берется первая из встречающихся в управляющем файле.

§3. Проект Компилятор формул Вот полный текст управляющего файла, который используется в рассматриваемом проекте:

Makefile.

# -*- mode: makefile -*PHONY : run clean # Запустить тест рекурсивного компилятора формул.

java RecursCompfTest # Откомпилировать текст рекурсивного компилятора формул.

RecursCompfTest.class: RecursCompfTest.java RecursCompf.java \ javac RecursCompfTest.java # Удалить лишние файлы.

clean:

rm -f *.class *.expand Кроме описания трех целей (run, RecursCompfTest.class и clean) в нем содержится информация для редактора emacs о специальном режиме работы с этим файлом и указание для утилиты make, сообщающее, что цели run и clean относятся к разряду особых они не является именами файлов, создаваемых при их построении. Символ \ в конце строки означает, что следующая строка файла должна рассматриваться, как продолжение предыдущей.

Команда make, которая в данном случае эквивалентна make run, сначала выяснит, нет ли уже построенной цели RecursCompfTest.class. Если она существует и времена модификации всех файлов, от которых зависит эта цель (RecursCompfTest.java, RecursCompf.java и Xterm.java) не превосходят времени создания цели RecursCompfTest.class, то будет просто выполнена команда запуска java RecursCompfTest. Если же хотя бы один из файлов с исходными текстами был модифицирован, то произойдет его перекомпиляция.

Утилита make, таким образом, позволяет не заботиться о перекомпиляции измененных исходных файлов, выполняя ее автоматически.

Следующее замечание касается поведения построенной нами программы при работе с некорректными формулами. При попытке откомпилировать с ее помощью подобную формулу поведение программы является непредсказуемым. Это, однако, вполне соответствует ее спецификации программа должна была компилировать только правильные формулы.

Глава III. Применение ООП к разработке программных проектов И еще одно замечание. При компиляции формулы a b c получается результат a b c - -, что явно не верно!. Правильным результатом является a b - c -. Значит написанная нами программа ошибочна?

На самом деле программа написана абсолютно правильно, а причина неверной компиляции заключается в грамматике G2. Дело в том, что эта грамматика, верно отражая приоритеты арифметических операций, неявно считает их все правоассоциативными, в то время как они являются на самом деле левоассоциативными. Это хорошо видно из рисунка 19, где изображено дерево вывода формулы a b c в грамматике G2.

Определенная выше грамматика G0, задавая тот же язык, предполагает правильную ассоциативность операций. К сожалению, использовать ее для написания рекурсивного компилятора формул нельзя. При обработке формулы совершенно не ясно, с чего она начинается с терма или с формулы. Кроме того, рекурсивная цепочка вызовов в данном случае вполне может оказаться бесконечной.

Одним из способов построения компилятора, который будет учитывать левоассоциативность всех арифметических операций, является использование грамматики G3. Основываясь на ней, можно построить другую реализацию рекурсивного компилятора формул, в которой метод compileF после вызова метода обработки терма будет содержать цикл, обеспечивающий обработку всех следующих за ним других термов этой формулы. Аналогичное изменение необходимо сделать и в методе compileT.

§3. Проект Компилятор формул Такая реализация компилятора будет уже корректно обрабатывать все правильные арифметические формулы. Ее основной недостаток невозможность простой модификации. Внесение даже небольших изменений во входной язык требует внесения глобальных изменений и переписывания значительной части программы. Примером подобного изменения может быть повышение приоритета вычитания так, что формула a b c должна будет трактоваться, как a (b c).

Для построения достаточно гибкой реализации компилятора формул целесообразно применить совсем иной подход.

4. Стековый компилятор формул. Напомним, что компилятор представляет собой программную реализацию отображения из множества цепочек одного языка в множество цепочек другого. По этой причине его можно рассматривать, как функцию на пространстве последовательностей. Легко понять, что в рассматриваемом случае перевода с языка правильных арифметических формул на язык программ для стекового калькулятора эта функция не индуктивна.

Для доказательства этого факта применим отрицание критерия индуктивности. Результатом компиляции цепочек w1 = a b и w2 = (a b) является одна и та же цепочка a b -. Если дописать к обеим этим цепочкам двухэлементную цепочку x = c (любая одноэлементная приводит к неправильной формуле), то результатом компиляции первой из них будет программа a b c * -, a второй a b - c *, т.е. (w1 x) = (w2 x).

Попробуем построить индуктивное расширение T функции так, чтобы с его помощью реализовать однопроходный алгоритм, осуществляющий нужный нам перевод. Прежде всего заметим, что любую правильную формулу можно откомпилировать так, что, во-первых, переменные в выходной цепочке (программе для стекового калькулятора) будут идти в том же порядке, что и переменные в исходной формуле; и, во-вторых, все операции в выходной цепочке будут расположены позже соответствующих им операций в исходной формуле.

Доказательство этого утверждения можно провести с помощью индукции по числу операций в исходной формуле. База индукции (случай полного отсутствия операций) проверяется непосредственно, а индуктивный переход осуществляется следующим рассуждением.

Пусть сформулированное выше утверждение справедливо для любой формулы, число операций в которой не превосходит n. Рассмотрим произвольную формулу с n + 1 операцией. Выделим ту из этих операций, которая должна выполняться последней в соответствии с действующими приоритетами и ассоциативностью. Данная операция разделяет два фрагмента исходной формулы, в каждом из которых содержится не более, чем 232 Глава III. Применение ООП к разработке программных проектов по n операций. По предположению индукции каждый из них может быть откомпилирован с соблюдением двух сформулированных выше условий.

Запишем последовательно результат компиляции каждого из них, а затем символ выделенной операции. Получившаяся цепочка, являющаяся переводом исходной формулы, удовлетворяет нужным требованиям, что и завершает доказательство.

Таким образом, формулу можно компилировать так: встретив имя переменной, немедленно его печатать, а встретив знак операции или скобку, печатать те из предыдущих, но еще не обработанных операций (будем их называть отложенными), которые выполнимы в данный момент, после чего откладывать и новый знак. Поскольку в любой момент времени среди отложенных операций нет таких, которые выполнимы до только что пришедшего знака, то в качестве контейнера для хранения отложенных операций можно использовать стек. Этот стек и будет содержать ту дополнительную информацию, которая необходима для индуктивного перевычисления функции T, осуществляющей компиляцию исходной формулы.

Требуемый нам класс Compf, содержащий метод compile, можно сделать выведенным из класса Stack, являющегося непрерывной реализацией стека символов на базе вектора. Как это было объяснено выше, метод compile должен обеспечивать последовательную обработку всех символов исходной формулы, что будет осуществляться с помощью private-метода processSymbol.

В момент появления в формуле правой скобки необходимо выполнить все отложенные, но еще не выполненные операции, содержащиеся в стеке.

То же самое нужно сделать и тогда, когда формула закончится. Для того, чтобы не различать эти две ситуации можно взять в скобки исходную формулу, что и реализовано в методе compile:

public void compile(char[] str) { processSymbol(’(’);

processSymbol(’)’);

Xterm.print("\n");

Все возможные входные символы делятся (с помощью метода symType) на четыре категории: две скобки (SYM_LEFT и SYM_RIGHT), знаки операций (SYM_OPER) и все остальные (SYM_OTHER). К последним относятся, прежде всего, имена переменных.

Реализация метода processSymbol полностью соответствует проведенному выше обсуждению компиляции с помощью стека:

§3. Проект Компилятор формул private void processSymbol(char c) { switch (symType(c)) { processSuspendedSymbols(c); pop(); break;

processSuspendedSymbols(c); push(c); break;

Открывающая скобка всегда заносится в стек отложенных операций; закрывающая скобка приводит к вызову метода processSuspendedSymbols, обрабатывающего отложенные символы, и удалению из стека парной ей открывающей скобки; символ операции вызывает обработку отложенных символов и сам затем помещается в стек; а имя переменной просто печатается с помощью методов nextOther и nextOper.

Метод processSuspendedSymbols обеспечивает обработку всех тех отложенных операций, которые выполнимы в данный момент, что определяется приоритетом операций (метод priority) и правилами предшествования (метод precedes):

private void processSuspendedSymbols(char c) { while (precedes(top(), c)) private int priority(char c) { private boolean precedes(char a, char b) { if(symType(a) == SYM_LEFT) return false;

if(symType(b) == SYM_RIGHT) return true;

return priority(a) >= priority(b);

protected void nextOper(char c) { Xterm.print("" + c + " ");

Текст проекта целиком приведен в последней секции параграфа. Обратите внимание, насколько эта реализация компилятора сложнее рекурсивной. Однако она позволяет легко модифицировать ее при изменении входного языка. Например, изменение ассоциативности всех арифметических 234 Глава III. Применение ООП к разработке программных проектов операций требует только удаления одного символа: в методе precedes нужно >= заменить на >. Многие значительно более сложные задачи на модификацию также сводятся к минимальным изменениям в тексте программы и не требует изменения структуры всей реализации в целом.

Так же, как и построенный ранее рекурсивный компилятор формул, стековый компилятор не делает никаких попыток сообщить о характере и месторасположении ошибки в некорректной формуле, данной ему на вход. Это отличает его от реально используемых компиляторов, в которых анализ ошибок во входной программе и выдача максимально полной информации о них является одной из важнейших задач. Причем зачастую эта задача ничуть не проще, нежели основная задача компилятора осуществление перевода на выходной язык.

Использование в тексте программы ключевого слова protected и некоторые другие не вполне понятные моменты объясняются тем, что построенный класс Compf будет использован в качестве базового для реализации интерпретатора арифметических выражений. Подобный подход является характерной особенностью объектно-ориентированного программирования уже написанный код может быть использован для решения родственной задачи без какой-либо его модификации.

5. Интерпретатор арифметических выражений. Если компилятор осуществляет перевод с одного языка на другой, то интерпретатор вычисляет значение арифметической формулы, в которой вместо имен переменных содержатся записанные тем или иным способом числа.

После применения компилятора (называемого также транслятором) полученная программа на выходном языке обычно выполняется с помощью специальной программы. Интерпретатор совмещает в себе обе эти стадии компиляцию и выполнение.

В случае программ на языках C и C++ компилятор позволяет получить файл, который содержит машинные команды и, следовательно, может быть выполнен непосредственно. Для языка Java компилятор строит так называемый байт-код, для исполнения которого необходима специальная программа (запускаемая с помощью команды java).

При однократном выполнении программы использование интерпретатора обычно предпочтительнее, а вот в случае необходимости многократного выполнения целесообразнее выполнить предварительно компиляцию, а затем нужное число раз осуществить быстрый запуск откомпилированной программы.

§3. Проект Компилятор формул Таблица 1. Запись чисел в римской системе счисления

I II III IV V

VI VII VIII IX X

XI XIII XVIII XIX XXII

XXXIV XXXIX XL LX XCIX

CC CDXXXVIII DCXLIX CMXCIX MCCVII

MMXLV MMMDLV MMMDCLXXVIII MMMCM MMMCMXCIX

В рассматриваемом нами случае языка правильных арифметических формул для реализации интерпретатора достаточно реализовать стековый калькулятор. Эту задачу мы сейчас и рассмотрим, предварительно обсудив запись чисел в различных системах счисления.

Выше уже отмечалось, что наряду с десятичной системой счисления в программировании часто используют двоичную, восьмеричную и шестнадцатеричную. В целом ряде языков программирования принято соглашение, согласно которому числа, запись которых начинается с нуля, считаются восьмеричными, а те, запись которых начинается с 0x или 0X, шестнадцатеричными. Таким образом, запись 0458 является некорректной (так как восьмеричная система счисления не содержит цифры 8), а в записи чисел, начинающихся с 0x или 0X, могут использоваться буквы от A до F, обозначающие шестнадцатеричные цифры со значениями от до 15.

Хорошо известным примером непозиционной системы счисления являются римская. В этой системе цифры I, V, X, L, C, D и M всегда обозначают 1, 5, 10, 50, 100, 500 и 1000 соответственно, вне зависимости от позиции цифры в записи числа. При записи чисел в римской системе счисления значением числа является алгебраическая сумма цифр, в него входящих. При этом цифры в записи числа следуют, как правило, в порядке убывания их значений, и не разрешается записывать рядом более трех одинаковых цифр. В том случае, когда за цифрой с бльшим знао чением следует цифра с меньшим, ее вклад в значение числа в целом 236 Глава III. Применение ООП к разработке программных проектов является отрицательным. Таблица 1 содержит типичные примеры, иллюстрирующие общие правила записи чисел в римской система счисления (не превосходящих 3999).

Перейдем теперь к построению интерпретатора, ограничившись случаем, когда в качестве чисел могут использоваться только однозначные положительные числа.

Задача 3.2. Напишите программу (интерпретатор формул), которая для любой правильной арифметической формулы (элемента языка L(G0 )), содержащей цифры от 0 до 9, вычисляет и печатает значение этой формулы.

Для того чтобы реализовать стековый калькулятор, конечно, необходим стек целых чисел. Его непрерывная реализация будет осуществляться классом StackInt. Класс Calc, который будет осуществлять интерпретацию арифметических формул, во многом похож на класс Compf. Одним из отличий является то, что в формуле присутствуют числа, а не идентификаторы переменных. Вторым и более существенным выполнение операций вместо их печати в виде программы для стекового компилятора.

Последнее означает, что обработка переменной должна быть заменена на помещение числа в стек калькулятора, а печать арифметической операции следует заменить на извлечение двух верхних элементов из стека и выполнение этой операции с последующей записью ее результата обратно в стек.

Из вышесказанного следует, что класс Calc целесообразно сделать дочерним по отношению к ранее нами созданному классы Compf, включив в него private-компоненту s (стек целых чисел) и переопределив методы symOther, nextOther и nextOper:

protected int symOther(char c) { Xterm.println("Недопустимый символ: " + c);

protected void nextOper(char c) { §3. Проект Компилятор формул protected void nextOther(char c) { s.push(char2int(c));

Метод char2int позволяет преобразовать символ в соответствующее ему целое число:

private static int char2int(char c) { return (int)c - (int)’0’;

Конструктор класса Calc должен создать стек целых чисел, а метод compile после вызова одноименного метода родительского класса обязан напечатать результат вычислений, находящийся на вершине стека.

Итоговый текст интерпретатора вместе с содержимом файлa Makefile, предусматривающим работу как с компилятором формул, так и с интерпретатором, приведены в последней секции параграфа.

6. Задачи для самостоятельного решения.

Задача 3.3. Докажите, что языки, порожденные двумя указанными грамматиками, совпадают:

a) G0 и G1 ;

b) G0 и G2 ;

c) G0 и G3.

Задача 3.4. Задайте с помощью грамматики следующие языки:

a) язык всех целых десятичных чисел;

b) язык всех целых неотрицательных восьмеричных чисел;

c) язык всех целых неотрицательных шестнадцатеричных чисел;

d) язык всех римских чисел от 1 до 3999;

e) язык всех допустимых идентификаторов в Java;

f) язык всех констант типа double в Java;

g) язык над алфавитом = {0, 1}, состоящий из всех цепочек, в которых четное количество нулей и нечетное количество единиц;

h) язык над алфавитом = {0, 1}, состоящий из всех цепочек, в которых количество нулей и единиц совпадают;

i) язык над алфавитом = {0, 1}, состоящий из всех цепочек, инвариантных относительно операции инвертирования;

238 Глава III. Применение ООП к разработке программных проектов j) язык над алфавитом = {0, 1}, состоящий из всех цепочек, начинающихся с нуля и заканчивающихся нулем, в которых и количество нулей и количество единиц нечетны.

Задача 3.5. Модифицируйте текст эталонного проекта Рекурсивный компилятор формул так, чтобы:

a) все арифметические операции трактовались, как левоассоциативные;

b) приоритеты операций сложения и вычитания были выше, чем у операций умножения и деления;

c) в качестве имен переменных допускались произвольные идентификаторы языка Java;

d) для группировки в формулах можно было использовать не только круглые, но также квадратные и фигурные скобки;

e) компилировались формулы, содержащие операцию % (остаток от деления) с приоритетом, равным приоритету операций умножения и деления;

в язык стекового компилятора при этом также добавляется операция %;

f) компилировались формулы, содержащие пробелы и комментарии двух видов: /* */ и //;

g) компилировались формулы, запись которых состоит из нескольких строк;

h) компилировались формулы, содержащие унарные арифметические операции + и -; в язык стекового компилятора при этом также добавляются операции + и -;

i) компилировались формулы, содержащие бинарные битовые операции | и &; в язык стекового компилятора при этом также добавляются операции | и &;

j) компилировались формулы, содержащие унарную битовую операцию ^;

в язык стекового компилятора при этом также добавляется операция ^.

Задача 3.6. Модифицируйте текст эталонного проекта Рекурсивный компилятор формул так, чтобы:

a) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

b) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа;

c) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

§3. Проект Компилятор формул d) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

e) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

f) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

g) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

h) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

i) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

j) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа.

Задача 3.7. Напишите программу (компилятор формул), которая для любой правильной арифметической формулы (элемента языка L(G 3 )), данной ей на вход, выдает семантически эквивалентную ей программу стекового калькулятора (элемент языка L(GS )).

Задача 3.8. Модифицируйте текст эталонного проекта Стековый компилятор формул так, чтобы:

a) деление трактовалось, как левоассоциативная операция;

b) приоритеты операций сложения и вычитания были выше, чем у операций умножения и деления;

c) в качестве имен переменных допускались произвольные идентификаторы языка Java;

d) для группировки в формулах можно было использовать не только круглые, но также квадратные и фигурные скобки;

e) компилировались формулы, содержащие операцию % (остаток от деления) с приоритетом, равным приоритету операций умножения и деления;

в язык стекового компилятора при этом также добавляется операция %;

f) компилировались формулы, содержащие пробелы и комментарии двух видов: /* */ и //;

g) компилировались формулы, запись которых состоит из нескольких 240 Глава III. Применение ООП к разработке программных проектов строк;

h) компилировались формулы, содержащие унарные арифметические операции + и -; в язык стекового компилятора при этом также добавляются операции + и -;

i) компилировались формулы, содержащие бинарные битовые операции | и &; в язык стекового компилятора при этом также добавляются операции | и &;

j) компилировались формулы, содержащие унарную битовую операцию ^;

в язык стекового компилятора при этом также добавляется операция ^.

Задача 3.9. Модифицируйте текст эталонного проекта Стековый компилятор формул так, чтобы:

a) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

b) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа;

c) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

d) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

e) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

f) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

g) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

h) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

i) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

§3. Проект Компилятор формул j) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа.

Задача 3.10. Модифицируйте текст эталонного проекта Стековый компилятор формул так, чтобы:

a) формулы, содержащие унарные операции sin и cos, правильно компилировались на язык стекового калькулятора, расширенный операциями S и C, которые вычисляют синус и косинус элемента, расположенного на вершине стека, размещая результат там же;

b) формулы, содержащие операцию возведения в степень ^, которая правоассоциативна и имеет максимальный приоритет, правильно компилировались на язык стекового калькулятора, расширенный операцией ^;

c) формулы, содержащие операцию возведения в степень **, которая правоассоциативна и имеет максимальный приоритет, правильно компилировались на язык стекового калькулятора, расширенный операцией ^;

d) для коммутативных операций аргументы в программе для стекового компилятора появлялись в алфавитном порядке;

e) формулы, содержащие квадратные скобки [], обозначающие удвоение выражения, в них стоящего, компилировались на язык стекового калькулятора, расширенный операцией D (duplicate), которая извлекает верхний элемент из стека и записывает его обратно в стек дважды;

f) формулы, содержащие фигурные скобки {}, обозначающие возведение в квадрат выражения, в них стоящего, компилировались на язык стекового калькулятора, расширенный операцией D (duplicate), которая извлекает верхний элемент из стека и записывает его обратно в стек дважды;

g) перед обработкой каждого символа формулы печаталась ее откомпилированную часть, содержимое стека отложенных операций и необработанную еще часть формулы;

h) формулы, содержащие переменную a, значение которой следует считать равным нулю, компилировались в оптимизированные формулы, не содержащие лишних сложений и вычитаний;

i) формулы, содержащие переменную b, значение которой следует считать равным единице, компилировались в оптимизированные формулы, не содержащие лишних умножений и делений;

j) при компиляции неправильных формул выдавалась диагностика об ошибке и корректная часть исходной формулы.

Задача 3.11. Модифицируйте текст эталонного проекта Стековый компилятор формул так, чтобы:

a) формулы, содержащие переменные a и b, значение которых следует считать равным двойке, компилировались в оптимизированные формулы, 242 Глава III. Применение ООП к разработке программных проектов в которых умножение заменено сложением;

b) результатом его работы была формула на входном языке, из которой удалены все лишние скобки;

c) результатом его работы была формула на входном языке, в которой каждое из выполняемых действий заключено в скобки;