Что различные виды парсеров LR используют в качестве заглядывания?

Question

1. Верно ли, что LR(0)-парсеры просто уменьшаются, если нет перехода для следующего входного символа (потому что у него нет заглядывания вперед)?
2. Правильно ли, что SLR(1)-парсеры используют FOLLOW-Set производств в качестве предвидения?
3. Верно ли, что LR (1) -парсеры используют FIRST-, а не FOLLOW-Set в качестве предвидения?

---

Алгоритм для closure четко использует FIRST

closure(S)
For each item [A → α ⋅ B β, t] in S,
  For each production B → γ in G,
    For each token b in FIRST(βt),
      Add [B → ⋅ γ, b] to S

---

Опять же, я запутался в этом.

Под абзацем 4.7.1 Canonical LR(1) Items Книга Дракона говорит:

Таким образом, мы вынуждены уменьшать на A → α только те входные символы a, для которых [A → α·, a] является элементом LR (1) в состоянии на вершине стека. Множество таких всегда будет подмножеством FOLLOW (A), но это может быть правильное подмножество, как в Примере 4.51.

Answer 1

1. У парсера LR(0) нет перспективы, поэтому он не может выбирать между действиями уменьшения и сдвига, если оба будут возможны в данном состоянии парсера. Таким образом, состояние сокращения не может иметь сдвиговые переходы.

2. Да, алгоритм SLR переоценивает набор прогнозирования для каждого действия сокращения, просто используя набор FOLLOW для нетерминального сокращения.

3. Нет. Канонический алгоритм LR вычисляет набор данных для каждого действия на основе контекста синтаксического анализатора (то есть состояния). Чтобы вычислить этот набор, полезно знать набор FIRST каждого нетерминала (и иметь возможность вычислять набор FIRST любой формы предложения), но вычисленный набор прогнозных данных не является набором FIRST любого нетерминала. Как указано в учебнике, это подмножество набора FOLLOW нетерминального сокращаемого числа, а в некоторых состояниях в некоторых грамматиках оно будет правильным подмножеством. Это подразумевает, что "одно и то же" сокращение в двух разных состояниях может иметь разные наборы ориентиров, потому что два состояния достигаются в разных контекстах. Как вы заметили, в учебнике приведен пример, и его стоит подробно изучить.