Построение алгоритмов методом пошаговой детализации

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

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

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

Причем на протяжении всего процесса логика выражается основными конструкциями структурного программирования.

В методе пошаговой детализации можно выделить следующие существенные этапы [3].

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

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

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

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

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

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

18. Построение и использование деревьев в динамической памяти.

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

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

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

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

Пусть книга состоит из частей, части — из глав, главы — из параграфов. Сама книга представляется корнем дерева, из которого выходят ребра к вершинам, соответствующим частям книги. В свою очередь, из каждой вершины-части книги выходят ребра к вершинам-главам, входящим в эту часть, и так далее. Файловую систему компьютера также можно представить в виде дерева. Вершинам соответствуют каталоги (их также называют директориями или папками) и файлы. Из вершины-каталога выходят ребра к вершинам, соответствующим всем каталогам и файлам, которые содержатся в данном каталоге. Файлы представляются терминальными вершинами дерева. Корню дерева соответствует корневой каталог диска. Программы, осуществляющие работу с файлами, такие, как Norton Commander в системе MS DOS или Проводник Windows, могут изображать файловую систему графически в виде дерева.

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

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

19. Построение и использование списков в динамической памяти.

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

GetMem(Size: Integer; out P: Pointer); - выделение памяти;

FreeMem(P: Pointer); - освобождение памяти

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

Общая структура звеньев может выглядит так:

Однонаправленный список:

Pchain = ^Tchain;

Tchain = record

Element: Telement;

Next: Pchain; End;

Двухнаправленный список:

Pchain = ^Tchain;

Tchain = record

Element: Telement;

Next: Pchain;

Prev: Pchain; End;

Здесь Pchain – указатель (ссылочный тип) на звено цепочки, а поле элемент является объектом, цепочка которых организуется. Для доступа к элементам цепочки необходимо иметь хотя бы указатель на первый элемент или на последний.

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

При этом цепочка, изображенная на первом рисунке с указателем на первый элемент называется стеком (LIFO – last input first output) – так как такая организация, реализует алгоритм, когда последний размещенный элемент, извелекается первым. Если использовать еще указатель на последний элемент, то можно организовать очередь, FIFO – first input first output, когда первый размещенный элемент будет первым извлечен. Алгоритм и организация полностью зависят от желаний программиста.

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

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

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

При этом пользователю необходимо следить за корректным значением всех указателей в цепочке, вовремя их обнулять. Однако алгоритм остается похожим на приведенный выше. Т.е. при добавлении создается новый элемент, его поля Next и Prev получают указатели на элементы в разрыв, которых идет вставка (возможно вставка в пустой список или в начало (конец) – в этом случае они нулевые).А эти элементы в свою очерель меняют свои указатели (следующий для прудыдущего и предыдущий для следующего) на вставляемый. Также корректируются указатели на первый, последний и текущий элементы.

При удалении – сам элемент удаляется (память его освобождается). Однако перед этим, его “соседи” связываются в цепочку между собой.

20. Проблемы взаимодействия процессов и общая схема решения задачи синхронизации.

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

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

Пролог Эпилог

Проблема отстранения процесса.

Проблема отстранения процесса связана с расслоением критической секции. Может возникнуть ситуация, в которой процессы окажутся взаимоблокированны (см. рис.). Пусть процесс p запросил некоторый критический ресурс №1 и вошёл в критическую секцию; процесс q тоже запросил критический ресурс №2 и вошёл в критическую секцию. Процесс p захотел ресурс №2 не освободив первый, а процесс q наоборот. Ресурс №1 будет всё время занят и процесс p будет ожидать ресурс №2, который тоже занят.

Если процессы независимы и никак друг с другом не взаимодействуют и контексты их не пересекаются, то никакая синхронизация не нужна. Задача синхронизации возникает когда процесс является независимым, тогда возникает задача синхронизации их времени трасс в связи с иными причинами, чем выделение физическому процессору. Конкуренция – в системе имеются критические ресурсы, т.е. которые нужны разным процессам, и которых не хватает на всех (пример вызов ДОС).

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

Общая постановка задачи синхронизации.

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

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

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

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

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

21. Программирование конечного автомата.

Определение конечного автомата

Конечным автоматом (КА) называют пятерку следующего вида:

M(Q, V, δ, qo, F),

где

Q — конечное множество состояний автомата;

V — конечное множество допустимых входных символов (алфавит автомата);

δ — функция переходов, отображающая V*Q (декартово произведение множеств) во множество подмножеств Q: R(Q), то есть ;

q0 — начальное состояние автомата Q, ;

F — непустое множество конечных состояний автомата, .

КА называют полностью определенным, если в каждом его состоянии существует функция перехода для всех возможных входных символов, то есть: .

Работа конечного автомата представляет собой последовательность шагов (или тактов). На каждом шаге работы автомат находится в одном из своих состояний Q (в текущем состоянии), на следующем шаге он может перейти в другое состоя­ние или остаться в текущем состоянии. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов δ. Она зависит не только от текущего состояния, но и от символа из алфавита V, поданного на вход автомата. Когда функция перехода допускает несколько следующих состояний автомата, то КА может перейти в любое из этих состояний. В начале работы ав­томат всегда находится в начальном состоянии q0. Работа КА продолжается до тех пор, пока на его вход поступают символы из входной цепочки .

Видно, что конфигурацию КА на каждом шаге работы можно определить в виде (q,ω,n), где q — текущее состояние автомата, ; ω — цепочка входных симво­лов, ; n — положение указателя в цепочке символов, (N — множество натуральных чисел). Конфигурация автомата на следующем шаге — это (q', ω, n+1), если и символ находится в позиции n + 1 цепочки ω. Начальная конфигурация автомата: (q0,ω,0); заключительная конфигурация ав­томата: (f, ω, n), , она является конечной конфигурацией, если .

Язык, заданный конечным автоматом

Конечный автомат M(Q, V, δ, qo, F) принимает цепочку символов , если, получив на вход эту Цепочку, он из начального состояния q0 может перейти в одно из конечных со­стояний . В противном случае КА не принимает цепочку символов.

Язык L(M), заданный KA M(Q,V,δ,qo,F), - это множество всех цепочек симво­лов, которые принимаются этим автоматом. Два КА эквивалентны, если они за­дают один и тот же язык. Все КА являются распознавателями для регулярных языков.

Граф переходов недетерминированного конечного автомата

Граф переходов полностью определенного недетерминированного конечного автомата

Определение детерминированного конечного автомата

Конечный автомат M(Q, V, δ, qo, F) называют детерминированным конечным автоматом (ДКА), если в каждом из его состояний для любого входного символа функция перехода содержит не более одного состояния : либо , либо .

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

Из этого определения видно, что автоматы, представленные ранее на рисунках являются недетерминированными КА.

ДКА может быть задан в виде пятерки:

M(Q, V, δ, qo, F),

где

Q — конечное множество состояний автомата;

V — конечное множество допустимых входных символов;

δ — функция переходов, отображающая V*Q в множество Q: ;

q0 — начальное состояние автомата Q, ;

F — непустое множество конечных состояний автомата, .

Если функция переходов ДКА определена для каждого состояния автомата, то авто­мат называется полностью определенным ДКА: : либо .

Доказано, что для любого КА можно построить эквивалентный ему ДКА. Моде­лировать работу ДКА существенно проще, чем работу произвольного КА, поэто­му произвольный КА стремятся преобразовать в ДКА. При построении компи­ляторов чаще всего используют полностью определенный ДКА.

22. Разработка в стиле экстремального программирования.

Экстремальное программирование (eXtreme Programming, XP) - облегченный (подвижный) процесс (или методология), главный автор которого - Кент Бек (1999). ХР-процесс ориентирован на группы малого и среднего размера, стро­ящие программное обеспечение в условиях неопределенных или быстро изменяю­щихся требований. ХР-группу образуют до 10 сотрудников, которые размещаются в одном помещении.

Основная идея ХР — устранить высокую стоимость изменения, характерную для приложений с использованием объектов, паттернов и реляционных баз данных. Поэтому ХР-процесс должен быть высокодинамичным процессом. ХР-группа име­ет дело с изменениями требований на всем протяжении итерационного цикла раз­работки, причем цикл состоит из очень коротких итераций. Четырьмя базовыми действиями в ХР-цикле являются: кодирование, тестирование, выслушивание за­казчика и проектирование. Динамизм обеспечивается с помощью четырех харак­теристик: непрерывной связи с заказчиком (и в пределах группы), простоты (все­гда выбирается минимальное решение), быстрой обратной связи (с помощью модульного и функционального тестирования), смелости в проведении профилак­тики возможных проблем.

Большинство принципов, поддерживаемых в ХР (минимальность, простота, эво­люционный цикл разработки, малая длительность итерации, участие пользовате­ля, оптимальные стандарты кодирования и т. д.), продиктованы здравым смыслом и применяются в любом упорядоченном процессе. Просто в ХР эти принципы, как показано в таблице, достигают «экстремальных значений».

Практика здравого смысла	ХР-экстремум	ХР-реализация
Проверки кода	Код проверяется все время	Парное программирование
Тестирование	Тестирование выполняется все время, даже с помощью заказчиков	Тестирование модуля, функциональное тестирование
Проектирование	Проектирование является частью ежедневной деятельности каждого разработчика	Реорганизация (refactoring)
Простота	Для системы выбирается простейшее проектное решение, поддерживающее ее текущую функциональность	Самая простая вещь, которая могла бы работать
Архитектура	Каждый постоянно работает над уточнением архитектуры	Метафора
Тестирование интеграции	Интегрируется и тестируется несколько раз в день	Непрерывная интеграция Игра планирования
Короткие итерации	Итерации являются предельно короткими, продолжаются секунды, минуты, часы, а не недели, месяцы или годы	Парное программирование

Тот, кто принимает принцип «минимального решения» за хакерство, ошибается, в действительности ХР — строго упорядоченный процесс. Простые решения, име­ющие высший приоритет, в настоящее время рассматриваются как наиболее цен­ные части системы, в отличие от проектных решений, которые пока не нужны, а могут (в условиях изменения требований и операционной среды) и вообще не понадобиться. Базис ХР образуют перечисленные ниже двенадцать методов.

1. Игра планирования (Planning game) — быстрое определение области действия следующей реализации путем объединения деловых приоритетов и техниче­ских оценок. Заказчик формирует область действия, приоритетность и сроки с точки зрения бизнеса, а разработчики оценивают и прослеживают продви­жение (прогресс).

2. Частая смена версий (Small releases) — быстрый запуск в производство про­стой системы. Новые версии реализуются в очень коротком (двухнедельном) цикле.

3. Метафора (Metaphor) — вся разработка проводится на основе простой, обще­ доступной истории о том, как работает вся система.

4. Простое проектирование (Simple design) — проектирование выполняется на­ столько просто, насколько это возможно в данный момент.

5. Тестирование (Testing) — непрерывное написание тестов для модулей, кото­рые должны выполняться безупречно; заказчики пишут тесты для демонстра­ции законченности функций. «Тестируй, а затем кодируй» означает, что вход­ным критерием для написания кода является «отказавший» тестовый вариант.

6. Реорганизация (Refactoring) — система реструктурируется, но ее поведение не изменяется; цель — устранить дублирование, улучшить взаимодействие, упростить систему или добавить в нее гибкость.

7. Парное программирование (Pair programming) — весь код пишется двумя про­граммистами, работающими на одном компьютере.

8. Коллективное владение кодом (Collective ownership) — любой разработчик может улучшать любой код системы в любое время.

9. Непрерывная интеграция (Continuous integration) — система интегрируется и строится много раз в день, по мере завершения каждой задачи. Непрерывное регрессионное тестирование, то есть повторение предыдущих тестов, гаранти­рует, что изменения требований не приведут к регрессу функциональности.

10. 40-часовая неделя (40-hour week) — как правило, работают не более 40 часов в неделю. Нельзя удваивать рабочую неделю за счет сверхурочных работ.

11. Локальный заказчик (On-site customer) — в группе все время должен нахо­диться представитель заказчика, действительно готовый отвечать на вопросы разработчиков.

12. Стандарты кодирования (Coding standards) — должны выдерживаться прави­ла, обеспечивающие одинаковое представление программного кода во всех ча­стях программной системы.

Игра планирования и частая смена версий зависят от заказчика, обеспечивающего набор «историй» (коротких описаний), характеризующих работу, которая будет выполняться для каждой версии системы. Версии генерируются каждые две неде­ли, поэтому разработчики и заказчик должны прийти к соглашению о том, какие истории будут осуществлены в пределах двух недель. Полную функциональность, требуемую заказчику, характеризует пул историй; но для следующей двухнедель­ной итерации из пула выбирается подмножество историй, наиболее важное для заказчика. В любое время в пул могут быть добавлены новые истории, таким обра­зом, требования могут быстро изменяться. Однако процессы двухнедельной гене­рации основаны на наиболее важных функциях, входящих в текущий пул, следо­вательно, изменчивость управляется. Локальный заказчик обеспечивает поддержку этого стиля итерационной разработки.

«Метафора» обеспечивает глобальное «видение» проекта. Она могла бы рас­сматриваться как высокоуровневая архитектура, но ХР подчеркивает желатель­ность проектирования при минимизации проектной документации. Точнее гово­ря, ХР предлагает непрерывное перепроектирование (с помощью реорганизации), при котором нет нужды в детализированной проектной документации, а для инженеров сопровождения единственным надежным источником информации является программный код. Обычно после написания кода проектная доку­ментация выбрасывается. Проектная документация сохраняется только в том случае, когда заказчик временно теряет способность придумывать новые исто­рии. Тогда систему помещают в «нафталин» и пишут руководство страниц на пять-десять по «нафталиновому» варианту системы. Использование реоргани­зации приводит к реализации простейшего решения, удовлетворяющего теку­щую потребность. Изменения в требованиях заставляют отказываться от всех «общих решений».

Парное программирование — один из наиболее спорных методов в ХР, оно влияет на ресурсы, что важно для менеджеров, решающих, будет ли проект использовать ХР. Может показаться, что парное программирование удваивает ресурсы, но ис­следования доказали: парное программирование приводит к повышению качества и уменьшению времени цикла. Для согласованной группы затраты увеличивают­ся на 15%, а время цикла сокращается на 40-50%. Для Интернет-среды увеличение скорости продаж покрывает повышение затрат. Сотрудничество улучшает процесс решения проблем, улучшение качества существенно снижает затраты сопровож­дения, которые превышают стоимость дополнительных ресурсов по всему циклу разработки.

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

«Тестируй, а затем кодируй» — эта фраза выражает акцент ХР на тестировании. Она отражает принцип, по которому сначала планируется тестирование, а тестовые варианты разрабатываются параллельно анализу требований, хотя традиционный подход состоит в тестировании «черного ящика». Размышление о тестировании в начале цикла жизни - хорошо известная практика конструирования ПО (правда, редко осуществляемая практически).

Основным средством управления ХР является метрика, а среда метрик — «боль­шая визуальная диаграмма». Обычно используют 3-4 метрики, причем такие, ко­торые видимы всей группе. Рекомендуемой в ХР метрикой является «скорость проекта» — количество историй заданного размера, которые могут быть реализо­ваны в итерации.

При принятии ХР рекомендуется осваивать его методы по одному, каждый раз выбирая метод, ориентированный на самую трудную проблему группы. Конечно, все эти методы являются «не более чем правилами» — группа может в любой мо­мент поменять их (если ее сотрудники достигли принципиального соглашения по поводу внесенных изменений). Защитники ХР признают, что ХР оказывает силь­ное социальное воздействие, и не каждый может принять его. Вместе с тем, ХР — это методология, обеспечивающая преимущества только при использовании за­конченного набора базовых методов.

Рассмотрим структуру «идеального» ХР-процесса. Основным структурным эле­ментом процесса является ХР-реализация, в которую многократно вкладыва­ется базовый элемент — ХР-итерация. В состав ХР-реализации и ХР-итерации входят три фазы — исследование, блокировка, регулирование. Исследование (exploration) — это поиск новых требований (историй, задач), которые должна выполнять система. Блокировка (commitment) — выбор для реализации конкрет­ного подмножества из всех возможных требований (иными словами, планиро­вание). Регулирование (steering) — проведение разработки, воплощение плана в жизнь.

ХР рекомендует: первая реализация должна иметь длительность 2-6 месяцев, про­должительность остальных реализаций — около двух месяцев, каждая итерация длится приблизительно две недели, а численность группы разработчиков не пре­вышает 10 человек. ХР-процесс для проекта с семью реализациями, осуществляе­мый за 15 месяцев, показан на рисунке. Процесс инициируется начальной исследовательской фазой. Фаза исследования, с которой начинается любая реализация и итерация, имеет клапан «пропуска», на этой фазе принимается решение о целесообразности даль­нейшего продолжения работы.

Предполагается, что длительность первой реализации составляет 3 месяца, дли­тельность второй — седьмой реализаций — 2 месяца. Вторая — седьмая реализа­ции образуют период сопровождения, характеризующий природу ХР-проекта. Каждая итерация длится две недели, за исключением тех, которые относят к по­здней стадии реализации — «запуску в производство» (в это время темп итерации

ускоряется).

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

Идеальный XP-процесс

23. Регулярные множества, языки и выражения.

Определение регулярного множества

Определим над множествами цепочек символов из алфавита V операции конка­тенации и итерации следующим образом:

PQ - конкатенация и : ;

P* - итерация : .

Тогда для алфавита V регулярные множества определяются рекурсивно:

1. — регулярное множество;
2. {λ} — регулярное множество;
3. {а} — регулярное множество ;
4. если Р и Q — произвольные регулярные множества, то множества также являются регулярными множествами;
5. ничто другое не является регулярным множеством.

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

Регулярные выражения. Свойства регулярных выражений

Регулярные множества можно обозначать с помощью регулярных выражений. Эти обозначения вводятся следующим образом:

1. 0 — регулярное выражение, обозначающее ;
2. λ — регулярное выражение, обозначающее {λ};
3. а — регулярное выражение, обозначающее {a} ;
4. если р и q - регулярные выражения, обозначающие регулярные множества Р и Q, то р + q, pq, p* - регулярные выражения, обозначающие регулярные мно­жества соответственно.

Два регулярных выражения αиβ равны α= β, если они обозначают одно и то же множество.

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

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

Если α, β и γ — регулярные выражения, то свойства регулярных выражений можно записать в виде следующих формул:

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. .

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

Следует также обратить внимание на то, что среди прочих свойств отсутствует равенство , то есть операция конкатенации не обладает свойством ком­мутативности. Это и не удивительно, поскольку для этой операции важен поря­док следования символов.

Свойства регулярных языков

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

• пересечения;
• объединения;
• дополнения;
• итерации;
• конкатенации;
• гомоморфизма (изменения имен символов и подстановки цепочек вместо символов).

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

Проблемы, разрешимые для регулярных языков

Регулярные языки представляют собой очень удобный тип языков. Для них раз­решимы многие проблемы, неразрешимые для других типов языков. Например, доказано, что разрешимыми являются следующие проблемы:

• Проблема эквивалентности. Даны два регулярных языка L1(V) и L2(V). Необходимо проверить, являются ли эти два языка эквивалентными.
• Проблема принадлежности цепочки языку. Дан регулярный язык L(V) и це­почка символов . Необходимо проверить, принадлежит ли цепочка дан­ному языку.
• Проблема пустоты языка. Дан регулярный язык L(V). Необходимо прове­рить, является ли этот язык пустым, то есть найти хотя бы одну цепочку , такую что .

Эти проблемы разрешимы вне зависимости от того, каким из трех способов за­дан регулярный язык. Следовательно, эти проблемы разрешимы для всех спосо­бов представления регулярных языков: регулярных множеств, регулярных грамматик и конечных автоматов. На самом деле достаточно доказать разрешимость любой из этих проблем хотя бы для одного из способов представления языка, то­гда для остальных способов можно воспользоваться алгоритмами преобразова­ния, рассмотренными выше.

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

Три способа задания регулярных языков

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

24. Связь прикладного процесса с ядром ОС.

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

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

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

Рис. 7.1. Два режима выполнения операций ввода-вывода

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

25. Синтаксический анализ методом рекурсивного спуска.

Распознаватели с возвратом - это самый примитивный тип распознавателей для КС-языков. Логика их работы основана на моделировании недетерминированного МП-автомата.

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

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

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

Второй вариант реализации алгоритма связан с управлением параллельными процессами в вычислительных системах, поэтому сложен в реализации. Кроме того, на каждом шаге работы МП-автомата альтернатив следующих состоя­ний может быть много, а количество возможных параллельно выполняющихся процессов в операционных системах ограничено, поэтому применение второго варианта алгоритма осложнено. По этим причинам большее распространение полу­чил первый вариант алгоритма, который предусматривает возврат к ранее запом­ненным состояниям МП-автомата, — отсюда и название «разбор с возвратами». Следует отметить, что, хотя МП-автомат является односторонним распознавате­лем, алгоритм моделирования его работы предусматривает возврат назад, к уже прочитанной части цепочки символов, чтобы исключить недетерминизм в пове­дении автомата (который невозможно промоделировать).

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

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

Принцип работы нисходящего распознавателя с подбором альтернатив

Нисходящий распознаватель с подбором альтернатив моделирует работу МП-автомата с одним состоянием q:R({q},V,Z,δ,q,S,{q}). Автомат распознает цепочки КС-языка, заданного КС-грамматикой G(VT,VN,P,S). Входной алфавит авто­мата содержит терминальные символы грамматики: V = VT, а алфавит магазин­ных символов строится из терминальных и нетерминальных символов грамма­тики: Z = VT VN.

Начальная конфигурация автомата определяется так: (q,α,S) — автомат пребы­вает в своем единственном состоянии q, считывающая головка находится в нача­ле входной цепочки символов , в стеке лежит символ, соответствующий целевому символу грамматики S.

Конечная конфигурация автомата определяется так: (q,λ,λ) — автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, стек пуст.

Функция переходов МП-автомата строится на основе правил грамматики:

1. , если правило А → α содержится во
   множестве правил Р грамматики G: А → α P;
2. .

Работу данного МП-автомата можно неформально описать следующим образом: если на верхушке стека автомата находится нетерминальный символ А, то его молено заменить на цепочку символов а, если в грамматике языка есть правило А → α, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «подбор альтернативы»); если же на верхушке стека находится тер­минальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется «выброс»). Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернати­вы в грамматике языка может оказаться более одного правила вида А → α, тогда функция δ(q,λ,A) будет содержать более одного следующего состояния — у МП-автомата будет несколько альтернатив.

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

