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

жүктеу 14,81 Mb.

бет	118/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

1 ... 114 115 116 117 118 119 120 121 ... 127

Зертханалық жұмыс №6 LL(1)- грамматикасы үшін рекурсивті түсу әдісімен синтаксисті талдау Мазмұны
Теория негізі Анықтама 6.1.
Анықтама 6.2.
Анықтама 6.3.

Мысал 5.2. Грамматика үшін 5.1 мысалынан кеңейтілген МП-автоматын құру. Последовательность построения МП-автомата құру жүйелілігі мынадай болады.

1) Q={q,r}, q₀ = q, T={+,(,),a}, N={+,(,),a,S,A}, N₀ = #, Z=r.

2) F(q, ε, S+A) = (q, S), F(q, ε, A) = (q, S), F(q, ε, (S)) = (q, A), F(q, ε,a) = (q,A).

3) F(q, t, ε ) = (q, t) әрбіреуі үшін t

{+, (, ), a}.
4 )F(q,ε,#S) = (r,ε).

Кеңейтілген МП-автоматы бойынша құрылған(а) жолын тану 5.2 кестесінде көрестілген. Алынған МП-автомат детерминалсыз болады.

Кесте 5.2 – Кеңейтілген МП-автоматы бойынша (а)жолын анықтау

Конфигурации номері	Ағымдағы қалпы	Енгізу жолы	Магазин құрамы
1	q	(a)	#
2	q	a)	#(
3	q	)	#(а
4	q	)	#{А
5	q	)	#(S
6	q	ε	#(S)
7	q	ε	#A
8	q	ε	#S
9	r	ε	ε

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

Келесі функцияларды орындайтын, бағдарламалық құралды өңдеу:

а) формальды грамматиканы енгізу және оның КС – грамматика классына сәйкестігін тексеру;

б) КС – грамматика бойынша МП-автоматын құру;

в) КС – грамматика бойынша кеңейтілген МП-автоматын құру;
Құрылған автомат көмегімен кейбір енгізу жолын бейнелеу:

а) енгізу жолы КС-грамматикасының тіліне енеді және МП-автоматымен қабылданады;

б) енгізу жолы КС-грамматикасының шығу тіліне енбейді және МП-автоматымен қабылданбайды.

Тапсырманың дара нұсқалары 4.1 кестесінде көрсетілген.

Зертханалық жұмыс №6

LL(1)- грамматикасы үшін рекурсивті түсу әдісімен синтаксисті талдау
Мазмұны: LL(1)-грамматикасы үшін айқындауыштардың функционалдық модельдеуі. LL(1) - грамматикасының қажетті және жеткілікті шарттарын қолдану. LL(1) - грамматикасы үшін тізбектерді анықтау функционалдау.
Мақсаты: - «LL(k) - грамматика» түсінігін толықтыру, LL(k) –грамматикасының қажетті және жеткілікті шарттары;

- LL(1)-грамматика үшін FIRST(k, α) және FOLLOW(k, α), көптігінің құрылымын үйреніп дағдылану.

Теория негізі

Анықтама 6.1. КС-грамматикада LL(k) қасиеті бар кейбіреуіне k>0, егер әрбір шығу қадамында біртекті таңдау үшін МП-автоматына стектың жоғарыдағы символын білу жеткілікті және енгізу жолының басындағы ағымдағы қалыптың бірінші k символдарын қарастыру.

Анықтама 6.2. егер ол кейбіреуіне k>0 LL(k) қасиетінде болса, онда КС-грамматикасы LL(k)-грамматикасы деп аталады.

LL(k)-грамматика талдауының негізінде тіл жолының сол жақ талдауы орналасқан. Грамматиканың бастапқы символы шығу сентенциальдық форма болады, ал бүтін – тілдің берілген жолы. Талдаудың әрбір қадамында грамматика ережесі сентенцияның терминал емес сол жағына қолданылады. Берілген процесс талдау ағашын жоғарыдан төменге құруға сәйкес келеді. Осыдан шықанны LL(k): бірінші «L» («left» сөзінен) символдар тізбегінің соңғы енгізілудің сол жақ шығаруы дегенді білдіреді, екіншісі «L» - анықтаманың жұмысындағы сол жақ шығуы.

Анықтама 6.3. LL(k)-грамматикасын анықтауды құру үшін екі жиын қолданылады:

FIRST(k, α) – терминалды жиындар тізбегі, k символына дейін шектелген α(VTV_N)*, тізбегінен шығарылған;
FOLLOW(k, A) – терминалды тізбектегі k символына дейін қысатылған жиын, олар A V_N шығару тізбегімен аяқталады. Формальды түрде бұл жиындар төмендегідей тілдермен анықтауға болады:
- FIRST(k, α) = {ω V_T* | 3 нәтижесі α ^*со и |ω| ≤ k немесе 3 нәтижесі α ^

- FOLLOW(k, A) = {ω V_T* | 3 нәтижесі S^*aA/n иωFIRST(k, γ); α, γ V* AV_N,k>0}.

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:

1 ... 114 115 116 117 118 119 120 121 ... 127