Формална граматика — разлика између измена

Разлика између ових типова јесте у томе што неки типови [[граматика]] имају строжа правила па могу изразити и мање формалне језике. Два важна типа су контексно слободне граматике (тип 2) и регуларне граматике (тип 3). [[Језик|Језици]] који се могу описати оваквим граматикама се зову контексно слободни језици и регуларни језици. Иако нешто мање моћне од граматика без ограничења (тип 0), које могу изразити било који језик који прихвата [[Тјурингова машина]], ова два ограничена типа граматика су најчешће кориштена јер се [[raščlanjivanje|парсер]] за њих може врло успешно имплементирати. На пример, све регуларне језике може препознати [[коначан аутомат|коначни аутомат]], а за корисне подскупове контексно слободних граматика постоје добро познати алгоритми за генерисање учинковитих [[LL анализатор]]а и [[LR анализатор]]а који препознавају одговарајуће језике које граматика генерише.

Контексно слободан језик може бити препознат у времену <math>O(n^3)</math> користећи алгоритме као што је [[Леонард Ојлер|Ојлеров]]ов алгоритам. Другим речима, за сваки контексно слободан језик се може изградити машина која на улазу прима неки низ знакова и одређује у <math>O(n^3)</math> времену да ли ниска припада [[језик]]у, при чему је <math>n</math> дужина низа симбола за ту ниску. Надаље, неки важни подскупови контекстно слободних језика могу бити препознати у линеарном времену користећи друге алгоритме.

* ''Синтаксичку анализу наниже'' ({{јез-енгл|Top-down parsing language, TDPL}}): минималистички формализам аналитичких граматика развијен у раним 1970им у сврху проучавања [[парсерraščlanjivanje|парсера]]а од врха према дну.

У компјутерским језицима обично фигурише [[контекстно слободна граматика]] ({{јез-енгл|Context free grammar}} - -{CFG}-) која креира одговарајуће контекстно независне језике. На пример, програмски језик -{[[ПрограмскиC језик(програмски Cјезик)|C]]}-, нетерминал који представља читав језик генерисан граматиком, је контекстно зависан али се представља као контекстно независан с тим да се контекстна зависност решава у приступу изради скенера. '''Скенер''' је део преводиоца који програм написан у програмском језику разбија на терминалне симболе, и саставни је део ''front-end'' преводиоца. Скенер емитује терминалне симболе '''парсеру''' као ток ({{јез-енгл|stream}}) везујући за сваки семантичку вредност.

Нпр. када се користи неки љуска (нпр. љуска [[Баш (интерпретер командне линије)|Беш]] у Јуниксу или -{COMMAND.COM}- у [[Дос]]у) и ако је потребно да се виде сви фајлови које је могуће извршити, онда се користи: