В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 3
Текст из файла (страница 3)
При этом могут учитываться такие свойства программы,как межпроцедурный анализ, межмодульный анализ, анализ областей жизнипеременных и т. п.Наконец, генерация кода — последняя фаза трансляции. Ее результатомявляется либо ассемблерный модуль, либо объектный (или загрузочный)модуль. В процессе генерации кода могут выполняться некоторые локальныеоптимизации, такие, как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие,как таблицы решений, сопоставление образцов, включающее динамическоепрограммирование, различные синтаксические методы.Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного трансляторанет явной фазы генерации промежуточного представления и оптимизации,остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.1.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}
