Кодировать FIRST и FOLLOW устанавливает в парсер рекурсивного спуска - PullRequest
Новая
       59

Кодировать FIRST и FOLLOW устанавливает в парсер рекурсивного спуска

1 голос
/ 18 марта 2012

Это продолжение предыдущего вопроса, который я задал Как кодировать наборы FIRST и FOLLOW внутри компилятора , но этот больше касается дизайна моей программы.

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

Примечание: весь код будет псевдокодом

Вариант 1) Используйте карту и сопоставьте все нетерминалы по их имени двум наборам, которые содержат их наборы FIRST и FOLLOW: 

class ParseConstants
    Map firstAndFollowMap = #create a map .....
    firstAndFollowMap.put("<program>", FIRST_SET, FOLLOW_SET)
end

Это кажется приемлемым вариантом, но внутри моего парсера мне бы понадобился такой ужасный код, как этот, чтобы получить FIRST и FOLLOW и перейти к функции ошибки: 

#processes the <program> non-terminal
def program
    List list    = firstAndFollowMap.get("<program>")
    Set FIRST    = list.get(0)
    Set FOLLOW   = list.get(1)  

   error(current_symbol, FOLLOW)
end

Вариант 2) Создать класс для каждого нетерминала и иметь свойство FIRST и FOLLOW: 

class Program
    FIRST    = .....
    FOLLOW = .... 
end

это приводит к тому, что код выглядит немного лучше: 

#processes the <program> non-terminal
def program
   error(current_symbol, Program.FOLLOW)
end

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

Я также разместил этот вопрос здесь: http://www.coderanch.com/t/570697/java/java/Encode-FIRST-FOLLOW-sets-recursive

1 Ответ

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

Вам не нужны наборы FIRST и FOLLOW.Вы должны вычислить их, чтобы получить таблицу разбора.Это таблица {<non-terminal, token> -> <action, rule>}, если LL (k) (что означает просмотр non-terminal в стеке и token на входе, который action взять и, если применимо, который rule применить), илитаблица {<state, token> -> <action, state>} if (C | LA |) LR (k) (что означает данные state в стеке и token на входе, которые action взять и перейти к которым state.

После того, как вы получите эту таблицу, вам больше не нужны FIRST и FOLLOWS.

Если вы пишете семантический анализатор, вы должны предположить, что анализатор работает правильно. Обработка ошибок на уровне фраз(что означает обработку ошибок синтаксического анализа), полностью ортогональна семантическому анализу.

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

Вы можете взглянуть на myбиблиотека компиляторов для примеров.

Об обработке ошибок на уровне фразы, вам снова не нужно ПЕРВЫЙ и СЛЕДУЙТЕ.Давайте поговорим о LL (k) сейчас (просто потому, что о LR (k) я пока особо не задумывался).После того, как вы построите грамматическую таблицу, у вас будет много записей, как я сказал так: 

<non-terminal, token> -> <action, rule>

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

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

Если то, что вы получите, не является терминалом (T)вместо этого вы должны взглянуть на свой лексер, взять lookahead и посмотреть на свой стол.Если запись <T, lookahead> существовала, значит, вы готовы.Следуйте за действием и нажмите / сложите из стека.Если, однако, такой записи не было, опять-таки запускается обработчик ошибок на уровне фразы:

Роль вторая: обрабатывать неожиданные терминалы - вы можете сделать много вещей, чтобы пройти это.То, что вы делаете, зависит от того, что такое T и lookahead, и от вашего экспертного знания грамматики.

Примеры того, что вы можете сделать:

  • Fail!Вы ничего не можете сделать
  • Игнорировать этот терминал.Это означает, что вы помещаете lookahead в стек (после повторного нажатия T) и продолжаете анализатор.Сначала парсер совпадет с lookahead, выбросит его и продолжит.Пример: если у вас есть такое выражение: *1+2/0.5, вы можете сбросить неожиданное * таким образом.
  • Измените lookahead на что-то приемлемое, нажмите T назад и повторите попытку.Например, выражение вроде этого: 5id = 10; может быть недопустимым, потому что вы не принимаете идентификаторы, которые начинаются с цифр.Вы можете заменить его на _5id, например, чтобы продолжить
...