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

  1. Верно ли, что LR(0)-Parsers просто уменьшает, если нет перехода для следующего входного символа (потому что он не имеет просмотра вперед)?
  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.


parsing lr bottom-up
person von spotz    schedule 18.10.2017    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

  3. Нет. Канонический алгоритм LR вычисляет упреждающий набор для каждого действия на основе контекста синтаксического анализатора (то есть состояния). Чтобы вычислить этот набор, полезно знать ПЕРВЫЙ набор каждого нетерминала (и быть в состоянии вычислить ПЕРВЫЙ набор любой сентенциальной формы), но вычисленный опережающий набор не является ПЕРВЫМ набором любого нетерминала. Как указано в учебнике, это подмножество СЛЕДУЮЩЕГО множества сокращаемого нетерминала, и в некоторых состояниях в некоторых грамматиках оно будет правильным подмножеством. Это означает, что «одна и та же» редукция в двух разных состояниях может иметь разные упреждающие наборы, поскольку эти два состояния достигаются в разных контекстах. В учебнике приведен пример, как вы заметили, и стоит подробно изучить этот пример.

person rici    schedule 18.10.2017
comment
Итак, используется ли ПЕРВЫЙ набор в LR (1) для остальной части элемента после нетерминала справа от точки плюс просмотр вперед (как описано в примере алгоритма выше)? Если да, то я вижу, что это будет подмножество СЛЕДУЮЩЕГО набора нетерминала справа от точки. - person von spotz; 19.10.2017
comment
@vonspotz: я думаю, вы правильно поняли алгоритм функции закрытия. - person rici; 19.10.2017