Computing the Follow Set

Question

Хорошо, я понял, как вычислить набор Follow_k (N) (N является нетерминалом): для каждого правила производства формы A -> aBc вы добавляете First_k (First_k (c) Follow_k (A)) to Follow_k (B) (a, c - любая группа терминалов и нетерминалов или даже lambda). ... и вы повторяете это, пока нечего добавить.

Но что происходит для производственных правил, таких как: S -> ABCD (A, B, C, D - все нетерминалы)?

Должен ли я
добавить First_k (First_k (КОР) Follow_k (S)), чтобы Follow_k (A) или
добавить First_k (First_k (CD) Follow_k (S)), чтобы Follow_k (B) или
добавить First_k (First_k (D) Follow_k (S)) to Follow_k (C) или
добавить First_k (First_k (лямбда) Follow_k (S)) в Follow_k (D) или
сделать все вышеперечисленное?

ОБНОВЛЕНИЕ:
Давайте рассмотрим следующую грамматику, например:

S -> ABC
А -> а
Б -> б
С -> с

Наглядно, Follow_1 (S) = {}, потому что ничего не следует после S
Follow_1 (A) = {b}, поскольку b следует после A,
Follow_1 (B) = {c}, поскольку c следует после B,
Follow_1 (C) = {}, потому что после C. ничего не следует.
Чтобы получить этот результат с использованием алгоритма, вы должны рассмотреть все случаи для S -> ABC.

Но мое решение или пример не может быть правильным, так что вопрос остается открытым ...

Answer 1

Если у вас возникли проблемы на другие проблемы грамматики, как это, дать этому online first, follow, & predict set finder выстрел. Это автоматическое, и вы можете сравнить ответы на свой результат, чтобы понять, как работать с ними.

Но что происходит для производственных правил, таких как: S -> ABCD (A, B, C, D - все нетерминалы)?

Вот rules for finding follow sets.

1. Первый положить $ (конец входного маркера) в FOLLOW (S) (S является началом символа)
2. Если есть производство → Abb, (где может быть целая строка), то все в FIRST (b), за исключением ε, помещается в FOLLOW (B).
3. Если есть производство → ав, то все в FOLLOW (А) находится в FOLLOW (B)
4. Если есть производство → Abb, где ПЕРВЫЙ (б) содержит ε, то все, что в FOLLOW (А) находится в FOLLOW (B)

Давайте использовать пример грамматики:

• S -> ABC
• А -> а
• B -> б

• C -> с

  1. Правило 1 гласит, что последующие (S) содержит $.
  2. Правило 2 дает нам: следовать (A) содержит первое (B); также, следовать (B) содержит первое (C).
  3. Правило 3 гласит, что следующее (C) содержит следующее (S).
  4. Ни одно из ваших постановок не имеет значения NULL, поэтому нам не важно правило №4. Символ имеет значение NULL, если он выводит ε, или если он выводит нулевый нетерминальный символ.

допустимость пустых transitivity-х могут срабатывать народ. Рассмотрим грамматику:

• S -> A
• A -> B
• B -> ε

Поскольку B получает ε, обнуляемым Б. Так как A выводит B, который выводит ε, значение A также равно нулю. S выводит A, который выводит B, который выводит ε, поэтому S также является нулевым.

Конечно, вы не принесли это, но это общий источник путаницы в курсах компилятора, поэтому я решил, что я выложу это.

Кроме того, если вам нужны образцы грамматик для работы, http://faculty.stedwards.edu/laurab/cosc4342/g1answers.txt может быть удобно.