Может ли восстановление ошибок парсера автоматически руководствоваться грамматикой?

Question

Я пишу генератор парсера LALR в качестве любимого проекта.

Я использую книгу пурпурного дракона, чтобы помочь мне с дизайном, и из этого я понял, что в парсере есть четыре метода восстановления после ошибок:

• Режим паники: начать сбрасывать символы ввода, пока не будет найден символ, предварительно выбранный конструктором компилятора
• Восстановление на уровне фраз: измените входную строку на что-то, что позволит сократить текущее производство
• Ошибки производства: Предвидеть ошибки, включив их в грамматику
• Глобальная коррекция: гораздо более сложная версия восстановления на уровне фраз (насколько я понимаю)

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

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

Answer 1

Слишком легко заблудиться в тупике, когда вы пытаетесь вслепую следить за всеми доступными постановками. Есть вещи, которые вы знаете о своем языке, которые генератору синтаксического анализатора будет очень трудно понять. (Как, например, переход к разделителю следующего оператора очень вероятно позволит восстановить анализ.)

Это не значит, что автоматизированные процедуры не были опробованы. Об этом есть длинный раздел в теории парсинга (Sippu & Soisalon-Soininen). (К сожалению, эта статья платная, но если у вас есть членство в ACM или доступ к хорошей библиотеке, вы, вероятно, найдете ее.)

В целом стратегия yacc оказалась "не ужасной" и даже "достаточно хорошей". Существует один хорошо известный способ сделать его лучше: собирать действительно некорректные сообщения об ошибках синтаксиса (или не удалось восстановить ошибки), отслеживать их состояние, которое активно при их возникновении (что легко сделать), и прикреплять процедура восстановления ошибки до этого точного состояния и жетон ожидания. Смотрите, например, подход Расс Кокса.