Көпмағыналы грамматикалар

Түрлі шығарулардың көмегімен шынжыр пайда болған грамматикалар бар. Мысалы: грамматикаларда шынжыры екі түрлі шығару көмегімен пайда болуы мүмкін және оған екі түрлі синтаксистік ағаш сәйкес келеді.

Бұл шынжырдың бірінші шығаруы келесі түрде болады:

ал екіншісін былай алуға болады:

Келесі грамматика да түрлі синтаксистік ағашы бар түрлі шығарулар арқылы шынжыр құруға мүмкіндік береді.

Бұл грамматикалық шынжыр тудыратын екі шығаруы келесі түрде көрсетіледі:

Грамматиканың қарастырылған қасиеті көп мағыналық деп аталады. Ол келесі тәсіл арқылы анықталуы мүмкін. тілінің шынжыры егер оны шығару үшін біреуден артық синтаксистік ағаш бар болса көп мағыналы деп аталады. Егер грамматикасы көпмағыналы шынжыр тудырса, онда ол көп мағыналы деп аталады.

Көп мағыналық тек қана жасанды тілде болуы мүмкін емес. Яғни табиғи тілде де көп мағынасы бар сөйлемдер болуы мүмкін.

Мысалы: «Пальто испачкало окно» бұл сөйлемде бастауыш қайсы, толықтауыш қайсысы екені түсініксіз. Ал ағылшынның "They are flying planes" сөйлемі екі түрлі түсіндірілуі мүмкін, яғни : "Они пилотируют самолет" немесе «Это летящие самолеты". Көп мағыналық жасанды тілге өте жағымсыз қасиет болып саналады, себебі көп мағыналық шынжырдың бірнеше мағынасы бар және ол шығару ағашын бір мағына тәсілімен құруға мүмкіндік бермейді.

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

Егер және грамматикалары бір тілді тудырса, онда олар эквивалентті деп аталады.

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

Грамматика кестесінде бұл ережелердің біреуі болсын болуы грамматиканың көп мағыналы екенін көрсетеді. Алайда бұл ереженің грамматика кестесінде болмауы грамматиканың көп мағыналы еместігіне кепілдік бере алмайды.

Дәріс

Тақырып. Бағдарламалау тілінің жай конструкцияларын мазмұндайтын грамматикалар

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

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

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

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

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

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

Толық және заттық ауыспалыларды мазмұндауға арналған грамматика құру қажет делік. Нақты түрдегі ауыспалыларды мазмұндау 'real' немесе 'int' типті көрсеткіштермен басталу қажет.

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

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

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

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

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

Енді Паскаль тілінде қолданылатын 'while', 'do', 'repeat', 'until' бөлгіштері тәріздес цикл операторларын мазмұндауды қарастырайық.

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

Мұндай грамматикаларды құру берілген тіл конструкциясына арнайы жеке ереже құрылатын әр терминалдық символ үшін грамматика құру қажеттілігіне әкеледі. Қарастырылып жатқан цикл операторларына анықталған терминал емес символдарды қолданған грамматика кестесі келесі түрде болады:

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

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

Дәріс

Тақырып. Тудырмайтын, жетпейтін және пайдасыз символдарды анықтау

Грамматиканың төрт түрінің ішінде мәнмәтінді–бос грамматика бағдарламамлау тілдеріне қосымша мен компиляциялар көз қарасынан ең негізгі болып келеді. –грамматика көмегімен бағдарламамлау тілі құрылымының үлкен бөлігін анықтауға болады.

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

а) егер символ шығару кезінде алына алмаса

б) егер символдан соңғы терминалды шынжыр алына алмаса.

Алдымен соңғы шынжырды шығаруға мүмкін емес символдарды айқындау алгоритімін қарастырайық. Егер символынан соңғы терминалды шынжыр шығарылмаса ол тудырылмайтын деп аталады.

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

1 Оң жағы терминал еместерді құрамынды ұстайтын бір болсын ереже табылатын терминал еместер тізімін құру.

2 Егер жоғарыда айтылған ереже табылатын болса, онда терминалдар емес тізіміне оның сол жақында тұрғандарды енгізу.

3 Егер 2 қадамда тізім толықтырылмаса, грамматиканың барлық тудыратын терминал емес тізімі алынады, ал оның құрамына енбеген барлық терминал еместер тудырмайтын болып келеді.

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

Егер ешбір шығарылатын шынжырда болмаса, онда – грамматикада символы жетпейтіндеп аталады.

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

1 Егер сол жағы тізімге енгізілген болса, онда оның оң жағындағыларда тізімге енгізілетін ереже табылса.

2 Егер 2 – қадамда тізімге жаңа терминал еместер қосылмаса, онда барлық жеткен терминал еместер тізімі жетпейтін болып келеді.

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

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

Алдымен және тудырмайтын символ екенін байқап, тудырмайтын символдары бар ережелерді жоя келе аламыз.

Алынған схемада символы жетпейтін символ болып келеді. Бұл символды құрамында ұстайтын ережені шығара келе аламыз.

Келтірілген грамматикалар.

Егер –грамматикасының құрамында пайдасыз символдар болмаса, онда ол келтірілген деп аталады.

түріндегі ереже оң жақты рекурсивті, ал түріндегі ереже – сол жақты рекурсивті деп аталады.

Дәріс

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

Оң жақ рекурсивті ережесі бар әрбір – грамматикасы үшін сол жақ рекурсивті ережесі жоқ эквивалентті Г грамматикасын құруға болады.

Эквивалентті грамматика құру тәсілі келесідей:

Айтылған тәсілмен сол жақты рекурсиялы –де барлық ережелерді ауыстыра келе грамматикасын аламыз және де себебі грамматикаларда шығарылған әрбір шынжыр грамматикаларда құрылуы мүмкін. және –гі шығару реттерін қарастырайық. грамматикаларда шынжырды шығару түрі келесідей:

– грамматикаларда осы шынжыр былайша шығарылады:

Өзгеру техникасын көрсету үшін мысал қарастырайық. грамматикасын өзгерту қажет, ол

кестесімен берілген.

Мазмұндалған тәсілге сүйене келе ережесін және ережесіне, ал және ережесіне өзгертеміз. Нәтижесінде келесі кестедегі грамматикасын аламыз:

және оның құрамында сол жақ рекурсивті ереже жоқ.

болатын түріндегі грамматика ережесі шынжырлы деп аталады.

Шынжырлы ережесі құрамында бар , –грамматикасы үшін оған эквивалентті шынжырлы ережесі жоқ грамматикасын құруға болады. Дәлелдеу ойы келесіде: егер грамматика схемасы түрінде болса, онда ондай грамматика түріндегі схемамен эквивалентті болады, себебі шынжырындағы схемалы грамматикадағы шығару схемалы грамматикасында ережесінің көмегімен алынады.

Жалпы жағдайда ақырғы пайымдауды төменгіде келтірілгендей дәлелдеуге болады: –ды екі және , жиындарына бөлеміз және құрамына барлық түріндегі ережелер енеді. барлық ережесі үшін ереже жиындарын табамыз. Ал оларбылай құрылуы керек: егер және –де ережесі бар (бұнда сөздігінің шынжыры) болса, онда –ға ережесін енгіземіз. , және барлық жат жиындарын біріктіру тәсілімен жаңа схемасын құрамыз.

Сонда берілген грамматикаға эквивалентті және түріндегі ережесі құрамында жоқ грамматикасын аламыз.

Мысал ретінде грамматикасынан төмендегі кестелі шынжыр ережелерін шығаруды орындаймыз:

Алдымен грамматика ережесін екі ішінаралық жиынға бөлеміз:

Әрбір -дің ережесі үшін сәйкес ішінаралық жиын құрамыз:

Нәтижесінде грамматиканың шынжыр ережесінсіз ізделіп отырған келесі түрдегі кестесін аламыз: