Содержание курса
Көпмағыналы грамматикалар
жүктеу/скачать 2,16 Mb.
|
111 tokkojina m.a. khurast. tilder men avtomattar teoriyasi
- Бұл бет үшін навигация:
- 1.5 Грамматика кестелерін беру тәсілдері
| 1.4 Көпмағыналы грамматикалар
Түрлі шығарулардың көмегімен шынжыр пайда болған грамматикалар бар. Мысалы: грамматикаларда шынжыры екі түрлі шығару көмегімен пайда болуы мүмкін және оған екі түрлі синтаксистік ағаш сәйкес келеді. Бұл шынжырдың бірінші шығаруы келесі түрде болады: ал екіншісін былай алуға болады: Келесі грамматика да түрлі синтаксистік ағашы бар түрлі шығарулар арқылы шынжыр құруға мүмкіндік береді. Бұл грамматикалық шынжыр тудыратын екі шығаруы келесі түрде көрсетіледі: Грамматиканың қарастырылған қасиеті көп мағыналық деп аталады. Ол келесі тәсіл арқылы анықталуы мүмкін. тілінің шынжыры егер оны шығару үшін біреуден артық синтаксистік ағаш бар болса көп мағыналы деп аталады. Егер грамматикасы көпмағыналы шынжыр тудырса, онда ол көп мағыналы деп аталады. Көп мағыналық тек қана жасанды тілде болуы мүмкін емес. Яғни табиғи тілде де көп мағынасы бар сөйлемдер болуы мүмкін. Мысалы: «Пальто испачкало окно» бұл сөйлемде бастауыш қайсы, толықтауыш қайсысы екені түсініксіз. Ал ағылшынның "They are flying planes" сөйлемі екі түрлі түсіндірілуі мүмкін, яғни : "Они пилотируют самолет" немесе «Это летящие самолеты". Көп мағыналық жасанды тілге өте жағымсыз қасиет болып саналады, себебі көп мағыналық шынжырдың бірнеше мағынасы бар және ол шығару ағашын бір мағына тәсілімен құруға мүмкіндік бермейді. Бұдан келіп шығатын қағида, яғни тәжірибеде бір мағыналы грамматикаларды қолдану қажет. Қарастырылып жатқан грамматика көп мағыналы екеніне көз жеткізу үшін бұл грамматика тудыратын түрлі шығарулар көмегімен құрылуы мүмкін шынжырды табу жеткілікті. Бірақ бұл жерде туатын қиындық көп мағыналы шынжырды тауып алуда арнайы алгоритмнің жоқтығы. Бұл қағида формалды тілдер теориясында дәлелденген. Егер және грамматикалары бір тілді тудырса, онда олар эквивалентті деп аталады. Жалпы жағдайда екі берілген грамматика эквивалентті екенін тексеруге мүмкіндік беретін алгоритм жоқ екені дәлелденген. Бірақ көп мағыналық мәселесі жалпы түрде шешілмейді және кейбір жағдайларда, мысалы -грамматикасы үшін грамматика кестесінде грамматиканы көп мағыналы ететін ережелер түрі анықталған. Бұған келесі түрдегі ережелер мысал бола алады: Грамматика кестесінде бұл ережелердің біреуі болсын болуы грамматиканың көп мағыналы екенін көрсетеді. Алайда бұл ереженің грамматика кестесінде болмауы грамматиканың көп мағыналы еместігіне кепілдік бере алмайды. 1.5 Грамматика кестелерін беру тәсілдері Грамматика кестесінде тілдің синтаксисін анықтайтын шығару ережесі және басқаша айтқанда туатын тілдің мүмкін компоненттері мен шынжыр конструкциялары болады. Ережелерді тапсыру үшін түрлі атап айтсақ, олар: рәміздік (символдық), Наур-Бэкус формасы, итерациондық форма және синтаксистік диаграммалар. Грамматиканың жалпы қасиеттерін қарастырумен байланысты жұмыстарда әдетте ережені тапсырудың символдық формасын қолданады. Ол элемент ретінде бөлек символдардың терминал емес сөздігі мен ереженің оң және сол жағын бөлуші ретінде – жебені қолдану алдын-ала қарастырылады. Бағдарламалау нақты тілдің синтаксисін мазмұндауда көп мөлшерде терминалды емес символдар енгізуге тура келеді және осыдан жазылымның символдық формасы өз көрнекілігінен айрылады. Бұл жағдайда бұрыштық жақшаларға алынған терминалды емес символдар ретінде табиғи тілдің сөздер комбинациясын алдын ала қолдануды қарастыратын Наур-Бэкус формасын, ал бөлгіш ретінде екі қос нүкте мен теңдіктен тұратын арнайы белгі қолданылады. Мысалы, егер немесе ережелері символдық формада жазылған болса және символы "тізім", -"тізім элементі" түсінігіне сәйкес келсе, оларды Наур-Бэкус формасында төмендегідей көрсетуге болады: <тізім >:=<тізім элементі >< тізім , <тізім:=<тізім элементі>. Грамматика кестесін мазмұндауда қысқарту үшін, БНФ-да тік сызықпен бөлінген оң жақ бөлігі біріктірілген ережелердің оң жағын енгізу қажет сол жағы бірдей болып келетін ережелерді бір ережеге біріктіру рұқсат етіледі. Қарастырылып жатқан мысалға ережелердің біріктірілуін пайдалана отырып келесі көріністі аламыз: <тізім>:=<тізім элементі><тізім>|<тізім элементі>. Синтаксистік шағын мазмұндауын алу үшін мазмұнның итерациондық формасын қолданады. Бұл форма арнайы итерация деп аталатын және қос фигуралық жақша мен жұлдызшамен белгіленетін операцияны енгізуді қажет етеді. түріндегі итерация жиын ретінде анықталады да өзінің құрамында а символы мен бос шынжырды пайдаланып құрылған мүмкін ұзындықтағы шынжырды ұстайды Символдың ережелермен берілетін шынжыр жиындарын мазмұндау үшін итерацияны пайдаланып, келесі түзілуді аламыз: Мазмұндаудың итерациялық формаларында итерациялық жақшалармен қатар жиі олардың ішіне алынған шынжырдың жоқтығына көрсететін тік жақшаларға алу кездеседі. Бұндай жақшалардың көмегімен және ережесі төмендегідей жазылуы мүмкін: Көзбен көріп қабылдауды жақсарту және күрделі синтаксистік мазмұндау түсініктерін жеңілдету үшін синтаксистік диаграмма түріндегі грамматика ережелерін көрсетуді қолданады. Синтаксистік грамматика грамматиканың әрбір ережесіне бағытталған граф ретінде көрсетіледі. Бұндай диаграммалардың құрылу ережесін келесі түрде тұжырамдауға болады: Әрбір түріндегі ережеге құрылымы ереженің оң жағымен анықталатын диаграммаға сәйкес қойылады. шынжырдағы терминалды символының көрінуі символы жазылған доға мен дөңгелек диаграммасында бейнеленеді. шыңжырында терминалды емес символдың әрбір көрінуі символы жазылған доға мен тік бұрыш диаграммаларда бейнеленген. түрі бар грамматиканың тудыру ережесі. түрі бар грамматиканың тудыру ережесі. Егер ереже итерация түрінде берілсе, оған диаграмма сәйкес келеді. Грамматиканың берілген кестесі үшін құруға болатын синтаксистік диаграммалар саны ереже санымен анықталады. Диаграммалар санын азайту үшін оларды біріктіріп, оларға арналып құрылған диаграммаларға енетін термин емес символдарға ауыстырылады. 3-6 ережелері біріктірілген диаграммада шынжыры ретінде бұл шынжырдарға арналған диаграммалар қолданылуы мүмкін деп болжайды. Мысал ретінде бастапқы символды келесі грамматиканы қарастырайық: жүктеу/скачать 2,16 Mb. Достарыңызбен бөлісу:
|