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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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