Рубрики

СЛЕДУЙТЕ за набором в синтаксическом анализе

Мы обсудили следующие темы по синтаксическому анализу.

Введение в синтаксический анализ
Почему ПЕРВЫЙ и СЛЕДУЕТ?
Первый набор в синтаксическом анализе

В этом посте обсуждается FOLLOW Set.

Следуйте (X), чтобы быть набором терминалов, которые могут появиться сразу справа от Нетерминала X в некоторой форме предложения.
Пример:

S ->Aa | Ac
A ->b  

      S                  S  
     /  \              /   \
    A    a            A     C  
    |                 |
    b                 b   

Here, FOLLOW (A) = {a, c}


Правила для расчета следуют следующим образом:


1) FOLLOW(S) = { $ }   // where S is the starting Non-Terminal

2) If A -> pBq is a production, where p, B and q are any grammar symbols,
   then everything in FIRST(q)  except Є is in FOLLOW(B).

3) If A->pB is a production, then everything in FOLLOW(A) is in FOLLOW(B).

4) If A->pBq is a production and FIRST(q) contains Є, 
   then FOLLOW(B) contains { FIRST(q) – Є } U FOLLOW(A) 

Пример 1:

Production Rules:
E -> TE’
E’ -> +T E’|Є
T -> F T’
T’ -> *F T’ | Є
F -> (E) | id

FIRST set
FIRST(E) = FIRST(T) = { ( , id }
FIRST(E’) = { +, Є }
FIRST(T) = FIRST(F) = { ( , id }
FIRST(T’) = { *, Є }
FIRST(F) = { ( , id }

FOLLOW Set
FOLLOW(E)  = { $ , ) }  // Note  ')' is there because of 5th rule
FOLLOW(E’) = FOLLOW(E) = {  $, ) }  // See 1st production rule
FOLLOW(T)  = { FIRST(E’) – Є } U FOLLOW(E’) U FOLLOW(E) = { + , $ , ) }
FOLLOW(T’) = FOLLOW(T) =      { + , $ , ) }
FOLLOW(F)  = { FIRST(T’) –  Є } U FOLLOW(T’) U FOLLOW(T) = { *, +, $, ) }


Пример 2:

Production Rules:
S -> ACB|Cbb|Ba
A -> da|BC
B-> g|Є
C-> h| Є

FIRST set
FIRST(S) = FIRST(A) U FIRST(B) U FIRST(C) = { d, g, h, Є, b, a}
FIRST(A) = { d } U FIRST(B) = { d, g, Є }
FIRST(B) = { g, Є }
FIRST(C) = { h, Є }

FOLLOW Set
FOLLOW(S) = { $ }
FOLLOW(A)  = { h, g, $ }
FOLLOW(B) = { a, $, h, g }
FOLLOW(C) = { b, g, $, h }


Замечания :

  1. Є как FOLLOW ничего не значит (Є — пустая строка).
  2. $ называется end-marker, который представляет конец входной строки, поэтому используется при синтаксическом анализе, чтобы указать, что входная строка была полностью обработана.
  3. Используемая выше грамматика является контекстно-свободной грамматикой (CFG). Синтаксис языка программирования может быть указан с помощью CFG.
  4. CFG имеет форму A -> B, где A — это один нетерминал, а B может быть набором грамматических символов (то есть как терминалов, так и нетерминалов)
  5. Тест на синтаксический анализ

    Эта статья составлена Вайбхавом Баджпаем . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

    СЛЕДУЙТЕ за набором в синтаксическом анализе

    0.00 (0%) 0 votes