Мәнмәтіннен еркін грамматикаларды эквивалентті түрлендірудің кейбір тәсілдері



Дата12.06.2016
өлшемі221.5 Kb.
#131136
Мәнмәтіннен еркін грамматикаларды эквивалентті түрлендірудің кейбір тәсілдері
Байдарманова Б.Н.

М.Х. Дулати атындағы ТарМУ, Тараз қ.
Формальды тілдер және автоматтар теориясы информатиканың математикалық негізі болып есептелінеді. Жоғарғы деңгейдегі алгоритмдік тілдер үшін (мысалы, Паскаль, С++) компиляторларды құру формальды тілдер және автоматтар теориясының нәтижелеріне сүйене отырып жүзеге асырылады. Теорияда зерттелетін жалпы заңдылықтарды білу негізгі технологияларды қолдану арқылы практикада түрлі тілдер үшін түрлі компиляторларды іске асыру мүмкіндігіне жеткізеді [2].

Формальды тілдер теориясының дамуына Хомскидің (Chomsky N.) формальды грамматикалар бойынша жұмысы (1959ж.) және Бэкус (Backus J.W.) пен Наур (Naur P.) ұсынған белгілеулер жүйесі арқылы Алгол-60 тілінің синтаксисінің сипатталуы өз ықпалын тигізді [1-2].

Формальды грамматиканың Хомский анықтаған түрі (типі) тек ол грамматиканың ережелерінің құрылым үлгісімен ғана байланыста болады. Хомский грамматикаларды олардың түрлеріне сәйкес төрт класқа топтастыруды ұсынған, яғни Хомский классификациясын (иерархиясын) 0,1,2- және 3-түрдегі грамматикалар топтары құрады да, бірдей түрдегі (типтегі) грамматикалар тек бір класта жатады [2].

Кейінгі зерттеулерде Хомский иерархиясындағы әрбір грамматика үшін оның класына сәйкес талдаушы (автомат) табылатыны дәлелденді. Сонымен, алгоритмдерді сипаттаудың жаңа тәсілімен оған дейін белгілі болған Тьюринг (Turing A.M.) машиналарының (1936ж.) байланысы айқын болды. Талдаушылардың қалған түрлері Тьюринг машиналарының дербес жағдайларында алынады, мысалы, ақырлы автомат (1943ж.), магазиндік жады бар автомат (1961ж.).

Мақалада [1], [2], [3] жұмыстарының нәтижелеріне сүйене отырып, грамматикалар үшін жоғарыға талдайтын синтаксистік талдаушы магазиндік жады бар автомат түрінде іске асырылған.
Анықтама 1. Қайсыбір сөзі үшін қорытып шығаруы орындалатындай бейтерминалы табылса, грамматика сол жақты рекурсиялы деп аталады.
Айтылған қорытып шығару бір-ақ қадамды қажет етсе, ол тікелей сол жақты рекурсия деп аталады (яғни грамматикада ережесі бар). Бірден артық қадам қажет болған жағдайды тікелей емес рекурсия дейді[2].
Ескерту 1. Төменге синтаксистік талдау әдістері сол жақты рекурсиялы грамматикалармен жұмыс істей алмайды, сондықтан мұндай грамматикаларда сол жақты рекурсияны жою мәселесі маңызды болып табылады.
Мысал 1. Сол жақты рекурсиялы ережелерін сол жақты рекурсиясыз
,


ережелеріне алмастыруға болады[1].
Тікелей сол жақты рекурсияны жоюдың алгоритмі
Кіріс: – МЕ – грамматика;

Шығыс: – тікелей сол жақты рекурсиясы болмаған МЕ– грамматика.


Қадам 1. Сол жақты рекурсиялы бейтерминалы үшін барлық ережелерді топтау:
,

,
мұнда сөздері бейтерминалынан басталмайды,

ал сөздерінің ешқайсысы бос сөзіне тең емес.

Қадам 2. Жаңа бейтерминалын енгізумен жоғарыдағы ережелерді жаңа ережелерге ауыстыру:

,


Қадам 3. Бейтерминалдар жиынын жаңа бейтерминалымен толықтыру.

Қадам 4. Грамматиканың кезектегі сол жақты рекурсиялы ережелері үшін 1,2,3 қадамдарын қайталау.

