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

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

Әрбір аланып тастаған құрылым элементіне белгі берейік.

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

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

1 берілген символдарынан тұратын шынжыр ережесіне сәйкес келеді.

2 берілген символдан басталатын шынжыр ережесіне сәйкес келеді.

3 берілген символдан аяқталатын шынжыр ережесіне сәйкес келеді.

4 берілген символ басталатын және аяқталатын шынжыр ережесіне сәйкес келеді.

5 символы ортасында келетін шынжыр ережесіне сәйкес келеді.

6 l =2 ұзындығы ретінде берілген шынжыр және ережесіне сәйкес келеді.

7 символы қайталанатын шынжыр рекурсивтік ережемен және рекурсиясын анықтайтын ережеге сәйкес келеді.

8 және символдарының кезектесіп қайталануынан құрылған шынжыр және ережесіне сәйкес келеді.

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

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

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

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

Егер бөлгіштері бар тізім бос болса, онда жоғарыда келтірілген ережелер жиынтығын оң жағы бос тағы да бір ережемен толықтыру керек. Нәтижесінде келесі шығады:

Көп жағдайда егер өзі кейбір тілдерді өкілет ететін шынжырлар жиынын мазмұндалған және бұл шынжырлар жиынын тудыратын грамматиканы құру қажет болса, онда төменде келтірілшендей іс-әрекет жасау қажет:

1 Берілген шынжырлар жиынынан бірнеше мысал жазып алу керек.

2 Шынжырлар құрылымын бастауы мен соңын, қайталанатын символдар және символдар тобын ерекшелеп алып, талдау.

3 Символдар тобынан тұратын күрделі құрылымдарға белгі енгізу.

4 Әрбір белгіленген құрылымға қайталану құрылымының рекурсивті ережелерін қолданып ереже құру.

5 Барлық ережелерді біріктіру.

6 Шығару көмегімен түрлі құрылымды шынжыр алу мүмкіндігін тексеру.

Келтірілген нұсқаулардың қолданылуын келесі мысалдарда қарастырайық. тіліне терминалды сөздігі , ал тілді құрайтын құрылымы:

а) әр шынжыр * әрпіне басталып, * * әрпіне аяқталады.

b) шынжырдың басы мен соңының арасында не бос таяқшалар реттігі, немесе * символымен бөлінген бірнеше реттіліктер болуы мүмкін грамматика құруды қажет етеді.

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

*

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

|*

||**, *

*|*||*

Nbsp; 2 Келтірілген шынжырларды қарастыра отырып, олардың келесі құрылымдық компоненттерін ерешелеуге болады: - шынжыр бастауы (*символы), - шынжыр соңы (**символы), - таяқшалардың бос емес тобы, - жұлдызшалармен бөлінген таяқшалар тобының реттілігі. 3 Таяқшалар тобын символымен, ал таяқшалар тобының реттілігін символымен белгілейміз. 4 Ерекшеленген құрылымдарды тізім ретінде қарастыруға болады. Осылайша таяқшалар реттілігі элементі таяқша болып келетін бөлгіштерсіз тізімді білдіреді. Бұндай тізімді тапсыратын грамматика ережесі келесі түрде болады:     Жұлдызшалармен бөлінген таяқшалар тобының реттіліг бөлгіштері бар тізім болып келеді. бұндай тізімнің элементі болып таяқшалар тобы, ал жұлдызша – бөлгіші саналады. бұндай тізімді тапсыратын грамматика ережесін төмендегідей жазуға болады:     Әрбір тіл шынжырының басы мен аяғы болу керегін ескере келе және грамматиканың бастапқы символы ретінде таңдай келе, шынжырдың жалпы түрін анықтайтын келесі ережені аламыз:     5 Құрылған ережелерді біріктіре келе, төмендегі түрдегідей нақты грамматикалық ізделіп отырған кестесін аламыз:     6 Құрылған грамматика ережесінің көмегімен келесі, мысалы:     шынжырын алуға болады. Формалды грамматиканы қолданудың ең негізгі облыстарының бірі бағдарлама тілін мазмұндау болып табылады. Бұндай мазмұндаулардың әдебиеттерде кеңінен қолданылуы мен олардың компиляторды құрудағы мәнін ескере отырып, бағдарлама тілінің жай конструкциясы үшін грамматикалық реттілігін қарастырайық.   1.7 Бағдарламалау тілінің жай конструкцияларын мазмұндайтын грамматикалар   Толық сандар цифралардың реттілігін білдіреді, сондықтан оларды элементтері цифр болып келетін тізім ретінде қарастыруға болады. Тізімді бөлгіштерсіз тапсыратын аналог ретінде грамматиканы қолдана отырып, келесі түрдегі толық сандар үшін грамматика кестесін аламыз:     Идентификатор құрылымын бастануы және негізгі бөлік компоненттері түрінде көрсетуге болады. Бастауы ретінде кез келген әріп болса, негізгі бөлік ретінде не әріп, не цифр элементі болып саналатын бөлгіштерсіз тізімді білдіреді. ерекшеленген компоненттерді қолдана отырып келесі түрдегі грамматикалық кестесін аламыз:     Егер идентификатор ұзындығына шектеу қойсақ, мысалы, тек қана үш символдан тұратын идентификаторды ғана қолдануға рұқсат берсе, онда грамматика кестесі жеңілдей түседі:     Қосу және айыру белгілері бар арифметикалық формулаларды ғана қарастыруды уәделесіп алайық. Алдымен жақшасыз формулалар үшін грамматика құрайық. Бұндай формулалар бөлгіштерінің қызметін операция белгілері атқаратын бөлгіштері бар тізім ретінде қарастыруға болады. Осыған сәйкес анықтамасы жоғарыда келтірілген символы идентификаторды білдіретін грамматика схемасын аламыз:     Арифметикалық формулаларда жақшаларды еңгізусіз қолдануға мүмкіндік беретін грамматиканы құру үшін бұндай формула құрылымдарын бөлгіштері бар тізім ретінде көрсетеміз және оның элементтері болып жақшасыз формула табылады. Бұл тізімнің бөлгіш болып операция белгілері келеді. Бұндай құрылымға төмендегі грамматика кестесі сәйкес келеді:     Бұл грамматика кестесінде грамматикасында анықталған терминал еместер қолданылады. Толық және заттық ауыспалыларды мазмұндауға арналған грамматика құру қажет делік. Нақты түрдегі ауыспалыларды мазмұндау 'real' немесе 'int' типті көрсеткіштермен басталу қажет. Толық мәтінде нақты түрдегі ауыспалыларды мазмұндау қайталануы мүмкін. толық мазмұндау құрылымын бөлгіштері бар екі енгізілген тізім ретінде көрсетуге болады. сыртқы тізім элементі ретінде қарастырылатын ішкі тізім бір типті ауыспалыларды мазмұндау болып келеді. Ішкі тізім бөлгіш ретінде нүктелі үтірді қолданады. Қарастырылып отырған грамматика кестесі келесідей жазылуы мүмкін:     Айтарлық иемдену операторын оң жағында грамматикасы мазмұндайтын жақшасыз формула ғана қолданылуы мүмкін дейік. Операторлардың бөлгіші ретінде нүктелі үтірді қабылдайық. Операторлар реті нүктелі үтірді бөлгіші ретінде пайдаланатын тізімге сәйкес және ертеде анықталған идентификаторлардың конструкцияларымен қолдана отырып жақшасыз анықтамаларды келесі түрдегі грамматика кестесін аламыз:     Айтарлықтай Паскаль тілінде 'if', 'then', 'else' бөлгіштерімен ұқсас шартты операторлар қарастырылып отыр делік. Шарт ретінде бұндай операторларда екі идентификатордан тұратын және, белгілерімен байланыстырылған, ал оператор ретінде 'then' немесе 'else' оң жақтағы арифметикалық формулалармен иемдену операторларын қолдануға рұқсат беріледі. Бұндай оператордың құрылымы жазылып алынатын ұзындық ретінің түрлерімен анықталады да, оларды мазмұндауға жай ғана компоненттерді атап өтуге болады. Бірінші реттілік толық және қысқартылған шартты операторларды анықтайды, ал екінші-«қарым-қатынас» конструкциясын. Бұл реттіліктерді беретін грамматика кестесі келесідей болады:     Бұл грамматикада грамматикасының кестесімен анықталады. Енді Паскаль тілінде қолданылатын 'while', 'do', 'repeat', 'until' бөлгіштері тәріздес цикл операторларын мазмұндауды қарастырайық. Әр оператор жоғарыда құрылған және грамматикада анықталған терминал еместер қолданылатын жай ғана реттілік түрінде мазмұндалуы мүмкін тәжірибеде көбінесе ережелердің оң жағы терминалдық символмен басталатын грамматикамен жұмыс істеген тиімдірек жағдайлар жиі кездеседі. Мұндай грамматикаларды құру берілген тіл конструкциясына арнайы жеке ереже құрылатын әр терминалдық символ үшін грамматика құру қажеттілігіне әкеледі. Қарастырылып жатқан цикл операторларына анықталған терминал емес символдарды қолданған грамматика кестесі келесі түрде болады:     Бэкустер немесе синтаксистік диаграммалар. Формалды грамматика құру міндетіне жиын шынжырын мазмұндау мен берілген терминалды алфавит үшін терминалды емес символдар алфавитін анықтау және грамматика кестесін құру қажеттілігі жатады. Тәжірибеде шешімді іздеу берілген шынжырдың құрылымдық талдауын қолданумен орындалады. Бұндай талдау нәтижесінде шынжырдың құрылымдық компоненттреі анықталады да, олар терминалды емес грамматика сөздігіне енеді, ал шынжырдағы ілесу компоненттерінің реті грамматика ережесін құру негізі болып келеді.