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



жүктеу 2,68 Mb.
бет112/127
Дата19.11.2018
өлшемі2,68 Mb.
#20473
1   ...   108   109   110   111   112   113   114   115   ...   127

Мысал 4.5. Грамматикасы G = ({+,n}, {L, M, N},P, L) ережелерімен Р:

1) L → M ; 2 ) M → N; 3) N —→ N+ | n. Эквивалентті грамматиканы G алгоритм 4.5 бойынша құрамыз.

Қадам 1.;N0L={L}

N0L = {L};

N1L = {L, M};

N2L = {L, M, N};

N3L = {L, M, N}.

Сонымен қатар N2L = N3L , то N L = {L, M, N}.



N0M = {M};

N1M = {M, N};

N2M = {M, N}.

Сонымен қатар N1M = N2M , то NM = {M, N}.



N0N = {N};

N1N = {N}.

N1N = N0N , то N N = {N}.

Алгоритм 4.6. Сол факторизация ережесін шектеу.

Кіру: КС-грамматикасы G = (VT, VN, P, S).



Шығу: Эквивалентті КС-грамматикасы G'=(VT,VN′,P,S′) біркелкі префиксіз оң бөліктегі бөлімнен терминал еместі анықтайтын.

Қадам 1. Записать все правила для нетерминала X терминал емес барлық ережелерді жазу, біркелкі префиксы α V* барларды альтернативті түрдегі : X →αβ1 αβ 2 K αβ n β1 β 2 K β n V

Қадам 2. Сол жақтағы жақшадан префикс α- ны альтернативтің әрбір жолына шығару:.X → α (β1 | β2 | K | β n Рп )•

Қадам 3. Терминал еместі Y жаңа белгімен белгілеймі қалған жақшадағы: X →αY, Y → β1 | β 2 |K| β n.

Қадам 4. Терминал еместі жаңа териналь емес Y –мен толықтырамыз және ережені X және Y өзгертеміз.

Қадам 5.Қадам 1-4 қайталаймыз.

Мысал 4.6. G = ({k,l,m,n},{S},P,S) грамматикасы ережелерімен P: 1) S kSl; 2) S kSm; 3) S n.

Эквивалентті грамма­тиканы G алгоритму 4.6 құрамыз:

Қадам1. SkSl|kSm|n.

Қадам2. S→kS(l|m)|n.

Қадам 3,4. Терминал еместі жаңа териналь емес С –мен толықтырамыз , сонда G = ({k,l,m,n}, {S, C},P, S) грамматикасын ережесімен аламыз P: 1) S → kSC; 2)S→n; 3) C → m.

Алгоритм 4.7. Тура сол рекурсияны шектеу.

Кіру: КС-грамматикасы G = (VT, VN, P, S).



Шығу: Эквивалентті КС-грамматикасы G'= (VT,VN′,P,S′ ереже түрінсіз. A→Aα, A VN, α V *

Қадам 1. Грамматикадан барлық X терминал емес рекурсия ережелерін шығарамыз:
Қадам 2. Жаңа терминал емес Y шығарамыз


Қадам 3. X оң бөлік үшін рекурсивті ережені ауыстырамыз, жаңа терминал еместі қолдана отырып, бірақта тіл өзгермеуі қажет:

Қадам 4. Жиынды жаңа терминал емес Y грамматикасымен толықтырамыз. Қадам3–тегі алынған жиынның грамматика ережесімен толықтырамыз

Қадам 5. Барлық рекурсивті терминал емес грамматикаға қадам1-4 қайталаймыз.Одан кейін терминал емес жиынды және ережені мына түрде қарастырамыз VN′ және .P
4 зертханалық жұмысқа орындау тапсырмалары.


жүктеу 2,68 Mb.

Достарыңызбен бөлісу:
1   ...   108   109   110   111   112   113   114   115   ...   127




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

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