В классе есть методы определяющие размеры списка данных (SizeList) и размеры информации о текущих данных (SizeInfo).

Класс содержит несколько методов обрабатывающих навигацию по элементам списка: переход к следующему (NextTarget) или предыдущему элементу списка (PreviousTarget), а так же переход к следующей (NextPageTarget) или предыдущей (PreviousPageTarget) странице списка элементов.

Класс содержит аналогичные базовому методы для работы с фокусом (TakeFocus, ReturnFocus, HandleEvent).

Для отрисовки списка присутствуют методы: определения атрибутов элемента списка (FontRecord), метод рисования списка (DrawContent), метод рисования элемента списка (DrawTarget), метод рисования активного элемента списка (DrawTarget), метод рисования информации об элементе списка (DrawRecordInfo), а так же метод обновления состояния списка (ChangeContent).

На рисунке 3.13 представлен класс ListSelectBox.

Рисунок 3.17 - Класс ListSelectBox

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

В классе содержаться данные о количестве выделенных элементов (is_select), списке элементов с флагом выделения (select_list) и цвете выделения (select). Так же есть методы, которые позволяют получать и изменять эти данные (SelectColor, IsSelect, Select, ClearSelect).

Остальные методы наследуются от базового и имеют такой же функционал.

На рисунке 3.14 представлен класс ListFileBox.

Рисунок 3.18 - Класс ListFileBox

В классе содержаться данные о списке файлов (folder) и об иерархической структуре первого видимого файла (visible_position) и первого целевого файла (target_position).

Конструкторы аналогичны конструкторам базового класса.

В классе есть методы для привязки источника списка файлов (ViewFolder), входа в выбранную директорию (Enter) и выхода из директории (Exit). Так же методы для сохранения контекста текущей директории (SaveContextFolder) перед открытием новой и восстановление контекста родительской директории после закрытия предыдущей (RestoreContextFolder). Остальные методы наследуются от базового класса и имеют подобную функциональность.

На рисунке 3.15 представлен класс ListVolumeBox.

Рисунок 3.19 - Класса ListVolumeBox

В классе содержится указатель на список файловых систем (volume) и метод привязки списка к визуальному элементу (ViewVolume).

Конструкторы аналогичны конструкторам базового класса.

Остальные методы наследуются от базового класса и имеют подобную функциональность.

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

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

На рисунке 3.16 представлена схема наследования классов работы с файлами.

Рисунок 3.20 - Схема наследования классов работы с файлами

Классы IStatus, IMediaRecord, IFileRecord, IFile, IVolumeRecord, IVolume, IMediaLocator являются полностью абстрактными и определяют интерфейс для файловой системы.

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

На рисунке 3.17 представлен класс EFIMediaLocator.

Рисунок 3.21 - Класса EFIMediaLocator

Класс содержит данные об идентификаторе локатора, который необходим для реализации локатора (guid), который будет объединять различные реализации, данные о статусе последней операции (status), историю найденных файловых систем (history), количество найденных файловых систем (number) и список идентификаторов найденных файловых систем (id). Описанные данные возвращают соответствующие методы (LastStatus, LocatorGUID, Number, ID). Так же есть метод, который возвращает идентификатор файловой системы, с которой осуществлен запуск программы (StatusID).

Класс не содержит конструкторы.

В классе содержаться методы поиска активных файловых систем (Locate) и для получения интерфейса файловой системы (Volume), для определения текущего индекса файловой системы по идентификатору (Index), методы для добавления в список элементов активных файловых систем (AddID), очистки списка активных файловых систем (ClearID).

На рисунке 3.18 представлен класс EFIVolumeRecord.

Рисунок 3.22 - Класса EFIVolumeRecord

Класс содержит указатель на структуру с информацией о файловой системе (info) и статус последней операции (status). Все методы этого класса возвращают или изменяют соответствующие свойства объекта файловой системы.

На рисунке 3.19 представлен класс EFIVolume.



Рисунок 3.23 - Класса EFIVolume

Класс содержит дескриптор файловой системы (handle), указатель на встроенный интерфейс файловой системы (volume), на корневой каталог (root) и информацию о файловой системе (info).

В классе есть методы для получения интерфейса работы с корневым каталогом (Root) и метод закрытия текущего интерфейса файловой системы (Close).

Прочие методы аналогичны классам предыдущего метода.

На рисунке 3.20 представлен класс EFIFileRecord.

