Когда я учился на курсе по компиляции в колледже, я не понимал ПЕРВЫЙ и СЛЕДУЮЩИЙ Я реализовал алгоритмы, описанные в книге «Дракон», но понятия не имел, что происходит. Я думаю, что я делаю сейчас.
Полагаю, у вас есть книга, которая дает формальное определение этих двух наборов, и книга совершенно непостижима. Я постараюсь дать их неформальное описание, и, надеюсь, это поможет вам понять, что в вашей книге.
ПЕРВЫЙ набор - это набор терминалов, которые вы можете увидеть как первую часть расширения нетерминала. Набор FOLLOWS - это набор терминалов, которые вы можете увидеть после расширения нетерминала.
В вашей первой грамматике есть только три вида терминалов: =, * и id. (Вы также можете считать $, символ конца ввода, как терминал.) Единственными нетерминалами являются S (оператор) и L (Lvalue - «вещь», которую вы можно назначить).
Думайте о FIRST (S) как о множестве нетерминалов, которые могли бы начать оператор. Интуитивно понятно, что вы не начинаете утверждение с =. Так что вы не ожидаете, что это появится в ПЕРВОМ (S).
Так как начинается утверждение? Есть два производственных правила, которые определяют, как выглядит S, и оба они начинаются с L. Итак, чтобы выяснить, что находится в FIRST (S), вам действительно нужно посмотреть, что находится в FIRST (L). Есть два производственных правила, которые определяют, как выглядит Lvalue: он начинается с * или с id. Итак, FIRST (S) = FIRST (L) = {*, id}.
СЛЕДУЕТ (S) легко. Ничего не следует за S, потому что это начальный символ. Таким образом, единственное, что в FOLLOWS (S) - это $, символ конца ввода.
СЛЕДУЮЩИЙ (L) немного сложнее. Вы должны посмотреть на каждое производственное правило, где появляется L, и посмотреть, что последует за ним. В первом правиле вы видите, что = может следовать за L. Так что = в следующих (L). Но вы также заметили в этом правиле, что в конце производственного правила есть еще L. Итак, еще одна вещь, которая может следовать за L, это все, что может следовать за этим производством. Мы уже выяснили, что единственное, что может следовать за производством S, - это конец ввода. Так СЛЕДУЕТ (L) = {=, $}. (Если вы посмотрите на другие правила производства, в конце их всегда появляется L, поэтому вы просто получаете $ из них.)
Взгляните на это Простое объяснение и пока игнорируйте все, что связано с ϵ, потому что у вас нет произведений, которые содержат пустую строку. Под «Правилами для первых сетов» должны иметь смысл правила № 1, № 3 и № 4.1. В «Правилах для наборов подписок» правила 1, 2 и 3 должны иметь смысл.
Все становится сложнее, когда у вас есть ϵ в ваших правилах производства. Предположим, у вас есть что-то вроде этого:
D -> S C T id = V // Declaration is [Static] [Const] Type id = Value
S -> static | ϵ // The 'static' keyword is optional
C -> const | ϵ // The 'const' keyword is optional
T -> int | float // The Type is mandatory and is either 'int' or 'float'
V -> ... // The Value gets complicated, not important here.
Теперь, если вы хотите вычислить FIRST (D), вы не можете просто посмотреть на FIRST (S), потому что S может быть «пустым». Вы интуитивно знаете, что FIRST (D) это {static, const, int, float}. Эта интуиция кодифицирована в правиле № 4.2. Думайте о SCT в этом примере как Y1Y2Y3 в правилах «Простого объяснения».
Если вы хотите вычислить СЛЕДУЮЩИЕ (S), вы не можете просто смотреть на ПЕРВЫЙ (С), потому что он может быть пустым, поэтому вы также должны смотреть на ПЕРВЫЙ (T). Так СЛЕДУЕТ (S) = {const, int, float}. Вы получаете это, применяя «Правила для последующих наборов» № 2 и № 4 (более или менее).
Надеюсь, это поможет, и вы сами сможете выяснить ПЕРВЫЙ и СЛЕДУЮЩИЙ для второй грамматики.
Если это помогает, R представляет R-значение - «вещь», которую вы не можете назначить, например, константу или литерал. Lvalue также может выступать в качестве Rvalue (но не наоборот).
a = 2; // a is an lvalue, 2 is an rvalue
a = b; // a is an lvalue, b is an lvalue, but in this context it's an rvalue
2 = a; // invalid because 2 cannot be an lvalue
2 = 3; // invalid, same reason.
*4 = b; // Valid! You would almost never write code like this, but it is
// grammatically correct: dereferencing an Rvalue gives you an Lvalue.