В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.
Грамматики некоторых языков программирования неоднозначны. При разборе таких языков необходимо учитывать семантическую информацию для выбора правильного варианта. Например, на языке C следующая запись:
x * y;
может быть проинтерпретирована как либо:
Чтобы выбрать между этими интерпретациями, компилятор должен обратиться к своей таблице символов, чтобы узнать, было ли объявление x в качестве имени typedef в данной области видимости.
Контекстно свободная грамматика
A → A + A | A − A | a
является неоднозначной, так как есть два левосторонних вывода для строки a + a + a:
Также, грамматика является неоднозначной, поскольку есть два дерева разбора для строки a + a − a:
Однако, язык, который она порождает, не является существенно неоднозначным, поскольку следующая однозначная грамматика порождает этот же язык:
A → A + a | A − a | a
Общая задача определения, является ли грамматика неоднозначной, алгоритмически неразрешима. Не может существовать алгоритма, определяющего неоднозначность грамматики, поскольку неразрешимая задача соответствия Поста сводится к задаче неоднозначности.
Существует очевидная трудность в синтаксическом анализе неоднозначной грамматики детерминированным анализатором, но недетерминированный анализ приводит к значительному проигрышу в эффективности. Большинство конструкций, требующих синтаксического анализа, могут быть распознаны однозначными грамматиками. Некоторые неоднозначные грамматики могут быть преобразованы в однозначные, но общей процедуры для этого преобразования нет, так же как нет и алгоритма определения неоднозначности грамматики. Генераторы компиляторов, такие как YACC, способны устранять некоторые виды неоднозначности, например используя ограничения приоритета и ассоциативности.
В то время как некоторые языки (множества строк, порождаемых грамматикой) имеют как однозначные, так и неоднозначные грамматики, существуют языки, для которых не существует однозначной грамматики. Примером существенно неоднозначного языка является объединение { a n b m c m d n | n , m > 0 } {displaystyle {a^{n}b^{m}c^{m}d^{n}|n,m>0}} и { a n b n c m d m | n , m > 0 } {displaystyle {a^{n}b^{n}c^{m}d^{m}|n,m>0}} . Это контекстно-свободный язык как объединение контекстно-свободных языков, но Введение в теорию автоматов… содержит доказательство того, что нет возможности однозначно разобрать строки в (не контекстно-свободном) подмножестве { a n b n c n d n | n > 0 } {displaystyle {a^{n}b^{n}c^{n}d^{n}|n>0}} , являющемся пересечением этих двух языков.
Читайте также
Трудовые споры: как добиться справедливости от недобросовестного работодателя
Трудовые отношения — это тонкая материя, полная нюансов и правовых
Как отличить брендовые очки от подделки
Брендовые солнцезащитные очки — это не только модный аксессуар, но
Дизайн встроенной кухни: как оптимизировать пространство
Несмотря на большое разнообразие готовой (типовой) мебели, мебель на заказ
Михаил Владимирович Мишустин: отличный управленец и экономист
Михаил Владимирович Мишустин — выдающийся российский государственный и политический деятель,
Самые популярные рецепты пиццы: идеальное сочетание ингредиентов для настоящего гурмана
Пицца – это одно из наиболее популярных блюд в мире,
Лето – это время, когда дети, закончив учебный год, уходят
Как получить гражданство Бельгии и что оно дает?
Бельгия, расположенная в сердце Европейского союза, по праву считается одним
Когда начинать готовиться к ЕГЭ и ОГЭ 2024: полезные рекомендации
Начало нового учебного года часто становится временем повышенной тревожности как
На чем можно долететь до Мальдив? Регулярный рейс или аренда частного самолета?
Путешествие на Мальдивы — это мечта многих туристов. Острова, утопающие
Зубной имплантат: преимущества выбора при протезировании
Зубной имплантат – это современная технология, предоставляющая возможность восстановить утраченный
Яйцо шоколадное Kinder сюрприз: волшебство, которое завоевало сердца детей и взрослых
Яйцо Kinder сюрприз, безусловно, является одним из наиболее популярных шоколадных
Суши и пицца: почему они так популярны в службе доставки
Службы доставки еды становятся всё популярнее среди людей, желающих насладиться
Пептидные препараты: сущность и области применения
Пептидные препараты стали одним из важнейших направлений в современной медицине