Кіріспе
Контекстсіз грамматиканың түрі. Компьютер ғылымында, екі мәнді грамматика – бұл бір тізбектің бірнеше сол жақтан туындауы немесе синтаксистік ағашы болуы мүмкін контекстсіз грамматика. Бос емес кез келген контекстсіз тіл, мысалы, қайталама ереже енгізу арқылы екі мәнді грамматиканы қабылдайды. Тек екі мәнді грамматикаларды ғана қабылдайтын тіл – туа біткен екі мәнді тіл деп аталады. Детерминистік контекстсіз грамматикалар әрқашан бірмәнді болады және бірмәнді грамматикалардың маңызды кіші классы болып табылады; алайда, детерминистік емес бірмәнді грамматикалар да бар. Компьютерлік бағдарламалау тілдері үшін анықтамалық грамматика көбінесе екі мәнді болады, себебі ол, мысалы, «ілінген else» сияқты мәселелерге байланысты. Егер осындай екі мәнділік болса, оны әдетте басымдық ережелерін немесе басқа контекстке сезімтал талдау ережелерін қосу арқылы шешеді, сондықтан жалпы фразалық грамматика бірмәнді болады. Кейбір талдау алгоритмдері (мысалы, Эрли немесе GLR талдағыштары) синтаксистік тұрғыдан екі мәнді тізбектерден талдау ағаштарының (немесе «талдау ормандарының») жиынтығын құра алады.
In computer science, an ambiguous grammar is a context free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non empty context free language admits an ambiguous grammar by introducing e. g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non deterministic unambiguous grammars, however. For computer programming languages, the reference grammar is often ambiguous, due to issues such as the dangling else problem. If present, these ambiguities are generally resolved by adding precedence rules or other context sensitive parsing rules, so the overall phrase grammar is unambiguous. Some parsing algorithms (such as Earley or GLR parsers) can generate sets of parse trees (or "parse forests") from strings that are syntactically ambiguous.
Екіжақты грамматиканы тану
Кез келген грамматиканың екі мәнді екендігі туралы шешім мәселесі шешілмейді, себебі оны Пост сәйкесдік мәселесімен тең деп көрсетуге болады. Дегенмен, контекстсіз грамматиканың екі мәнділігін анықтау үшін жартылай шешім процедурасын іске асыратын құралдар бар. Контекстсіз грамматиканы талдаудың тиімділігі оны қабылдайтын автоматқа байланысты. Детерминистік контекстсіз грамматикалар детерминистік стек автоматтарымен қабылданады және мысалы, LR анализаторы арқылы сызықтық уақытта талдануы мүмкін. Олар контекстсіз грамматиканың қатаң кіші жиыны болып табылады, олар стек автоматтарымен қабылданады және мысалы, CYK алгоритмімен полиномиалдық уақытта талдануы мүмкін. Бірмәнді контекстсіз грамматикалар детерминистік емес болуы мүмкін. Мысалы, 0 және 1 алфавитіндегі жұп ұзындықтағы палиндромдар тілі үшін бірмәнді контекстсіз грамматикасы: S → 0S0 | 1S1 | ε. Бұл тілдің кез келген тізбегін оның барлық символдары оқылмай талдау мүмкін емес, яғни стек автоматы жартылай талдаған тізбектің әртүрлі ұзындығына бейімделу үшін баламалы күйлерге өтуді сынап көруі керек. Дегенмен, грамматикалық екі мәнділікті жою детерминистік контекстсіз грамматиканы тудыруы мүмкін, соның арқасында тиімді талдау жасауға болады. YACC сияқты компилятор генераторлары кейбір екі мәнділікті шешу үшін, мысалы, басымдық және байланыс шектеулерін пайдалану мүмкіндіктерін қамтиды.
Өзінен-өзі түсініксіз тілдер
Кейбір контекстсіз тілдерде (грамматика арқылы құрастырылатын тізбектер жиыны) екі мәнді де, бір мәнді де грамматикалар болуы мүмкін, бірақ бір мәнді контекстсіз грамматиканың болуы мүмкін емес контекстсіз тілдер де бар. Мұндай тілдер табиғи түрде екі мәнді деп аталады. Өзінен-өзі екі мәнді реттелген тілдер жоқ. Контекстсіз тілдердің табиғи екі мәнділігінің болуы 1961 жылы Рохит Парик MIT зерттеу есебінде Парик теоремасымен дәлелденді. Дәл сол тіл табиғи түрде екі мәнді. Огден леммасы белгілі бір контекстсіз тілдердің, мысалы, , табиғи екі мәнді екенін дәлелдеу үшін қолданылуы мүмкін. Дәлел үшін осы бетке қараңыз. тілдерінің бірігісі табиғи түрде екі мәнді. Бұл жиын контекстсіз, өйткені екі контекстсіз тілдің бірігісі әрқашан контекстсіз болады. Бірақ , осы бірігіс тілі үшін кез келген контекстсіз грамматиканың формадағы тізбектерді бірмәнді түрде талдай алмайтындығын көрсетеді. Бассино және Нико (2011) контекстсіз тілдердің табиғи екі мәнділігін дәлелдеу әдістерінің жалпы шолуын және қосымша мысалдар келтіреді.
More examples, and a general review of techniques for proving inherent ambiguity of context free languages, are found given by Bassino and Nicaud (2011).