LL(1 ) –грамматикалар.
4..Грамматикаларни LL(1) кўринишга айлантириш.
Калит сузлар.
ПС-тахлил
Барг
Илдиз
Қатор
Махсулот
Қисм қатор
S-грамматика
Йўналтирувчи белгилар
Хамрох-белги
Рекурсия
1.«Перенос-свертка» туридаги синтаксис тахлил.
Ушбу булимда юкориловчи синтаксис тахлилнинг « перенос-свертка» туридаги синтаксис тахлилнинг асосий усуллари каралади. Бундан буёгига кискача ПС-тахлил деб аталади.
ПС-тахлил барглардан бошлаб ва илдиздан дарахт юкорисига караб ишлайди ва кирувчи каторнинг разбор дарахтини куришга харакат килади. Бу жараённи w каторни грамматиканинг бошлангич белгисига свертка- алмашиш сифатида караш мумкин. Алмашувнинг хар бир кадамида кандайдир махсулотнинг унг булакидаги кисмкатор махсулотнинг чап булагидаги белги билан алмаштирилади ва агар хар бир кадамда кисмкаторлар тугри ва аник танланса, у холда биз унгдан келтириб чикарилувчи мурожатни оламиз.
Мисол:
Куйидаги грамматикани караймиз.
S aABe
A Abc| b
B d
abbcde гап S га куйидаги кадамлар ёрдамида келтирилади:
abbcde
aAbcde
aA de
aABe
S
Биз кандайдир махсулотни унг булагига мос келувчи abbcde каторни кисмкаторни кидириш максадида сканерлаймиз. Бундай кисмкаторлар булиб b ва d хисобланади. Энг четки чапки b ни оламиз ва уни А b; махсулотнинг чап булаги булган нотерминал А билан алмаштирамиз., шундай килиб aAbcde каторни оламиз. Энди махсулотнинг унг булагига Abc, b ва d кисмкаторлар мос келади. махсулотнинг унг булагига мос келувчи b энг четки чап кисмкатор булса хам кисмкаторни алмаштириш учун Abc кисмкаторни танлаймиз ва уни А Abc махсулотга мос нотерминал A билан алмаштирамиз. Натижада aAde каторни оламиз. Махсулотнинг чап булагини В d да dни В га алмаштириб aABe ни оламиз ва у биринчи махсулотга мос равишда бошлангич белги S билан алмаштирилади. Шундай килиб, туртта алмаштиришдан келиб чикадиган кетма-кетлик abbcde каторни бошлангич белги S га келтиришга имкон беради. Бу кискартиришлар унгдан келтириладиган алмаштиришлар (яъни тескари тартибда ёзилган) ни ифодалайди.
S aABe aA de aAbcde abbcde
Do'stlaringiz bilan baham: |