Рисунок 3.24 - Класса EFIFileRecord

Класс содержит указатель на структуру с информацией о файловой системе (info) и статус последней операции (status). Все методы этого класса возвращают или изменяют соответствующие свойства объекта файла.

На рисунке 3.21 представлен класс EFIFile.

Рисунок 3.25 - Класс EFIFile

Класс содержит указатель на встроенный интерфейс файла (file) и информацию о файловой системе (info).

Класс содержит методы для открытия нового файла (Open), закрытия текущего (Close), удаления текущего (Delete), методы для получения или установки указателя на позицию внутри файла, для чтения информации о файле, содержащемся в каталоге или для чтения набора байт из файла (Read), для записи массива в файл (Write) и для сброса данных кешированых операции на жесткий диск (Flush).

Прочие методы аналогичны классам предыдущего метода.

3.3 Разработка алгоритмов выполнения файловых операций на основе спроектированных интерфейсов

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

На рисунке 3.22 представлена схема алгоритма копирования.

Рисунок 3.26 - Схема алгоритма копирования

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

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

По схеме видно, что сначала происходит проверка входных параметров, а затем вызывается один из методов, зависимости от типа входных данных.

На рисунке 3.23 показана схема алгоритма копирования из директории в директорию.

Рисунок 3.27 - Схема алгоритма копирования из директории в директорию

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

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

На рисунке 3.24 показана схема алгоритма копирования из файла в директорию.

Рисунок 3.28 - Схема алгоритма копирования из файла в директорию

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

На рисунке 3.25 показана схема алгоритма копирования из файла в файл.

Рисунок 3.29 - Схема алгоритма копирования из файла в файл

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

На рисунке 3.26 представлена схема алгоритма удаления.

Рисунок 3.30 - Схема алгоритма удаления

Если удаляемы объект является директорией, то для каждого элемента директории рекурсивно вызывается алгоритм удаления, если файлом - удаляется.

3.4 Разработка поддержки пользовательских сценариев

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

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

Функции встраиваются в интерпретатор по средствам метода AddNative объекта CTinyJS.

В интерпретатор встроены три функции.

Функция VolumeLocator() возвращает объект VolumeLocator для обеспечения доступа к файловым системам.

Функция Filter() возвращает объект Filter для обеспечения отсечения не нужных файлов при выполнении файловых операции.

Функция print(string) выводит форматированную текстовую строку в стандартный поток ввода/вывода.

Пример вывода текстовой строки с переходом на следующую строку -

print("Hello, world!!!\n");

В результате работы вышеприведенной строки в стандартный поток ввода вывода будет записана строка «Hello, world!!!» и специальным символом «\n» будет осуществлен переход на следующую строку.

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

На рисунке 3.27 изображена схема наследования классов интерпретатора пользовательских сценариев.

Рисунок 3.27 - Схема наследования классов интерпретатора пользовательских сценариев

Объект VolumeLocator применяется для получения доступа к файловым системам.

Пример создания объекта доступа к файловой системе VolumeLocator

var sys = VolumeLocator();

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

Метод sys.Find() предназначен для обновления списка доступных файловых систем. Например, после подключения устройства хранения (Flash - накопителя) необходимо вызвать данный метод, чтобы можно было получить доступ к её файловой системе из пользовательского сценария. При запуске интерпретатора автоматически происходит формирование списка файловых систем, поэтому при неизменной конфигурации оборудования вызывать данный метод необязательно. Во всех остальных случаях необходимо обновить список файловых систем.

Метод sys.NumberVolume() возвращает значение количества файловых систем найденных последним вызовом Find();

Метод sys.Volume(index) принимает в качестве входного параметра - индекс и возвращает объект файловой системы. Индекс файловой системы в списке файловых систем - это целое число в диапазоне от нуля до количества файловых систем минус один [0, NumberVolume() - 1].

Функция sys.StartVolume() возвращает объект файловой системы, которая содержит файл запущенного интерпретатора, то есть если программа запущена с USB - накопителя, то данным методом будет возвращен объект файловой системы USB - накопителя.

Для всех далее описанных методов передаваемый путь может состоять из вложенных каталогов разделенных знаком «\», в том числе и служебных имен «.» и «..». Служебное имя «.» указывает на текущий каталог, то есть пути «.\dir1\dir12» и «dir1\dir12» равнозначны. Служебное имя «..» указывает на родительский каталог, то есть пути «dir1\..\dir1\dir12» и «dir1\dir12» равнозначны. Пример пути: «..\dir\file.txt»

