Алгоритм исправления ошибок при анализе в парсерах типа перенос-свертка, основанный на предположении об избыточности языка Дипломная работа студента 545 группы Ефимова Андрея Александровича Научный руководительст. преп. Кириленко Я.А. Рецензентк.ф.-м.н. Лукичев А.С. Санкт-Петербургский государственный университет математико-механический факультет кафедра системного программирования 2008 г

Введение Устаревшая документация Избыточные грамматики Разработка новых грамматик

Постановка задачи 3 подхода обработки ошибок: 1. Обнаружение ошибок (error detection) 2. Восстановление при ошибках (error recovery) 3. Исправление ошибок (error correction)

Обзор алгоритмов 1. Специальные методы 2. Обработка ошибок на уровне фраз 3. Локальная обработка ошибок 4. Глобальная обработка ошибок

Управляющая таблица a+$ES 0s12 1r2 2s2s3 3accept 4s15 5r1 Грамматика a(+a)* 0) S -> E $ 1) E -> E + E 2) E -> a

Управляющая таблица a+$ES 0s1pa1 2 1r2 2p+2s2s3 3accept 4s1pa1 5 5r1 Грамматика a(+a)* 0) S -> E $ 1) E -> E + E 2) E -> a

Пример разбора строки с ошибкой СтекВходная строкаДействие 0 0 a 1 0 E 2 0 E E a 1 0 E E 5 0 E 2 0 E 2 $ 3.aa$.a$.$. shift, go to 1 reduce rule 2 push +, go to 4 shift, go to 1 reduce rule 2 reduce rule 1 shift, go to 4 accept

Пример работы инструмента Кратко: state 0: accept only a symbol; default: push a, go to 1 state 2: accept only + symbol; default: push +, go to 4 state 4: accept only a symbol; default: is push a, go to 1 total 3 default pushes Подробнее: state 0 0 $accept:. E $end 1 E:. E + E 2 |. a $default push symbol a, and go to state 1

Результаты анализа ANSI C Лишние скобки (всего 15): selection_statement -> IF ( expression ) statement Лишние точки с запятой (всего 4): jump_statement: CONTINUE ';' Идентификаторы (всего 7): jump_statement -> GOTO IDENTIFIER ; Цикл DO…WHILE: iteration_statement -> DO statement WHILE ( expression ) ; expression -> expression, assignment_expression

Результаты Дан обзор существующих методов исправления ошибок Предложен алгоритм исправления ошибок, на основе предположения о возможной избыточности грамматики Реализован инструмент анализа грамматики на избыточность на основе Bison (2.3-1) Полученный инструмент проверен на нескольких грамматиках существующих языков программирования