shkolakz.ru 1 2 3 ... 8 9

1.3 Шығару ағашы. Сол жақты және оң жақты шығарулар


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

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

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


  • Бастапқы шың немесе ағаш тамыры ретінде грамматикалық бастапқы символымен белгілейтін шыңды алайық; бұл шың ағаштың нөлдік қабатын құрайды.

  • Егер шынжырды шығару кезінің келесі адымында терминал емес болып белгіленген, нөмірімен қабатта орналасқан грамматика ережесі немесе шың қолданылса, онда құрылған ағашқа ?шынжырында неше символ болса, сонша шың қосу керек және бұл шыңдарды қабатына орналастырып, ?шынжырының символдарымен белгілеп, бұл шынжырларды шыңымен доға көмегімен байланыстыру. Соңғы түйіндер – жапырақтар жиыны шығару қорытындысы болып келеді де, ағашты қарастыру кезінде солдан – астына – оңға – үстіне деп көрсетіледі.

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



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


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







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





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





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







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





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

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

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


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

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

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





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


1.5 Грамматика кестелерін беру тәсілдері


Грамматика кестесінде тілдің синтаксисін анықтайтын шығару ережесі және басқаша айтқанда туатын тілдің мүмкін компоненттері мен шынжыр конструкциялары болады. Ережелерді тапсыру үшін түрлі атап айтсақ, олар: рәміздік (символдық), Наур-Бэкус формасы, итерациондық форма және синтаксистік диаграммалар.

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


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

Мысалы, егер немесе ережелері символдық формада жазылған болса және символы "тізім", -"тізім элементі" түсінігіне сәйкес келсе, оларды Наур-Бэкус формасында төмендегідей көрсетуге болады: <тізім >:=<тізім элементі >< тізім , <тізім:=<тізім элементі>.

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

<тізім>:=<тізім элементі><тізім>|<тізім элементі>.

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





Символдың ережелермен берілетін шынжыр жиындарын мазмұндау үшін итерацияны пайдаланып, келесі түзілуді аламыз:




Мазмұндаудың итерациялық формаларында итерациялық жақшалармен қатар жиі олардың ішіне алынған шынжырдың жоқтығына көрсететін тік жақшаларға алу кездеседі. Бұндай жақшалардың көмегімен



және

ережесі төмендегідей жазылуы мүмкін:





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


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

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

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

  4. түрі бар грамматиканың тудыру ережесі.

  5. түрі бар грамматиканың тудыру ережесі.

  6. Егер ереже итерация түрінде берілсе, оған диаграмма сәйкес келеді.

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

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








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


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

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

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

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


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

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

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

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


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

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

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

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

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



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


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



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



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


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

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

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

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

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

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

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

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

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

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


*|||**,

*|*|*|**,

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

*|||*|*||*||||||**


  1. Келтірілген шынжырларды қарастыра отырып, олардың келесі құрылымдық компоненттерін ерешелеуге болады:

    • шынжыр бастауы (*символы),

    • шынжыр соңы (**символы),

    • таяқшалардың бос емес тобы,

    • жұлдызшалармен бөлінген таяқшалар тобының реттілігі.

  2. Таяқшалар тобын символымен, ал таяқшалар тобының реттілігін символымен белгілейміз.

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





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





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





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





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



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

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


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


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





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





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




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






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





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

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

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





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

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




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






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

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

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

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







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

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


2-тақырып Мәнмәтінді-бос грамматикалар мен дүкендік автоматтар


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


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

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

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

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

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

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

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

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

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



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

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

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


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

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

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

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




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


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


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

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

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


2.2 Сол жақты рекурсивті және шынжырлы ережелердің шығарылуы


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

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

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




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






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




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

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





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

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

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

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


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

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





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





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





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





2.3 Қысқартылмайтын грамматикалардың түрленуі


түріндегі ереже жоюшы ереже деп аталады.

Ал грамматика қысқартылмайтын немесе жою ережелерінсіз грамматика деп келесі жағдайларда аталады:


  1. егер грамматика кестесінде жою ережелері болмаса

  2. немесе грамматика кестесінде грамматикасының бастауыш символы және оң жағында кездесетін түріндегі бір ғана ереже болса.

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

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

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



2.4 Дүкендік автоматтар


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

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

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

Қарастырылып жатқан кезде бүршік астындағы позицияны дүкен шыңы деп атайды.

дүкендік автомат жеті объектілерінің арақатынасымен анықталады.

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

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

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


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


2.5 Дүкендік автомат жұмысы


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

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





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

Бастауыш конфигурация деп конфигурациясы аталады. Онда –бастапқы жай-күйі және –дүкен түбінің маркері, ал қорытынды деп конфигурациясы аталады, онда .






соңғы жай-күй жиынына жатады.

Егер конфигурация реттілігі сақталса, онда ? шынжыры автоматы үшін рұқсат етілетін деп аталады. Яғни онда бірінші конфигурация ?шынжырымен бастауыш, ал ақырғы





аяқтаушы болып келгенде, бұнда .

автоматымен рұқсат етілетін шынжырлар жиыны автомат рұқсат беретін немесе анықтайтын тіл деп аталады да, бейнеленеді 




<< предыдущая страница   следующая страница >>