Қадам 5. Табылған бейтерминалдар жиыны мен ережелер жиынын сәйкес түрде және деп қабылдау[2].
Ескерту 2. Тікелей сол жақты рекурсиялары жойылған грамматикада –ережелер кездесіп қалуы мүмкін. Бізді тікелей сол жақты рекурсияларымен қатар –ережелері де болмаған грамматика қызықтыратын болса, алгоритмнің екінші қадамын былайша өзгертуге болады:
,

,

.

Ескерту 3. Сипатталған алгоритм тікелей емес сол жақты рекурсияларды жоя алмайды.
Мысал 2. болған себепті,
,


грамматикасында бейтерминалы сол жақты рекурсиялы, бірақ бұл рекурсия тікелей емес.
Ескерту 4. Тікелей емес сол жақты рекурсияны жоюдың алгоритмі [2,184-бет] жұмысында кеңінен көрсетілген.
Мысал 3. 1-кестеде тікелей сол жақты рекурсияны жоятын алгоритмнің
,



,


МЕ-грамматикасына қолданылуы көрсетілген.

1-кесте


3. мысалындағы грамматиканы түрлендіру


Қадам

Әрекет және нәтиже

1

,

2

, , ,

3



4

Басқа тікелей сол рекурсия жоқ

5

, ,

, , ,


Мысал 4. Арифметикалық өрнектер үшін
,

,


грамматикасын қарастырамыз, мұнда {-өрнек, -терм, -көбейткіш}, {+, ( ,, ), -идентификатор}[3].

Тікелей сол жақты рекурсияларды жоя отырып алатынымыз:


,

,

,

,

.
Грамматика ережелерін сол жақтан факторизациялау
Анықтама 2. Тізбектің төменге талдануы деп талдау ағашының оның тамырынан бастап төбелеріне қарай құрылуын айтады. Төменге талдауды тізбекті сол жақты тудырудың әрекеті деп те түсінсе болады[3].
Анықтама 3. Рекурсиялы төмен түсумен талдау деп бірқатар рекурсиялы шаралар орындалған төменге талдау тәсілін айтады (шара әрбір терминалмен байланысқан).
Анықтама 4. Егер рекурсиялы төмен түсу әдісі тізбекті қайталап оқуды қажет етпесе, онда ол болжағыш талдау әдісі деп аталады.
Анықтама 5. Грамматиканы болжағыш әдіспен талдау үшін ыңғайлы түрге келтіруді сол жақтан факторизациялау деп атайды.
Ереже туындысын (продукциясын) таңдау варианты белгісіз болған жағдайда ережелерді факторизациялау арқылы дұрыс шешім қабылдауды кіріс ағынынан жеткілікті сандағы символ оқылғанға дейін уақытша кешіктіруге болады[2-3]. Мысалы,
Инструкция if Өрнек then Инструкция else Инструкция,

Инструкция if Өрнек then Инструкция,


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

.
Ережелерді сол жақтан факторизациялаудың алгоритмі
Кіріс: – МЕ – грамматика;

Шығыс: – ережелерінің оң жақтарында бірдей префикстері болмаған МЕ– грамматика[1].


Қадам 1. бейтерминалының екі немесе одан да артық туындысына (продукциясына) ортақ болатын ең ұзын префиксін табу.

Қадам 2. болса, онда 4-қадамға көшу,

әйтпесе ережелерін

,


ережелеріне алмастыру. Мұндағы тізбектері- префиксінде болмаған тізбектер, -жаңа бейтерминал.

Қадам 3. Бейтерминалдар жиынын жаңа бейтерминалымен толықтыру.

Қадам 4. Екі альтернативаның ешқайсысы үшін ортақ префикс табылмай қалғанға дейін грамматиканың кезекті бейтерминалдары үшін 1,2,3 қадамдарын қайталау.

Қадам 5. Бейтерминалдар мен ережелердің табылған жиындарын сәйкес түрде және деп қабылдау[1].


Мысал 5. 2-кестеде сол жақтан факторизациялау алгоритмінің
,

,


МЕ-грамматикасына қолданылуы көрсетілген.
2-кесте

5. мысалындағы грамматиканы түрлендіру




Қадам

Әрекет және нәтиже

1



2

,

3



4

Бейтерминалдардың ешқайсысы үшін ережелердің оң жақтарында ортақ префикс қалған жоқ

5

, ,

әдебиетТЕР


  1. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. –М.: Вильямс, 2002.-528 с.

  2. Хомский Н. Три модели для описания языка // Кибернетический сборник. –М.: ИЛ, 1961.-Вып.2.-С.237-266.

  3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. –М.: Мир, 1979.-536 с.


Достарыңызбен бөлісу:




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет