Метод айронса нейтрализация ошибок

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

Во многих случаях,
когда неправильно используется
идентификатор, достаточно вывести
сообщение об ошибке и продолжить
компиляцию. Например, если анализируется
оператор AB;
где A
– переменная
типа REAL,
а B
– переменная
типа BOOLEAN,
то мы можем просто сообщить о несовместимости
типов для A
и B
в операторе
присваивания и продолжить работу, так
как нет необходимости связывать с
нетерминалом инструкция
присваивания
какую либо “семантику”
и, следовательно, лишние сообщения
выводится не будут.

Рассмотрим теперь
переменную с индексами A[e₁,
,
e_n],
когда с
идентификатором связана некоторая
“структура”.
Положим,
что в программе A
не объявлено, как массив. Тогда будет
выдано сообщение об ошибке и продолжится
грамматический разбор индексов. После
окончания разбора индексов их число
будет сравниваться с размерностью
массива, которая указана в элементе
таблицы идентификаторов для A.
Так как A
не имя
массива, то появится второе сообщение
об ошибке. Такую ошибку можно довольно
просто нейтрализовать и подавить лишние
сообщения, относящиеся к данному
идентификатору, если заменить его в
исходной программе “корректным”
идентификатором.
В таблицу
идентификаторов заносится новый
корректирующий элемент с правильными,
насколько это возможно, атрибутами.
Программе, формирующей сообщения об
ошибке, передается в качестве параметра
указатель элемента таблицы идентификаторов,
который вызвал ошибку. Программа
проверяет, не является ли этот элемент
корректирующим идентификатором,
вставленным для нейтрализации ранее
обнаруженной ошибки, и если это так, то
лишнее сообщение об ошибке не формируется.

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

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

6.5.3. Нейтрализация синтаксических ошибок

На
любом этапе грамматического разбора
исходная программа имеет следующий вид
x T t,
где x –
обработанная часть, T
– следующий сканируемый символ, а
t –
остальная часть исходной программы.
Предположим, что встретилась ошибка.
При нисходящем разборе это означает,
что построено частичное дерево,
опирающееся на x, но
его нельзя расширить так, чтобы оно
опиралось и на T. При
восходящем разборе может оказаться,
что либо между хвостом x
и символом T
не определено отношение предшествования,
либо никакой хвост x
не является основой и т.п.

Здесь
мы должны решить, как изменить программу,
чтобы “подправить”
ошибку. Проще всего воспользоваться
одним из следующих способов (или их
комбинацией):

1.
Исключить T
и попытаться продолжить разбор.

2.
Вставить цепочку q,
состоящую из терминалов, между x
и T (получится
цепочка xqTt)
и начать разбор, используя голову
цепочки qTt. Эта вставка
позволит целиком обработать qT,
прежде чем возникнет другая ошибка.

3.
Вставить цепочку q
между x и
T (получится цепочка
xqTt), но
разбор начать с T. (При
восходящем разборе q
необходимо поместить в стек.)

4.
Исключить несколько последних символов
из цепочки x.

Способы
1 и 2 предпочтительнее для нейтрализации,
так как они не меняют содержимое стека,
а значит, и не требуют изменения семантики.
Так как цепочка x уже
обработана, с ней, возможно, уже связана
семантическая информация. Добавление
q к x или
выбрасывание части x означает,
что нужно соответствующим образом
изменить и семантическую информацию,
а сделать это совсем не просто.

Казалось
бы, что можно добавить “ошибочные”
правила в грамматику и заранее принять
меры против ошибок. Например, мы могли
бы добавить правило

присваивание
 выражение

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

Рассмотрим
метод нейтрализации ошибок при нисходящем
разборе, предложенный в 1963 году Е.
Айронсом, на примере грамматики в
расширенной форме Бэкуса-Наура:

P 
A;

A 
iE

E 
T{T}

T 
F{F}

F 
i(E)

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

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

На
любом шаге разбора мы имеем дело с одним
или несколькими синтаксическими
деревьями, в которых есть несколько
неполных кустов. Например, на рис. 6.18 а,
сплошными линиями показано, как выглядит
частично построенное дерево, а пунктирными
– как можно было бы дополнить кусты с
именами P
и E.

Неполный
куст U
соответствует применению правила

UX₁X₂X_i-1X_iX_n

где X₁X₂X_i-1
– построенная, а X_iX_n
– недостающая часть куста. На рис.
6.18 а неполный куст с именем P
соответствует применению правила
PA;
, а “”
– недостающая часть куста. Неполный
куст E
соответствует применению правила
E 
T{T}.
Чтобы дополнить куст необходим нетерминал
T, за
которым следует любое количество цепочек
“T”.
Недостающей частью, следовательно
является T{T}.

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

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

1.
Строится список L
из символов недостающих частей
неполных кустов.

2.
Головной символ T
в цепочке Tt
проверяется и отбрасывается (при этом
каждый раз получается новая цепочка
Tt) до тех пор, пока не
найдется символ T, такой,
что U^
T
для некоторого UL
(либо U=T,
либо U^
T).

3.
Определяется неполный куст, который на
шаге 2 стал причиной появления символа
U в
списке L.

4.
Определяется терминальная цепочка q,
такая что, если ее вставить
непосредственно перед T,
то продолжение разбора привело бы к
правильной привязке T
к неполному кусту, найденному на
шаге 3. С этой целью
исследуется неполный куст и все кусты
поддерева, которые он определяет. Для
каждого такого неполного куста
генерируется цепочка терминалов,
дополняющая этот куст, а конкатенация
этих цепочек дает цепочку q.

5.
Цепочка q
вставляется непосредственно перед
T, и
разбор продолжается, начиная с головного
символа цепочки q,
который становится входным символом.

Рассмотрим
пример грамматического разбора,
изображенного на рис. 6.18 а. Ошибка
была обнаружена, когда входным символом
была скобка “)”. Строим
список L={; , T, }.
На шаге 2 пропускается символ “)”.
Неполный куст, вызвавший появление “;”
в L, есть P

A;. Мы должны, следовательно,
вставить цепочку q,
чтобы дополнить куст E 
T{T}.
Проще всего вставить идентификатор i
(см. рис. 6.18 б).

Рис.
6.19 а иллюстрирует, как предлагаемая
схема нейтрализации использует
“глобальный”
контекст. Кажется, что ошибка такая же,
что и на рис. 6.18 а: за “+”
идет “)”.
Однако теперь L={; , ), T, }
и на этот раз скобка на шаге 2 не
выбрасывается. Неполный куст, вызвавший
появление “)”
в L, — правило F

(E). Для того, чтобы “)”
была связана с этим кустом, мы должны
вставить цепочку, чтобы дополнить куст
, и такой цепочкой снова будет i
(см. рис. 6.19 б). Заметим, что открывающая
скобка могла стоять намного дальше от
места ошибки, и все же она учитывалась
бы при нейтрализации, поскольку при
нейтрализации ошибки принимаются во
внимание все неполные кусты.

При
использовании одной из разновидностей
нисходящего разбора – рекурсивного
спуска (см. раздел 5.1.2), частично построенное
синтаксическое дерево явно не представлено,
и здесь применяется несколько иной
подход. Если рекурсивная процедура
обнаруживает ошибку, то она выводит
сообщение о ней и в зависимости от
очередного входного символа
T можно
выбрать одну из двух альтернатив – либо
что-то вставить и таким образом исправить
ошибку, после чего продолжить работу,
либо вернуться в вызывающую программу
с указанием об ошибке. Например, если
программа для правила

F 
i(E)

не находит “(”
или “i”,
то она может вставить “i”
и продолжить разбор. Если она нашла
“(E”,
но не обнаружила закрывающей скобки,
то она может предположить, что эта скобка
есть, и вернуться в вызывающую программу.

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

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

Подобный
подход используется и при восходящем
разборе. Так в системе построения
компиляторов XPL
[12] разработчик компилятора должен
занести в массив STOPIT
“особые” синхронизирующие
символы типа “;”
и “END”.
Если обнаружена ошибка, то выполняется
следующее:

1.
Символы в цепочке Tt
последовательно просматриваются
и выбрасываются до тех пор, пока один
из них не совпадет с каким-либо символом
из STOPIT.

2.
Получен новый символ T.
Теперь просматриваются и выбрасываются
символы цепочки x
до тех пор, пока символ не состыкуется
правильно с оставшимися символами x.

Упражнения.

6.1. Перевести в
ПОЛИЗ, используя метод Замельсона –
Бауэра, следующий фрагмент программы:

iabc

if ( (i

0)
and (y 
x10)
) then begin

x 
b10ay(b-x)
j15

while
(j 
20) do begin y(y2)a
jj1
end

i(i
a)bc

end
aa
bc
d

Проинтерпретируйте
полученную строку ПОЛИЗа и сгенерируйте
по ней эквивалентный набор команд на
языке ассемблера.

6.2. Перевести в
тетрады, используя метод Замельсона –
Бауэра, следующий фрагмент программы:

if ( (x

100)
or (y 

x10)
and (y 
b) then

x 
(ab
DIV 10)y
MOD b-x

else
begin yabcd
if y 
a then yy2a
x yab
end;

aabcd

Сгенерируйте по
полученным тетрадам эквивалентный
набор команд на языке ассемблера.

Упражнения
на программирование.

6.3.
Программно реализуйте алгоритм Замельсона
– Бауэра для перевода ПОЛИЗ арифметических
выражений, оператора присваивания и
ряда управляющих конструкций. Напишите
программу, интерпретирующую строку
ПОЛИЗа и формирующую набор команд на
языке ассемблера по заданной строке.

6.4. Программно
реализуйте алгоритм Замельсона – Бауэра
для перевода тетрады арифметических
выражений, оператора присваивания и
ряда управляющих конструкций. Напишите
программу, интерпретирующую тетрады и
формирующую набор команд на языке
ассемблера по заданному набору тетрад.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

С интаксический распознаватель вычисляемого оператора перехода языка FORTRAN.

Министерство науки, высшей школы и технической политики Российской Федера­ции.

Новосибирский Государственный

Техниче­ский Университет.

Курсовая работа по системному программированию.

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

Факультет: АВТ.

Кафедра: АСУ.

Группа: А-513.

Студент: Борзов Андрей Николаевич.

Преподаватель: Шорников Юрий Владимирович.

Ассистент: Панова Вера Борисовна.

Дата: 19 мая 1997 года.

Отметка о защите: _______________________________

Новосибирск – 1997.

Язык оператора.

Язык вычисляемого оператора перехода языка FORTRAN.

GOTO МЕТКА½КОНСТАНТА½АРИФМЕТИЧЕСКОЕ ВЫРАЖЕНИЕ

МЕТКА – Идентификатор

КОНСТАНТА – ЦЕЛОЕ БЕЗ ЗНАКА

АРИФМЕТИЧЕСКОЕ ВЫРАЖЕНИЕ – ВЫРАЖЕНИЕ, СОДЕРЖАЩЕЕ В СЕБЕ ОПЕРАЦИИ *, /, -, +, **, А ТАКЖЕ ( ).

** – ВОЗВЕДЕНИЕ В СТЕПЕНЬ.

Грамматика языка.

G[<ОПЕРАТОР>]:

1. <ОПЕРАТОР> ® GOTO <ВЫРАЖЕНИЕ>

2. <ВЫРАЖЕНИЕ> ® Т ç<ВЫРАЖЕНИЕ>+Т ç <ВЫРАЖЕНИЕ>—Т

3. Т ® О çТ*О ç Т/О êТ**О

4. О ®(<ВЫРАЖЕНИЕ>) ç<ИДЕНТИФИКАТОР> ç<ДБЗ>

5. <ИДЕНТИФИКАТОР> ® Б{Б çЦ}[L]

6. <ДБЗ> ® Ц{Ц}[.Ц{Ц}][L]

Т	–	ТЕРМ
О	–	ОПЕРАНД
Б	–	БУКВА
Ц	–	ЦИФРА
ДБЗ	–	ДРОБНОЕ БЕЗ ЗНАКА
L	–	КОНЕЦ СТРОКИ (пусто)
**	–	ВОЗВЕДЕНИЕ В СТЕПЕНЬ

Классификация грамматики.

Данная грамматика G[<ОПЕРАТОР>], согласно классификации Хомского, является контекстно-свободной, так как правая часть каждой редукции начинается либо с терминального символа, либо с нетерминального, принадлежащего объединённому словарю.

A ® a, AÎV_n, aÎV^*.

Грамматика G[<ОПЕРАТОР>] не является автоматной, так как не все её редукции начинаются с терминального символа. По этой же причине данная грамматика не является S — грамматикой.

Метод анализа.

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

Идея метода состоит в том, что каждому нетерминальному символу ставится в соответствие определённая программная единица (функция), которая распознаёт цепочку, порождаемую этим нетерминалом.

Эти процедуры и функции вызываются в соответствии с правилами грамматики и иногда вызывают сами себя.

Данный метод реализован на языке C++, поскольку он обладает рекурсивными возможностями.

Диагностика и нейтрализация ошибок.

Для данной грамматики производится только диагностика и нейтрализация ошибок. Исправление ошибок не производится.

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

Тестирование.

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

Протокол работы синтаксического распознавателя вычисляемого оператора перехода языка FORTRAN.

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

GOTO A+B-DD**(CC/(23+34**R))+Y*((C))

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘A’ с кодом 65.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа A.

SCAN — Сканирование. Текущий символ ‘+’ с кодом 43.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘B’ с кодом 66.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа B.

SCAN — Сканирование. Текущий символ ‘-‘ с кодом 45.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘D’ с кодом 68.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа D.

SCAN — Сканирование. Текущий символ ‘D’ с кодом 68.

SCAN — Сканирование. Текущий символ ‘*’ с кодом 42.

SCAN — Сканирование. Текущий символ ‘*’ с кодом 42.

SCAN — Сканирование. Текущий символ ‘(‘ с кодом 40.

T — Проверка на Терм.

O — Проверка на Операнд.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘C’ с кодом 67.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа C.

SCAN — Сканирование. Текущий символ ‘C’ с кодом 67.

SCAN — Сканирование. Текущий символ ‘/’ с кодом 47.

SCAN — Сканирование. Текущий символ ‘(‘ с кодом 40.

T — Проверка на Терм.

O — Проверка на Операнд.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘2’ с кодом 50.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа 2.

FLOAT — Проверка на Дробное Без Знака с цифры 2.

SCAN — Сканирование. Текущий символ ‘3’ с кодом 51.

SCAN — Сканирование. Текущий символ ‘+’ с кодом 43.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘3’ с кодом 51.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа 3.

FLOAT — Проверка на Дробное Без Знака с цифры 3.

SCAN — Сканирование. Текущий символ ‘4’ с кодом 52.

SCAN — Сканирование. Текущий символ ‘*’ с кодом 42.

SCAN — Сканирование. Текущий символ ‘*’ с кодом 42.

SCAN — Сканирование. Текущий символ ‘R’ с кодом 82.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа R.

SCAN — Сканирование. Текущий символ ‘)’ с кодом 41.

SCAN — Сканирование. Текущий символ ‘)’ с кодом 41.

SCAN — Сканирование. Текущий символ ‘+’ с кодом 43.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘Y’ с кодом 89.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа Y.

SCAN — Сканирование. Текущий символ ‘*’ с кодом 42.

SCAN — Сканирование. Текущий символ ‘(‘ с кодом 40.

T — Проверка на Терм.

O — Проверка на Операнд.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘(‘ с кодом 40.

T — Проверка на Терм.

O — Проверка на Операнд.

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘C’ с кодом 67.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа C.

SCAN — Сканирование. Текущий символ ‘)’ с кодом 41.

SCAN — Сканирование. Текущий символ ‘)’ с кодом 41.

SCAN — Сканирование. Текущий символ NULL с кодом 0.

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

GOTO A

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

AB — Проверка на Арифметическое Выражение.

SCAN — Сканирование. Текущий символ ‘A’ с кодом 65.

T — Проверка на Терм.

O — Проверка на Операнд.

IDENT — Проверка на Идентификатор с символа A.

SCAN — Сканирование. Текущий символ NULL с кодом 0.

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

Листинг программы.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// FILE «KURSOVIK.CPP».

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// ВАРИАHТ № 3.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Оператор перехода вычисляемый языка FORTRAN.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Кафедра: АСУ.

// Группа: А-513.

// Студент: Борзов Андрей Hиколаевич.

// Преподаватели: кандидат технических наук, доцент Шорников Юрий Владимирович,

// ассистент Панова Вера Борисовна.

// Дата: 29 апреля 1997г.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Подключаемые файлы.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

#include

#include

#include

#include

#include

#include

#include

#include»keyboard.h»

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Макроопределения.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

#define ERROR 0 // Код ошибки.

#define COL_STR 20 // Максимальное количество строк.

#define STR_LEN 35 // Длина строки.

#define MAX_STR_LEN 255 // Максимальная длина строки.

#define FILENAME «TEST.TXT» // Имя файла, открываемого по умолчанию.

#define YES 1

#define NO 2

#define OK 3

//#define TEST // Определено, если включен отладочный режим.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Прототипы функций.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

int I_ReadKey(void); // Опрос клавиатуры.

void Welcome(void); // Экран при старте программы.

void Menu(void); // Меню.

void Help(void); // Помощь.

void MyExit(int=0); // Корректный выход из программы.

void Beep(int=500,int=100); // Звуковой сигнал.

void Usage(void); // Использование программы.

int OpenFile(void); // Открытие файла.

void DrawBox(int,int,int,int,char*); // Рисует рамку с заголовком.

void PrintText(void); // Печатает основной текст.

void Screen(void); // Перерисовка экрана.

void Compile(void); // Компиляция.

void Message(int); // Вывод сообщений об ошибках.

void MyPuts(char*,int); // Аналог puts(char*);.

void Language(void); // Язык оператора.

void Grammar(void); // Грамматика языка.

void GetFilename(void); // Запрос имени файла для открытия.

int ScanStr(char*); // Поиск GOTO.

int Scaner(char*); // Обработка строки.

void Scan(void); // Сканирование следующего символа.

void Delspace(char*); // Удаление ненужных пробелов в строке.

int AB(void); // Реализация нетерминала .

int T(void); // Реализация нетерминала .

int O(void); // Реализация нетерминала .

int IDENT(void); // Реализация нетерминала .

int FLOAT(void); // Реализация нетерминала .

void Error(int=0,char* =»»); // Обработка ошибки.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Глобальные переменные.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

char filename[MAX_STR_LEN]; // Имя файла.

char *text[COL_STR+1]; // Массив указателей на строки текста.

char screen[4096]; // Буфер под копию экрана.

char mes[21][20][80]; // Массив под сообщения об ошибках.

char nx; // Текущий символ.

int pos; // Текущая позиция в строке.

char STR[80]; // Сканируемая строка.

int ERR1; // Счетчик страниц в массиве ошибок.

int ERR2; // Счетчик строк в массиве ошибок.

FILE *errors; // Дескриптор файла.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

// Функция MAIN.

//¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

void main(int argc,char* argv[])

{

textcolor(LIGHTGRAY);

textbackground(BLACK);

_setcursortype(_NOCURSOR);

clrscr();

if(argc>2)

{

Usage();

MyExit();

}

if(argc==2)

strcpy(filename,argv[1]);

else

{

Welcome();

gettext(20,7,60,17,screen);

GetFilename();

}

while(OpenFile())

{

Данный метод реализован на языке C++, поскольку он обладает рекурсивными возможностями.

Диагностика и нейтрализация ошибок.

Для данной грамматики производится только диагностика и нейтрализация ошибок. Исправление ошибок не производится.

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

Тестирование.

12=1

Имя идентификатора должно начинаться с буквы.

———————————————————

s223=(s)+(((d)))

ОШИБОК НЕТ!!!!!

———————————————————

sdsds=skshj**mxnx dc

Пропущена операция или неправильное имя идентификатора.

———————————————————

;;=0

Имя идентификатора должно начинаться с буквы.

Идентификатор состоит только из букв или цифр.

———————————————————

as=115/3

ОШИБОК НЕТ!!!!!

———————————————————

32=-*=

Имя идентификатора должно начинаться с буквы.

Пропущен идентификатор или число.

Пропущен идентификатор или число.

Неизвестная операция или неправильное имя идентификатора.

Пропущен идентификатор или число.

———————————————————

sdvsf+gsdf=0

Слевa от ‘=’операций быть не может .

———————————————————

К-во Просмотров: 394

Бесплатно скачать Реферат: Оператор присваивания языка FORTRAN

Piece of pascal

Реализация программы для анализа синтаксиса декларирования простых переменных на IDE Lazarus c графическим интерфейсом.

Пример работы программы:

Построение алгоритма синтаксического анализа «Декларирование простых переменных языка PASCAL«

Подбор порождающей грамматики

Типичное декларирование переменных в паскале выглядит так:

var bo,bo1:BOOLEAN;i:integer;r:REAL;c:CHAR;

Пусть Id = {<Буква> | <Буква >{<Буква> | <Цифра> | _ }, Буква – буква латинского алфавита, Цифра – целое число.

Тогда формальная грамматика декларирования простых переменных в языке паскаль будет:

𝐺[𝐴]
𝐴− > 𝑣𝑎𝑟𝐵|
𝐵− > (𝑖𝑑)𝐶
𝐶− > 𝐵 : (𝑡𝑦𝑝𝑒); 𝐷
𝐷− > 𝐵|

где < 𝑖𝑑 > — идентификатор переменной, < 𝑡𝑦𝑝𝑒 > — название типа данных.

Классификация

Грамматика 𝐺[𝐴], описанная в предыдущей главе, относится к классу автоматной, так как все входящие правила имеют вид 𝐴− > 𝑎|𝑎𝐵|.

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

По классификации Хомского, данная грамматика относится к контекстно-свободным.

Алгоритм

Метода анализа

Синтаксический анализ

К данной грамматики применим нисходящей алгоритм Эрли.

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

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

В данной грамматике используется следующий список состояний:

1. Стартовый символ грамматики (Ключевое слово var )
2. Идентификатор переменной
3. Символ разделитель (запятая)
4. Тип данных
5. Терминальный символ (точка с запятой)

Нейтрализация ошибок

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

ISSN 1814-1196 Научный вестник НГТУ том 75, № 2, 2019, с. 37-48

http://journals.nstu.ru/vestnik Science Bulletin of the NSTU Vol. 75, No. 2, 2019, pp. 37-48

ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ

INFORMATICS, COMPPUTER ENGINEERING AND CONTROL

УДК 004.43 Б01: 10.17212/1814-1196-2019-2-37-48

Обработка ошибок в синтаксическом

*

анализаторе компилятора языка Е1

А. А. МАЛЯВКО

630073, РФ, г. Новосибирск, пр. Карла Маркса, 20, Новосибирский государственный технический университет

а.та1уауко@еогр. тЫ. ги

Рассматривается задача обработки синтаксических ошибок в компиляторе функционально-императивного языка программирования El, выполняемой с целью организации продолжения синтаксического разбора после останова для нахождения максимально возможного количества действительно допущенных ошибок. Предлагается комбинация нескольких известных способов нейтрализации синтаксических ошибок, ориентированная на особенности используемого в трансляторе алгоритма детерминированного синтаксического разбора. Парсер компилятора реализован в виде стекового автомата, управляемого входным токеном и символом, снимаемым с верхушки стека. Предлагаемый метод нейтрализации ошибок основан на полном переборе всех возможных вариантов модификации одного ошибочного токена: поочередная вставка, замена и удаление для выбора такого варианта перезапуска автомата, при котором следующая синтаксическая ошибка обнаруживается на максимальном расстоянии от нейтрализуемой. Если никакая модификация одиночного ошибочного токена не приводит к успешной нейтрализации, то в предлагаемом методе после каждого удаления расширяется множество допустимых токенов, вычисляемое как объединение множеств выбора нескольких символов, находящихся на верхушке стека автомата. Этот переход от обработки одиночной ошибки к обработке множественной позволяет уменьшить количество входных токенов, считываемых парсером без анализа, по сравнению с известным режимом паники. Описываемый алгоритм нейтрализации сочетается в El-компиляторе с «правилами для типичных ошибок», включаемыми в грамматику для таких возможных ситуаций, когда для успешной нейтрализации ошибки требуется вставить не один, а два или три токена. Подобные ошибки возможны в программах на языке El, их эффективная нейтрализация другими способами представляется весьма затруднительной.

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

Статья получена 10 января 2019 г.

ВВЕДЕНИЕ

Разработка транслятора для нового языка программирования [1], отличающегося от уже существующих языков рядом существенных свойств и характеристик, может быть связана с необходимостью поиска путей решения ранее неизвестных задач [2, 3] или, по меньшей мере, сочетания способов решения задач, ранее рассматривавшихся отдельно друг от друга. Некоторые из таких задач и пути их решения применительно к новому функционально-императивному языку программирования El были рассмотрены в [4].

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

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

В этой работе не рассматриваются семантические ошибки и проблемы их обработки. Предлагаются некоторые модификации известных стратегий нейтрализации синтаксических ошибок и описывается их реализация в трансляторе языка El.

1. ПОСТАНОВКА ЗАДАЧИ

Синтаксический анализатор (парсер) транслятора функционально -императивного языка El представляет собой детерминированный стековый автомат с одним состоянием [5, 6], осуществляющий нисходящий разбор входного текста. Автомат парсера был построен пакетом автоматизации проектирования трансляторов «Вебтранслаб» [7] путем преобразования ЬЬ(1)-грамматики языка El. Небольшой фрагмент этой грамматики (без встроенных в нее действий, расширяющих парсер и осуществляющих функции семантического анализа, оптимизации и генерации кода) выглядит так:

module : moduleName [ options ]? [ imports ]* [ initialyzers ]*

[functionDef]+ moduleName : «module » ident [ «.» ident ]* «;» options : «options» «(» options «)» «;» imports : «import» ident [ («.» | «,») ident]* «;» initialyzers : [ tuple [guard]? ]? block initialyzers : «record»ident «(» options «)» «;» functionDef: [access ]? ident argTuple bodyFunction access : «public» | «private»

argTuple : «(» [argTupleElem [ «,»argTupleElem ]*]? «)»

argTupleElem : varDef [varType ]? ident

argTupleElem : varType ident

argTupleElem : expression

bodyFunction : guard block restBody

bodyFunction : block

restBody : bodyFunction

Полная грамматика языка Е1 [8] содержит 342 порождающих правила (без специальных правил для типичных ошибок), в которых используются 112 терминалов (токенов) и 157 нетерминалов. Принадлежность грамматики к классу ЬЬ(1) позволяет реализовать на ее основе детерминированный нисходящий синтаксический разбор [3]. Для построения Е1-компилятора эта грамматика была преобразована в стековый автомат, управляемый входным токеном и символом, снимаемым с верхушки стека [3, 5, 9].

Управляющая таблица автомата, полученная в результате этого преобразования, имеет размер 157 строк на 112 колонок и является сильно разреженной. В программе парсера эта таблица хранится в виде связанного списка строк, содержащих только непустые клетки. Структура автомата и его логические связи с обрабатываемой программой (сверху), стеком (слева), грамматикой (справа) и функционалом нейтрализации ошибок (снизу) показаны на рисунке.

Анализируемая программа

Г»

I I I

Jf_

С т е к

4 4A

— — > 3 — — —-

Правила грамматики

—►

Обработка ошибок

Шаги 1-6

Правило 3

Взаимные связи управляющей таблицы парсера, анализируемой программы, стека, правил грамматики и функционала нейтрализации ошибок

Interconnections of the parser control table, the program being analyzed, the, grammar rules stack, and error neutralization functional

Управляющая таблица в центре показана в обычном неразреженном представлении. Каждая строка соответствует одному нетерминалу, который может находиться на верхушке стека автомата. Непустые клетки управляющей таблицы содержат порядковые номера порождающих правил, правые части которых должны быть занесены в стек автомата в порядке от последнего символа к первому. С каждой непустой клеткой сопоставлен терминал, принадлежащий множеству выбора [10, 11] того правила, порядковый номер которого находится в клетке.

Перед запуском парсера в его стек заносятся вначале терминал (токен) EndOfFile, а затем начальный нетерминал грамматики (в данном случае это нетерминал module). Из входного файла считывается первый токен (далее считанный, но еще не обработанный токен называется текущим). Автомат запускается, далее он работает циклически [12, 13].

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

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

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

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

Идея нейтрализации ошибок [14-16] основывается на понятии одиночной ошибки. Это означает, что программа, содержащая синтаксическую ошибку, может быть представлена как правильное начало — цепочка токенов ф, один ошибочный токен s и, вероятно, правильное продолжение -цепочка у:

program : ф s щ

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

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

2. ОБРАБОТКА ОШИБОК В ЕЬ-ТРАНСЛЯТОРЕ

Обычно под нейтрализацией [14-16] понимается попытка продолжения анализа программы после обнаружения любой синтаксической ошибки путем последовательного перебора следующих вариантов поиска «исправления» ошибки:

• удаление ошибочного токена;

• вставка перед ошибочным токеном некоторого другого токена;

• замена ошибочного токена некоторым другим токеном.

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

В том случае, если после очередного перезапуска автомат заново не останавливается по ошибке на заданном расстоянии от точки первичного останова, ошибка считается нейтрализованной и парсер возвращается в обычный режим работы. Если же на очередном шаге оказались исчерпаны все возможные варианты модификации ошибочного токена, то ошибка квалифицируется как множественная (не одиночная). Парсер либо останавливает обработку транслируемой программы вообще, либо переходит в режим паники [17-19], ожидая появления на входе одного из так называемых реперных токенов. Такими токенами обычно считаются слова, завершающие целые синтаксические конструкции [20, 21].

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

В трансляторе языка Е1 с целью уменьшения количества неанализируе-мых токенов при переходе к режиму паники описанный механизм модифицирован следующим образом. Процедура нейтрализации синтаксических ошибок организована циклически. Изменена по сравнению с обычно описываемой в литературе очередность применения модификаций ошибочного то-кена. Вначале обрабатываются все допустимые вставки, затем все допустимые замены, после чего — удаление ошибочного токена. Цикл, включающий все вставки, все замены и одно удаление, повторяется до тех пор, пока не бу-

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

Шаг 1, инициализация. Для выполнения всех попыток вставки и замены предварительно формируется множество всех допустимых токенов. Его составляет множество выбора символа, находящегося на верхушке стека автомата. Если этот символ — терминал, то только он и будет входить в множество допустимых токенов. Если же это нетерминал, то вычисляется объединение множеств выбора всех правил грамматики с этим нетерминалом в левой части. Только допустимые токены будут использоваться в попытках вставки/замены при выполнении шагов 2, 3 и 4 процедуры нейтрализации. Символ, для которого вычислено множество всех допустимых токенов, считается обработанной верхушкой стека (см. шаг 5).

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

Шаг 3, замена. Аналогичным образом обрабатывается множество допустимых символов для реализации всех попыток замены. При каждой из них полностью восстанавливается стек автомата, допустимый токен вставляется вместо ошибочного во входной поток, и парсер перезапускается. Попытка считается неудачной, если автомат останавливается по ошибке на токене, следующем во входном потоке за первичным ошибочным. Иначе попытка считается успешной и, точно так же, как на шаге 2, фиксируется наиболее удачный вариант нейтрализации в случае последующего останова по ошибке либо работа компилятора завершается, если достигнут конец входного потока.

Шаг 4, удаление. Те же действия с теми же условиями оценки успешности попытки нейтрализации выполняются при удалении первичного ошибочного токена. После этого выполняется либо шаг 5, либо шаг 6 в зависимости от того, была ли успешной хотя бы одна из попыток вставки/замены/ удаления.

Шаг 5, расширение. Если ни одна из выполненных на шагах 2-4 попыток нейтрализации первичной ошибки не удалась, то реализуется существенно модифицированный режим паники. Как известно, при переходе в этот режим из входного потока считываются и без анализа отбрасываются все токе-ны, не совпадающие с одним из так называемых реперных символов. Такие символы выбираются разработчиком транслятора и в правильных программах обычно завершают такие синтаксические конструкции, как оператор

(символ «;») или блок операторов (символ «}»). После обнаружения одного из этих токенов во входном потоке анализируется стек автомата и с его верхушки последовательно сбрасываются те символы, которые не являются эквивалентами конструкции, соответствующей считанному реперному символу. В отличие от такого способа в Е1-компиляторе после каждого повторения шага 5 множество всех допустимых токенов, вычисленное на шаге 1, дополняется токенами, принадлежащими множеству выбора символа, находящегося в стеке под обработанной верхушкой. Обработанная верхушка расширяется на одну позицию вниз. После этого повторяется шаг 4 и, в зависимости от его успешности, либо шаг 5, либо шаг 6.

Шаг 6, завершение. Если в очередном цикле удалась хотя бы одна попытка вставки/замены/удаления, то парсер выводится из режима нейтрализации. Восстанавливается состояние стека автомата и позиция во входном потоке, сохраненная для наиболее успешной попытки, и автомат перезапускается. Если в процессе нейтрализации шаг 4 выполнялся несколько раз, то перед перезапуском автомата просматривается обработанная верхушка стека и с него сбрасываются все те символы, для которых первый из неудаленных входной токен не принадлежит множеству выбора. Для каждой следующей вновь обнаруженной синтаксической ошибки весь процесс нейтрализации повторяется (следует помнить, что достижение конца входного потока в любой попытке нейтрализации приводит к немедленному завершению работы транслятора).

Приведем пример ситуации, в которой предложенный и реализованный метод нейтрализации позволяет пробросить без анализа меньше входных то-кенов, чем известный режим паники. Пусть в С-подобном языке (в языке Е1 синтаксис присваивания такой же) сильно искаженный оператор присваивания выглядит так:

а = Ь + ) ) с — й / е + * /;

Ни вставки, ни замены, ни удаление одного символа не приведут к успешной нейтрализации ошибки, обнаруженной при чтении первой закрывающей круглой скобки. Вход в режим паники приведет к игнорированию всех входных токенов вплоть до «;». При этом не будет обнаружена вторая ошибка, допущенная в этом операторе (последовательность токенов « ) / + g)»), которая могла бы быть нейтрализована путем замены закрывающей скобки на открывающую.

Парсер Е1-компилятора, удалив сначала первую, а затем вторую открывающую скобки, восстановит процесс распознавания арифметического выражения при чтении токена «с» и вновь остановится по ошибке, прочитав то-кен «*».

Описанная процедура нейтрализации синтаксических ошибок в компиляторе языка Е1 сочетается с включением в грамматику «правил для типичных ошибок». Эти правила добавляются для выявления и обработки таких возможных ситуаций, когда для успешной нейтрализации ошибки требуется вставить в анализируемую программу (или заменить в ней) не один, а два или три токена. Подобные ошибки возможны в программах на языке Е1, их эффективная обработка какими-либо другими способами представляется весьма затруднительной.

Примером подобной ошибки может являться появление одного или нескольких выражений when (или of) вне контекста управляющего оператора by. Любые одиночные модификации ошибочного токена when (или of) согласно вышеприведенному алгоритму нейтрализации в лучшем случае приведут к возникновению наведенных ошибок при обработке токена «:», следующего после выражения за ним, т. е. на расстоянии, большем единицы. Другими словами, описанная выше процедура нейтрализации будет завершаться успехом, но приводить к формированию диагностических сообщений о несуществующих ошибках.

Выходом из этой ситуации [22], используемым и в El-компиляторе, стало включение в грамматику дополнительных правил, согласно которым появление выражений when и of вне контекста оператора by не вызывают запуска процедуры нейтрализации одиночных ошибок. Однако в эти правила в форме действий включены вызовы специально написанных методов класса «парсер», которые формируют сообщения об ошибке и блокируют процессы синтеза.

Пример правила для типичной ошибки в грамматике языка El выглядит

так:

operator : «when»Expression «:» {typicalError(tError.whenOutsideBy);}

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

Кроме приведенного примера с выражениями when и of вне контекста охватывающего их оператора by в грамматику языка El включены и другие «правила для типичных ошибок», уменьшающие возможность выдачи парсе-ром сообщений о наведенных ошибках.

ЗАКЛЮЧЕНИЕ

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

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

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

Описываемый алгоритм нейтрализации сочетается в El-компиляторе с «правилами для типичных ошибок», включаемыми в грамматику для обработки таких возможных ситуаций, когда для успешной нейтрализации ошибки требуется вставить в анализируемую программу (или заменить в ней) не один, а два или три токена. Появление подобных ошибок в принципе возможно в программах на языке El, их эффективная обработка другими способами представляется весьма затруднительной.

СПИСОК ЛИТЕРАТУРЫ

1. Maliavko A. Novel functional-imperative programming language El: a brief introduction // Proceedings of the 2018 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon). — Vladivostok, October 2018. — P. 1-7.

2. Crespi-Reghizzi S. Formal languages and compilation. — London: Springer, 2009. — 364 p.

3. Compilers: principles, techniques, and tools / A. Aho, M. Lam, R. Sethi, J. Ullman. — Reading: Addison-Wesley, 2006. — 795 p.

4. Maliavko A., Zhurkin P., Nagornov N. The functionally-imperative programming language El and its translator // 14th International Scientific-Technical Conference on Actual problems of Electronic Instrument Engineering (APEIE-2018). — Novosibirsk, 2018. — Vol. 1, pt. 4. — P. 469-476.

5. Watson D. A practical approach to compiler construction. — Springer, 2017. — 254 p.

6. Carroll J., Long D. Theory of finite automata with an introduction to formal languages. -New Jersey: Prentice Hall, 1989. — 447 p.

7. Малявко А.А. Использование веб-приложений и веб-технологий при разработке учебного программного обеспечения для изучения методов трансляции // Современное образование: технические университеты в модернизации экономики России: материалы Международной научно-методической конференции, 27-28 января 2011 года. — Томск: Изд-во ТУСУР, 2011. — С. 45-47.

8. Meduna A. Formal languages and computation: models and their applications. — Boca Raton: CRC Press, 2014. — 315 p.

9. Rosenkrantz D., Stearns R. Properties of deterministic top down grammars // Information and Control. — 1970. — Vol. 17 (3). — P. 226-256.

10. Waite W., Goos G. Compiler construction. — Heidelberg: Springer, 2012.

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

11. Dos ReisA. Compiler construction using Java, JavaCC, and Yacc. — Hoboken: Wiley & Sons, 2012. — 664 p.

12. МалявкоА.А. Формальные языки и компиляторы: учебное пособие для вузов. — М.: Юрайт, 2017. — 429 с.

13. KumarR. Theory of automata, languages and computation. — Tata: McGraw-Hill, 2010.

14. Medeiros S. Mascarenhas F. Syntax error recovery in parsing expression grammars // Applied computing 2018: the 33rd Annual ACM Symposium on Applied Computing. — New York, 2018.

15. CooperK., Torczon L. Engineering a compiler. — San Francisco: Morgan Kaufmann, 2003.

16. Wilhelm R., SeidlH., Hack S. Compiler design: syntactic and semantic analysis. — New York: Springer, 2013. — 216 p.

17. Parr T., HarwellS., Fisher K. Adaptive LL(*) parsing: the power of dynamic analysis // Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications. — New York: ACM, 2014. — P. 579-598.

18. ChandakM., Khurana K. Compiler design. — Hyderabad, India: Universitet press, 2018. —

480 p.

19. Grune R., Jacobs C. Parsing techniques: a practical guide. — New York: Springer, 2007. —

585 p.

20. PlaistedD. Source-to-source translation and software engineering // JSEA Special Issue on Software Dependability. — 2013. — Vol. 6, N 4A.

21. Afroozeh A., Izmaylova A. Faster, practical GLL parsing // Compiler Construction: 24th International Conference. — Heidelberg: Springer, 2015. — P. 89-108.

22. Safonov V. Trustworthy compilers. — Hoboken: Wiley & Sons, 2010. — 317 p.

Малявко Александр Антонович, кандидат технических наук, доцент кафедры вычислительной техники факультета автоматики и вычислительной техники Новосибирского государственного технического университета. Основные направления научных исследований: языки программирования и теория трансляции, нейронные сети с элементами самообучения, параллельные вычисления. Имеет около 50 публикаций, в их числе одна монография и один учебник для вузов. E-mail: a. malyavko@corp.nstu.ru

Malyavko Alexander Antonovich, PhD (Eng.), associate professor, Department of Computer Engineering, Faculty of Automation and Computer Engineering, Novosibirsk State Technical University. His research interests are focused on programming languages and translation theory, neural networks with elements of self-learning and parallel computations. He is the author of about 50 publications including 1 monograph and 1 textbook for universities. E-mail: a. malyavko@corp.nstu.ru

DOI: 10.17212/1814-1196-2019-2-37-48

Errors handling in the parser for the El-language compiler

A.A. MALYAVKO

Novosibirsk State Technical University, 20, K. Marx Prospekt, Novosibirsk, 630073, Russian Federation a. malyavko@corp. nstu. ru

Abstract

We consider the problem of processing syntax errors in the compiler of the functional-imperative programming language El aimed at continuing syntactic parsing after a stop to find the maximum possible number of actually made errors. A combination of several well-known methods of neutralizing syntax errors is proposed. It is focused on the features of the deterministic parsing algorithm used in the translator. The compiler parser is implemented in the form of a stack automaton controlled by an input token and a symbol taken from the top of the stack. The proposed error neutralization method is based on a complete enumeration of all possible options for modifying one erroneous token — its alternate insertion, replacement and deletion to select such an option for restarting the automat in which the following syntax error is detected

*

Received 10 January 2019.

at the maximum distance from the initially detected error. If no modification of a single erroneous token leads to a successful neutralization, then in the proposed method, after each deletion of the input token, a set of valid tokens expands, calculated as an integration of multiple selection sets for symbols at the top of the automaton stack. This transition from processing a single error to processing a multiple error allows you to reduce the number of input tokens read by the parser without analysis as compared to the known panic mode. The proposed neutralization algorithm combines in the El-compiler with «rules for typical errors», which are included in the grammar for such possible situations when, in order to successfully neutralize an error, you need to insert (or replace) not one, but two or three tokens.

Keywords: grammar, production rule, automat, selection sets, top-down parsing, single error, errors neutralization, compiler

REFERENCES

1. Maliavko A. Novel functional-imperative programming language El: a brief introduction. Proceedings of the 2018 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon), Vladivostok, October 2018, pp. 1-7.