Объект Volume применяется для получения доступа к файлам и директориям файловой системы. Объект создается методами Volume(index) и StartVolume() объекта VolumeLocator.

Пример создания объекта файловой системы Volume -

var vol = sys.StartVolume();

Метод vol.ID() возвращает идентификатор файловой системы. Идентификатор файловой системы неизменен для существующих портов ввода/вывода (например, USB-портов) на все время работы приложения. Если в течение времени работы приложения устройство хранения информации будет исключено, а затем включено в тот же самый порт, то после обновления конфигурации устройство хранения будет иметь тот же идентификатор.

Метод vol.CheckFile(path) принимает на вход путь до файла и определяет, существует ли по такому пути файл и на выходе возвращает логическое значение «истина» или «ложь». В случае если путь не указывает на файл или вовсе не существует, то возвращаемое значение будет «ложь», в противном случае «истина».

Метод vol.CheckFolder(path) принимает на вход путь до директории и определяет существует ли по такому пути директория и на выходе возвращает логическое значение «истина» или «ложь». В случае если путь не указывает на директорию или вовсе не существует, то возвращаемое значение будет «ложь», в противном случае «истина».

Метод vol.File(path) принимает на вход путь и возвращает объект файла. При создании объекта не производиться никаких проверок, то есть путь, передаваемый в метод, может не существовать или указывать на директорию, в любом случае объект файла будет создан.

Метод vol.Folder(path) принимает на вход путь и возвращает объект директории. При создании объекта не производиться никаких проверок, то есть путь, передаваемый в метод, может не существовать или указывать на файл, в любом случае объект файла будет создан.

Объект Folder применяется для получения информации о директории и выполнения операций над содержимым директории. Объект создается методом Folder(path) объектов Volume и Folder.

Пример создания объекта директории Folder -

var fol = vol.Folder(“path”);

Метод fol.Check() возвращает логическое значение «истина», если путь, указываемый при создании объекта директории, был верным и был получен доступ к объекту, в противном случае возвращаемое значение будет «ложь» и дальнейшие операции с таким объектом бессмысленны.

Метод fol.Size() - возвращает числовое значение «0», соответствующее файловому размеру директории.

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

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

Метод fol.Arhive() возвращает логическое значение «истина», если директория имеет установленный атрибут «архивный», в противном случае возвращаемое значение будет «ложь».

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

Метод fol.LastAccessDateTime() возвращает строковое представление даты и времени последнего открытия директории.

Метод fol.LastModificationDateTime() возвращает строковое представление даты и времени последнего изменения директории.

Метод fol.CreateDateTime() возвращает строковое представление даты и времени создания директории.

Метод fol.Name() возвращает строковое представление имени директории.

Метод fol.GetContentFile() последовательно, с каждым новым вызовом возвращает объект файла, содержащегося в директории. Как только все файлы будут перебраны, функция будет возвращать объект, ссылающийся на не существующий файл.

Метод fol.GetContentFolder() последовательно, с каждым новым вызовом возвращает объект директории, содержащейся в родительской директории. Как только все директории будут перебраны, функция будет возвращать объект, ссылающийся на не существующую директорию.

Метод fol.ResetFilePointer() сбрасывает счетчик, который указывает на порядковый номер следующего открываемого файла, в начальное значение. После сброса можно заново получить объекты файлов методом GetContentFile(), содержащиеся в директории.

Метод fol.ResetFolderPointer() сбрасывает счетчик, который указывает на порядковый номер следующей открываемой директории, в начальное значение. После сброса можно заново получить объекты директории методом GetContentFolder(), содержащиеся в родительской директории.

Метод fol.CheckFile(path) принимает на вход путь до файла и определяет существует ли по такому пути файл и на выходе возвращает логическое значение «истина» или «ложь». В случае если путь не указывает на файл или вовсе не существует, то возвращаемое значение будет «ложь», в противном случае «истина».

Метод fol.CheckFolder(path) принимает на вход путь до директории и определяет существует ли по такому пути директория и на выходе возвращает логическое значение «истина» или «ложь». В случае если путь не указывает на директорию или вовсе не существует, то возвращаемое значение будет «ложь», в противном случае «истина».

Метод fol.File(path) принимает на вход путь и возвращает объект файла. При создании объекта не производиться никаких проверок, то есть путь, передаваемый в метод, может не существовать или указывать на директорию, в любом случае объект файла будет создан.

