Рубрики

Неоднозначная грамматика

Вы также можете прочитать нашу ранее обсуждаемую статью по классификации контекстно-свободных грамматик.

КОНТЕКСТ F РЗЭ G rammars (CFGs) классифицируются на основе:

  • Количество деривационных деревьев
  • Количество строк

В зависимости от количества деревьев деривации CFG подразделяются на 2 типа:

  • Неоднозначные грамматики
  • Однозначные грамматики

Неоднозначная грамматика:

КС — грамматика называется неоднозначной , если существует более одного деривации дерево для данной входной строки , т.е., более чем один L EFT M ост D erivation T РЗЭ (LMDT) или R РАВО М ОСТ Д erivation Т РЗЭ (RMDT).

Определение: G = (V, T, P, S) — это CFG, который называется неоднозначным тогда и только тогда, когда в T * существует строка, которая имеет больше, чем в дереве разбора.
где V — конечное множество переменных.
T — конечный набор терминалов.
P — конечный набор произведений вида A -> α, где A — переменная, а α ∈ (V ∪ T) * S — обозначенная переменная, называемая начальным символом.

Например:

1. Рассмотрим эту грамматику: E -> E + E | id

Мы можем создать 2 дерева разбора из этой грамматики, чтобы получить строку id + id + id :

Ниже приведены 2 дерева разбора, сгенерированных самой левой деривацией:

Оба приведенных выше дерева разбора основаны на одних и тех же грамматических правилах, но оба дерева разбора различны. Следовательно, грамматика неоднозначна.

2. Давайте теперь рассмотрим следующую грамматику:

Set of alphabets ∑ = {0,…,9, +, *, (, )}

E -> I        
E -> E + E
E -> E * E
E -> (E)
I -> ε | 0 | 1 | … | 9
 

Из приведенной выше грамматики строка 3 * 2 + 5 может быть получена двумя способами:

I) First leftmost derivation                   II) Second leftmost derivation
        E=>E*E                          E=>E+E
         =>I*E                           =>E*E+E
         =>3*E+E                                       =>I*E+E
         =>3*I+E                           =>3*E+E
         =>3*2+E                           =>3*I+E
         =>3*2+I                           =>3*2+I
         =>3*2+5                           =>3*2+5

Ниже приведены некоторые примеры неоднозначных грамматик:

  • S-> aS | Sa | Є
  • E-> E + E | E * E | Я бы
  • A -> AA | (А) |
  • S -> SS | AB, A -> Aa | a, B -> Bb | b

Принимая во внимание, что следующие грамматики однозначны:

  • S -> (L) | a, L -> LS | S
  • S -> AA, A -> aA, A -> b

По своей сути неоднозначный язык:

Пусть L будет контекстно-свободным языком (CFL). Если каждая контекстно-свободная грамматика G с языком L = L (G) неоднозначна, то говорят, что L по своей сути является неоднозначным языком. Неоднозначность — это свойство грамматики, а не языков. Неоднозначная грамматика вряд ли будет полезна для языка программирования, потому что две структуры деревьев разбора (или более) для одной и той же строки (программы) подразумевают два разных значения (исполняемые программы) для программы.

Неоднозначный по своей природе язык был бы абсолютно непригоден в качестве языка программирования, потому что у нас не было бы никакого способа зафиксировать уникальную структуру для всех его программ.

Например,

L = {anbncm} ∪ {anbmcm} 

Примечание. Неоднозначность грамматики неразрешима, т. Е. Не существует конкретного алгоритма удаления неоднозначности грамматики, но мы можем устранить неоднозначность следующим образом:

Устраните неоднозначность грамматики, т. Е. Переписайте грамматику так, чтобы для строки языка, которую представляет грамматика, было возможно только одно дерево деривации или синтаксического анализа.

Эта статья составлена Сайкиран Гауд Бурра .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Неоднозначная грамматика

0.00 (0%) 0 votes