Классификация, анализ возможностей классических методов синтаксического разбора, их современных модификаций и дальнейших перспектив в рамках задачи создания САПР ПО

Аннотация

Пилипенко А.С., Григорьев А.В., Морозова О.В. Описание, изучение, классификация, сравнение базовых алгоритмов разбора, их модификаций В работе представлено описание базовых алгоритмов, их модификаций, достоинств и недостатков, модифицированного алгоритма, его этапов работы, изменений и отличий от других алгоритмов.

Введение

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

Пользователи для этих целей используют специальные программные сервисы, решающие те или иные задачи и составляющие базовые средства построения САПР ПО. САПР ПО обеспечивают синтез или прямое построение программ. Для решения тех или иных задач применяется ряд методов.

В частности, как один из наиболее перспективных в задаче классификации текстов по назначению можно назвать метод поверхностного анализа текстов [1].

При анализе текстов обязательными являются три этапа: грамматический разбор, синтаксический разбор, семантический разбор [2,3,4]. Рассмотренные в статье алгоритмы являются частью синтаксического разбора.

Каждый язык имеет свой алфавит, он образует грамматику языка. Есть различные виды грамматик, но базовый класс составляют формальные грамматики. Для анализа текстов контекстно-свободных грамматик используются различные алгоритмы разбора (в статье рассмотрены базовые алгоритмы (LL(k), LR(k)), а также их модификации(SLR(k), LALR(k), GLR(k), алгоритм модификации LL и LR, который позволит синтезировать новую грамматику)) [5]. Указанное в скобочках число (k) означает количество шагов, которые смогут просматриваться данным алгоритмом. Как правило, данная цифра указывает на количество стеков, необходимых для их реализации.

Имеются различные подходы к созданию САПР ПО. Одна из них – это Р-технология Вельбицкого [6]. Данная технология делает разбор грамматики, является открытой технологией для ввода любых алгоритмов разбора. Также существует ПРИЗ – технология [7], именно благодаря данной технологии возникла задача создать генератор программ на основе теоретико-множественных операций (ТМО) над контекстно-свободными грамматиками.

В данной работе мы будем рассматривать роль такого рода алгоритмов в случае их использования для построения САПР ПО на основе подходов теории Концептуального программирования (Тыугу Э.Х.).

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

• Обучение, т.е. создание грамматики, ограниченной только текстами, используемыми для решения поставленной задачи;
• Вывод, т.е. синтез требуемого решения (программы) на основе технического задания.
Алгоритм реализации ТМО, предложенный ранее авторами, собственно и построен на базе комплекса такого рода алгоритмов. Алгоритмы синтаксического разбора, используемые в алгоритме ТМО, были подвержены модификации.

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

Присутствуют явные недостатки алгоритмов ТМО: нет явного ТЗ, неизвестная семантика языка.

Сейчас решаются такие задачи в области ТМО:

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

Таким образом, сейчас все задачи сводятся к объединению задач искусственного интеллекта и САПР ПО. В статье представлен алгоритм, который с помощью ТМО может создавать новые грамматики на основе существующих.

Цель работы:

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

1. Анализ возможностей классических алгоритмов синтаксического разбора

Для того, чтобы понять, что необходимо для их реализации, рассмотрим два самых популярных алгоритма: LL(k), LR(k). Предлагается рассмотреть их реализации, а также их модификации: SLR(1), LALR(1), LR(1).

1.1. Анализ алгоритма LL

Алгоритм LL – это нисходящий алгоритм синтаксического разбора (дословно переводится left left), входной поток в данном алгоритме читается слева направо, выходной выводится тоже слева направо. Используется данный алгоритм для ограниченного класса контекстно-свободных грамматик, однако имеет преимущество: довольно простой и интуитивно понятный. Для построения дерева разбора использует польскую нотацию.

1.2. Анализ алгоритма LR

Алгоритм LR – это восходящий алгоритм синтаксического разбора (дословно переводится left right), входной поток в данном алгоритме читается слева направо, выходной выводится справа налево. Является довольно мощным алгоритмом, в то же время довольно сложным. Для построения дерева разбора использует обратную польскую нотацию.

1.3. Анализ модификаций алгоритма LR

Алгоритмы разбора SLR(1) (дословно: simple left right), LALR(1) (дословно: lookahead left right), LR(1) являются последовательными расширениями друг друга после и их прародителем считается LR(0). SLR (1) работает, когда построение таблицы разбора из-за конфликтов сдвиг – приведение или приведение – приведения невозможно.

Данный алгоритм уже не используется, таблицы для SLR-анализа имеют одинаковый объект с более продвинутой версией: LALR. Алгоритм LALR(1) также является модификацией SLR (1) и используется по той же причине, что и SLR(1) для LR(0).

Большинство используемых языков программирования имеют именно LALR(1)- грамматики, поэтому данного вида анализаторов будет вполне достаточно для разбора их большинства. LR(1) также является улучшенной версией LALR(1). Данный алгоритм называется полной версией, также любая LR(k)-грамматика может быть автоматически преобразована в LR(1) для того же самого языка.

Таблица 1 – Анализ функциональных возможностей классических алгоритмов грамматического разбора

№	Название	Назначение	Краткая характеристика	Используемые структуры данных	Достоинства и Недостатки
1	LL(1)	Необходим для разбора кода в некоторых языках	Входной поток читается слева направо, выходной поток выводится тоже слева направо.	Используется 1 стек, таблица разбора, которая определяет для каждой пары продукцию или признак ошибки.	Достоинство: Может быть реализован вручную, без использования специальных программ Недостаток: Используется для ограниченного класса
2	LR(0)	Необходим для разбора кода в некоторых языках (большее количество, чем у LL)	Входной поток читается слева направо, выходной поток выводится справа налево.	Используется 1 стек, тип для отображения грамматических символов, массив для хранения грамматик в виде записей, таблица разбора	Достоинства: Имеет более широкий круг языков, которые может анализировать, чем у LL Недостатки: Сложная реализация
3	SLR(1)	Необходим для разбора кода в некоторых языках (большее количество, чем у LR(0))	Алгоритм является простой модификацией, основан на алгоритме LR(0), работает когда построение таблиц разбора невозможно.	Используются те же структуры, что и в LR(0). Различаются лишь алгоритмы построения таблицы разбора.	Достоинства: Возможность анализировать больше грамматик, нежели  с помощью LR(0). Недостаток: Устарел, есть более новая модификация
4	LALR(1)	Необходим для разбора кода в некоторых языках (больше, чем SLR(1))	Основан на алгоритме SLR(1), работает когда построение таблиц разбора невозможно.	Используются те же структуры, что и в LR(0). Различаются лишь алгоритмы построения таблицы разбора.	Достоинства: Возможность анализировать больше грамматик, нежели  с помощью SLR(1). Недостаток: Устарел
5	LR(1)	Может разбирать любую контекстно-свободную однозначную грамматику	Основан на алгоритме LALR(1), работает, когда построение таблиц разбора невозможно.	Используются те же структуры, что и в LR(0). Различаются лишь алгоритмы построения таблицы	Достоинства: Возможность анализировать больше грамматик, нежели  с помощью LALR(1). Недостатки: Высокая сложность реализации

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

Рассматриваемый [8,9,10] алгоритм выполнения ТМО является комбинированной версией стандартных алгоритмов синтаксического анализа, в частности, алгоритмов LR и LL. Также используется прямой и обратный проходы.

Функциями данного алгоритма являются:

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

Алгоритм ТМО создаёт новую грамматику с помощью теоретико-множественных операций над грамматиками: пересечение, объединение, разность, дополнение.

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

Таблица 2 – Характеристика алгоритма ТМО над контекстно-свободными грамматиками как  комбинации модифицированных классических алгоритмов грамматического разбора

№	Этап работы	Аналог	Модификация	Новый функционал	Структуры данных
1	Алгоритм записи в стек	LR	Изменения записи в стек	Каждый терм записывается в отдельную ячейку стека и совокупность термов накрывается специальным знаком &. Каждый синтерм записывается в отдельную ячейку стека. Знак операции, соединяющий подмножества - в вершине стека.	Вход: правая часть множества, записанная в регистр ZAKON Выход:STEK
2	Алгоритм разложения	LR	Отличается алгоритм дозаписи	Если нашли, то записи правой части вSTEK, затем дозапись в STEK1 и STEK2, а синтерма – в VSTEK1 или VSTEK2 соответственно с признаком R.	Вход: один элемент множества Выход: TORM (таблица определения идентификаторов множеств)
3	Алгоритм сворачивания	LL, LR	Алгоритм отличается в связи с записью данных в различные структуры в зависимости от признака	Для реализации алгоритма используется тиной набор структур данных.	Вход: STEK,TCH (текущее значение счётчиков амперсендов),TORM, PRST (признак стека), VSTEK (вспомогательный стек, их два, предназначены для левого и правого множеств). Выход: STEK ,THNA (таблица счётчиков номеров амперсендов)
4	Алгоритм прямого хода	LL	Заключается в сравнении имён множеств	Отличие заключается в нахождении несовпадения и не выводе ошибки, а подаче сигнала о создании новой грамматики.	Вход: STEK1, STEK2, VSTEK1,VSTEK2,TORM Выход: STEK1,STEK2,VSTEK1, VSTEK2
5	Алгоритм обратного хода	LR	Перепись и создание новой грамматики	Cоздаются новые грамматики, а не выдают ошибку.	Вход: STEK1, STEK2,VSTEK1,VSTEK2, TORM, THAN Выход: TORM

Существующий алгоритм ТМО имеет такие недостатки:

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

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

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

Проделанный анализ позволит обеспечить решение данной задачи.

Заключение

В предлагаемой работе решено две задачи: 1) анализ существующих стандартных методов синтаксического анализа; 2) анализ их модификаций в рамках создания алгоритма ТМО над контекстно-свободными грамматиками.

По задаче №1 можно сделать вывод, что классические алгоритмы имеют ряд недостатков, в том числе описанных в введении. Однако, их анализ и модификация является важным шагом для перспективного развития области САПР ПО.

По задаче №2 выполнены:

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

Как перспективную задачу можно определить:

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

Литература

• 1. Свердлов С. З. Введение в методы трансляции: Учебное пособие. – Вологда: Издательство Русь, 1994. – 80 с.
• 2. Серебряков В.А., Галочкин М.П. Основы конструирования компиляторов. УРСС, 2001. – 224 с.
• 3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В двух томах. Т.1. Синтаксический анализ. Пер. Агафонова В.Н. Под. ред. Курочкина В.М. Мир, М.: 1978, с. 614.
• 4. М. Грос, А. Латен. Теория формальных грамматик. Мир, М.: 1971. с. 295.
• 5. В. Алферова. Теория алгоритмов. Статистика, М.: 1973. с. 165.
• 6. И.В. Вельбицкий, В.Н. Ходаковский, Л.И. Шолмов. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ – 6. – Москва: Статистика, 1980. – 263 с., ил.
• 7. Тыугу Э. Х. Концептуальное программирование .– М.: Наука. Главная редакция физикоматематической литературы, 1984. – 256 с., ил.
• 8. Григорьев А.В. Пути создания интеллектуальных САПР при различных уровнях квалификации экспертов /Научно-теоретический журнал Искусственный интеллект, №3, 2005. – Донецк: ИПИИ МОН и НАН Украины Наука и образование, 2005. – С. 758 – 763.
• 9. Григорьев А.В. Теоретико-множественные операции над грамматиками как механизм работы со знаниями в интеллектуальных САПР. Вiсник Схiдноукраiнського нацiонального унiверситету iменi Володимира Даля, N 2(48). Луганск, ВУТУ, 2002. – С. 186 – 194.
• 10. Григорьев А.В. Алгоритм выполнения теоретико-множественных операций над грамматиками в среде специализированной оболочки для создания интеллектуальных САПР. Науковi працi нацiонального технiчного унiверситета. Серия Проблемы моделирования и автоматизации проектирования динамических систем (МАП – 2002). Выпуск 52: Донецк: ДонНТУ, 2002. – С.83 – 93.