Реферат на тему:


Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск






Загрузка...
Национальная академия наук Украины

Национальная академия наук Украины

Институт кибернетики имени В. М. Глушкова

На правах рукописи

КОНДРАТЕНКО Виктория Александровна

УДК 681.3

аксиоматическую МОДЕЛИ И МЕТОДЫ

ПРОЕКТИРОВАНИЕ ЛИНГВИСТИЧЕСКИХ транслятор

01.05.03 математическое и программное обеспечение

вычислительных машин и систем

Диссертация на соискание ученой степени

кандидата физико-математических наук

Киев-2001

Актуальность темы исследования.

Работа выполнена в Институте кибернетики имени В.М. Глушкова НАН Украины.

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

Провотарь Александр Иванович, Киевский

Государственный лингвистический университет

заведующий кафедрой информатики.

Официальные оппоненты: доктор физико-математических наук, профессор

Вельбицкий Игорь Вячеславович

Международный научный центр технологии программирования

ТЕХНОСОФТ НАН Украины, директор.

кандидат физико-математических наук, доцент

ШКИЛЬНЯКСтепан Степанович

Киевский национальный университет имени Тараса Шевченко

Ведущая организация: Институт программных систем НАН Украины.

Защита состоится 25.05.2001 г.. В 14 часов на заседании диссертационного совета Д26.194.02 при Институте кибернетики имени В.М. Глушкова НАН Украины по адресу:

03680 МСП Киев 187, проспект Академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

Автореферат разослан 23.04.2001 г..

Ученый секретарь

диссертационного совета СИНЯВСКИЙ В.Ф.

Общая характеристика работы

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

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

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

Отметим, что предложенный в диссертации подход к проектированию лингвистических трансляторов, в основе которого лежат методы искусственного интеллекта, стало возможным благодаря теоретическому и практическому доработку как зарубежных (М. Дэвис, П. Гилмор, Х. Патнэм, Дж. Робинсон, Новиков П. С., Поспелов Г. С.), так и отечественных ученых (Сергиенко И.В., Редько В.Н., Андон П.И., Скурихин В.И., Капитонова Ю.В., Летичевский А. А .).

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

Для достижения поставленной цели в работе решались следующие задачи:

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

- разработка правил эквивалентных преобразований продукций контекстно-свободных (КВГ) и атрибутные транслирующих грамматик (КЗГ) в правила логики предикатов;

- разработка алгоритма трансляции на основе резолютивной вывода;

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

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

Научная новизна. В диссертации получены следующие новые результаты:

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

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

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

- доказано ряд теорем для абстрактных моделей логических исчислений;

- построены обобщенные конструкции алгоритма унификации и метода резо-Люций;

- реализованы основные компоненты языка GIPLANG в системе программирования Arity Prolog.

Практическая ценность. Диссертационная работа выполнялась в Институте кибер-нетикы им. В.М. Глушкова НАН Украины в соответствии с планами научно-технических работ по темам: & ldquo; разработка и обоснование основ процедурно-объектного макромодульного программирования и соответствующих эффективных ин-ментальных средств создания прикладных программных систем на ПЭВМ для различных интегрированных сред и приложений & rdquo; (В.Ф.155.01), & ldquo; Создание ком-пьютерних систем методами макромодульного программирования & rdquo; (М.Н.155. 02).

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

Апробация. Основные результаты диссертационной работы докладывались и обсуждались на XIX и XX Международных научно-технических конференциях "Проблемы физической и биомедицинской электроники" (Киев, 1999-2000), Республиканском семинаре "Оптимизация вычислений" (Киев, 1986),Семина-рах научного совета НАН Украины по проблеме & ldquo; Кибернетика & rdquo; (Киев, 1985-2000), конференциях молодых ученых и специалистов Института кибернетики и Национального технического университета "КПИ".

Публикации. По теме диссертации опубликовано 8 работ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы (81 наименования). Общий объем работы 130 страниц.

содержание работы

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

Пусть задана множество компьютеров С = {c1, с2, ..., Сn}; множество архитек-ных типов компьютеров А = {a1, a2, ..., аm}; множество уровней функциональной полноты компьютеров F = {f1, f2, ..., fd}; множество длительностей выполнения проце-сорных команд В = {b1, b2, ..., bh}; множество типов команд Т = {t1, t2, ..., tg}; множество потребительских ценностей компьютеров S = {s1, s2, ..., sq} и предикаты: Т (ci, aj) - & lt; компьютер си относится к архитектурному типу aj & gt ;; Ф (ci, fk) - & lt; ком-пьютер си имеет функциональную полноту уровня fk & gt ;; Р (си, tx, uy, uz, bw) - & lt; продолжительность выполнения компьютером ci процессорной команды типа tx, первый операнд которой размещен в уровне памяти uy, а второй - в уровне памяти uz, составляет bw периодов тактовой частоты & gt ;; S (ci, se) - & lt; потребительская стоимость компьютера си равна se & gt ;; VIG (ci, aj, fk, tx, uy, uz, bw, se) - & lt; компьютер си имеет архитектурный тип aj, функ-нальных полноту fk, продолжительность выполнения команды tx-типа, первый операнд которой размещен в уровне памяти uy, второй операнд - в уровне памяти uz, равную bw и потребительскую вармость, равную se & gt ;. Тогда математическая модель задачи выбора ком-тера необходимого качества задается формулой

($ aj) ($ fk) ($ bw) ($ se) ($ tx) ($ uy) ($ uz) ($ ci) (VIG (ci, aj, fk, tx, uy, uz, bw, se) Ю

Ю (T (ci, aj) Щ F (ci, fk) Щ R (ci, tx, uy, uz, bw) Щ S (ci, se))).

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

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

В парарафи 2.1 приводится упрощенная структура компилятора, который состоит из трех блоков - лексического, синтаксического, генератора кодов и рабочих таблиц компилятора. При этом лексический блок предназначен для разбиения предложения на лексемы. Синтаксический блок переводит последовательность лексем в другую последовательность, которая более точно отражает порядок, в котором должны выполняться операции в программе. Генератор кода & ldquo; разворачивает & rdquo; атомы, построенные синтаксическим блоком, в последовательность команд процессора, которые выполняют соответствующие действия. И, наконец, рабочие таблицы компилятора содержат данные, которые используются при работе его блоков.

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

G = (V, T, P, S),

где V - конечное множество структурных элементов языка (нетерминальных символов) T - конечное множество лексем языка (терминальных символов) P - конечное множество правил (продукций) взаимосвязи как между элементами множества V, так и между структурными элементами и лексемами; S - начальный нетерминальный символ, с которого начинается вывод допустимых фраз в этой грамматике.

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

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

будет иметь вид

1. & Lt; E & gt; = & Gt; & Lt; E & gt; + & Lt; T & gt; {+};

2. & Lt; E & gt; = & Gt; & Lt; T & gt ;;

3. & Lt; T & gt; = & Gt; & Lt; T & gt; & lt; P & gt; {};

4. & Lt; T & gt; = & Gt; & Lt; P & gt ;;

5. & Lt; P & gt; = & Gt; (& Lt; E & gt;);

6. & Lt; P & gt; = & Gt; a {a};

7. & Lt; P & gt; = & Gt; b {b};

8. & Lt; P & gt; = & Gt; c {c}.

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

В параграфе 2.3 определяется понятие синтаксически управляемых переводов (СК-переводов) в отношении транслирующих грамматик. Такие перевода образует ются из выражений входного языка и выражений из символов действия. Исходный язык произведу ется входной грамматикой, которую получают из транслирующей грамматики путем изъятия из ее продукций символов действия. Выражения из символов действия - это синонимы Постфиксная польских форм записи, соответствующие инфиксное арифметич ным выражениям входного языка. Такому синтаксически управляемом переводу, которое определяется транслирующим грамматикой, относится, например, пара & lt; a + b c, {a} {b} {c} {} {+} & gt;.

Пусть S и D - два алфавита и T Н S г D - произвольное отношение на паре языков L Н S , l Н D (L - область определения, а l - множество значений отношения).

Определение. Схеме СК-перевода называется пятерка U = (N, S, D, R, S), где N - множество нетерминальных символов; S - входной алфавит; D - выходной алфавит; R - конечное множество правил вида A®a, b, где AО (N ИS) Bо (NИD) и вхождения нетерминалов в слово b образует перестановку вхождений нетерминалов в слово a; S - начальный нетерминал с N.

Отношением перевода, заданного схеме U, называется множество пар {(x, y) зело (S, S) Ю (x, y), xОS и yОD }.

Отношение перевода TНS ґD на пару языков LН S , l Н D называется отношением трансляции, если область его определения решаемая.

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

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

Определение. Атрибутными транслируя грамматика - это транслируя грамматика, в которой

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

- все атрибуты нетерминальных символов и символов действия делятся на наследственные и синтезированные;

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

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

Введем символы действия {ДОБАВИТЬ}, {умножить}, которые соответствуют атомам ДОБАВИТЬ и умножить. Тогда АТГ грамматика перевода инфиксное арифметических выражений в эквивалентные арифметические выражения в Постфиксная польском форме записи будет иметь вид

1) & lt; E & gt; x = & gt; & Lt; E & gt; q + & lt; T & gt; r {ДОБАВИТЬ} y, z, p

(x, p) ¬ НОВТ y ¬ q z ¬ r;

2) & lt; E & gt; x = & gt; & Lt; T & gt; p

x ¬ p;

3) & lt; T & gt; x = & gt; & Lt; T & gt; q & lt; P & gt; r {умножить} y, z, p

(x, p) ¬ НОВТ y ¬ q z ¬ r;

4) & lt; T & gt; x = & gt; & Lt; P & gt; p

x ¬ p;

5) & lt; P & gt; x = & gt; (& Lt; E & gt; p)

x ¬ p;

6) & lt; P & gt; x = & gt; & Lt; I & gt; p

x ¬ p

где & lt; E & gt; - начальный нетерминальный символ НОВТ означает, что значение p, x должны исчисляться с помощью процедуры НОВТ.

Такая АТГ позволяет вычислять значения синтаксически правильных арифметических выражений.

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

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

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

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

- правая часть каждого правила логики предикатов соединяет между собой с помощью

Загрузка...

Страницы: 1 2 3






Ещё Рефераты по вашей теме

Эффективность комплексной терапии больных хронический гастродуоденит - Автореферат
ФОРМИРОВАНИЕ изменения сердечно-сосудистой системы и ее клинико-функциональных ОСОБЕННОСТИ У ДЕТЕЙ С ХРОНИЧЕСКИМИ бронхолегочной ЗАБОЛЕВАНИЯМИ - Автореферат
ФОРМИРОВАНИЕ воспроизводственных способностей у быков-производителей абердин-ангусской ПОРОДЫ - Автореферат
Структурные, семантические и функциональные особенности имен современного немецкого языка (на материале личных имен, прозвищ и псевдонимов) - Автореферат
ПРОЦЕССЫ ЭЛЕКТРОННОГО ВОЗБУЖДЕНИЯ АВТОИОНИЗАЦИЙНИХ СОСТОЯНИЙ атома лития - Автореферат
условия обеспечения макроэкономической сбалансированности и их применение в регулирования банковской системы - Автореферат
Источники зимостойкости для селекции озимой М 'ЛИБО пшеницы В Лесостепи УКРАИНЫ - Автореферат