Метод fol.Folder(path) принимает на вход путь и возвращает объект директории. При создании объекта не производиться никаких проверок, то есть путь, передаваемый в метод, может не существовать или указывать на файл, в любом случае объект файла будет создан.

Метод fol.Copy(filter, vol, path) не возвращает значений, принимает в качестве входных параметров объекты:

- filter - объект фильтра определяет свойства, которыми должен соответствовать файл, чтобы быть скопированным;

- vol - объект файловой системы, на которой будет создана копия;

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

Копирование содержимого директории источника производиться в директорию с аналогичным именем по путь назначения. Например, если директорией источником является «dir\source», а директорией назначения «dir\destination», то после успешного копирования содержимое директории источника будет находиться по пути «dir\destination\source».

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

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

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

До создания объектов методами File(path) и Folder(path) объектов Volume и Folder можно вызывать методы CheckFile(path) и CheckFolder(path) или после создания объектов вызвать метод объекта Check(), которые проверят корректность пути.

Объект File применяется для получения информации о файле и выполнения операций над файлом. Объект создается методом File(path) объектов Volume и Folder.

Пример создания объекта директории File -

var fol.File(“folder/file.txt”);

Метод file.Check() возвращает логическое значение «истина», если путь, указываемый при создании объекта файла, был верным и был получен доступ к объекту, в противном случае возвращаемое значение будет «ложь» и дальнейшие операции с таким объектом бессмысленны.

Метод file.Size() возвращает значение размера файла в байтах.

Метод file.ReadOnly() возвращает логическое значение «истина», если файл имеет установленный атрибут «только для чтения», в противном случае возвращаемое значение будет «ложь».

Метод file.Hidden() возвращает логическое значение «истина», если файл имеет установленный атрибут «скрытый», в противном случае возвращаемое значение будет «ложь».

Метод file.Archive() возвращает логическое значение «истина», если файл имеет установленный атрибут «архивный», в противном случае возвращаемое значение будет «ложь».

Метод file.System() возвращает логическое значение «истина», если файл имеет установленный атрибут «системный», в противном случае возвращаемое значение будет «ложь».

Метод file. LastAccessDateTime() возвращает строковое представление даты и времени последнего открытия файла.

Метод file.LastModificationDateTime() возвращает строковое представление даты и времени последнего изменения файла.

Метод file. CreateDateTime() возвращает строковое представление даты и времени создания файла.

Метод file.Name() возвращает строковое представление имени файла.

Метод file.Copy(filter, vol, path) не возвращает значений, принимает в качестве входных параметров объекты:

- filter - объект фильтра определяет свойства, которыми должен соответствовать файл, чтобы быть скопированным;

- vol - объект файловой системы, на которой будет создана копия;

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

Путь назначения должен является файлом. Копия файла создается с тем именем, который указан в пути. Например, если файлом источником является «dir\source.doc», а файлом назначения «dir\destination.doc», то после успешного копирования содержимое файла источника будет находиться по пути «dir\destination.doc».

Если путь назначения является директорией, то копия файла создается внутри директории с аналогичным именем. Например, если файлом источником является «dir\source.doc», а директорией назначения «dir\destination», то после успешного копирования содержимое файла источника будет находиться по пути «dir\destination\source.doc».

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

Метод file.CopyFile(vol, path) метод аналогичен методу Copy(filter, vol, path) за исключением того, что не принимает на вход объект фильтра, то есть, безусловно, копирует файл.

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

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

Пример создания объекта фильтра Filter -

var filter = Filter();

Метод filter.GetMaxLastAccessDateTime() возвращает верхнюю границу отрезка для пропускания по времени последнего доступа к файлу.

Метод filter.GetMaxLastModificationDateTime() возвращает верхнюю границу отрезка ограничения по времени последней модификации файла.

Метод filter.GetMaxCreateDateTime() возвращает верхнюю границу отрезка ограничения по времени создания файла.

Метод filter.GetMaxSize() возвращает верхнюю границу отрезка по размеру файла.

Метод filter.GetMinLastAccessDateTime() возвращает нижнюю границу отрезка для пропускания по времени последнего доступа к файлу.

Метод filter.GetMinLastModificationDateTime() возвращает нижнюю границу отрезка ограничения по времени последней модификации файла.

Метод filter.GetMinCreateDateTime() возвращает нижнюю границу отрезка ограничения по времени создания файла.

