ПРОГРАММИРОВАНИЕ, 2008, Ml, с. 61-66
— ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
НЕЙТРАЛИЗАЦИЯ СИНТАКСИЧЕСКИХ ОШИБОК В ГРАФИЧЕСКИХ ЯЗЫКАХ
© 2008 г. О. Г. Шаров, А. Н. Афанасьев
Ульяновский государственный технический университет 432027 Ульяновск, ул. Северный Венец, 32 E-mail: o.sharov@ulstu.ru Поступила в редакцию 24.09.2006 г.
Большинство анализаторов современных формальных текстовых языков способны обнаружить более одной ошибки за один проход. Проблеме нейтрализации синтаксических ошибок в диаграммах графических языков уделяется мало внимания. Авторами предпринята успешная попытка построения методики анализа формальных графических языков, обеспечивающей обработку ошибок.
1. НЕЙТРАЛИЗАЦИЯ ОШИБОК
Несмотря на большой интерес исследователей к графическим языкам и средствам их синтаксического анализа, проблеме нейтрализации синтаксических ошибок уделяется мало внимания. В то же время, эффективные технологии обработки ошибок необходимы для анализаторов графических языков, которые используются при построении инструментария для редактирования и трансляции или компиляции реализованных диаграмм. Такой анализатор должен быть способен давать точные и наглядные сообщения об ошибках и обеспечивать обнаружение как можно большего количества ошибок за один проход.
В статье [1] авторы предлагают два метода нейтрализации ошибок, которые дополняют друг друга и интегрируются в анализатор реляционных грамматик [2].
• Подмена атрибутов (Attribute Patching). Идея метода состоит в том, что пассивные состояния, представляющие нетерминалы, могут быть безопасно созданы при частичном анализе при условии, что проанали-зированые символы из правой части обеспечивают формирование всех расширенных атрибутов. Это гарантирует, что следующие действия анализатора, действующие на состояние, не будут фатальными из-за не-
определенных значений расширенных атрибутов.
• Поиск обходного пути (Finding a Detour). Этот метод предполагает игнорирование части диаграммы с целью попытаться найти состояние, в котором можно возобновить разбор диаграммы.
В данной статье предлагается формализм автоматной графической грамматики, способной выполнить нейтрализацию ошибок (RVN-грамматика), являющейся расширением RV-грамматики [3, 4]. Анализатор, построенный на базе такой грамматики, позволяет выявлять более одной ошибки за проход и обеспечивает линейное время анализа.
2. RVN-ГРАММАТИКА
RVN-грамматика задает алгоритм "обхода" графической диаграммы. При каждом применении правила RVN-грамматики (шаге алгоритма) возможны операции с внутренней памятью. Она используется для хранения информации о ветвлениях, слияниях, частично проанализированных элементах диаграммы, продолжателях анализа и т.п. На завершающем шаге алгоритма производится проверка состояния памяти. В случае успеха этой проверки анализ признается положительно выполненным.
Для нейтрализации ошибок на этапе проектирования грамматики выделяются типы графических объектов, экземпляры которых будут использоваться в качестве продолжателей анализа. Понятно, что важно найти "золотую середину" при определении количества типов продолжателей анализа, поскольку при анализе некорректной диаграммы чрезмерно большое количество объектов - продолжателей анализа повлияет на скорость анализа (будет затрачивать много времени), но будет проанализирована большая часть диаграммы. Малое количество продолжателей, наоборот, позволит сократить время анализа, но проанализирована будет меньшая часть диаграммы.
2.1. Определение КУТУ-грамматики
Н\Ш-грамматикой языка Ь(С) называется упорядоченная пятерка непустых множеств О = (V, £, £, В,, г0), где
• V = {¡уе, е = 1 ,...Ь} - вспомогательный алфавит (алфавит операций над внутренней памятью);
• £ = Ь = 1,.. .Г} - терминальный алфавит визуального языка, являющийся объединением множеств его графических объектов и связей (множество примитивов визуального языка);
• £ = {щ, Ь = 1,... ,Т} - квазитермальный алфавит, являющийся расширением терминального алфавита. Алфавит £ включает:
— квазитермы графических объектов, не являющихся продолжателями анализа;
— квазитермы графических объектов -продолжателей анализа;
— квазитермы графических объектов, имеющих более одного входа;
— квазитермы связей - меток с определенными для них семантическими различиями;
— квазитерм для проверки наличия графических объектов - продолжателей анализа;
— квазитерм для завершения анализа;
= |гг-, г = 0,...,/} - схема грамматики С (множество имен комплексов продукций, причем каждый комплекс гг-
состоит из подмножества Гг = {Рг1, .7 = 1,-••,«/});
Я
и
продукции
го £ Я - аксиома Н\Ш-грамматики (имя начального комплекса продукций), г^ £ В, -заключительный комплекс продукций.
аг
Продукция Pij £ Г{ имеет вид Pi
и
> г г,
где
• (71, ..., 7„) - га-арное отношение, определяющее вид операции над внутренней памятью в зависимости от г/ 6 {0,1,2,3};
• - оператор модификации, определенным образом изменяющий вид операции над памятью, причем ¡1 £ {0,1, 2};
• гт £ В, - имя комплекса продукции - приемника.
Определим следующую интерпретацию правил Н\Ш-грамматики в зависимости от параметров ¡1 иг/.
Пусть ¡1 = 0, тогда [И^ (71, ..., уп)] = = И-А (71, • • •, 7гг), т.е. - пустой оператор.
Отношение ТУа (71, ..., уп) определяет операции над магазинной памятью.
При А = 0 никаких действий над памятью не производится.
При А = 1 (А = 2) в магазин с номером Б £ {1,..., га} записывается (стирается) уе £ V, причем, если запись производится безусловно, то стирание осуществляется при условии, что 75 в правиле Н\Ш-грамматики и в вершине магазина совпадают. В противном случае данное правило считается неприемлемым (стирание не производится).
При ¡1=1 оператор имеет вид
[И^ (71
7„)] = ^л(тГ,
Тп
определен для А = 1,2,3 и задает простую операцию записи, чтения или сравнения, но уже не над магазинной, а над ленточной памятью, где («1(^1), ..., ап(Ьп)) указывают номера ячеек соответствующих эластичных лент (1, ..., га), куда будут записаны при А = 1 (считаны при А = 3, сравнены при А = 2) символы 71, ..., 7 п£У.
НЕЙТРАЛИЗАЦИЯ СИНТАКСИЧЕСКИХ ОШИБОК В ГРАФИЧЕСКИХ ЯЗЫКАХ Таблица 1. Терминальный и квазитермальный алфавиты языка ПГСА
Алфавит термов Графическое представление Алфавит квазитермов
начало С.) Л
действие -*- —X— А
условие <ф> Ра, РЬ
объединение взаимоисключающих ветвей V Ж, т, ж
распараллеливание Ра, Ръ
слияние ^а, ¿6) Ь.
конец с-) Ак
связь 1 ге1, 1аЬе1р, 1аЪе1\у, 1аЬе1ц, 1аЬе1^, /¡пс1, по_1аЬе1
При ¡1 = 2 оператор имеет вид - 7п)] =
ЕЕ Ид, (ТГ , • • • , ГпП) 1 , . . • , Т£") ,
определен для А1 = 1, 2, А2 = 2, 3 и задает условную операцию над ленточной памятью, т.е. операция в числителе выполняется при условии выполнения операции в знаменателе.
В операциях над внутренней памятью номера ячеек лент («¿) кодируются следующим образом:
• £ - номер текущего графического примитива из числа примитивов данного типа;
• Ь - номер графического примитива, от которого исходит "управляющий сигнал", т.е. возврат к графическому объекту по метке (применяется только для связей).
Квазитермы графического объекта - продолжателя анализа необходимы для обработки следующих событий:
• "первичного" анализа объекта;
• "вторичного" анализа объекта.
Эти события возникают при:
• естественном переходе от связи к графическому объекту;
Таблица 2. RVN-грамматики для языка ПГСА
№ продукции Комплекс Квазитерм Комплекс приемник RV-отношение
1 го Л ri 0
2 г el гз 0
3 Г2 labelp гз W2{blm)
4 labelw гз w2(b2m)
5 labelp гз W2{bim)
6 labelp гз W2{b4m,kt^)/W3{mt^ ==
7 Г2 find гз w2(tbm)
8 noJabel Гк *
9 Гз A Г1
10 Pa Г1 ^(^.l^j/^fe'i8))
11 Pb Г2 W2( l'W)
12 Wa Г2
13 Wb Г2 Wiil^/W^e^,!^)
14 w Г2 Wiiincim^))/}Уз{т^ < 2)kW2{lt(*))
15 Ra Г1
16 Rb Г2 W2( 1*1*>)
17 La Г2 Wiik^J4"1,1Ч8>)/1¥2(еЧ2>)
18 Lb Г2
19 L Г2 Wiiincim^))/\У3(т^ <
20 Ak Г2 0
21 Гк 0
• выборе данного объекта в качестве продолжателя анализа.
Работа с внутренней памятью и методика построения Н\Ш-грамматики практически аналогичны НУ-грамматике. Единственным отличием является добавление элементов памяти для хранения информации о продолжателях (магазина для списка возможных продолжателей и ленты для проанализированных графических объектов).
2.2. Пример КУТУ-грамматики для языка ПГСА
Терминальный алфавит языка параллельных графических схем алгоритмов (ПГСА) состоит из следующих элементов: начало, де-ствие, условие, объединение взаимоисключающих ветвей, распараллеливание, слияние, конец и связь. Определив семантические различия для связей и выбрав продолжателей анализа (условие, объединение взаимоисключающих ветвей, распараллеливание, слияние), получаем квазитермальный алфавит (см. таблицу 1).
Значения квазитермов:
• find - поиск продолжателей анализа;
• noJabel - завершение анализа;
• для элемента Е = {Р, W, R, L} labelE -связь - метка, исходящая из Е, Еа - первичный анализ Е, Еь - вторичный анализ Е, Е_ — уже анализированный элемент Е.
Далее, согласно методике построения RVN-грамматики определяем операции над внутренней памятью, допустимые паросочетания, производим синтез грамматики и минимизируем ее. Результат этих действий представлен в таблице 2.
Используемые элементы внутренней памяти (в скобках указаны номера магазинов и лент):
• четыре магазина для хранения информации для связей - меток, исходящих из условия (1), объединения взаимоисключающих ветвей (2), распараллеливания (3) и слия-ния(4);
НЕЙТРАЛИЗАЦИЯ СИНТАКСИЧЕСКИХ ОШИБОК В ГРАФИЧЕСКИХ ЯЗЫКАХ
65
Алгоритмическая структура БУМ-анализатора.
• один магазин для хранения списка возможных продолжателей (5);
• четыре ленты для хранения информации об уже проанализированных объединениях взаимоисключающих ветвей (1), слияниях (2), продолжателях анализа (8), количестве входов в слияния (3).
Операция "*" выполняется после анализа последнего символа и представляется следующим образом:
* = Цг2{е1т) кк \¥2{е2т) кк И^е3"1) кк Ж2(е4т) кк \У2(2а'М) кк Ж(та'<2) > 2) кк (та'(2) == ка°(3)) Ж2(е5т) кк (та'(8) == 1).
3. АЛГОРИТМИЧЕСКАЯ СТРУКТУРА ЕУ]М-АН
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.