Данный МП-автомат строит левосторонние выводы для грамматики G(VT,VN,P,S). Для моделирования такого автомата необходимо, чтобы грамматика G(VT,VN,P,S) не была леворекурсивной, — в противном случае, очевидно, алгоритм может войти в бесконечный цикл. Поскольку, как было показано выше, произ­вольную КС-грамматику всегда можно преобразовать к нелеворекурсивному виду, этот алгоритм применим для любой КС-грамматики. Следовательно, им можно распознавать цепочки любого КС-языка.

26. Синтаксическое дерево.

Способы внутреннего представления программ Виды внутреннего представления программы.

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

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

Известны следующие формы внутреннего представления программ:

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

Дерево вывода. Методы построения дерева вывода

Деревом вывода грамматики G(VT,VN,P,S) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

• каждая вершина дерева обозначается символом грамматики ;
• корнем дерева является вершина, обозначенная целевым символом грамма­тики — S;
• листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки λ;
• если некоторый узел дерева обозначен нетерминальным символом , а связанные с ним узлы - символами b₁b₂…b_n; n > 0, то в грамматике G(VT,VN,P,S) существует правило .

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

Примеры деревьев приведены на рисунке.

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

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

Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева. По­строение дерева идет по слоям. На втором шаге построения в грамматике выби­рается правило, правая часть которого соответствует крайним символам в слое дерева (крайним правым символам при правостороннем выводе и крайним левым — при левостороннем). Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой дерева вместо выбранных вершин. Построение дерева закончено, если дос­тигнута корневая вершина (обозначенная целевым символом), а иначе надо вер­нуться ко второму шагу и повторить его относительно полученного слоя дерева. Поскольку все известные языки программирования имеют нотацию записи «сле­ва направо», компилятор также всегда читает входную программу слева напра­во (и сверху вниз, если программа разбита на несколько строк). Поэтому для построения дерева вывода методом «сверху вниз», как правило, используется левосторонний вывод, а для построения «снизу вверх» — правосторонний вы­вод. На эту особенность компиляторов стоит обратить внимание. Нотация чтения программ «слева направо» влияет не только на порядок разбора программы компилятором (для пользователя это, как правило, не имеет значения), но и на порядок выполнения операций — при отсутствии скобок большинство равноправ­ных операций выполняются в порядке слева направо, а это уже имеет сущест­венное значение.

