Анализатор GLR с восстановлением ошибок: слишком много альтернатив при ошибках ввода - PullRequest
Новая
       37

Анализатор GLR с восстановлением ошибок: слишком много альтернатив при ошибках ввода

1 голос
/ 09 декабря 2010

Преамбула

Я написал GLR-парсер с исправлением ошибок.Когда он сталкивается с ошибкой, он разбивается на следующие альтернативы:

  1. Вставьте ожидаемый элемент во ввод (может быть, пользователь только что пропустил его) и действуйте как обычно.
  2. Замените ошибочный элементс ожидаемым (может быть, пользователь только что набрал опечатку) и действуйте как обычно.
  3. Пропустите ошибочный элемент, и если следующий элемент также ошибочен, перейдите к # 2.

Ноесли на входе много ошибок (например, пользователь по ошибке передал файл JPEG в анализатор), число вариантов возрастает экспоненциально.

Пример

Такойсинтаксический анализатор, соответствующий следующей грамматике: 

Program -> Identifier WS Identifier WS '=' WS Identifier
Identifier -> ('a'..'z' | 'A'..'Z' | '0'..'9')*
WS -> ' '*

, примененный к следующему тексту: 

x = "abc\"def"; y = "ghi\"jkl";

завершается с ошибкой "недостаточно памяти" на умеренно современном настольном компьютере.

Вопрос

Как уменьшить количество альтернатив в случае ошибок при вводе?

1 Ответ

3 голосов
/ 09 декабря 2010

Выполнение GLR (следовательно, анализа) исправления ошибок на уровне символов возможно, но усугубляет вашу проблему.

Используемая нами процедура восстановления после ошибки GLR работает с токенами, поэтому она не так плоха.

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

Я создал анализаторы GLR с восстановлением после ошибок. Я не был таким амбициозным. В общем синтаксический анализатор в основном просто прерывается, когда количество активных анализаторов становится больше «большого числа» (например, 10000), или количество обнаруженных синтаксических ошибок превышает пороговое значение (например, 10 или 20). Вы можете прервать анализатор, если он не продвинул поток ввода в последнюю секунду, что является косвенным признаком того, что у него слишком много живых анализаторов.

...