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

Преамбула

Я написал 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";

не работает с «недостаточно памяти» на умеренно современном настольном компьютере.

Вопрос

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


parsing error-recovery language-agnostic glr
person Lavir the Whiolet    schedule 09.12.2010    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

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

person Ira Baxter    schedule 09.12.2010