Дефаззификация – процесс нахождения нечеткого значения для каждой лингвистической переменной, имя которой встречается в заключении правил. Цель дефаззификации заключается в том, чтобы, используя результат аккумуляции, получить количественное значение выходной переменной.При дефаззификации используют методов: центра тяжести, центра площади, левого или правого модальных значений.
При использовании метода центра площади находят такое значение y=u, при котором выполняется следующее равенство:
.
Центр площади равен абсциссе, которая делит площадь, ограниченную графиком кривой функции принадлежности на две равные части.
Для рассматриваемого примера результат дефаззификации показан на рис. 5.6 (площадь фигуры ABCD равны площади фигуру CDHG).
Рис. 13.6.
1. Определите нечеткое высказывание.
2. Определите нечеткую посылку.
3. Определите нечеткие логические правила.
4. Опишите алгоритм фаззификации.
5. Опишите алгоритм агрегации.
6. Опишите алгоритм активизации.
7. Опишите алгоритм аккумуляции.
8. Опишите алгоритм дефаззификации.
ФГБОУ ВПО «Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева»
Курс лекций по дисциплине «Системное программное обеспечение»
Красноярск 2010 г.
В данной главе излагаются некоторые основные сведения о месте, занимаемом трансляторами в системном программном обеспечении ЭВМ, а также приводится информация о видах и функциях трансляторов. Размещенная в данной главе обобщенная схема компилятора позволяет ознакомиться с сущностью и назначением основных фаз процесса трансляции.
Системное программное обеспечение – совокупность программных и языковых средств, предназначенных для поддержания функционирования ЭВМ и наиболее эффективного выполнения ею целевого назначения. Системные программы осуществляют организацию вычислительного процесса и управление ресурсами ЭВМ. Вследствие этого они обычно тесно связаны со структурой машины, для которой созданы.
По функциональному назначению в системном программном обеспечении можно выделить две системы: операционную систему и систему программирования.
Операционная система – комплекс программ, которые обеспечивают управление аппаратурой ЭВМ, планирование эффективного использования ее ресурсов, автоматизацию процесса подготовки программ и прохождения их в ЭВМ, взаимодействие между пользователем и вычислительной машиной.
Система программирования – совокупность программных средств, обеспечивающих автоматизацию разработки и отладки пользовательских программ.
Понятие системы программирования возникло с появлением языков программирования более высокого по сравнению с машинным уровня, что повлекло за собой разработку специальных программных средств, которые должны обеспечивать перевод программ, записанных в терминах входного языка, на внутренний язык вычислительной машины. Таким образом, система программирования включает в себя, по крайней мере, два компонента: входной язык системы и транслятор с этого языка.
Система программирования тесно связана с операционной системой. Все трансляторы, входящие в состав систем программирования, работают под управлением операционной системы, являясь одновременно составной частью последней, так как функционально трансляторы принадлежат к группе системных обрабатывающих программ операционной системы.
Таким образом,основные функции системы программирования следующие:
- трансляция (перевод) программ пользователей с языка программирования в машинные коды команд;
- регистрация синтаксических и логических ошибок в программах.
Средства системы программирования, выполняющие эти функции, включают в себя ассемблеры, компиляторы и интерпретаторы.
Трансляторы, которые используются для программ, написанных на языке Ассемблера, называются ассемблеры.
Для трансляции программ с языков высокого уровня используются компиляторы или интерпретаторы.
Компиляторы – преобразуют операторы языка в машинные коды целиком для всей программы. В результате обработки исходного текста программы формируется объектный модуль, который затем может многократно выполняться после его загрузки в оперативную память.
Интерпретаторы – осуществляют преобразование операторов в машинные коды во время выполнения программы. После запуска программы в оперативную память одновременно загружаются исходный текст программы, написанный на языке высокого уровня, и интерпретатор, который последовательно транслирует операторы программы и сразу же их выполняет.
В современных ЭВМ одни и те же языки программирования могут быть представлены как компилирующие или интерпретирующие системы программирования.
Интерпретирующие системы программирования эффективны на этапе разработки программ, так как минимизируют время на отладку. Применение режима интерпретации для многократного выполнения отлаженных программ нецелесообразно, так как интерпретатор занимает дополнительный объем оперативной памяти, а также из-за трансляции замедляется выполнение программы.
Компилирующие СП эффективны при регулярной эксплуатации программ, так как имеется уже готовый к выполнению объектный модуль, что экономит время, затрачиваемое на трансляцию, и место в оперативной памяти. Разработка и отладка программ с использованием компилятора связаны с дополнительными временными затратами на трансляцию всего текста при определении ошибки.
Компиляторы обычно несколько проще в реализации, чем интерпретаторы, кроме того, не каждый язык программирования допускает построение простого интерпретатора. Однако интерпретаторы имеют существенное преимущество перед компиляторами, которое долгое время не принималось во внимание: откомпилированный код всегда привязан к архитектуре вычислительной системы, на которую он ориентирован, в то время как исходный текст программы непосредственно связан только с семантикой языка программирования, которую проще стандартизировать. В настоящее время с развитием глобальных вычислительных сетей и распространением всемирной сети Интернет вопрос о переносимости программ и их независимости от аппаратной платформы приобретает все большую актуальность. Поскольку в состав сети могут входить ЭВМ различной архитектуры, то требование единообразного выполнения текста исходной программы на каждой из этих ЭВМ становится определяющим. Язык описания гипертекста HTML (Hypertext Markup language), на основе которого функционирует сейчас практически вся структура сети Интернет, является интерпретируемым языком. Трансляторы языков Java и JavaScript сочетают в себе функции компиляции и интерпретации: текст исходной программы компилируется в некоторый промежуточный двоичный код, не зависящий от архитектуры вычислительной системы; этот код передается по сети и выполняется в режиме интерпретации на принимающей стороне.
Рассмотрим обобщенную структуру компилятора и основные фазы процесса компиляции (рис. 1.1).
Рис. 1.1. Структурная схема компилятора
В целом процесс компиляции разделяется на два этапа – анализ и синтез. На этапе анализа осуществляется распознавание текста исходной программы, создание и заполнение таблиц символов (идентификаторов). Результатом процесса анализа является некоторое промежуточное (внутреннее) представление программы, понятное компилятору. Полученные результаты играют роль исходных данных для процесса синтеза, в ходе которого формируется объектный код – результирующая программа. Таким образом, наличие этапов анализа и синтеза в процессе функционирования компилятора непосредственно связано с тем, что в целом с точки зрения теории формальных языков компилятор выступает одновременно как в роли распознавателя для языка исходной программы, так и в роли генератора для языка результирующей программы.
Этапы анализа и синтеза, в свою очередь, состоят из более мелких этапов, называемых фазами компиляции. Состав и взаимосвязь фаз компиляции представлена нами в самом общем виде, так как их конкретная реализация и процесс взаимодействия существенно зависят от версии компилятора.
Кроме этого, можно выделить единый для всех фаз процесс анализа и исправления ошибок, существующих в обрабатываемом исходном тексте программы.
Фазы функционирования компиляторов тесно связаны с такими понятиями, как семантика, синтаксис и лексика языка, поэтому представляется необходимым коротко остановиться на этих понятиях.
Синтаксис языка – это набор правил, определяющих допустимые конструкции данного языка. Иначе говоря, это совокупность правил образования семантически значимых последовательностей символов в данном языке.
Однако следует заметить, что возможность задания синтаксиса в виде строго формализованного набора правил полностью осуществима только для чисто формальных языков.
Семантикой языка называется совокупность правил интерпретации предложений и конструкций языка. Другими словами, семантика определяет смысловое содержание языковых конструкций.
Семантика подавляющего большинства языков определяется неформально (чисто формальные языки лишены смыслового содержания).
Лексика – это совокупность слов языка, которые и являются лексическими единицами (лексемами) языка. Лексема состоит из элементов алфавита языка и не содержит в себе других лексем.
Лексическими единицами языков программирования обычно являются ключевые слова, идентификаторы, константы, знаки операций, а также символы-разделители (скобки, запятые, точки с запятой, двоеточия и т.п.). В основе построения предложений конкретного языка программирования лежит набор формально заданных синтаксических правил. Однако этих правил не достаточно для того, чтобы строго определить все возможные синтаксические конструкции, так как практически всегда существуют дополнительные ограничения, которые накладываются семантикой языка. Это такие семантические ограничения как необходимость предварительного описания переменных и функций, соответствие количества и типов фактических и формальных параметров функций, требования к соответствию типов переменных и констант в арифметических и логических выражениях, ограничение области действия локальных переменных и т.п. Подобные семантические ограничения описываются неформально для каждого конкретного языка программирования, поэтому во всех трансляторах кроме синтаксического анализа исходного текста программы предусматривается еще и фаза семантического анализа.
Рассмотрим кратко сущность, назначение и взаимосвязь основных фаз процесса компиляции.
На фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы – слова в соответствии с определениями языка. В общем случае результатом фазы лексического анализа являются специальным образом организованные наборы данных – таблица лексем и таблицы идентификаторов. Лексический анализ может не выделяться в самостоятельную фазу, а производиться на последующем этапе синтаксического анализа. В этом случае лексический анализатор работает как подпрограмма, вызываемая синтаксическим анализатором для получения значения очередной лексемы. На этапе лексического анализа обнаруживаются некоторые простейшие ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и другие). Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные грамматики.
Синтаксический анализ (синтаксический разбор) – это главная фаза этапа анализа. Основная задача синтаксического анализа – синтаксический разбор структуры программы. На этой фазе происходит выделение синтаксических конструкций в тексте исходной программы, обработанном лексическим анализатором; устанавливается тип и проверяется правильность каждой выделенной конструкции; кроме того, синтаксические конструкции представляются в виде, удобном для дальнейшей генерации объектного кода. Результатом синтаксического анализа является синтаксическое дерево (дерево разбора) со ссылками на таблицы символов. Основой для построения синтаксических анализаторов является формализм контекстно-свободных грамматик (КС-грамматик).
Семантический (контекстный) анализ – это такая фаза работы компилятора, на которой проверяется семантическая правильность исходной программы. Это в основном связи «описание-использование», в частности, анализ типов объектов, анализ областей видимости, соответствие типов и количества формальных и фактических параметров подпрограмм, правильность использования меток и прочее. В процессе синтаксического анализа таблицы лексем и идентификаторов пополняются информацией об описаниях (свойствах) объектов. На фазе семантического анализа могут быть выявлены ошибки, связанные с неправильным использованием объектов (лексем). Кроме этого, на данной фазе осуществляются некоторые преобразования текста программы, обусловленные семантикой входного языка (например, добавление функций неявного преобразования типов). Основным формализмом, использующимся при семантическом анализе, является аппарат атрибутных грамматик. Результатом семантического анализа является атрибутированное дерево программы. В зависимости от реализации, семантический анализ может представлять собой как самостоятельную фазу процесса компиляции, так и частично осуществляться на предыдущей и последующей фазах.
Затем программа может быть переведена в промежуточное (внутреннее) представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. В этом случае только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие формы представления программы.
Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная – только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д.
Наконец, генерация кода – последняя фаза компиляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы.
Таким образом, процесс компиляции состоит из нескольких фаз, причем в реальных компиляторах те или иные фазы могут быть либо разбиты на составляющие, либо объединяться, либо отсутствовать совсем. Кроме того, в различных версиях компиляторов может меняться порядок взаимодействия фаз компиляции: они могут выполняться по однопроходной либо по многопроходной схеме. Проход – это процесс последовательного чтения компилятором данных из внешней памяти, последующей обработки считанных данных и помещения результата работы во внешнюю память. Один проход обычно содержит в себе одну или несколько фаз компиляции. В общем случае многопроходная схема компиляции предусматривает
В простейшем случае однопроходного компилятора нет явной фазы генерации промежуточного представления и оптимизации, а остальные фазы объединены в одну. Чем сложнее грамматика и семантические правила языка, тем больше проходов необходимо компилятору для порождения объектного кода. При этом всегда присутствует стремление разработчиков компилятора сократить количество проходов с целью повышения эффективности работы компилятора (увеличения скорости трансляции, сокращения объема используемой памяти). Однопроходные компиляторы возможны только для самых простых языков. Реальные компиляторы, как правило, выполняют трансляцию текста исходной программы за несколько проходов (от двух до пяти).
Транслятор с языка Ассемблера (ассемблер), безусловно, представляет собой компилятор, так как результатом его работы является объектный модуль исходной программы. По сравнению с компиляторами для языков высокого уровня, ассемблеры имеют более простую схему реализации, что обусловлено следующими особенностями языка Ассемблера.
Язык Ассемблера, как правило, содержит символьные коды машинных команд. Синтаксические правила языка Ассемблера предельно просты, что позволяет объединить фазы лексического и синтаксического разбора в одном распознавателе. Семантические правила языка Ассемблера полностью определяются особенностями вычислительной системы, на которую ориентирован данный язык. Семантика языка Ассемблера определяет, какая машинная команда соответствует каждой команде языка, а также типы и количество операндов в командах. Поэтому семантический анализ в ассемблерах также прост, как и синтаксический. В функции семантического анализатора входит проверка допустимости использования операндов заданных типов в командах, проверка наличия описаний используемых в программе идентификаторов и меток, а также их обязательного отличия от предопределенных служебных слов, обозначающих коды операций и регистры процессора. Также следует отметить, что на этапе генерации кода в ассемблерах не производится оптимизация, поскольку решение задачи оптимального распределения регистров процессора возлагается ан разработчика программы. Компиляторы с языка Ассемблера реализуются обычно по двухпроходной схеме: на первом проходе компилятор выполняет разбор исходной программы, построение таблицы идентификаторов и генерацию машинных кодов команд, но с использованием символических адресов; на втором проходе компилятор заменяет символические адреса на реальные. Необходимость в двух проходах обусловлена возможностью использовать идентификаторы до их описания. Например, наличие метки в соответствующем поле команды (метка: оператор) является одновременно и описанием данной метки, но команда безусловного перехода вполне может располагаться ранее в тексте программы, чем команда, которой передается управление.
Общая структура интерпретатора мало отличается от структуры аналогичного компилятора, за исключением одной важной особенности. В структуре интерпретаторов отсутствует фаза оптимизации, поскольку на этапе генерации кода сгенерированные интерпретатором машинные команды не записываются в объектный файл, а выполняются по мере их порождения. Отсутствие фазы оптимизации определяет еще одну особенность, характерную для многих интерпретаторов: в качестве внутреннего (промежуточного) представления программы в них часто используется очень удобная форма представления операций - обратная польская запись (см. главу 4), которая плохо поддается оптимизации, что для интерпретаторов как раз не существенно. Для того чтобы язык программирования допускал возможность его интерпретации, должна существовать возможность построения компилятора, выполняющего разбор исходного текста программы за один проход.
Не смотря на то, что некоторые технические приемы, применяемые при построении трансляторов различных типов, могут существенно отличаться друг от друга, в любом случае для получения результата трансляции сначала необходимо каким-то образом вычленить смысл, заключенный в предложениях входного текста на исходном языке. Такое вычленение смысла из входной информации во всех типах трансляторов осуществляется по одной и той же схеме, на основе результатов одной и той же теории, независимо от того, является ли транслятор компилятором, интерпретатором или языковым процессором любого другого назначения. В основе разработки подавляющего большинства существующих трансляторов лежит идея синтаксически-ориентированной трансляции, предложенная в 50-х годах прошлого столетия выдающимся американским лингвистом Ноамом Хомским, профессором Массачусетского Технологического института. В своих работах Хомский исследовал механизмы понимания человеком смысла фраз естественного языка и пришел к выводу, что основную роль в процессе понимания смысла предложения естественного языка человеком играет этап построения структуры этого предложения, и именно эта построенная структура используется человеком далее на интуитивном уровне для извлечения смысла, заключенного в предложении. Хотя идеи Хомского сейчас не очень широко используются в лингвистике, они составили теоретическую основу формальных моделей искусственных языков и их трансляции в современной вычислительной науке. Идея использования только структурных аспектов предложения языка при его анализе оказалась чрезвычайно удобной в информатике при построении трансляторов. В соответствии с идеей синтаксически-ориентированной трансляции процесс трансляции в информатике связывается с двумя основными этапами (рис. 1.2). На первом этапе блок, который можно назвать распознавателем, строит структуру входной цепочки, а на втором этапе построенная структура используется для генерации выхода, выражающего смысл входной цепочки.
Исходя из вышесказанного, можно считать, что теория построения трансляторов в значительной своей части посвящена методам выявления структуры входного текста и использования этой структуры для преобразования входа с сохранением его смысла.
В следующих главах учебного пособия подробно рассматриваются теоретические основы построения трансляторов, а также некоторые широко используемые методы их практической реализации.
.
Для рассматриваемого примера результат дефаззификации показан на рис. 5.6 (площадь фигуры ABCD равны площади фигуру CDHG).