Синтаксические деревья. Преобразование дерева разбора в дерево операций.

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

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

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

То, какой узел в дереве является операцией, а какой — операндом, никак невоз­можно определить из грамматики, описывающей синтаксис входного языка. Также ниоткуда не следует, каким операциям должен соответствовать объектный код в результирующей программе, а каким — нет. Все это определяется только исходя из семантики — «смысла» — языка входной программы. Поэтому только разработчик компилятора может четко определить, как при построении дерева опера­ций должны различаться операнды и сами операции, а также то,, какие операции являются семантически незначащими для порождения объектного кода. Алгоритм преобразования дерева семантического разбора в дерево операций можно представить следующим образом:

Шаг 1. Если в дереве больше не содержится узлов, помеченных нетерминальны­ми символами, то выполнение алгоритма завершено; иначе перейти к шагу 2.

Шаг 2. Выбрать крайний левый узел дерева, помеченный нетерминальным сим­волом грамматики, и сделать его текущим. Перейти к шагу 3.

Шаг 3. Если текущий узел имеет только один нижележащий узел, то текущий узел необходимо удалить из дерева, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерева цепочку) и вернуться к шагу 1; иначе перейти к шагу 4.

Шаг 4. Если текущий узел имеет нижележащий узел (лист дерева), помеченный терминальным символом, который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе перейти к шагу 5.

Шаг 5. Если текущий узел имеет один нижележащий узел (лист дерева), поме­ченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо уда­ лить из дерева, текущий узел пометить этим знаком операции и перейти к шагу 1; иначе перейти к шагу 6.

Шаг 6. Если среди нижележащих узлов для текущего узла есть узлы, помечен­ные нетерминальными символами грамматики, то необходимо выбрать крайний левый среди этих узлов, сделать его текущим узлом и перейти к шагу 3; иначе выполнение алгоритма завершено.

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

27. Сортировка одномерного массива.

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

· С использованием Min и Max – очень медленный алгоритм, заключается в последовательном поиске мин или макс. элемента в массиве, а затем размещение его в начале или конце списка! После чего указатель передвигается на следующий элемент (следующий после найденного), и все повторяется для оставшейся части массива.

· Метод пузырька – заключается в последовательном сравнении двух соседних элементов массива, и упорядочивании путем обмена каждой пары! Так продолжается до упорядочивания всего массива. Это также не самый быстрый алгоритм.

· Алгоритм быстрой сортировки и ее модификации – один из самых быстрых алгоритмов! Подробно ниже.