Алгоритм исправления ошибок при анализе в парсерах типа перенос-свертка, основанный на предположении об избыточности языка Дипломная работа студента 545. - презентация

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

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

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

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

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

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

7 Пример разбора строки с ошибкой СтекВходная строкаДействие 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

8 Пример работы инструмента Кратко: 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

9 Результаты анализа 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

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