Регулярные схемы над абстрактными типами памяти - Банк бесплатных рефератов, курсовых, дипломных работ

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

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

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

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

Статическая и динамическая декомпозиции применяются для разработки представленных посредством РС над АТП методов поуровневого синтаксического анализа и трансформации текстов, их диалогового конструирования и синтеза алгоритмов и программ.

Декомпозиция цепочек

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

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

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

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

Регулярные схемы над абстрактными типами памяти

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

Пусть F (Z) - РС над базисом Z, состоящим из операторов и предикатов, отражающих специфику выбранной предметной области. Эти операторы и предикаты определяются на совокупности обрабатываемых типов данных. Так определенные предикаты и операторы можно рассматривать в качестве компонентов сигнатуры некоторой многоосновной алгебраической системы, в терминах которой формализуется известная концепция абстрактных типов данных (АТД). Отметим при этом, что доступ к элементам АТД и их преобразование можно осуществлять лишь с помощью операций и предикатов, входящих в состав сигнатуры АТД. Тем самым АТД представляет собой «капсулу» и указанное свойство принято называть принципом инкапсуляции. С АТД ассоциируем гипотетическую машину ГМ, функционирующую по известной схеме взаимодействия управляющей и операционной структур. Доступ к состояниям операционной структуры и их преобразование возможны лишь в результате применения сигнатурных компонент АТД - команд ГМ. Эти команды представимы регулярными схемами F (Z): в терминах базиса этих схем осуществляется взаимодействие управляющей и операционной структур ГМ.

При этом регулярные схемы F (Z) по своей роли аналогичны микропрограммам, а элементы базиса Z - микрокомандам.

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

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

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

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

Построим РС СИН/У, представляющую новый метод поуровневого синтаксического анализа программ, базирующийся на использовании процедуры статической декомпозиции цепочек и структуры памяти БС.

Пусть G = (Vт, Vн, n0, P) - бесконтекстная грамматика и Р (u) = НУ2 У3 u К - разметка цепочки u, подлежащей анализу, L (G) ? V*т - язык, порожденный грамматикой G.

Рассмотрим далее терминальную цепочку u = a1 a2. an ? V*т - подлежащую синтаксическому анализу. Процесс анализа состоит в проверке принадлежности u ? L (G) (фаза контроля) и построении дерева грамматического разбора цепочки u по грамматике G (фаза анализа).

/*В результате выполнения оператора ИНИЦ в основу БС записывается пара (n0, u) с последующей перезаписью маркера # из вершины r1 в основание r0 БС, так что пара (n0, u) перемещается в вершину r1. */

[КОНЕЦ АНАЛИЗА] - предикат, истинный в случае успешного завершения синтаксического анализа цепочки u, или обнаружения в процессе ее анализа синтаксических ошибок;

ЧТЕ. БС - оператор чтения пары (n, u') - содержимого вершины БС, здесь n ? Vн - нетерминал, u' - имя соответствующей терминальной подцепочки, анализируемой цепочки u (на первом витке основного цикла n = n0, u' = u);

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

При обнаружении применимой продукции р: n ? w по его правой части образуется форма, в противном случае выдается информация о наличии синтаксической ошибки;

ОБРАБОТКА УЗЛА:: = = =ЕСЛИ [Ф (р) - форма] ТО ДЕК/С (u'/Ф (р)) * ЗАП. БС[ (n1, u1') (n2, u2'). (nm, um') ] KE * ЕСЛИ ['r1 = # ] ТО ПЗ. БС (#) КЕ

В результате выполнения данного оператора осуществляется статическая декомпозиция подцепочки u' по форме Ф (р) с фиксацией пар (n1, u1') (n2, u2'). (nm, um') сформировавшихся в процессе декомпозиции; генерируется соответствующее количество дуг, исходящих из обрабатываемого узла (n, u') к узлам, помеченным указанными парами и расположенными на следующем уровне формируемого дерева грамматического разбора. При этом помечающие пары в указанном порядке записываются в БС. Если при чтении БС 'r1 = #, то выполняется перезапись маркера # из r1 в r0;

КОНТРОЛЬ:: = = =ЕСЛИ [КОНЕЦ АНАЛИЗА] ТО ['БС = #] * «u ? L (G)» ИНАЧЕ СОШ КЕ.

После выхода из основного цикла при отсутствии синтаксических ошибок опустошение очереди ('БС = #) означает синтаксическую правильность цепочки u, иначе выдается информация о наличии в ней синтаксических ошибок; [Q]? - фильтр. */.

Осуществив развертку, стратегии СИМ по I5 получим РС СИН/У = (СИМ?I5,), такую что

СИН/У:: = = =ИНИЦ * ПОКА НЕ [КОНЕЦ АНАЛИЗА] ЦИКЛ (ЧТЕ. БС * ППП * ОБРАБОТКА УЗЛА) КЦ * КОНТРОЛЬ.

В процессе выполнения данной РС осуществляется построение дерева грамматического разбора анализируемой цепочки с выдачей информации о возможных синтаксических ошибках. РC СИН/У допускает естественное распараллеливание в связи с возможностью совместной обработки нескольких узлов на каждом уровне дерева, в зависимости от наличных вычислительных ресурсов. Таким образом, приходим к методу параллельного поуровневого нисходящего синтаксического анализа программ. Данный метод дополняет известный метод восходящего параллельного синтаксического анализа. Этот факт обеспечивает сочетание параллельных нисходящего и восходящего методов синтаксического анализа программ на основе стратегий двусторонней и многослойной мультиобработки программ.

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

ЛИТЕРАТУРА.

1. Г. Е. Цейтлин «Введение в алгоритмику» «Сфера» Киев 1998год 310стр. 2. К. Л. Ющенко С. В. Суржко Г. Е. Цейтлин А. И. Шевченко «Алгоритмические алгебры» Киев 1997год 480стр. 3. Г. Е. Цейтлин «Алгебра логики и конструирование программ» «Наукова думка» Киев 1994год 84стр.

Описание предмета: «Психология»

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

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

наук, изучающих природу и общество.

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

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

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

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

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

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

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

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

Внимание!

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

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