2. Crespi-Reghizzi S. Formal languages and compilation. London, Springer, 2009. 364 p.

3. Aho A., Lam M., Sethi R., Ullman J. Compilers: principles, techniques, and tools. Reading, Addison-Wesley, 2006. 795 p.

4. Maliavko A., Zhurkin P., Nagornov N. The functionally-imperative programming language El and its translator. 14th International Scientific-Technical Conference on Actual problems of Electronic Instrument Engineering (APEIE-2018), Novosibirsk, 2018, vol. 1, pt. 4, pp. 469-476.

5. Watson D. A practical approach to compiler construction. Springer, 2017. 254 p.

6. Carroll J., Long D. Theory offinite automata with an introduction to formal languages. New Jersey, Prentice Hall, 1989. 447 p.

7. Malyavko A.A. [Using web applications and web technologies in the development of educational software for studying methods of translation]. Sovremennoe obrazovanie: tekhnicheskie univer-sitety v modernizatsii ekonomiki Rossii: materialy Mezhdunarodnoi nauchno-metodicheskoi konfer-entsii [Modern education: technical universities in the modernization of the Russian economy: materials of the International Scientific and Methodological Conference]. Tomsk, TUSUR Publ., 2011, pp. 45-47. (In Russian).

8. Meduna A. Formal languages and computation: models and their applications. Boca Raton, CRC Press, 2014. 315 p.

9. Rosenkrantz D., Stearns R. Properties of deterministic top down grammars. Information and Control, 1970, vol. 17 (3), pp. 226-256.

10. Waite W., Goos G. Compiler construction. Heidelberg, Springer, 2012.

11. Dos Reis A. Compiler construction using Java, JavaCC, and Yacc. Hoboken, Wiley & Sons, 2012. 664 p.

12. Maliavko A. Formal’nyeyazyki i kompilyatory [Formal languages and compilers]. Moscow, Yurait Publ., 2017. 429 p.

13. Kumar R. Theory of automata, languages and computation. Tata, McGraw-Hill, 2010.

14. Medeiros S. Mascarenhas F. Syntax error recovery in parsing expression grammars. Applied computing 2018: the 33rd Annual ACM Symposium on Applied Computing. New York, 2018.

15. Cooper K., Torczon L. Engineering a compiler. San Francisco, Morgan Kaufmann, 2003.

16. Wilhelm R., Seidl H., Hack S. Compiler design: syntactic and semantic analysis. New York, Springer, 2013. 216 p.

17. Parr T., Harwell S., Fisher K. Adaptive LL(*) parsing: the power of dynamic analysis. Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications. New York, ACM, 2014, pp. 579-598.

18. Chandak M., Khurana K. Compiler design. Hyderabad, India, Universitet press, 2018.

480 p.

19. Grune R., Jacobs C. Parsing techniques: a practical guide. New York, Springer, 2007.

585 p.

20. Plaisted D. Source-to-source translation and software engineering. JSEA Special Issue on Software Dependability, 2013, vol. 6,no. 4A.

21. Afroozeh A., Izmaylova A. Faster, practical GLL parsing. Compiler Construction: 24th International Conference. Heidelberg, Springer, 2015, pp. 89-108.

22. Safonov V. Trustworthy compilers. Hoboken, Wiley & Sons, 2010. 317 p.

Для цитирования:

Малявко А.А. Обработка ошибок в синтаксическом анализаторе компилятора языка El / А.А. Малявко // Научный вестник НГТУ. — 2019. — № 2 (75). — С. 37-48. — DOI: 10.17212/18141196-2019-2-37-48.

For citation:

Maliavko A.A. Obrabotka oshibok v sintaksicheskom analizatore kompilyatora yazyka El [Errors handling in the parser of the El-language compiler]. Nauchnyi vestnik Novosibirskogo gosudar-stvennogo tekhnicheskogo universiteta — Science bulletin of the Novosibirsk state technical university, 2019, no. 2 (75), pp. 37-48. DOI: 10.17212/1814-1196-2019-2-37-48.

ISSN 1814-1196, http://journals.nstu.ru/vestnik Science Bulletin of the NSTU Vol. 75, No 2, 2019, pp. 37-48