Наборы FIRST и FOLLOW Для чего они используются при разборе?

Question

Что такое наборы FIRST и FOLLOW? Для чего они используются при разборе?Используются ли они для анализаторов сверху вниз или снизу вверх?

Может кто-нибудь объяснить мне ПЕРВЫЙ и СЛЕДУЮЩИЙ наборы для следующего набора грамматических правил:

> E := E+T | T
> 
> T := T*V | T
> 
> V := <id>

Answer 1

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

Если у вас есть альтернатива A | B, а также FIRST(A) = {"a"} и FIRST(B) = {"b", "a"}, тогда у вас будет конфликт ПЕРВЫЙ / ПЕРВЫЙ, потому что, когда на входе появляется «а», вы не будете знать, расширять ли А или Б. (Предполагается, что прогноз - 1).

С другой стороны, если у вас нетерминал, который можно обнулять, например, AOpt: ("a")?, тогда вы должны убедиться, что FOLLOW(AOpt) не содержит «a», потому что иначе вы бы не знали, расширять AOpt или нет. здесь: S: AOpt "a" Либо S, либо AOpt может потреблять «a», что дает нам конфликт FIRST / FOLLOW.

FIRST-наборы также могут использоваться во время анализа для повышения производительности. Если у вас есть Nullable нетерминальный NullableNt, вы можете расширить его, чтобы увидеть, может ли он что-либо потреблять, или может быть быстрее проверить, содержит ли FIRST(NullableNt) следующий токен, а если нет, то просто проигнорировать его (обратный просмотр против прогнозирующего анализа). Другим улучшением производительности может быть дополнительное предоставление лексическому сканеру текущего набора FIRST, чтобы сканер не пробовал все возможные терминалы, а только те, которые в настоящее время разрешены контекстом. Это конфликтует с зарезервированными терминалами, но они не всегда нужны.

В парсерах снизу вверх возникают конфликты разного типа, а именно: уменьшение / уменьшение и смещение / уменьшение. Они также используют наборы предметов для обнаружения конфликтов, а не ПЕРВЫЙ, СЛЕДУЮЩИЙ.

Ваша грамматика не будет работать с LL-парсерами, потому что она содержит левую рекурсию. Но ПЕРВЫМИ наборами для E, T и V будут {id} (при условии, что ваш T := T*V | T означает T := T*V | V).

Answer 2

Ответ:

E-> E + T | T

левая рекурсия

E-> TE '

E' -> + TE'| eipsilon

T-> T * V | T

левая рекурсия

T-> VT'

T '-> * VT' |epsilon

нет рекурсии в

V -> (id)

Поэтому грамматика:

E-> TE '

E '-> + TE' | epsilon

T-> VT '

T' -> * VT '| epsilon

V-> (id)

FIRST (E) = {(}

FIRST (E ') = {+, epsilon}

FIRST (T) = {(}

FIRST(T ') = {*, epsilon}

FIRST (V) = {(}

Начальный символ = FOLLOW (E) = {$}

E->TE ', E' -> TE '| epsilon: FOLLOW (E') = FOLLOW (E) = {$}

E-> TE ', E' -> + TE '| epsilon: FOLLOW (T) = FIRST (E ') = {+, $}

T-> VT', T '-> * VT' | epsilon: FOLLOW (T ') = FOLLOW (T) = {+,$}

T-> VT ', T -> * VT' | epsilon: FOLLOW (V) = FIRST (T) = {*, epsilon}

Правила для первых сетов

If X is a terminal then First(X) is just X!
If there is a Production X → ε then add ε to first(X)
If there is a Production X → Y1Y2..Yk then add first(Y1Y2..Yk) to first(X)
First(Y1Y2..Yk) is either
    First(Y1) (if First(Y1) doesn't contain ε)
    OR (if First(Y1) does contain ε) then First (Y1Y2..Yk) is everything in First(Y1) except for ε  as well as everything in First(Y2..Yk)
    If First(Y1) First(Y2)..First(Yk) all contain ε then add ε to First(Y1Y2..Yk) as well.

Правила для последующих наборов

First put $ (the end of input marker) in Follow(S) (S is the start symbol)
If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).
If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
If there is a production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)

Answer 3

Википедия - твой друг. См. обсуждение парсеров LL и первых / последующих наборов.

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