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

Барлық әдістер синтаксистік анализде процессордың құрылымын құруда және өзінің кейбір жұмысында КС-граматикасын қолданынылады.

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

Қарастырылған анализатор еңгізу тізбегінде солдан оңға қарай қарастырылады.Ол екі стратегияның біреуін қолданады:шығарылмаған және еңгізілген.Шығарылмаған анализаторды граматикалық ережесі жоғарыдан төменге қарай және жоғарғы ережелер төменгіге қарағанда бұрын орындалады.Еңгізілген анализаторда төменгі ережелер жоғарыға қарағанда бірінші орындалады.

W L(G) кейбір КС-грамматикасы үшін G анализденген немесе талданған дейік,егер оның берілген грамматикасында шығару ағашы болса ғана.

Әдетте компилятор синтаксистік анализді МП-автоматының модельдеу жолымен орындайды.Ол еңгізу тізбегін анализдейді.МП-автоматы еңгізу тізбегінде сол жаққа шығаруды және оң жаққа талдауды орындайды.Сол және оң талдаулар грамматика ережесінде мына түрінде беріледі 1,2,3,...,р .

Мысал1.

(1) EE+T (4) TP

(2) ET (5) Pi

(3) TT*P (6) P(E)

i*(i+i) тізбегінің сол шығарылуын қарастырайық:

E(2) T(3) T*P(4) P*P(5) i*P(6) i*(E)(1) i*(E+T)(2)

I*(T+T)(4) i*(P+T)(5) i*(i+T)(4) i*(i+P)(5) i(i+i).

Анықтама бойынша тізбектің сол талдауы сол жақ шығарылуда грамматика ережелерінің нөмерлерін кезекпен орындалуды қамтамассыз етеді.і*(і+і)-бұл тізбектің талдауы кезекпен 23456124545 орындалады.

І*(і+і) тізбектің оң шығарылуын құрайық:

E(2) T(3) T*P(6) T*(E)(1) T*(E+T)(4) T*(E+P)(5)

T*(E+i)(2) T*(T*i)(4) T*(P*i)(5) T*(i+i)(4)

P*(i+i)(5) i*(i+i).

Тізбектің оң талдауы –бұл ережелердің кезектің нөмірленуі .Сондықтан тізбктің і*(і+і)- оң талдауынан кейін кезекпен 54542541632 орындалады.

Сол және оң тізбектің і*(і+і) –талдауынан өзгереді.1.1 суретіндегі G грамматикасында көрсетілген.Шығару ағашы суретте деформирациялаған. Осыған орай грамматика ережелерінің қолданылуын кезекпен көреміз.1.1 суретінде а) ағаштың сонынан шығару ережесінде қолданылады,ал б) суретінде оңынан қолданылады.

E

(2) --------- ----------------------(2)

(3) ---- ------------------(3)

Т Р T P

Т

(4) ---- -----------------(6)

(5) ---- -------------------(1)

(6) ---------------------- E -------------(4)

-------------(5)

(1) ---------------------

E ------------------------------(2)

(2) -----------

T ------------------------------(4)

(4) ------------

-----------------------------(5)

P

(5) -----------

(4) -------------------------------------- ---------------------------------------(4)

P P

(5) ------------------------------------ ---------------------------------------(5)

суреті жақсы көрсетілген. Онда сол талдау сол шығарумен сәйкес келеді.Ал оң талдау оң шығарумен сәйкес келеді.
Шығарылмаған талдау.

Шарт бойынша КС-грамматикасының синтаксистік анализін орындалуын қарастырамыз.Анализденген тізбек солдан оңға қарай қарастырайық.Егер бізге сол талдау  тізбегінде L(G) онда G КС грамматикасында немесе мүмкіндіктермен ағаштар талдауын құрады.Ағаштың тамырын негізгі грамматикасының S символымен белгілейік.Егер =і1,і2... іп болса , онда і1 ереженің нөмерін анықтайды.Егер ереже бойынша SХ1 Х2...Хі-1 Хі Хі+1...Хк болады.S нүктесі х1,х2,...хі-1,хі,хі+1,...,хк символымен белгіленген .Егер хі-терминалды емес бірінші сол жақтағы тізбектегі х1,х2,хн болса, онда бірінші і-1 символындағы тізбек  символы х1, х2,...,хі-1 болады.Келесі шығару ережесі грамматикада і2 нөмерімен белгіленген.Мысалға, ереже бойынша ХіУ1 У2...У1 болса, онда оның құрылымы ағаштар тізбегінде  болады.Оны біз 1.2суретіндегі 1,2,...,1 символымен белгілейік. сурет.

S

S

w
талдаудың сол жақ стратегиясы ағаштар талдауын тамырынан бастап оңнан солға қарай барады.Әрбір G грамматикасы үшін терминалданбаған МП-құраушысының негізі синтаксистік анализатор болып табылады.Осыған орай құрылған М1 анализаторы сол жақ  тізбегімен анықталады.Ол келесі операциялардан тұрады:

Терминалды ашу дүкенін жоғарысында орналасады.Р ережесі бойынша ол  функциясымен бірге орындалады.

Ағымды еңгізу символы  функциясымен салыстырады.

МЫСАЛ 1.2.

G грамматикасы үшін сол анализатор құрамыз.

1 ЕЕ+Т 4 ТР

2 ЕТ 5 Рі

3 ТТ*Р 6 РР.

1q i +* i+*E,T,P, 1,2,3,4,5,6,,q,E,q

• 
  функциясын анықтайық.
  

Ереже бойынша 2 q,a,a)= анықтамасы үшін ортақ а є .

qqq

qq* q

qq qi

Шығу тізбегі үшін тізілген анализатор М1 мынадай мәндерді орындауы мүмкін

q i+ i*i, +(q, i+i*i , +, 1) +(q, i+i*I, +, 12)

+(q, i+i*i, P+,124) +(q, i+i*I +, 1245)

+(q, + i*i, +, 1245) +(q, i*i, , 1245)

+(q, i*i, T*P, 12453) +(q, i*I, *, 124534)

+(q, i*i, i*P, 1245345) +(q, * i, *, 1245345)

+(q, i, P, 1245345) +(q, I, i, 12453455)

+(q,  , 12453455).

Шығу тізбегі і+і*і мынаған тең1245345