Пәнін оқыту-әдістемелік кешен 5В060200 «Информатика» мамандығына арналған ОҚУ-Әдістемелік материалдар



жүктеу 2,68 Mb.
бет121/127
Дата19.11.2018
өлшемі2,68 Mb.
#20473
1   ...   117   118   119   120   121   122   123   124   ...   127

Алгоритм 6.3. LL(1)-грамматикасы үшін тізбекті анықтау функциясы

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



2 Қадам. Стекте және енгізу буферінде ε жолы бос қалғанына дейін, келесі әрекеттердің біреуін орындаймыз:

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

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

  • Егер стектың басында терминал емес а символы орналасса және ол енгізу жолының символымен сәйкес келсе, онда «алып тастау» операциясын орындаймыз. Бұл дегеніміз стектан және енгізу буферінен берілген терминалды символды өшіреміз;

  • Егер стектың құрылымы және енгізу буфері бос болса, онда шығару жолы толығымен оқылады, және талдау сәтті аяқталды;

  • Егер шарттардың біреуі орындалмаса, онда тізбек берілген тілге жатпайды, және алгоритм өзінің жұмысын қателікпен аяқтайды.

Мысал 6.1. G ({S, T, R}, {+, -, (, ), a, b}, P, S), грамматикасы P: 1) S→TR; 2) R→ε | +TR | - TR; 3) T→(S) |a|b ережелерімен берілген, G грамматика тілінің (a+(b-a)) жолына анықтауышты құру.

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



N0={R};

N1 = {R}, т.к. N0 = N1, онда P жиынына ерже енеді:

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) жиынының құрылуы



FIRSTi(1,A)

0

1

2

FIRST(1,A)

S

Т

T, (, a, b

T, (, a, b

(,a,b

R

+,-

+,-

+,-

+,-

Т

(,a,b

(,a,b

(,a,b

(,a,b

3 Кезең. А терминал еместің әрбіреуіне FOLLOW(1, A) жиынының құрылуы 6.2. кестесінде көрсетілген.

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



Қадам

Терминал емес

FOLLOWi(1, A)

FOLLOWi’(1,A)

FOLLOWi’(1,A)

0

S

)









R

Ø

Ø

Ø



Т

R

R,+,-

R,+,-

1

S

),ε

),ε

),ε



R

),ε

),ε

),ε



Т

R,+,-

R,+,-

R, +, -, ), ε

2

S

),ε

),ε

),ε



R

),ε

),ε

),ε



Т

R, +, -, ), ε

R, +, -, ), ε

R, +, -, ), ε

FOLLOW(1,S)

),ε

FOLLOW(1,R)

),ε

FOLLOW(1, T)

+, -,), ε

4 Кезең. FIRST(1, A) және FOLLOW(1, A) әрбір А терминал емес жиындары 6.3. кестесінде көрсетілген.

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



А

FIRST(1,A)

FOLLOW(1, A)

S

(,a,b

),ε

R

+,-

),ε

Т

(,a,b

+, -,), ε

G грамматикасы LL(1)-грамматикасы болып табылады, бұл дегеніміз әрбір А, терминал емес жиын үшін, FIRST(1, A) жиыны қос – қостан қиылыспайды, ал терминал емес R жиынында да олар FOLLOW(1,R)жиынымен қиылыспайды.

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



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

Стек

Ену буфер

Әрекет

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)

ε

ε

жол толығыменқабылданды

6 Қадам. Шығарудың келесі тізбегін алдық:


№ 6 зертханалық жұмысқа орындау тапсырмалары

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



  1. КС грамматикасына енгізуді орындау

  2. FIRST (1.A) және FOLLOW (1.A)жиындарын әрбір терминалды емес, символдар грамматикасына құру.

  3. LL(1)шартын қажетті және жеткілікті түрде тесеру, КС грамматикасына енгізу.

  4. LL(1)грамматикасы үшін функционалдық модельді тану

Осы жағдайда бақылау мысалдарын құру:

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

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

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

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

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


жүктеу 2,68 Mb.

Достарыңызбен бөлісу:
1   ...   117   118   119   120   121   122   123   124   ...   127




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау