Построение набора следования

Создавая первый набор для данной грамматики, я заметил сценарий, не описанный в моем справочнике по алгоритму.

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

<exp-list_tail> --> COMMA <exp> <exp-list_tail>

Выражения, окруженные ‹..>, не являются терминалами, запятая — это терминал.
Лучшее предположение — просто добавить пустую строку к следующему набору, но я не уверен.

Обычно для случая, когда нетерминал находится в конце производственного правила, вы просто вычисляете список следования для левого нетерминала, но вы можете видеть, насколько это может быть проблемой.


grammar context-free-grammar set-theory
person mamidon    schedule 26.04.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы правильно ответить на этот вопрос, было бы полезно знать всю грамматику. Тем не менее, вот попытка общего ответа:

Вот алгоритм расчета следующих групп:

Инициируйте все последующие группы до {}, кроме S, которая инициализируется до {$}.
Пока есть изменения, для каждого A∈V выполните:
Для каждого Y → αAβ выполните:
follow(A) = Follow(A) ∪ first(β)
Если β ⇒* ε, то также: Follow(A) = Follow(A) ∪ Follow(Y)

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

В частности, я не думаю, что это конкретное правило повлияет на набор последователей <exp-list_tail> (может, но, вероятно, не повлияет).

person Eran Zimmerman Gonen    schedule 27.09.2011
comment
Вам тоже не нужен For each Y -> aA do: follow(A) += follow(Y)? - person Christian Mann; 01.11.2012
comment
То, что показано выше, это случай, когда β=ε, и в этом случае, в частности β ⇒* ε, и поэтому мы действительно follow(A) = follow(A) ∪ follow(Y) - person Eran Zimmerman Gonen; 04.11.2012