Лекция 16 Тақырыбы: FIRST және FOLLOW функциялары

Лекция 16

Тақырыбы: FIRST және FOLLOW функциялары

2. FOLLOW функциясы

1. Болжаушы анализатор кестесін құруда бізге екі функция керек болады - FIRST және FOLLOW.

Айталық G = (N, T, P, S) - КБ-грамматика. Грамматика символдарынан құралған, еркін алынған α тізбегі үшін FIRST(α)-ны α-дан шығатын қатардың басы болып табылатын терминалдар жиыны ретінде анықтайық. Егер α→*е онда е де FIRST(α)-ға тиісті.

А бейтерминалы үшін FOLLOW(A) функциясын грамматиканың қайсыбір сентенциалды формасында тікелей А-дан кейін пайда болуы мүмкін а терминалдарының жиыны ретінде анықтаймыз, яғни кейбір α, β(N T)^* үшін S→ ^* α Aaβ түріндегі шығару бар болатын а терминалдарының жиыны ретінде анықтаймыз. Шығару барысында А және а арасында өздерінен е келіп шығатын бейтерминал символдар бар болуы мүмкін.Егер А қайсыбір сентенциалды форманың ең оң жақ символы бола алатын болса, онда $ да FOLLOW(A) жиынына жатады.

FIRST функциясын есептеу алгоритмін қарастырамыз. 

Алгоритм 4.3. Грамматика символдары үшін FIRST функциясын есептеу.

Кірісі. КБ-грамматика G = (N, T, P, S).

Шығысы. Әрбір х (N UT) символы үшін FIRST(х) жиыны

Тәсіл. 1-3 қадамдарын орындау:

• 
  Егер х – терминал болса, онда жиынға FIRST(X) = {X} енгізу; егер х – бейтермиал болса FIRST(X) = .
  
• 
  Егер Р-да х *e ережесі бар болса, онда e-ні FIRST(X)-ке енгізу.
  
• 
  FIRST(X)-ң ешқандай жиындарына жаңа элемент қосуға болмай қалғанынша төмендегіні орындау:
  

Алгоритм 4.4. FIRST функциясын тізбек үшін есептеу

Кірісі. КБ-грамматика G = (N, T, P, S).

Шығысы. FIRST(X₁X₂...X_n) жиындары, X_i (N T).

Тәсіл. 1-3 қадамдарын орындау:

• 
  Алдыңғы алгоритм көмегімен FIRST(X) функциясын әрбір X (N T) үшін есептеу.
  
• 
  Енгізу (Положить) FIRST(X₁X₂...X_n) = .
  
• 
  FIRST(X₁)-дегі е-элементеместердің барлығын FIRST(X₁X₂...X_n)-ге қосу. Оған тағы да егер е FIRST(X₁)-ге жататын болса, онда FIRST(X₂)-дегі барлық е-элемент еместерді қосу, егер е FIRST(X₁)-ге де, FIRST(X₂)-ге де жататын болса, онда FIRST(X₃)-тегі барлық е-элемент еместерді қосу, т.с.с. Ең соңында егер e FIRST(X_i) болса, онда е тізбегін FIRST(X₁X₂...X_n)-ке қосу.
  

2. FOLLOW функциясын есептеу алгоритмін қарастырайық.

Алгоритм 4.5. Грамматика бейтерминалдары үшін FOLLOW функциясын есептеу

Шығысы. Әрбір X Є N символы үшін FOLLOW(X) жиыны.

Тәсіл. 1-4 қадамдарын орындау:

• 
  Әрбір X Є N символы үшін FOLLOW(X) = (енгізу - положить)
  
• 
  $ -ды FOLLOW(S) –ке қосып қою.
  
• 
  Егер Р - A αBβ шығару ережесі болса, мұнда , α, β(NT)^*, онда FIRST(β)-дағы е-ден басқа барлық элементтерді FOLLOW(B)-ға қосып қою.
  
• 
  FOLLOW(X) жиындарының ешқайсысына ештеңе қосуға болмай қалғаншга мынаны орындау:
  

Мысал 4.4. Мысал4.3-тегі грамматиканы қарастырамыз. Ол грамматика үшін

 

	FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
	FIRST(E') = {+, e}
	FIRST(T') = {*, e}
	FOLLOW(E) = FOLLOW(E') = { ), $}
	FOLLOW(T) = FOLLOW(T') = {+, ), $}
	FOLLOW(F) = {+, *, ), $}

 

Мысалы, id және сол жақ жақша i = 1 кезінде FIRST(F)-ке 3- қадамда қосылады, өйткені 1-қадамға сәйкес FIRST(id) = {id} және FIRST(”(”) = {”(”}. i = 1 болғанда 3-қадамда T FT' шығару ережесіне сәйкес FIRST(T)-ға id мен сол жаң жақша қосылады. 2-қадамда FIRST(E') е енгізіледі.

FOLLOW жиындарын есептеу кезінде 2-ші қадамда FOLLOW(E)-ге $ енгізіліп қойылады3-ші қадамда F (E) шығару ережесіне сәйкес FOLLOW(E)-ге оң жақ жақша да қосылады. E TE' ережесіне қолданылған 4-ші қадамда FOLLOW(E')-ге $ мен оң жақ жақша енгізіледі. E'^*e болғандықтан олар FOLLOW(T) жиынына да қосылады. E TE' шығару ережесіне сәйкес 3-ші қадамда FOLLOW(T)-ға FIRST(E')-дегі е-ден бөлек барлық элементтер де қосылады.