2. Синтаксический анализ. Метод оперативного предшествования. Восходящие и нисходящие методы синтаксического анализа.

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

Во время синтаксического анализа предложения исходной программы распознаются как языковые конструкции, которые описываются используемой грамматикой. Существует 2 метода синтаксического разбора: нисходящие методы (сверху-вниз) и восходящие. Нисходящие методы. Начинаются с правила грамматики, определяющего цель разбора, с корня дерева грамматического разбора и наращивают его т.о., чтобы последующие узлы дерева соответствовали синтаксису анализируемого предложения. Восходящие методы (снизу-вверх) начинаются с конечных узлов дерева и поднимаются вверх до все более и более высокого уровня, пока не будет достигнут корень. Будем рассматривать восходящие методы и в частности метод операторного предшествования. Он основан на сравнении последовательно расположенных операторов исходной программы и принятии решения о том какой из них должен выполняться первым. Т.о. при рассмотрении с помощью метода операторного предшествования необходимо распознавать конструкцию до анализа соседних термом предложений. Т.о. при разборе процессора грамматического разбора, основанного на методе операторного предшествования должно быть установление отношений предшествования между операторами грамматик. При этом под оператором понимается любой терминальный символ (лексема), т.е. для программы необходимо установить все приоритеты. Таблица представляет собой матрицу приоритетов лексем. Для метода операторного предшествования необходимо однозначное задание отношений предшествования.

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

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

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

1. при инициализации формального параметра ф-и в случае передачи ей параметра по значению

2. вызывается при возврата объекта из ф-и по оператору return

При передаче ссылок и указателей конструктор копий не используется. Неявный конструктор-копий обеспечивает простое поэлементное копирование одного объекта в другой. Такой вид копирования называется поверхностным.

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

Деструктор класса предназначен для организации завершения работы с объектом. Его имя: ~Xclass (). Деструктор не может иметь параметров и не может быть перегружен. Если требуются выполнять различные действия при разрушении объектов, созданных при разных условиях, то необходимо использовать флаги, которые являются элементами данного класса и установлены конструктором индивидуально для каждого объекта.

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

Аргументы объектов списка инициализации могут быть сколь угодно сложными выражениями, содержащими параметры конструктора, объекта владельца, глобальные, статические переменные и простые константы. Класс Dclass содержит два объекта а и b классов Aclass и Bclass Инициализация этих объектов - список инициализации при описании конструкторов объекта Dclass.

Dclass::Dclass (double X, int i): b(x), a(i) {/*……….*/};

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

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

Создание объектов с различным временем жизни. Объекты - статические (глобальные), автоматические, динамические.

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

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

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

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

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

Point2D P1 [3]=(Point2D (2.4), Point2D (3,3), Point2D (4.5));

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

Если у класса имеется конструктор по умолчанию, то с помощью операции new[] можно создать массив в динамической области памяти Инициализация не допустима

Point2D *рArray ⁼ new Point2D [20];

Операция new[] гарантирует вызов конструктора для каждого элемента массива. В свою очередь операция delete обеспечивает вызов деструктора для каждого элемента массива при освобождении памяти.

Delete[] рАrray;

Использование операции delete без [] обеспечивает освобождение первого элемента массива. Операция delete не знает, что рАrrау указывает на массив объектов, а не на один объект.

Особенности копирования объектов. Копирование происходит в 4-х случаях:

1. присваивание;

2. поэлементное копирование при инициализации объектом того же типа;

3. при инициализации формального параметра ф-и фактическим, при передаче параметров по значению;

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

При возврате из функции по оператору return cоздается временный объект, который инициализируется значениями из оператора return с конструктора копий. В последней версии компилятора не создается временный объект, если в операторе return стоит конструктор и инициализирует этим конструктором возвращаемое значение ф-и.

Билет 22

1. МП-автомат определяется пятью параметрами:

1. Алфавит входных символов, в который включается концевой маркер ^

2. Алфавит магазинных символов, который включает в себя маркер дна магазина ☼

3. Алфавит состояний, включающий начальное состояние

4. Управляющее устройство, которое для каждой комбинации, состоящей из входного символа, магазинного символа и символа состояния ставит в соответствие операции – выход или переход. Выход – это конец распознавания, а переход – выполнение действий над магазином, состоянием и входом.

5. Начальное содержание магазина.

В МП-автомате запрещены операции, которые запрашивают входной символ после концевого маркера. Также запрещены операции, которые выталкивают маркер дна магазина. Во время операции переход возможны действия:

1. Вытолкнуть – верхний символ выталкивается из магазина

2. Втолкнуть (А) – в магазин вталкивается символ A

3. Состояние (S) – следующим текущим состоянием становится S

4. Сдвиг – осуществляется просмотр следующего текущего символа, входной цепочки

5. Держать – следующий текущий символ остается прежним

Если операция «Выход» имеет 2 состояния: допустить и отвергнуть, то такой автомат с магазинной памятью называется распознавателем.

Часто встречается автомат с одним состоянием, в этом случае оно не влияет на работу автомата и его можно опустить

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

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

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

Головка входной ленты может перемещаться только в одну сторону - вправо или

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

- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,

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

Магазинный автомат М определяется следующей совокупностью  семи объектов:            M={P , S , sо , f , F , H , hо }, где           P - входной алфавит,           S - алфавит состояний,           sо - начальное состояние,           sо О S ,           F - множество конечных состояний ,F является подмножеством S,           H - алфавит магазинных символов, записываемых на вспомогательную ленту,           hо- маркер дна, он всегда записывается на дно магазина , hо О   H,            f - функция переходов            f : {P И {e }} x S x H  ®  S x H* ,            если М-автомат - детерминированный, и             f:{P И {e }} x S x H  ®  M(S x H*) ,            если М-автомат - недетерминированный. Определение. Цепочка  a называется допустимой для автомата М, если существует последовательность конфигураций, в которой первая конфигурация является начальной c цепочкой a , а последняя - заключительной. (sо, a, hо) |--* (s1, $ , $) , где s1 О F .

Определение.Множество цепочек, допускаемых автоматом М, называется языком, допускаемым или определяемым автоматом М, и обозначается L(М).