Сначала и следуйте нетерминалов в двух грамматиках

Когда я учился на курсах компилятора в колледже, я этого не делал. Я вообще не понимаю ПЕРВОГО и ПОСЛЕДУЮЩЕГО. Я реализовал алгоритмы, описанные в книге «Дракон», но понятия не имел, что происходит. Думаю, теперь знаю.

Я полагаю, у вас есть какая-то книга, в которой дано формальное определение этих двух множеств, и эта книга совершенно непонятна. Я постараюсь дать их неформальное описание и, надеюсь, поможет вам разобраться в том, что написано в вашей книге.

ПЕРВЫЙ набор - это набор терминалов, которые вы могли бы увидеть как первую часть расширения нетерминала. Набор FOLLOWS - это набор терминалов, которые вы могли бы увидеть после расширения нетерминала.

В вашей первой грамматике есть только три вида терминалов: = , * и id . (Вы также можете рассматривать $ , символ конца ввода, как терминал.) Единственными нетерминалами являются S (оператор) и L (Lvalue - «вещь», которой вы можете присвоить).

Думайте о FIRST (S) как о множестве нетерминалов, которые могли бы начать оператор. Интуитивно вы знаете, что не начинаете оператор с = . Так что вы не ожидали, что это появится в ПЕРВОМ (S).

Так как же начинается утверждение? Есть два производственных правила, которые определяют, как выглядит S , и оба они начинаются с L .Итак, чтобы выяснить, что находится в ПЕРВОМ (S), вам действительно нужно посмотреть, что в ПЕРВОМ (L). Есть два производственных правила, которые определяют, как выглядит Lvalue: оно начинается с * или с id . Итак, ПЕРВЫЙ (S) = ПЕРВЫЙ (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.

Теперь, если вы хотите вычислить ПЕРВЫЙ (D), вы не можете просто смотреть на ПЕРВЫЙ (S), потому что S может быть «пустым». Вы интуитивно знаете, что FIRST (D) - это { static , const , int , float }. Эта интуиция закреплена в правиле № 4.2. Подумайте о SCT в этом примере как о Y1Y2Y3 в правилах «Простого объяснения».

Если вы хотите вычислить СЛЕДУЮЩИЕ (S), вы не можете просто смотреть на ПЕРВЫЙ (C), потому что он может быть пустым, поэтому вам также нужно смотреть на ПЕРВЫЙ (T). Итак, FOLLOWS (S) = { const , int , float }. Вы получаете это, применяя «Правила для последующих наборов» №2 и №4 (более или менее).

Я надеюсь, что это поможет, и что вы сможете разобраться ПЕРВЫЙ и ПОСЛЕДУЮЩИЕ для второй грамматики самостоятельно.

Если это помогает, R представляет Rvalue - «вещь», которой вы не можете присвоить, например константу или литерал. 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.