Грамматикаларды құру әдістері

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

1. 
   берілген символдарынан тұратын шынжыр ережесіне сәйкес келеді.
   
2. 
   берілген символдан басталатын шынжыр ережесіне сәйкес келеді.
   
3. 
   берілген символдан аяқталатын шынжыр ережесіне сәйкес келеді.
   
4. 
   берілген символ басталатын және аяқталатын шынжыр ережесіне сәйкес келеді.
   
5. 
   символы ортасында келетін шынжыр ережесіне сәйкес келеді.
   
6. 
   l =2 ұзындығы ретінде берілген шынжыр және ережесіне сәйкес келеді.
   
7. 
   символы қайталанатын шынжыр рекурсивтік ережемен және рекурсиясын анықтайтын ережеге сәйкес келеді.
   
8. 
   және символдарының кезектесіп қайталануынан құрылған шынжыр және ережесіне сәйкес келеді.
   

1. 
   Берілген шынжырлар жиынынан бірнеше мысал жазып алу керек.
   
2. 
   Шынжырлар құрылымын бастауы мен соңын, қайталанатын символдар және символдар тобын ерекшелеп алып, талдау.
   
3. 
   Символдар тобынан тұратын күрделі құрылымдарға белгі енгізу.
   
4. 
   Әрбір белгіленген құрылымға қайталану құрылымының рекурсивті ережелерін қолданып ереже құру.
   
5. 
   Барлық ережелерді біріктіру.
   
6. 
   Шығару көмегімен түрлі құрылымды шынжыр алу мүмкіндігін тексеру.
   

1. 
   Алдымен төменде келтірілетін түрде болатын берілген тілдің бірнеше шынжырын құрайық:
   

*|||**,
*|*|*|**,

2. 
   Келтірілген шынжырларды қарастыра отырып, олардың келесі құрылымдық компоненттерін ерешелеуге болады:
   
   • 
     шынжыр бастауы (*символы),
     
   • 
     шынжыр соңы (**символы),
     
   • 
     таяқшалардың бос емес тобы,
     
   • 
     жұлдызшалармен бөлінген таяқшалар тобының реттілігі.
     
3. 
   Таяқшалар тобын символымен, ал таяқшалар тобының реттілігін символымен белгілейміз.
   
4. 
   Ерекшеленген құрылымдарды тізім ретінде қарастыруға болады. Осылайша таяқшалар реттілігі элементі таяқша болып келетін бөлгіштерсіз тізімді білдіреді. Бұндай тізімді тапсыратын грамматика ережесі келесі түрде болады:
   

Жұлдызшалармен бөлінген таяқшалар тобының реттіліг бөлгіштері бар тізім болып келеді. бұндай тізімнің элементі болып таяқшалар тобы, ал жұлдызша – бөлгіші саналады. бұндай тізімді тапсыратын грамматика ережесін төмендегідей жазуға болады:

Әрбір тіл шынжырының басы мен аяғы болу керегін ескере келе және грамматиканың бастапқы символы ретінде таңдай келе, шынжырдың жалпы түрін анықтайтын келесі ережені аламыз:

5. 
   Құрылған ережелерді біріктіре келе, төмендегі түрдегідей нақты грамматикалық ізделіп отырған кестесін аламыз:
   

6. 
   Құрылған грамматика ережесінің көмегімен келесі, мысалы:
   

шынжырын алуға болады.

Толық сандар цифралардың реттілігін білдіреді, сондықтан оларды элементтері цифр болып келетін тізім ретінде қарастыруға болады. Тізімді бөлгіштерсіз тапсыратын аналог ретінде грамматиканы қолдана отырып, келесі түрдегі толық сандар үшін грамматика кестесін аламыз:

Идентификатор құрылымын бастануы және негізгі бөлік компоненттері түрінде көрсетуге болады. Бастауы ретінде кез келген әріп болса, негізгі бөлік ретінде не әріп, не цифр элементі болып саналатын бөлгіштерсіз тізімді білдіреді. ерекшеленген компоненттерді қолдана отырып келесі түрдегі грамматикалық кестесін аламыз:

Егер идентификатор ұзындығына шектеу қойсақ, мысалы, тек қана үш символдан тұратын идентификаторды ғана қолдануға рұқсат берсе, онда грамматика кестесі жеңілдей түседі:

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

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

Бұл грамматика кестесінде грамматикасында анықталған терминал еместер қолданылады.

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

Айтарлықтай Паскаль тілінде 'if', 'then', 'else' бөлгіштерімен ұқсас шартты операторлар қарастырылып отыр делік. Шарт ретінде бұндай операторларда екі идентификатордан тұратын және , белгілерімен байланыстырылған, ал оператор ретінде 'then' немесе 'else' оң жақтағы арифметикалық формулалармен иемдену операторларын қолдануға рұқсат беріледі. Бұндай оператордың құрылымы жазылып алынатын ұзындық ретінің түрлерімен анықталады да, оларды мазмұндауға жай ғана компоненттерді атап өтуге болады. Бірінші реттілік толық және қысқартылған шартты операторларды анықтайды, ал екінші-«қарым-қатынас» конструкциясын. Бұл реттіліктерді беретін грамматика кестесі келесідей болады:

Бұл грамматикада грамматикасының кестесімен анықталады.

Бэкустер немесе синтаксистік диаграммалар.