Назначение FIRST и FOLLOW в парсерах LL (1)?

Ответ 1

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

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

Шаг прогнозирования - это то, где отображаются FIRST и FOLLOW. Анализатор должен уметь угадывать, основываясь исключительно на текущем нетерминале и следующем знаке ввода, которое должно использоваться. Вопрос в том, как это сделать.

Предположим, что текущий нетерминал равен A, а следующий токен ввода - t. Если вы знаете постановки A, какой из них вы бы выбрали? Там один простой случай: если есть вид формы A → t & omega;, где & omega; это некоторая произвольная строка, тогда вы должны выбрать эту продукцию, потому что т, который вы смотрите на вход, будет соответствовать t в начале производства.

Также есть несколько сложных случаев. Предположим, что у вас есть постановка формы A → B & omega;, где B является нетерминалом и & omega; это некоторая строка. При каких обстоятельствах вы хотите угадать эту продукцию? Ну, если вы знаете, что находится следующий символ терминала, вы не захотите угадать это производство, если не знаете, что B может расширяться до строки, которая начинается с терминала t (там есть еще один случай, о котором мы поговорим в второй). Это место, где входят FIRST. В грамматиках без & epsilon; производств, набор FIRST (X) для некоторого нетерминала X является множеством всех терминалов, которые потенциально могут появиться в начале некоторой строки, полученной из X. Если у вас есть вид формы A → B & Omega; и вы видите нетерминал t, вы бы предположили использовать это производство именно тогда, когда t & in; ПЕРВЫЙ (В); то есть B может выводить некоторую строку, начинающуюся с t. Если B не выводит ничего, начиная с t, то нет причин его выбирать, и если B действительно что-то делает с t, вы хотите сделать этот выбор так, чтобы вы могли в конечном итоге соответствовать t против него.

Все становится немного сложнее, когда & epsilon; производств. Теперь предположим, что у вас есть постановка формы A → BC & omega;, где B и C - нетерминалы и & omega; это строка. Предположим также, что следующий знак ввода - t. Если t & in; FIRST (B), тогда мы бы выбрали эту продукцию, как упоминалось выше. Однако, что произойдет, если t & notin; ПЕРВЫЙ (В)? Если есть & epsilon; постановки в грамматике, мы, возможно, все же захотим выбрать эту продукцию, если B может получить и эпсилон; и t & in; ПЕРВЫЙ (С). Почему это? Если это произойдет, это означает, что мы можем соответствовать t, создавая BC & omega;, затем создавая & epsilon; от B, оставив C & omega; против которого соответствует t. Это один из контекстов, где нам, возможно, придется "проглядеть" нетерминал. К счастью, это обрабатывается FIRST-наборами. Если нетерминал X может производить & epsilon;, то & epsilon; &в; ПЕРВЫЙ (Х). Поэтому мы можем использовать FIRST-установки, чтобы проверить, нужно ли нам "проглядывать" нетерминал, видя, есть ли & epsilon; &в; ПЕРВЫЙ (Х).

До сих пор мы не говорили о наборах FOLLOW. Куда они входят? Ну, предположим, что мы обрабатываем нетерминал A, мы видим терминал t, но ни одно из производств для A не может фактически использовать t. Что мы тогда делаем? Оказывается, есть еще способ, которым мы можем съесть это. Помните, что парсер LL (1) работает, поддерживая рабочее пространство со строкой в ​​нем. Возможно, что мы не смотрим на то, что мы не должны быть сопоставлены с текущим нетерминалом A вообще, и вместо этого мы должны иметь A production & epsilon; а затем пусть какой-то более поздний нетерминал в рабочем пространстве совпадает с t. Это происходит при наборе FOLLOW. Набор FOLLOW нетерминала X, обозначенный FOLLOW (X), представляет собой набор всех терминальных символов, которые могут появляться сразу после X в некотором деривации. Выбирая, какое производство выбрать для A, добавим окончательное правило - если символ терминала t находится в наборе FOLLOW A, мы выбираем какое-то производство, которое в конечном итоге будет производить & epsilon;. Таким образом, A "исчезнет", и мы сможем сопоставить t с некоторым символом, который появляется после нетерминала.

Это не полное введение в парсинг LL (1), но я надеюсь, что это поможет вам понять, почему нам нужны FIRST и FOLLOW. Для получения дополнительной информации возьмите книгу по разбору (я рекомендую Parsing Techniques: Практическое руководство от Grune и Jacobs) или возьмите курс по компиляторам. В качестве совершенно бесстыдной версии, я преподавал курс компиляторов летом 2012-2013 и все слайды лекции доступны в Интернете.

Надеюсь, это поможет!