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

Формальды тілдер теориясының дамуына Хомскидің (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].
Тікелей сол жақты рекурсияны жоюдың алгоритмі
Кіріс: – МЕ – грамматика;

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

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

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

,


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

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

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

,

.

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


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



,


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

1-кесте

Қадам	Әрекет және нәтиже
1	,
2	, , ,
3
4	Басқа тікелей сол рекурсия жоқ
5	, , , , ,

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

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

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

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

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

,


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

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

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

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

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

Қадам	Әрекет және нәтиже
1
2	,
3
4	Бейтерминалдардың ешқайсысы үшін ережелердің оң жақтарында ортақ префикс қалған жоқ
5	, ,

1. 
   Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. –М.: Вильямс, 2002.-528 с.
   
2. 
   Хомский Н. Три модели для описания языка // Кибернетический сборник. –М.: ИЛ, 1961.-Вып.2.-С.237-266.
   
3. 
   Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. –М.: Мир, 1979.-536 с.