В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 3
Текст из файла (страница 3)
Реализация множеств и отображений в Java111.3. Реализация множеств и отображений в JavaВ качестве программных приложений к книге на сайте тряп.рф приведеныпрограммы на языке Java, реализующие изложенные алгоритмы. Во многом реализация этих алгоритмов основана на пакете Java.util, в которомопределен ряд интерфейсов и классов, позволяющих определять множестваи отображения. Основу этой структуры составляет интерфейс Collection,который определяет набор методов по работе с конечными наборами данных.Рассмотрим кратко те из них, которые используются в приложениях к этойкниге.
В нем определены следующие методы.boolean add(Object obj) — добавляет obj к вызывающей коллекции. Возвращает true, если obj был добавлен к коллекции, и f alse, если obj ужеявляется элементом коллекции или если коллекция не допускает дубликатов.boolean addAll(Collection c) — добавляет все элементы коллекции c к вызывающей коллекции. Возвращает true, если все элементы были добавленык коллекции, и f alse в противном случае.boolean contains(Object obj) — возвращает true, если вызывающая коллекция содержит элемент obj , и f alse в противном случае.boolean isEmpty() — возвращает true, если вызывающая коллекция пуста,и f alse в противном случае.Iterator iterator() — Возвращает итератор для вызывающей коллекции(подробнее об итераторах сказано ниже).int size() — возвращает число элементов, содержащихся в вызывающейколлекции.Интерфейс List расширяет Collection, позволяя хранить последовательности (списки) элементов.
Элементы могут быть внесены или извлечены в соответствии с их позицией, отсчитываемой от нуля. Список может содержатьдублированные элементы. Интерфейс List добавляет следующие методы:void add(int index, Object obj) — вставляет obj в вызывающий списокв позицию с индексом index. Элементы списка, начиная с позиции index,сдвигаются (т. е. их позиции увеличиваются на 1).Object get(int index) — возвращает объект, хранящийся в позиции indexвызывающей коллекции.Интерфейс Set расширяет интерфейс Collection, не допуская дублирорвания элементов, что сказывается на поведении методов add и addAll.Собственных методов интерфейс Set не добавляет.Перечисленные интерфейсы реализуются следующими классами:Класс AbstractCollection — реализует бо́льшую часть интерфейсаCollection.Класс AbstractList — расширяет AbstractCollection и реализует бо́льшуючасть интерфейса List.12Глава 1. ВведениеКласс AbstractSequentialList — расширяет класс AbstractList для реализации последовательного, а не произвольного доступа к элементам.Класс LinkedList — реализует связный список, расширяя классAbstractSequentialList.
В классе LinkedList определены, в частности,следующие методы:void addF irst(Object obj) — добавить элемент в начало списка;void addLast(Object obj) — добавить элемент в конец списка;Object removeF irst() — удалить первый элемент списка;Object removeLast() — удалить последний элемент списка;Object getF irst() — получить первый элемент списка;Object getLast() — получить последний элемент списка;Класс ArrayList — реализует динамический (расширяющийся) массив,расширяя класс AbstractList. Для добавления элемента в позицию indexиспользуется метод void add(int index, Object obj).
Удалить элемент можнолибо указав ссылку на него, либо указав его позицию:Object remove(Object obj);Object remove(int index).Класс AbstractSet — расширяет класс AbstractCollection и реализуетбо́льшую часть интерфейса Set.Класс HashSet — расширяет класс AbstractSet для реализации множества в виде хэш-таблицы, T reeSet расширяет класс AbstractSet для реализации множества в виде дерева.Для перебора элементов коллекции используются итераторы, определенные в интерфейсе Iterator. В этом интерфейсе объявлены следующие методы.boolean hasN ext() — возвращает true, если в коллекции имеется следующий элемент, иначе возвращает f alse.Object next() — возвращает следующий элемент. Выбрасывает исключение N oSuchElementException, если следующего элемента нет.void remove() — удаляет текущий элемент.
Выбрасывает исключениеEllegalStateException, если сделана попытка вызвать метод remove(), которому не предшествует метод next().Для реализаций (конечных) отображений используется интерфейс M ap.В этом интерфейсе определены методы, позволяющие поместить в коллекциюпару (ключ, значение) и извлечь значение по ключу:Object put(Object k, Object v) — помещает в вызывающую коллекцию(отображение) объект v , доступный по ключу k . При этом, если с ключом kуже было связано некоторое значение, оно возвращается методом put, иначевозвращается null.Object get(Object obj) — возвращает значение, связанное с ключом k .boolean containsKey(Obect k) — возвращает true, если вызывающая коллекция содержит объект с ключом k .1.3.
Реализация множеств и отображений в Java13Set keySet() — возвращает Set-объект, состоящий из ключей вызывающейколлекции.Set entrySet() — возвращает Set-объект, который содержит элементыотображения, т. е. пары (ключ, значение), имеющие тип M ap.Entry . В интерфейсе M ap.Entry определены следующие методы.Object getKey() — возвращает ключ текущего входа вызывающей коллекции (типа M ap.Entry ).Object getV alue() — возвращает значение текущего входа вызывающейколлекции.Отметим, что сами коллекции являются наследниками класса Object,поэтому могут помещаться как элементы коллекций. При этом надо иметьв виду, что в каждом конкретном контексте использования элемента коллекции транслятору нужно указать тип, которому принадлежит используемыйэлемент коллекции.
Это делается с помощью явного приведения типа. Схемаиспользования выглядит следующим образом:MyClass element;String key;HashMap collection = new HashMap();collection.put(key, element);...HashSet collectionMap = new HashSet(collection.entrySet());Iteratot iter = collectionMap.iterator();while (iter.hasNext()){Map.Entry me = (Map.Entry)iter.next();String nextKey = (String) me.getKey();MyClass nextElement = (MyClass) me.getValue();}Глава 2ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ2.1. Алфавиты, цепочки и языкиАлфавит, или словарь — это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквамии специальными литерами типа: #, $.Пусть V — алфавит.
Цепочка в алфавите V — это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочкиявляются предложение, строка и слово. Пустая цепочка (обозначается e) —это цепочка, в которую не входит ни один символ.Конкатенацией цепочек x и y называется цепочка xy . Заметим, что xe == ex = x для любой цепочки x.Пусть x, y , z — произвольные цепочки в некотором алфавите. Цепочкаy называется подцепочкой цепочки xyz . Цепочки x и y называются соответственно префиксом и суффиксом цепочки xy . Заметим, что любой префиксили суффикс цепочки является подцепочкой этой цепочки.
Кроме того, пустаяцепочка является префиксом, суффиксом и подцепочкой для любой цепочки.Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества L1 = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка из множества L2 = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L1 ∪ L2 .Длиной цепочки w (обозначается |w|) называется число символов в ней.Например, |abababa| = 7, а |e| = 0.Язык в алфавите V — это некоторое множество цепочек в алфавите V .Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V :а) L1 = ∅ – пустой язык;б) L2 = {e} — язык, содержащий только пустую цепочку (заметим, что L1 и L2 —различные языки);в) L3 = {e, a, b, aa, ab, ba, bb} — язык, содержащий цепочки из a и b, длинакоторых не превосходит 2;г) L4 — язык, включающий всевозможные цепочки из a и b, содержащие четноечисло a и четное число b;2.1.
Алфавиты, цепочки и языки152д) L5 = {an |n > 0} — язык цепочек из a, длины которых представляют собойквадраты натуральных чисел.Два последних языка содержат бесконечное число цепочек.Введем обозначение V ∗ для множества всех цепочек в алфавите V , включая пустую цепочку. Каждый язык в алфавите V является подмножеством V ∗ .Для множества всех цепочек в алфавите V , кроме пустой цепочки, будемиспользовать обозначение V + .V+Пример 2.3. Пусть V = {0, 1}. Тогда V ∗ = {e, 0, 1, 00, 01, 10, 11, 000,. .
.},= {0, 1, 00, 01, 10, 11, 000, . . .}.Введем некоторые операции над языками.Пусть L1 и L2 — языки в алфавите V . Конкатенацией языков L1 и L2называется язык L1 L2 = {xy|x ∈ L1 , y ∈ L2 }.Пусть L — язык в алфавите V . Итерацией языка L называется язык L∗ ,определяемый следующим образом.1. L0 = {e}.2. Ln = LLn−1 , n > 1.∞S3. L∗ =Ln .n=0Пример 2.4. Пусть L1 = {aa, bb}, L2 = {e, a, bb}. ТогдаL1 L2 = {aa, bb, aaa, bba, aabb, bbbb},L∗1 = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, . .
.}.Большинство языков, представляющих интерес, содержат бесконечноечисло цепочек. При этом возникают три важных вопроса.Во-первых, как представить язык (т. е. специфицировать входящие в негоцепочки)? Если язык содержит только конечное множество цепочек, то ответпрост: можно просто перечислить его цепочки. Если язык бесконечен, то длянего необходимо найти конечное представление.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