Метод filter.GetMinSize() возвращает нижнюю границу отрезка по размеру файла.

Метод filter.GetExactLastAccessDateTime() возвращает точное значение ограничения времени последнего доступа к файлу.

Метод filter.GetExactLastModificationDateTime() возвращает точное значение ограничения времени последней модификации файла.

Метод filter.GetExactCreateDateTime() возвращает точное значение ограничения времени создания файла.

Метод filter.GetExactSize() возвращает точное значение ограничения размера файла.

Метод filter.SetMaxLastAccessDateTime(value) устанавливает верхнюю границу отрезка для пропускания по времени последнего доступа к файлу.

Метод filter.SetMaxLastModificationDateTime(value) устанавливает верхнюю границу отрезка ограничения по времени последней модификации файла.

Метод filter.SetMaxCreateDateTime(value) устанавливает верхнюю границу отрезка ограничения по времени создания файла.

Метод filter.SetMaxSize(value) устанавливает верхнюю границу отрезка по размеру файла.

Метод filter.SetMinLastAccessDateTime(value) устанавливает нижнюю границу отрезка для пропускания по времени последнего доступа к файлу.

Метод filter.SetMinLastModificationDateTime(value) устанавливает нижнюю границу отрезка ограничения по времени последней модификации файла.

Метод filter.SetMinCreateDateTime(value) устанавливает нижнюю границу отрезка ограничения по времени создания файла.

Метод filter.SetMinSize(value) устанавливает нижнюю границу отрезка по размеру файла.

Метод filter.SetExactLastAccessDateTime(value) устанавливает точное значение ограничения времени последнего доступа к файлу.

Метод filter.SetExactLastModificationDateTime(value) устанавливает точное значение ограничения времени последней модификации файла.

Метод filter.SetExactCreateDateTime(value) устанавливает точное значение ограничения времени создания файла.

Метод filter.SetExactSize(value) устанавливает точное значение ограничения размера файла.

Метод filter.GetPatternName() возвращает шаблон имени файла.

Метод filter.SetPatternName(value) устанавливает шаблон имени файла.

Ограничения на параметры времени последнего доступа, модификации и создания задаются и возврящаются в виде строки формата «ГГГГ-ММ-ДД ЧЧ:ММ».

Пример задания даты и времени -

2014-04-02 12:00

Ограничения на размер файла задаются в десятичной системе счисления, в байтах.

Пример задания ограничения размера файла -

1048576

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

- «*» предполагает наличие в позиции нахождения знака любых символов в количестве от нуля и более. Например, строка «file_of_*.doc» эквивалентна следующим вариантам: «file_of_.doc», «file_of_Mike.doc», «file_of_Anna.doc», и так далее.

- «?» предполагает наличие в позиции нахождения выражения одного любого символа. Например, строка «file?.doc» эквивалентна следующим вариантам: «file1.doc», «fileA.doc», «file9.doc», и так далее, но не эквивалентна строке «file12.doc»

- «[a-z]» предполагает наличие в позиции нахождения выражения одного символа из диапазона указанного в кавычках. Например, строка «file[0-9].doc» эквивалентна следующим вариантам: «file1.doc», «file5.doc», «file9.doc», и так далее, но не эквивалентна строке «fileA.doc» или «file12.doc».

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

Выводы

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



4 Теория формальных языков

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

4.1 Цепочки символов и операции над ними

Алфавитом называется непустое конечное множество символов.

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

Длиной цепочки является количество символов в ней. Например, цепочка имеет длину .

Две цепочки и совпадают (равны): , если они имеют один и тот же состав и порядок символов, и их количество.

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

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

Над цепочками можно выделить следующие операции:

Конкатенацией, или сцеплением (сложением) цепочек, называется строка, полученная их объединением, например

,

тогда конкатенация цепочек и будет иметь вид . Так как в цепочке важен порядок символов, очевидно, что операция сложения не коммутативна, т.е. в общем случае . Конкатенация ассоциативна, т.е. .

Обращение цепочки - это запись ее символов в обратном порядке, обозначается . Например, для цепочки ее обращение . Свойство операции обращения

.

Итерация цепочки раз - это ее сцепление (повторение) раз, обозначается .

Для пустой цепочки справедливы следующие равенства:

- ;

- ;

- ;

- ;

- .

4.2 Понятие языка. Способы задания языков

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

Цепочка символов является цепочкой над алфавитом , если в нее входят только символы этого алфавита.

Если - некоторый алфавит, то - множество всех цепочек над алфавитом без , - множество всех цепочек над алфавитом , включая .

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

Для любого языка справедливо .

Язык включает в себя язык

, если .

Два языка эквивалентны

, если и .

Конкатенацией (объединением) языков и называют язык , состоящий из всевозможных сцеплений цепочек языков и :

.

Замыкание Клини, или итерация языка , обозначается и определяется рекурсивно

, для , для всех . .

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

Язык состоит из бесконечного множества цепочек символов над некоторым алфавитом, или слов. Но не любая цепочка символов над этим алфавитом принадлежит языку, т.к. существуют правила построения допустимых цепочек для каждого конкретного языка. Указать эти правила - значит задать язык. Существуют три основных способа задания языка:

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

- указание способа порождения цепочек языка (задание грамматики языка) - применение т.н. генератора.

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

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

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

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

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

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

4.3 Понятие грамматики. Форма Бэкуса-Наура

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

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

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

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

Формально грамматика определяется как четверка

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

полный алфавит грамматики ; - множество правил вида

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

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

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, например

, , …,

Тогда эти правила записываются в одну строку

.

Рассмотренная форма записи правил грамматики называется формой Бэкуса-Наура. В ней, как правило, нетерминальные символы заключаются в угловые скобки .

Например, грамматика для порождения целых десятичных чисел со знаком

. : ; ;

В данной грамматике множество нетерминальных символов содержит три элемента (символы ,,), множество терминальных символов - 12 элементов (10 цифр и два знака), множество P - 15 правил, записанных в три строки. Начальный символ грамматики - .

В грамматике можно изменить названия нетерминальных символов без какого-то изменения языка, заданного ею. Терминальные символы изменять нельзя, так как они соответствуют алфавиту задаваемого языка.

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

В грамматиках и явная рекурсия присутствует во второй части второго правила

, .

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

, .

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

4.4 Классификация грамматик по Хомскому

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

Пусть грамматика обозначена как

В соответствии с иерархией Хомского выделяют четыре типа грамматик.

Тип 0 - грамматики с фразовой структурой, или без ограничений. На структуру их правил не накладывается никаких ограничений, т.е. правила имеют вид

где , . Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

Тип 1 - контекстно-зависимые и неукорачивающие грамматики. К этому типу относятся два основных класса грамматик.

Контекстно-зависимые грамматики имеют правила вида

, где , , .

Неукорачивающие грамматики имеют правила вид

где , .

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

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

Эти два класса грамматик эквивалентны.

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

Тип 2 - контекстно-свободные грамматики. Контекстно-свободные грамматики имеют правила вида , где , . В правой части у них стоит всегда хотя бы один символ.

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

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

Тип 3 - регулярные грамматики. К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

Леволинейные грамматики могут иметь правила двух видов

, или

где , .

Праволинейные грамматики имеют правила тоже двух видов

, или ,

где ,

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

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

4.5 Классификация языков

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

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

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

Тип 1 - контекстно-зависимые (КЗ) языки.В общем случае время на распознавание языка типа 1 экспоненциально зависит от длины исходной цепочки символов.

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

Однако языки программирования имеют более простую структуру, поэтому в компиляторах КЗ-языки не применяются.

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

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

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

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

4.6 Распознаватели. Задача разбора

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

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

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

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

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

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

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

Распознаватель входит в состав компилятора и является частью программного обеспечения компьютера. На рисунке 4.1 представлена условная схема распознавателя.

Рисунок 4.31 - Условная схема распознавателя

Основные компоненты распознавателя:

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

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

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

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

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

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

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

Такт состоит из следующих моментов:

- входная головка распознавателя сдвигается на одну ячейку вправо, влево или остается на месте;

- в память помещается некоторая информация;

- изменяется состояние УУ.

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

- состояние УУ;

- содержимое входной ленты и положение считывающей головки в ней;

- содержимое внешней памяти.

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

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

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

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

Язык, определяемый распознавателем - это множество всех цепочек, которые допускает этот распознаватель.

4.7 Виды распознавателей и их классификация

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

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

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

По видам внешней памяти распознаватели бывают следующих типов:

- распознаватели без внешней памяти;

- распознаватели с ограниченной внешней памятью;

- с неограниченной внешней памятью.

Распознаватели без внешней памяти моделируются конечными автоматами и используют в процессе работы только конечную память УУ.

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

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