Мысал 5.2. Грамматика үшін 5.1 мысалынан кеңейтілген МП-автоматын құру. Последовательность построения МП-автомата құру жүйелілігі мынадай болады.
1) Q={q,r}, q0 = q, T={+,(,),a}, N={+,(,),a,S,A}, N0 = #, 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 символына дейін шектелген α(VTVN)*, тізбегінен шығарылған;
FOLLOW(k, A) – терминалды тізбектегі k символына дейін қысатылған жиын, олар A VN шығару тізбегімен аяқталады. Формальды түрде бұл жиындар төмендегідей тілдермен анықтауға болады:
- FIRST(k, α) = {ω VT* | 3 нәтижесі α ^*со и |ω| ≤ k немесе 3 нәтижесі α ^
- FOLLOW(k, A) = {ω VT* | 3 нәтижесі S^*aA/n иωFIRST(k, γ); α, γ V* AVN,k>0}.
Достарыңызбен бөлісу: |