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

Question

Я пишу генератор парсера LALR в качестве проекта для домашних животных.

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

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

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

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

Answer 1

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

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

В целом стратегия yacc оказалась «не ужасной», и даже "достаточно хорошо". Существует один известный способ сделать его лучше, чтобы собирать действительно плохие сообщения об ошибках синтаксиса (или неудачное восстановление ошибок), отследить их до состояния, которое активно, когда они происходят (что легко сделать), и присоединить процедуры восстановления ошибок для этого точного состояния и токена. См., Например, Russ Cox's approach.