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

LR- талдау

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

LR-стегінің процессі терминалды және терминалды емес сөзін білдіреді, ол оң жақ бөлігінен шығарылады.

LR-процессін орындаған кезде кез-келген уақытта келесі екі әрекет орындалуы мүмкін:

+-----------------

|содержимое стека << входная цепочка

+-----------------

1. 
   Қозғалу. Біз бірінші енгізу тізбегінің оқылмағанм символын алып, оны стекке ауыстырамыз. Мысалы:
   
2. 
   +---------
   
3. 
   қозғалысқа дейін| aMBbaC abcdef
   
4. 
   +---------
   
5. 
   
   
6. 
   +---------
   
7. 
   қозғалыстан кейін| aMBbaCa bcdef
   
8. 
   +---------
   

9. 
   Түйген. кейбір ереже бойынша. по некоторому правилу. Стекте бар сөздің соңы, грамматика ережесінің оң жақ бөлігімен сәйкес келуі керек. Сонда осы ереже бойынша ереженің сол жақ бөлігіне ауыстырылу болып табылады. Келесі мысалды қарастырайық. Грамматикада ереже болсын.
   
10. 
    A -> baCa
    

+---------

| aMBbaCa bcdef

+---------

Осы ереже бойынша LR-процесс жағдайы түйгеннен кейін:

+---------

| aMBA bcdef

+---------

("baCa" сөзінің соңы стекте «А» ауыстырылған)

Анықтауыш. LR-процессі сәтті орындалады, егер оның соңында оқылмаған енгізу тізбегі бос болса, ал стекта метасимвол грамматикасының басы болса.

LR-процессінің сәтті соңғы жағдайы:

+----

| S

Мысал: грамматиканы қарастырайық:

S -> F

F -> a

F -> F*F

1. 
   +--
   
2. 
   | a+a*a
   
3. 
   +--
   

4. 
   LR-процессінің жағдайы
   
5. 
   +--
   
6. 
   |a +a*a
   
7. 
   +--
   

8. 
   +--
   
9. 
   |F +a*a
   
10. 
    +--
    
11. 
    әрекет –қозғалыс.

     
    

12. 
    +---
    
13. 
    |F+ a*a
    
14. 
    +---
    
15. 
    әрекет –қозғалыс.
     
    
16. 
    +---
    
17. 
    |F+a *a
    
18. 
    +---
    
19. 
    F -> a ережесі бойынша түйгеннің--әрекеті.

     
    

20. 
    +---
    
21. 
    |F+F *a
    
22. 
    +---
    
23. 
    әрекет –қозғалыс.
     
    
24. 
    +----
    
25. 
    |F+F* a
    
26. 
    +----
    
27. 
    әрекет –қозғалыс
    +-----
    
28. 
    |F+F*a
    
29. 
    +-----
    
30. 
    F -> a ережесі бойынша түйгеннің--әрекеті.
    +-----
    
31. 
    |F+F*F
    
32. 
    +-----
    
33. 
    F -> F*F ережесі бойынша түйгеннің--әрекеті.
    +----
    
34. 
    |F+F
    
35. 
    +----
    
36. 
    F -> F+F ережесі бойынша түйгеннің--әрекеті.
    +--
    
37. 
    |F
    
38. 
    +--
    
39. 
    S -> F ережесі бойынша түйгеннің--әрекеті.
    +--
    
40. 
    |S
    
41. 
    +--
    
42. 
    LR-процессінің сәтті соңғы жағдайы.
    

1. 
   Шығарылған синтаксистік талдауын атаңыз?
   
2. 
   LL(1) – грамматикасы қызметі қандай?
   
3. 
   Рекурсивтік түсу?
   
4. 
   КС-грамматикасының бейнеленуінің жүзеге асыру жолдарын атаңыз?
   
5. 
   Сол жақ рекурсияның жойылуы. Сол жақ факторизация?
   
6. 
   Енгізілген синтаксистік талдау. LL(1)-анализаторы?
   

1. Тілдің контексті бос емес қасиеттері. Символдар кестесінің ұйымдастыру. Идентификатордың кестесі. Орналастыру кестесі.

2. Тізімді қойылым кестесі. Орналастыру функциясы. Ағаштар кестесі. Блоқтық құрылым.

Текстік редакторден контексті еркін емес тілдерді текстілік тапсырмалармен қарастырайық, ол анализ жасауға рұқсат етеді және процесс олардың құрылысы болып табылады. Текстер соңғы қорытынды секілді статикалық емес, олардың құру технология түріндегі динамикалық болып көрінеді.

Контексті еркін емес текстілік редактор текстілік редактормен айырмашылығы олардың белгілеулері ортақ болып келеді, ол тексті дайындау кезінде үрдістің құрудың көтеріп, жіберілген қатерлерді тексереді. Ол негізгі құрылым тіліндегі контекстілік қасиетті қолданған жағдайда, тіл сөзіндегі ұйымдықты қолданушы қалған жағдайда болады. Контексті еркін емес редактор тілдері оқулық материалдарда информатика бойынша негізгі объектілер болып, контекстік еркін емес тілдерде құрастырылған текстік программалар және олардың фрагменттері кезінде пайдалы болады. Осындай материалдар маңыздылығы өспелі болады, егер объектілер тек қана текстік программаларды ғана емес, сонымен қатар үрдісте көрсетсе. Дәстүрлі оқулық әдебиеттерінде демонстрациялық технологиялық барабарлар программалық тапсырманы шығару іске асыруға қиынға түседі, егер ол оның алынған технологиясы мен бір мезетте құрылған, контексті еркін емес тіл редакторы сақталған тарихты құрылымдық мәтінде жабдықтаса.

Эффектілік контексті емес тіл редакторы мүмкін болатын сан альтернативі үшін қолданылады. Егер альтернативте контекстілік санды шамадан асыруға рұқсат етсе – ол ұйымдық болып саналады, мақсатқа жету үшін контексті есебінсіз мәтіндік редактор режиміне көшу керек. Грамматикада ережесі кең спектор альтернативін жібергенде, дайындау мәтіндік контексті еркін емес тілдер фрагментті кезінде сондай редактордан эффектіні күтпеуге де болады. Шекті жағдайда мұндай мүмкіндіктер дәстүрлі дайындау мәтіні толығымен қандай да бір мәтінде қолданса. Бұл жағдай редакторменде ұқсас.

Контексті еркін емес тілдер дайындау фрагменттері кезінде, өз бетінше символдарды тере бастайды.

Дайындау программалық мәтінінің технологиялық барабарлары редавкторде псевдо – мәтіндік механизмде ұсталынады және мәтіннің айналасындағы бақылауыш механизмді болып табылады. Псевдо – мәтіндік – ол атауларды, оның иерарахия құру кезінде мәтіндік фрагменттің белгілеулерін анықтайтын шығару мәтіні. Мәтіннің айналасында псевдо – мәтінді толықтыру мүмкіндіктері қолданылады. Мәтіннің айналасыдағы мысал программмалау тілі кезінде шығу және кіру параметрлері, тапсырмаларға және процедураларға шешімдер қолданушы, анықтаушы, объект қасиеттерінің атауы болады. Мұндай механизімінің кіріспесі қолданбалы тапсырмаларды шешу автоматтың көз қарасын суреттелген, құрылған урдіс барабарларымен қамтамасыз етеді.

Контексті негізгі тілдегі есеп “ойшылдық” редакторын кеңейтеді. әрбір мәтінде редактор мәтіндік объект анықтамасын құрайды және берілегн объектілер. Кіріспе сервистік процедурада алдын-ала контексті анализ дайындау мәтіндік программма кезінде қателерден алшақ жүрді, мәлімдеме объектілері қайталау, көріну облыстарындағы объектілер секілді. Сонымен қатар бұл ппроцедура синтаксикалық анализатордағы абсолютті аналог болмайды.

Мәтіндік контексті еркін емес тілдегі реализациясы қолданулар объектісінде негізделген. Негізінде нақты тілге көбінесе Pascal тілі таңдалынған. Синтаксикалық ережесі әрбір қадам үшін болса, ал басқасы – анықтауыш шекара мәтіндік қасиет болады. Зерттеу нұсқасында “контекстілі” редакторы былай болады.

• 
  <программа>,
  
• 
  <блок>,
  
• 
  <оператор>,
  
• 
  <оператор бағыттауышы>,
  
• 
  <шығу - кіру операторлары>.
  

Таңдау альтернативі үшін дайындау мәтіні үшін қалғып шығу менюі алдын-ала ескерілген. Сонымен теру альтернативі менюда ағымдағы контекстілі курсорды анықтайды. Редактор шығуда және әртүрлі стандарттағы дайындалған мәтінді қамтамасыз етеді.

Қолданушы редакторлар екі деңгейге бөлінеді – авторлар және оқырмандар. Бұл топтарға авторлық және оқырмандық режимдер берілгендер. Авторлық режим мәтіндерді дайындауға және оларды іске асыруға рұқсат етеді. Ал оқырмандық деңгей мәтіндерді қарауды қамтамасыздандырады.
Идентификаторлар кестесі және символдар кестесі.

Жоғары да айтқанымыздай, обьект ақпаратын әдетте екі бөлікке бөліп қарастырамыз: атау(идентификатор) және бейнеленуі. Бұл обьектің мінездемелерін жеке-жеке сақтау қолайлы. Бұл екі себеппен байланысты:

1) идентификатордың символдық құрылымдарының белгісіз ұзындықта болуы мүмкін.

2) әрбір облыстағы әртүрлі обьектердің бірдей атаулары болуы мүмкін және ол идентификатордың қайта сақталуы үшін жадты босқа ұстамауы керек. Идентификаторды сақтауға арналған кесте идентификатор кестесі деп аталады, ал обьектің қасиеттерін сақтауға арналған кесте- символдар кестесі деп аталады. Ондай жағдайда обьектің бір қасиеті оның атауы болып табылады және символдар кестесінде идентификатор кестесіне көрсететін сәйкес көрсеткіш сақталады.

Егер идентификатор ұзындығы шектеулі болса, онда идентификатор кестесі жай жиым түрінде ұйымдастырылуы мүмкін. Бұл мына суретте көрсетілген. Кейбір енгізулер бос емес, ал кйбіреулері бос болуы мүмкін.

+---------------------------------------+

| |

| s | o | r | t | | | | | | |<----

|---+---+---+---+---+---+---+---+---+---|

| a | | | | | | | | | |<----

|---+---+---+---+---+---+---+---+---+---|

| r | e | a | d | | | | | | |<----

|---+---+---+---+---+---+---+---+---+---|

| i | | | | | | | | | |<----

|---------------------------------------|

| |

Идентикатор кестелерін ұйымдастыру әдісі - жиымдар символында идентификаторларды сақтау. Бұл жағдайда идентификаторға символдың бірінші номері сәйкес келеді. Кестесінде идентификатор белгілі бір символмен аяқталады. (EOS).

| +------------------

| | +----------

| | | +-----

| | | |

| | | +--------------+

v v v v

| s | o | r | t |EOS| a |EOS| r | e | a | d |EOS| i |EOS|

+---+

0 | |

|...|

9 | --+-->| Idenp |--+-->| | x |

|---| +----------+ +--------+

|---| v v

|...| идентификатор көрсеткіші.

|---| +------------+

20 | --+-->| Idenp | x |

|---| +------------+

|---| v

|...| идентификатор көрсеткіші.

32 | --+-->| | -+-->| | -+-->| | x |

|---| +--------+ +--------+ +-------+

|...| v v

|---| идентификатор көрсеткіші.

Символдар кестесі және таблицаларды қою.

Символдар кестесінң ұйымын кесте қою арқылы қарастырамыз. Кесте қою- идентификаторға көрсететні жиымдар көрсеткіші тізімі. әрбір сондай тізімге идентификаторға көрсететін тізімдер кіреді және олар функцияны қоюдың бір мағынасын білдіреді. Бастапқыда кестені қою бос болып келеді. Барлық элементтердің NIL мағынасын білдіреді. Id идентификаторны іздестіруде H(id) функциясын қою есептелінеді және T[H]- ның сызықтық тізімі қарастырылады. Кестедегі іздестіру төмендегі процедурадағыдай болуы мүмкін.

Next:pointer to Element;

end;

Pointer=pointer to Element

var P:Pointer;

begin P:=T[H(Id)];

loop if P=nil then return(nil)

elsif IdenTab[P^.IdenP]=Id then return(P)

else P:=P^.Next

end end; end;
IdenTab – идентификаторлар кестесі. Кестеге обьекті кірістіру төмендегі прогцедурадағыдай болады:
function Insert(Id):Pointer;

var P,H:Pointer;

begin P:=Search(Id);

if P<>nil then return(P)

else H:=H(Id); new(P);

P^.Next:=T[H]; T[H]:=P;

P^.Idenp:=Include(Id);

end;

end;
|--| +------+ +------+

H----->| -+-x---->| |----->| |----->

|--| | +-->+------+ +------+

| | | |

|--| | +------------+

+---| |---+

P-------->+------+ 7.4. сурет.

Кестені жүзеге асырудың бірнеше әдістерін теңестірі.

Жадты қолдану техникасы тұрғысынан кестені жүзеге асырудың әдістерін қарастырамыз. Егер кесте жиымда орналасса, онда бір жағынан динамикалық жадты қолдану мүмкіндігі туады, ал екіншіден қиындық қатары туындайды. Динамикалық жадты қолдануқиын операция. Ол динамикалық жадпен жұмыс істеу механизмін қолдау өте қиын болғандықтан. Бос немесе бос емес жадтың тізімін қолдау керек, сұраныс кезінде жадтың қажетті бір бөлігін таңдау керек. Басқа тұрғыдан қарасақ, жиымды қолдану үлкен жадты қажет етеді, ал ол дегеніміз мағыналы жад мүлде қолданылмайды. Сонымен қатар жиымның барлық элементтерін толтырмауға тура келеді.

Көптеген синтаксистік анализдің әдістері ағаш тәрізді болады. Қарапайым түрлердің бірі – контекстті- еркін грамматикалар болып табылады, ол мына ережелерге сүйене отырып S=NP+VP немесе VP=V+NP, мұнда сол жағы оң жаққа контесттіксіз ауыса алады.Контекстті –еркін грамматикалар көптеген машиналық тілдерде көп қолданылады, және ол арқылы жоғары эффектілік анализдің әдістері құрылған. бұл әдістің жетіспеуі- граматикалық бұрыс фразаларға тыйым салуы жоқ болады, мысалы, бастауыш баяндауышпен қатысы жоқ.Бұл проблеманың шешімі бөлек екі грамматикалардың параллель жұмыс істеуі: бір жаңынан- жалғыз, басқа жағынан –көптік жалғауы. Бұдан басқа сөйлемдерге өзінің грамматикасы болуы керек және т.с.с.Семантикалық бұрыс сөйлем семантикалық жазуға айналуы мүмкін.Мұның бәрі үлкен ережелер жиынтығын береді, және контекстті- еркін грамматикалар NLP-ге жарамай қалады.

Ендігі біздің қарастыратын әдісіміз, конспект-бос грамматика .

1. 
   Әрбір тізбекте V-алфавит символы;
   
2. 
   2. Тізбектің соңы-S;
   
3. 
   3. Егер тізбек соңында бір ғана ереже , тізбек терминалды емес болуы керек;
   
4. 
   Егер n1, n2, n3,……nk түзу сызықты n ережесі , тізбекте А1, А2, А3, Ак байланысы, түзу тізбегінде n бар, А немесе А1, А2, А3, …..Ак болады.
   
5. 
   Екі ішкі сынып АТ грамматикасын қарастырайық.
   

L-атрибуттық және S-атрибуттық транслияциялық граммаатикалар

АТ-грамматикасында L-арибуттық бет, тексеруге болады, осы атрибутта әрбір ережені шығара отырып қолдануға болады. Мысалы L – атрибуттық транслияция грамматикасына G^A грамматикасы жатады.

Шығару алдында қарастырылып отырған атрибут тек қана шығару атрибуттық белгіге байланысты, L атрибут грамматикасын шығарылмаған синтаксистік анализаторды қолдануға мүмкіндік береді. 2 және 3 бөлімде АТ-грамматикасын жинақы Қылып жасайды.

Шектелген L-атрибуттық транслияциялық грамматиканы салады, атрибуттық мағынасын шығарылмайтын процесте шығаруға мүмкіндік береді. Шығарылмаған астерминалық анализатор LL(1)-грамматика керек етеді. L-атрибуттық транслятор грамматика суреттелетін аудару жай түрдің өзіне қаратуы болады.

Қойылым кестесі. Тізімді қойылым кестесі.

Бюфонның қарауынша, былай деп айтуға болады, программист - ол өзі жазған программаның стилі. Программалау стилі және оның элемементтері-формальды емес ұғым. Әртүрлі адамдардың стильге деген әртүрлі көзқарастары болады. 60-жылдары жақсы стильдің пайда болуы-бұл программаның қойылымдылығы.

Қойылым кестесі фрагменттерден құралады,олардың әрқайсысы бір кіретін бір шығатын бағыттауыш стрелкадан тұрады. Қарапайым фрагменттен – бос- ол бір бағыттауыш стрелкадан, кіретін жіне шығатын бір уақытта, оның артынан бір операторлы фрагмент жүреді.

Барлық түрлердің фрагменттері үш немесе төрт операторлардың композициялары болып табылады.Басқа да түрлердің фрагменттері ішкі фрагменттерді ауыстыра алады.

2. Кезектес композицияда шығатын бағыттауыш стрелка біреуінің екіншісінен шығатын операторлы сәйкес келеді, кіретін бағыттауыш стрелкамен ол басқа оператордікі.Қалған композицияның түрлері басқа операторлардың В фрагменттерін қарастырып, шарттардың орындалуын және басқа орындалмаған іһәрекеттерді қарастырады, сондықтан программа өзгермейді.

Альтернативті композицияда бір бағыттауыш стрелка ішкі операторға S1, екіншісі-S2 операторға апарады. Шығатын бағыттауыш стрелкалар осы операторлардың міндетті түрде біреуіне құйылады және олар басқа фрагменттерге кіруге құқықтары болмайды.

Кесте тағы бір оператор сақтайды деп ойлауға болады, ол ешқандай әрекет жасай алмайды.Ол кішкентай квадрат түрінде көрсетіліді.Онда стрелкалар құйылады.Альтернативті композицияның басқа да нұсқалары бар, онда ішкі бір фрагмент бос болып келеді.

Ақырғы композиция циклді. Стрелкалардың бірінің кіруі берілген фрагменттен шарттардың тексерілуінен шығуы болады. Ациклді фрагменттер.Егер фрагментте ешқандай тереңдікте циклді композициямен кезектессе, онда фрагмент ациклді граф болады. Кіретін және шығатын бағыттауыш стрелкалардың жолдары – жай болады. Оларды саны нешеу екені қызықты.

Альтернативті композициялы фрагменттердің жолдарының саны ішкі фрагменттерінің санына тең болып саналады.

Циклді композиция ішкі жағынан бір қарапайым жол қарастырады,ол бір В псевдооператорында цикл алдын ала тексеруші және екі оператордан SB құралған – цикл кейін тексеруші. Мұнда бір қарапайым контур қарастырылады: BSB.Қарапайым жолдардың санын қарастырсақ ең ішкі сапасында болса, онда ол 1-ге тең болады мынадай жағдайда жай жолдардың санының алдын ала және кейін тексеруден кейін.Жай контурлардығ саны – бұл ішкі S фрагмнтінің жай контурының сандары және жай жолдардың осы фрагментте сандарының жатуы.

Базалық жай контурлар схемасы барлық циклді фрагменттерде тұр екені дәлелденген. Осы ішкі Z фрагменттерден ациклді граф және максимальды жолдардан табуға болады. Осындай жолдардың саны z көптігінің элементтерінің санынан көп, сондықтан шарт арқылы әдіс табу керек болады. Қарастырылып отырған графтардың бастысы- операторлар болып саналады.
Бақылау сұрақтары:

1. 
   
   жүктеу 14,81 Mb.
   
   Достарыңызбен бөлісу: