«Соңғы автоматтар және формальдік тілдер теориясы»

1 Қадам. Стекқа S грамматикасының бастапқы символын орналастырамыз, ал енгізу буферіне символдардың шығу тізбегін орналастырамыз.

• 
  Егер стектың басында терминал емес А символы және енгізу жолының а символы орналасса, онда А→х ережесі бойынша «түйіншек» операциясын орындаймыз, бірақ шарт бойынша, онда аFIRST(1, x), бұл дегеніміз стектан А символын шығарамыз және стекқа жолын х енгіземіз, ал енгізу буферінің құрамын өзгертуге болмайды;
  
• 
  Егер стектың басында терминал емес А және енгізу жолының а символы орналасса, онда А→х ережесі бойынша «свертка» операциясын орындаймыз, бірақ шарт бойынша, онда аFOLLOW(1, A), бұл дегеніміз стектан А символын шығарамыз және стекқа жолын х енгіземіз, ал енгізу буферінің құрамын өзгертуге болмайды;
  
• 
  Егер стектың басында терминал емес а символы орналасса және ол енгізу жолының символымен сәйкес келсе, онда «алып тастау» операциясын орындаймыз. Бұл дегеніміз стектан және енгізу буферінен берілген терминалды символды өшіреміз;
  
• 
  Егер стектың құрылымы және енгізу буфері бос болса, онда шығару жолы толығымен оқылады, және талдау сәтті аяқталды;
  
• 
  Егер шарттардың біреуі орындалмаса, онда тізбек берілген тілге жатпайды, және алгоритм өзінің жұмысын қателікпен аяқтайды.
  

1 Кезең. G грамматикасын G^′, граммтикасына айналдырайық, оның құрамында ε-ережесі болмауы керек:

1) S→ TR | T; 2) R→ +TR | +T | -TR | -T; 3) T→(S) |a|b.

2 Кезең. А терминал емеске FIRST(1, A) жиынының құрылуы 6.1. кестесінде көрсетілген.

Кесте 6.1 – FIRST(1, A) жиынының құрылуы

Кесте 6.2 - FOLLOW(1,A) жиынының құрылуы

Кесте 6.3 - FIRST(1,A) және FOLLOW(1, A) жиындары

5 Қадам. G грамматикасы үшін (a+(b-a)) жолының талдануы 6.4. кестесінде көрсетілген

Стек	Ену буфер	Әрекет
S	(a+(b-a))	түйіншек S→TR, т.к. (FIRST(1, TR)
TR	(a+(b-a))	түйіншек T→(S), т.к. ( FIRST(1, (S))
W	(a+(b-a))	алып тастау
S)R	a+(b-a))	түйіншек S→TR, т.к. a FIRST(1, TR)
TR)R	a+(b-a))	түйіншек T→a, т.к. a FIRST(1, a)
aR)R	a+(b-a))	алып тастау
R)R	+(b-a))	түйіншек R→+TR, т.к. + FIRST(1, TR)
+TR)R	+(b-a))	алып тастау
TR)R	(b-a))	түйіншек T→(S), т.к. ( FIRST(1, (S))
(S)R)R	(b-a))	алып тастау
S)R)R	b-a))	түйіншек S→TR, т.к. b FIRST(1, TR)
TR)R)R	b-a))	түйіншек T→b, т.к. b FIRST(1, b)
bR)R)R	b-a))	алып тастау
R)R)R	-a))	түйіншек R→-TR, т.к. - FIRST(1, -TR)
-TR)R)R	-a))	алып тастау
TR)R)R	a))	түйіншек T→a, т.к. a FIRST(1, a)
aR)R)R	a))	алып тастау
R)R)R	))	түйіншек R→ε, т.к. ) FOLLOW(1, R)
)R)R	))	алып тастау
R)R	)	түйіншек R→ε, т.к. ) FOLLOW(1, R)
)R	)	алып тастау
R	ε	түйіншек R→ε, т.к. ε FOLLOW(1, R)
ε	ε	жол толығыменқабылданды

Программалық әдісті орындау үшін, LL(1) грамматикасының тізбегі үшін талдау процесі орындалады. Программалық әдіс келесі функцияларды орындау тиіс:

1. 
   КС грамматикасына енгізуді орындау
   
2. 
   FIRST (1.A) және FOLLOW (1.A)жиындарын әрбір терминалды емес, символдар грамматикасына құру.
   
3. 
   LL(1)шартын қажетті және жеткілікті түрде тесеру, КС грамматикасына енгізу.
   
4. 
   LL(1)грамматикасы үшін функционалдық модельді тану
   

А) енгізілген КС грамматикасы LL(1) грамматикасы болып табылмайды.

Б) шығарылған КС грамматикасы LL(1)грамматикасы болып табылады.

В) берілген КС грамматикасы LL(1)грамматикасы болып табылады және енгізілген жол грамматика тіліне жатады.

Тізбектің жиынын кесте көмегімен көрсету, шығару ағашы. Тапсырмалардың индивидуалдық нұсқаларын зертхналық жұмыста шығару мәліметтеріне негіздейді.

(а+(b-a)) тізбегі үшін ағаштардың шығарылуы