Вычисление первых и последующих наборов этой грамматики

Question

Я делаю экзаменационные вопросы для компиляторов.Вопрос в том, чтобы найти первый и последующий наборы следующей грамматики:

S → uBDz
B → Bv | w
D → EF
E → y | e
F → x | e

Вот что я получил, когда вычислил первый набор:

First
S  u,v,w,y,x,z,e
B  v,w
D  y,x,e
E  y,e
F  x,e

Мой лектор уже сделалРешение, но я не могу понять, где он получил ответ:

   First     Follow
S  u         $
B  w         y,x,z,y
D  y,x,e     z
E  y,e       x,z
F  x,e       z

PS.е = эпсилон

ПСС.это пример, которому я следовал https://www.youtube.com/watch?v=dDoo5BF9T4E&t=787s

Answer 1

Символ находится в первом наборе нетерминала, если расширение этого нетерминала может начинаться с этого символа.Это определение первого набора, и если ваш алгоритм не дает такого результата, алгоритм ошибочен.

Например, единственное произведение для S в вашей примерной грамматике:

S → uBDz

Это означает, что каждое расширение S должно начинаться с u.Нет никакого способа обойти этот факт.Невозможно пропустить u и продолжить производство с другой строкой.Таким образом, легко видеть, что FIRST (S) точно {u}.

Аналогично, B имеет два производства

B → Bv
B → w

Это означает, что B может производить:

w
Bv → wv
Bv → Bvv → wvv
Bv → Bvvv → wvvv

и так далее.Расширения могут содержать столько v, сколько вы хотите, но первый символ всегда будет w.Так что ПЕРВЫЙ (B) точно {w}.