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

Question

Может ли кто-нибудь объяснить мне, как FIRST и FOLLOW должны использоваться в грамматике LL (1)? Я понимаю, что они используются для построения таблицы синтаксиса, но я не понимаю, как это сделать.

Answer 1

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

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

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

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

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

Вещи немного сложнее, когда & epsilon; производств. Предположим теперь, что у вас есть постановка формы A → BC ω, где B и C являются нетерминалами, а ω - это строка. Предположим также, что следующий токен ввода - t. Если t ∈ FIRST (B), то мы выбрали бы эту продукцию, как упомянуто выше. Однако, что произойдет, если t ∉ FIRST (B)? Если есть & epsilon; постановки в грамматике, мы, возможно, все же захотим выбрать эту продукцию, если B может получить и эпсилон; и t ∈ FIRST (C). Почему это? Если это произойдет, это означает, что мы могли бы соответствовать t, создавая BC ω, а затем создавая & epsilon; от B, оставив C ω, против которого соответствует t. Это один из контекстов, где нам, возможно, придется «проглядеть» нетерминал. К счастью, это обрабатывается FIRST-наборами. Если нетерминал X может производить & epsilon ;, то & epsilon; ∈ FIRST (X). Поэтому мы можем использовать FIRST-установки, чтобы проверить, нужно ли нам «проглядывать» нетерминал, видя, есть ли & epsilon; ∈ FIRST (X).

До сих пор мы не говорили о наборах 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 с каким-то персонажем, который появляется после нетерминала A.

Это неполное введение в синтаксический анализ LL (1), но я надеюсь, что это поможет вам понять, почему нам нужны FIRST и FOLLOW. Для получения дополнительной информации возьмите книгу по разбору (рекомендую Методы анализа: Практическое руководство от Grune и Jacobs) или пройти курс по компиляторам. Будучи совершенно бесстыдным, я преподавал курс компиляторов летом 2012-2013 и all of the lecture slides are available online.

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