Содержание к диссертации
Введение
ГЛАВА 1. Контекстно-свободные языки, их синтаксический анализ и коммутативные образы 47
1.1. Контекстно-свободные грамматики и порождаемые ими языки 47
1.2. Идентификаторы языков программирования и их задание контекстно-свободными грамматиками 55
1.3. Проблема синтаксического анализакс-языков программирования 59
1.4. Коммутативные образы (производящие функции) кс-языков 63
ГЛАВА 2. Фундаментальные свойства коммутативных образов контекстно-свободных языков 66
2.1. Решение проблемы установления алгебраичности суммы степенного ряда (коммутативного образа формального языка) 66
2.2. Коммутативные образы кс-языков: связь с линейными языками..73
2.3. Коммутативные образы кс-языков как диагонали рядов Лорана рациональных функций 97
2.4. Конструктивное представление и приближенное вычисление коммутативных образов кс-языков 103
2.5. Фундаментальные свойства множеств сходимости коммутативных образов формальных языков 109
ГЛАВА 3. Распознавание контекстно-свободных языков: необходимые условия 117
3.1. Теорема Эйзенштейна для коммутативных образов кс-языков 117
3.2. Условия для коммутативных образов, сгруппированных по однородным многочленам 124
3.3. Условия для коммутативных образов, сгруппированных в ряды Гартогса 133
ГЛАВА 4. Распознавание контекстно-свободных языков достаточные условия для коммутативных образов 140
4.1. Достаточное условие алгебраического продолжения коммутативного образа языка 140
4.2. Композиция Адамара формальных языков и их коммутативных образов 153
4.3. Кс-языки и композиция Адамара линейных языков 159
4.4. Характер особенностей композиции Адамара линейных языков.172
4.5. Диагонали линейных языков 181
4.6. Композиция Адамара сгруппированных линейных языков 190
ГЛАВА 5. Вычислительное распознавание контекстно-свободных языков и грамматик 193
5.1. Решение проблемы вычислительного распознавания коммутативных образов кс-языков 193
5.2. Аффинные кс-грамматики и кс-языки 198
5.3. Опередепители Ганкеля и алгебраическая зависимость кс-языков 205
ЛИТЕРАТУРА 208
ПРИЛОЖЕНИЕ 228
- Контекстно-свободные грамматики и порождаемые ими языки
- Решение проблемы установления алгебраичности суммы степенного ряда (коммутативного образа формального языка)
- Теорема Эйзенштейна для коммутативных образов кс-языков
- Достаточное условие алгебраического продолжения коммутативного образа языка
- Решение проблемы вычислительного распознавания коммутативных образов кс-языков
Введение к работе
Актуальность исследования. Фундаментальным свойством большинства языков программирования является принадлежность классу контекстно-свободных языков (кс-языков), которые были введены в 50-х годах прошлого века выдающимся американским лингвистом Н. Хомским. Действительно, описание языка программирования определяет действующие в нем правила подстановки (продукции), совокупность которых является контекстно-свободной грамматикой (кс-грамматикой) и порождает соответствующий кс-язык, В связи с этим среди формальных языков Хомского именно кс-языки играют наиболее важную роль в теоретическом программировании. Основные аспекты проблематики, связанной с исследованием различных языков программирования, например, проблема определенности (однозначности) языка, его синтаксического и семантического анализа и др., могут быть рассмотрены с общей точки зрения, а именно, применительно к кс-языкам.
Пусть X = {х1,...,хп\ — конечное множество терминальных символов (слов) языка, например, операторов языка программирования, букв, цифр и т.д., a Y ={ух,...,ут} - множество нетерминальных символов, необходимых для задания грамматики языка, у, — символ (аксиома), означающий начало предложения (программы). На множестве X U Y введены операции конкатенации и формальной суммы, а также умножения на элементы числового поля. Тогда грамматике сопоставляется система полиномиальных символьных уравнений Хомского-Щютценберже
yt=Pi(x,y), і = 1,...,т, (1)
называемая собственной системой, коэффициенты которой удовлетворяют оп
ределенным условиям. Первая компонента у, решения (у\(х) Ут(х)) этой сис
темы, полученного методом последовательных приближений в виде формаль
ных степенных рядов от xi,..., хт является данным кс-языком, т.е. формальной
суммой мономов — всех предложений (программ) данного языка. Важнейший
подкласс кс-языков образуют наиболее простые из них - линейные, в частно-
сти, регулярные языки, для которых все многочлены системы (1) линейны по yJ3 j = 1,...,т.
Ранее в исследовании кс-языков основную роль играли методы алгебры и дискретной математики, например, анализ деревьев вывода мономов. При этом изучение символьной системы (1), которая содержит полную информацию о кс-языке, не проводилось. Прежде всего, это было связано с недостаточно разработанными методами многомерного комплексного анализа, позволяющими исследовать решения таких систем. Несмотря на значительные результаты, применение методов дискретной математики не позволило решить целый ряд важных проблем, например, проблему В.М. Глушкова распознавания кс-языков Хомского, т.е. установления их «внутренних» характеристических свойств, отличающих кс-языки от произвольных формальных языков над фиксированным множеством терминальных символов, проблему беступикового синтаксического анализа таких языков, проблему изучения кс-языков Хомского по свойствам системы уравнений Хомского-Щютценберже (1) и многие другие. В настоящей диссертации на основе полученных новых результатов в области комплексного анализа получены новые методы распознавания кс-языков и изучения их свойств, что имеет значительную актуальность в теории программирования.
Цель работы. Получение новых методов распознавания кс-языков (в том числе, языков программирования) и изучения их свойств на основе исследования определяющей системы (1).
Методика исследования. В диссертации использованы методы алгебры, комплексного анализа и теории формальных грамматик.
Научная новизна. Основные результаты диссертации состоят в следующем:
-
Решена проблема В.М. Глушкова распознавания кс-языков Хомского (в том числе, языков программирования), указаны соответствующие вычислительные алгоритмы.
-
Получен ряд новых необходимых, а также достаточных условий принадлежности формального языка классу кс-языков.
3. Разработан алгоритм беступикового синтаксического анализа кс-
языков (языков программирования), основанный на предложенном автором ме
тоде «мономиальных меток».
-
Решена проблема установления алгебраичности суммы степенного ряда - доказан критерий алгебраичности, обобщающий известный критерий Кроне-кера о рациональности (1881 г.); полученный результат используется в диссертации при исследовании кс-языков.
-
В соответствии со свойствами системы (1) введен широкий класс нелинейных аффинных кс-языков, для которых доказано, что они образуются из линейных языков над более широким терминальным множеством в результате простой «процедуры диагонализации»; тем самым частично решена проблема определения свойств кс-языка по системе уравнений Хомского-Щготценберже.
Все основные результаты диссертации являются новыми и получены лично автором.
Теоретическая значимость. Полученные в диссертации результаты существенно развивают теорию кс-языков программирования. Они доказаны новыми для этой теории методами, которые могут быть полезными и в дальнейших исследованиях.
Практическая значимость. Предложенный алгоритм беступикового синтаксического анализа необходимо использовать при исследовании языков программирования. В частности, этим методом можно установить, однозначны ли программы любой заданной длины N, что важно при разработке новых языков программирования; результаты дают принципиальную возможность вычислительного распознавания кс-языков, что позволяет решать новые задачи в теории кодирования информации.
Апробация работы. Результаты диссертации докладывались в Красноярском государственном техническом университете, Красноярском, Новосибирском, Томском государственных университетах, Институте математики им. С.Л. Соболева СО РАН, Институте динамики систем и теории управления СО РАН,
на всесоюзных, всероссийских и международных конференциях по комплексному анализу и его приложениям (1982—2003 гг.),
на Сибирских конгрессах по индустриальной и прикладной математике (1998 г., 2000 г.),
на международных и всероссийских конференциях по математическим моделям и методам их исследования (1997-2003 гг.),
на Сибирских научных школах-семинарах с международным участием по проблемам компьютерной безопасности и криптографии (2003, 2005 гг.),
на всероссийской конференций с международным участием «Математика, ее приложения и математическое образование» (2005 г.),
на всероссийской конференции «Математика, информатика, управление» (2005 г.) и др.
Публикации. По теме диссертации опубликовано более 30 работ, наиболее значительные из которых приведены ниже, из них 10 работ опубликованы в журналах, которые включены ВАК в Перечень ведущих научных рецензируемых журналов и изданий, а также в иностранных научных рецензируемых журналах. Основные результаты диссертации опубликованы в изданиях, входящих в указанный Перечень. Из работы [2], выполненной в соавторстве, в диссертацию включены результаты, принадлежащие лично автору.
Структура диссертации. Диссертационная работа состоит из введения, вспомогательной главы, пяти глав и списка литературы.
Контекстно-свободные грамматики и порождаемые ими языки
Как уже отмечалось, фундаментальным свойством большинства языков программирования является принадлежность классу контекстно-свободных языков (кс-языков), которые были введены в 50-х годах прошлого века выдающимся американским лингвистом Н. Хом-ским, заложившим основы теории кс-языков [113-119]. Действительно, в описании языка программирования определяются действующие в нем правила подстановки (продукции), совокупность которых является контекстно-свободной грамматикой (кс-грамматикой), порождающей соответствующий кс-язык программирования (напр., [5-8, 14, 22, 26, 27, 39, 41, 42, 46, 49, 53, 60, 65, 68, 70, 120]). Таким образом, основные аспекты проблематики, связанной с исследованием различных языков программирования (к их числу относятся проблемы определенности языка, его синтаксического и семантического анализа и др.), могут быть рассмотрены с общей точки зрения, а именно, применительно к изучению свойств кс-языков, определяемым следующим образом.
Пусть конечное множество X = {1,...,} терминальных символов (слов) языка, например, операторов языка программирования, букв, цифр и т.д., а У = {у\,... ,ут] — множество нетерминальных символов, необходимых для задания грамматики языка, yi — символ (аксиома), означающий начало программы (предложения); на множестве X U Y введены операции конкатенации и формальной суммы, а также умножения на элементы числового поля.
Рассмотрим кс-язык, порожденный совокупностью продукций (грамматикой) где fij(x, z) мономы от некоммутативных символьных переменных из X U Y (левая часть продукций содержит единственный символ и применяется независимо от контекста, а потому грамматика называется кс-грамматикой); как отмечалось, у\ — выделенный символ, означающий начало программы (предложения).
Решение проблемы установления алгебраичности суммы степенного ряда (коммутативного образа формального языка)
Коммутативные образы кс-языков являются алгебраическими функциями, и потому их изучение невозможно без установления характеристических свойств степенных рядов, представляющих функции этого класса.
Пусть степенной ряд сходится в окрестности начала координат. Вопрос о рациональности его суммы возникает в различных областях математики и ее приложениях в технике. Так, рациональными являются передаточные функции цифровых фильтров, а также коммутативные образы (производящие функции) линейных, в том числе, регулярных языков.
Этот вопрос решается хорошо известным критерием Кронекера (1881 г.) [17, с. 173], согласно которому рациональность суммы ряда равносильна тому, что при j JQ,1 IQ, равны нулю определители
Ганкеля равенства легко получаются, если умножить ряд (2.1) на многочлен, который является знаменателем его суммы - рациональной функции. Более точно, критерий Кронекера связывает рациональность с обращением в нуль определителей HQ , что равносильно исходной формулировке в силу свойств определителей Ганкеля.
Вопрос о существовании критерия, позволяющего определить алгеб-раичность суммы степенного ряда по его коэффициентам, оставался открытым, хотя класс алгебраических функций всегда вызывал большой интерес как математиков, так и специалистов, связанных с приложениями математики. Очевидно, что этот вопрос сводится к тому, как адекватно сформулировать условия на коэффициенты степенного ряда, которые получаются в результате его подстановки в полиномиальное (нелинейное) уравнение, определяющее его сумму.
Теорема Эйзенштейна для коммутативных образов кс-языков
Теорема 2.2 связывает коммутативные образы кс- и линейных языков. Как уже отмечалось, структура последних (степенных рядов рациональных функций) достаточно изучена. Например, рациональность суммы степенного ряда akzk эквивалентна тому, что а& = q(k), к Є N, где q{x) — квазимногочлен. Другим критерием рациональности является равенство нулю ганкелевых определителей; det(ai+ _2)y=i = О при к кн. Известен также критерий рациональности суммы кратного степенного ряда — коммутативного образа линейного языка (см., напр., [128, с. 96], [124]). Эти условия получаются применением одномерного критерия по каждой переменной кратного ряда.
Важной задачей является также получение необходимых условий алгебраичности коммутативных образов кс- и линейных языков: невыполнение условий свидетельствует о том, что исследуемый коммутативный образ не принадлежит соответствующему классу.
В связи с этим получим обобщение для коммутативных образов кс-языков известной теоремы Эйзенштейна (1852 г.), дающей эффективное необходимое условие алгебраичности [17, с. 172] суммы степенного ряда одной переменной в следующей ситуации. При изучении свойств функции одной переменной, представленной степенным рядом, большой интерес представляют случаи, когда все коэффициенты ряда — целые, либо рациональные числа; такие ряды наиболее часто встречаются в приложениях (соответственно, ряд называется целочисленным илирациональночисленным). Согласно теореме Эйзенштейна, если коэффициенты a,k степенного ряда алгебраической функции — рациональные числа, то найдется целое число с Ф" О, такое, что числа a,kck —целые, к 1, таким образом, рациональночисленный степенной ряд алгебраической функции f(z) заменой z на cz превращается в целочисленный ряд.
Очевидно, что если коэффициенты ряда — целые, и функция не является многочленом, то радиус сходимости ряда г 1. Фату в 1904 г. доказал, что если ряд имеет целые коэффициенты и представляет рациональную функцию, и г = 1, то все полюсы этой функции расположены в корнях целой степени из 1, если же такой ряд представляет алгебраическую иррациональную функцию, то обязательно г 1 [17].
Достаточное условие алгебраического продолжения коммутативного образа языка
Вопрос, рассматриваемый в данном разделе, состоит в том, чтобы исследовать, является ли коммутативный образ формального ряда алгебраической функцией, на минимально возможном множестве точек.
Следующая теорема дает достаточное условие алгебраического продолжения коммутативного образа некоторого формального языка — голоморфной в окрестности нуля функции, позволяющее провести такую проверку только на части границы некоторой области, и обобщает граничную теорему Э. Леви о рациональности по одному переменному [122, с. 216] на алгебраические функции произвольного числа переменных.
Теорема 4.1. Пусть коммутативный образ формального языка f(z ,Zn) голоморфен в области!) = V X Vn С С","1 хС и непрерывен в V, причем граница области V — кусочно гладкая. Предположим, что на дТ есть множество Е положительной (2п—3) меры, такое, что при каждом фиксированном ( Є Е функция f(( ,zn) алгебраич-на по zn. Тогда при каждом фиксированном ( Є V функция f(( ,zn) также алгебраичиа по переменной гп.
Не теряя общности, считаем, что О Є V. Из условия теоремы следует, что в некоторой окрестности начала координат функция раскладывается в ряд Гартогса и коэффициенты Ck{z ) этого ряда продолжаются до голоморфных в V и непрерывных в V функций [122, с. 216].
Решение проблемы вычислительного распознавания коммутативных образов кс-языков
Как отмечалось, серьезным препятствием для вычислительного распознавания кс-языков являлось отсутствие критерия алгебраичности суммы степенного ряда. Такой критерий, обобщающий известный критерий Кронекера, был получен в разделе 2,1 диссертации, что позволяет сформулировать алгоритм вычислительного рапознавания коммутативных образов кс-языков. Этот алгоритм заключается в следующем.
Рассмотрим коммутативный образ формального языка — степенной ряд
Если язык — контекстно-свободный, то функция (5.1) — голоморфная в нуле и алгебраическая. Рассмотрим, как установить это в случае функции одной переменной. Пусть степенной ряд сходится в окрестности нуля. В разделе 2.1 было показано, что алгеб-раичность эквивалентна обращению в нуль обобщенных ганкелевых определителей некоторой степени где число q — (I -f l)rf — 1.
Подразумевается, что задан общий вид коэффициентов ряда at как функции номера к. Тогда необходимо:
1) вычисляя определители Ганкеля как функции номеров j, I, проверить, равны ли они нулю;
2) вычислить коэффициенты агк как функции номера и проверить, равны ли нулю значения обобщенных определителей Ганкеля Я- (2);
3) вычислить для следующего значения г коэффициенты ау и ро-верить, обращаются ли в нуль обобщенные определители Ганкеля.
Вычисления продолжаются до тех пор, пока не будет установлено обращение в нуль требуемых определителей, либо будет установлено, что они как функции номеров, не равны нулю (последнее будет означать, что функция трансцендентна).
Полученная теорема дает принципиальную возможность исследовать алгебраических функций многих переменных: согласно алгебраическому варианту фундаментальнной теоремы Гатогса алгебраичность функции, голоморфной в какой-либо области, эквивалентна алгебраичности по каждой переменной в отдельности при фиксированных переменных, Принципиальную возможность установления алгебраичности функции многих переменных дает применение данного алгоритма по каждой переменной кратного степенного ряда (5.1). Действительно, перегруппировывая этот степенной ряд в ряд Гартогса по переменной.
