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

• Автор: Сафонов, Константин Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Красноярск
• Количество страниц: 237 с.

Оглавление
ВВЕДЕНИЕ.

0.1. Проблематика исследования

0.2. О содержании диссертации

ВСПОМОГАТЕЛЬНАЯ ГЛАВА

ГЛАВА 1. Контекстносвободные языки, их синтаксический анализ и коммутативные образы

1.1. Контекстносвободные грамматики и порождаемые ими языки

1.2. Идентификаторы языков программирования и их

задание контекстносвободными грамматиками.

1.3. Проблема синтаксического анализа

ксязыков программирования.

1.4. Коммутативные образы производящие функции ксязыков
1 ГЛАВА 2. Фундаментальные свойства коммутативных образов
контекстносвободных языков
2.1. Решение проблемы установления алгебраичности суммы степенного ряда коммутативного образа формального языка
2.2. Коммутативные образы ксязыков связь с линейными языками
2.3. Коммутативные образы ксязыков как диагонали
рядов Лорана рациональных функций
2.4. Конструктивное представление и приближенное
вычисление коммутативных образов ксязыков.
2.5. Фундаментальные свойства множеств сходимости
коммутативных образов формальных языков
ГЛАВА 3. Распознавание контекстносвободных языков необходимые условия
3.1. Теорема Эйзенштейна для коммутативных образов ксязыков
3.2. Условия для коммутативных образов, сгруппированных
по однородным многочленам
3.3. Условия для коммутативных образов, сгруппированных
в ряды Гартогса
ГЛАВА 4. Распознавание контекстносвободных языков достаточные условия для коммутативных образов
4.1. Достаточное условие алгебраического продолжения коммутативного образа языка
4.2. Композиция Адамара формальных языков и
их коммутативных образов.
4.3. Ксязыки и композиция Адамара линейных языков.
4.4. Характер особенностей композиции Адамара линейных языков.
4.5. Диагонали линейных языков.
4.6. Композиция Адамара сгруппированных
линейных языков
ГЛАВА 5. Вычислительное распознавание
контекстносвободных языков и грамматик
5.1. Решение проблемы вычислительного распознавания коммутативных образов ксязыков
5.2. Аффинные ксграмматики и ксязыки
5.3. Опеределители Ганкеля и алгебраическая
зависимость ксязыков.
ЛИТЕРАТУРА


Итерации метода последовательных приближений порождают мономы возрастающей длины, и через конечное число шагов их степень (число символов Xiy. Считывая” мономы необходимой степени и пропуская при этом метки Ujy можно определить, есть ли среди них моном w. Каждая переменная Uj, содержащаяся в соответствующем мономе, указывает, что при его выводе использована продукция t/j -> fij(x, у). Тем самым определяется, какие продукции и сколько раз использованы при выводе монома w (написании программы) с точностью до порядка их применения, а именно это и требуется при решении проблемы синтаксического анализа [1, 5, , , , 5]. Таким образом, в разделе 1. Теорема 1. Метод мономиальных меток, заключающийся в решении системы (0. В разделе 1. Пример. Проведем данным методом синтаксический анализ фрагмента арифметической программы (((а 4- Ь) * Ь) * Ь) на языке программирования, который порожден грамматикой, содержащей систему продукций: у -> (yi * у2)у У -> (а + 6), t/l -> b. Запишем систему (0. У2) использована дважды, продукция у (а + Ь) -один раз, и продукция у^ Ь - два раза. Теорема 1. ЛГ, принципиально возможно установить, будут ли однозначными все программы, длина которых не превосходит N. Это тем более важно, что доказательство определенности (однозначности) кс-языка, т. Алгоритм теоремы 1. Далее, в разделе 1. Поставим в соответствие формальному степенному ряду (или многочлену) поставим в соответствие ряд (многочлен) с комплексными переменными, задав отображение терминальных и нетерминальных символов из множества X и У в множество комплексных переменных, причем нетерминальными переменными оставляет прежние обозначения, а терминальные символы х;* отображаем в комплексные переменные г], тогда (г,у) € С? Заметим, что коммутативный образ кс-языка является функцией, голоморфной в непустой окрестности нуля. С другой стороны, нельзя не отметить, что коммутативный образ системы символьных уравнений (0. Однако применительно к символьным уравнениям роль корней соответствующих им характеристических уравнений не была изучена в достаточной мере. Как оказалось, характеристические уравнения (в нашем случае -коммутативные образы грамматик в форме Хомского-Щютценберже) позволяют символьных решений (кс-языков), например, свойство такого решения быть ’’диагональю” некоторого языка более простого класса. Глава 2 ’’Фундаментальные свойства коммутативных образов контекстно-свободных языков” посвящена изучению структуры степенных рядов коммутативных образов кс-языков. Коммутативный образ кс-языка, как отмечалось, является голоморфной в окрестности нуля алгебраической функцией, поскольку удовлетворяет системе полиномиальных уравнений, состоящей из коммутативных образов уравнений Хомского-Щютценберже. Согласно алгебраическому варианту фундаментальной теоремы Гартогса [], голоморфная в некоторой области функция, которая алгебраична по каждой переменной при фиксированных значениях остальных, алгебраична по совокупности переменных. Такие условия получены в разделе 2. Вопрос о рациональности суммы степенного ряда решается хорошо известным критерием Кронекера ( г. Актуальный вопрос о существовании подобного критерия, ” распознающего” степенные ряды агебраических функций, оставался открытым. Решение этого вопроса состоит в следующем. X)а*ак-<> а<к] = а^к-,1)ук = °>і»•••»; = 2,з,. Теорема 2. Для того чтобы функция (0. М) . Ганкеля степени 6, а число д = (1+1)6— 1. Теорема 2. Кронекера о рациональности: если функция — рациональная, то степень определяющего ее многочлена б = 1, и имеет место равенство Н^(с1) = Н^ т. Ганкеля. В разделе 2. Коммутативные образы кс-языков: связь с линейными языками” рассмотрен еще один подход к распознаванию коммутативных образов кс-языков. Ь.,2П) ? Сп, Ь = {а = (аь. Щг о,2)= ? Теорема 2. Для того чтобы голоморфная в окрестности нуля функция (0. Даьа) и необходимо существование голоморфной в нуле рациональной функции (0. З1,. Зп), А - унимодулярная матрица порядка п с неотрицательными целыми элементами. Ряд (0. А для этих рядов выполнено условие (0. Замечание. Если А = Е, Е — единичная матрица, то условие (0. Яаиа] а = (аь. В случае п = 1 теорему 2. Теорема 2.