Как кодировать наборы FIRST & FOLLOW внутри компилятора - PullRequest
1 голос
/ 18 марта 2012

Я пишу компилятор для курса по компиляции, который я прохожу, и в настоящее время я нахожусь на Синтаксическом анализе, где мне нужно написать парсер.

Мне нужно иметь наборы FIRST и FOLLOW для обработки любых ошибок, которые могут появиться в исходном тексте.Я предварительно вычислил наборы FIRST и FOLLOW для всех нетерминалов в моей грамматике, но у меня возникли проблемы с выбором, где я на самом деле должен кодировать их внутри моей программы.

Должен ли я разместить их на карте, где ключом является имя нетерминала?

Любой совет будет полезен

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

1 Ответ

2 голосов
/ 18 марта 2012

Если вы хотите сохранить их, вы хотите прикрепить их к нетерминалам, которые они представляют. Возможно, вам также понадобится инверсия, например, карта от заданных членов до нетерминалов, для которых они являются ПЕРВЫМИ или СЛЕДУЮЩИМИ.

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

Я на самом деле не храню их. Я использую синтаксический анализатор GLR, таблицы синтаксического анализа которого по сути являются таблицами синтаксического анализа LALR, и просто строю рекурсивный алгоритм для обхода таблиц, чтобы увидеть, какие токены могут позволить анализатору продолжить работу. Косвенно я использую преимущества FIRST и FOLLOW, поскольку они использовались для построения таблиц разбора.

Если вы проходите курс по разработке компилятора, я рекомендую сосредоточиться на проблемах после разбора. Вы можете потратить кучу времени, пытаясь «исправить» источник в ответ на ошибку, и все, что вы узнаете, это то, что а) это сложно, и б) никому не понравится тот выбор, который вы им предложите. Вы можете тратить энергию на исправление синтаксиса, пока вы не покраснете, но я подожду, пока кто-нибудь не попросит вас сделать это для работы. Тем временем для класса компилятора я бы позволил своему компилятору просто сказать «Синтаксическая ошибка в строке N» и прервать работу. Неприлично, но достаточно хорошо, чтобы позволить вам продолжить более интересную часть.

...