В главное отличие между двусмысленной и однозначной грамматикой заключается в том, что неоднозначная грамматика - это контекстно-свободная грамматика, для которой существует строка, которая может иметь более одного крайнего левого происхождения, в то время как однозначная грамматика - это контекстно-свободная грамматика, для которой каждая допустимая строка имеет уникальное крайнее левое происхождение.

Грамматика относится к синтаксическим правилам естественных языков. В 1956 году компьютерные ученые представили математическую модель грамматики для написания компьютерного языка. Если возможно получить все строки языка, используя определенную грамматику, то говорят, что язык генерируется из этой грамматики. Контекстно-свободная грамматика - это один из типов грамматики. Эта грамматика порождает контекстно свободный язык. Контекстно-свободная грамматика может быть неоднозначной или однозначной. Для конкретной строки, если есть два или более производных, эта грамматика называется неоднозначной. Для конкретной строки, если существует единственный уникальный крайний левый вывод, эта грамматика называется однозначной грамматикой.

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

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

Грамматика называется неоднозначной, если для строки существует два или более производных.

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

Предположим, что существует следующая грамматика.

G = ({S}, {a + b, +, *}, P, S}. Правила производства следующие. S -> S + S | S * S | a | b. Предположим, что требуется сгенерировать строку a + a * b.

Рассмотрим, S -> S + S

Замена "a" на крайнюю левую букву S даст следующее.

S-> а + S

Замена S на S осуществляется следующим образом.

S-> а + S * S

Замена "a" на крайний левый S даст следующий результат.

S -> а + а * S

Замена буквы S на "b" даст следующий результат.

S -> а + а * б

Это необходимая строка для генерации.

При использовании другого производственного правила это даст

S -> S * S

Применение S + S к крайнему левому краю S даст следующее.

S -> S + S * S

Заменить "a" на крайний левый S,

S -> а + S * S

Подставляя "a" в крайний левый угол S,

S -> а + а * S

Замена «b» на S даст следующий результат.

S -> а + а * б

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

Что такое недвусмысленная грамматика

В неоднозначной грамматике определенная строка имеет уникальное самое левое происхождение. См. Следующие производственные правила.

S -> L | a, L -> LS | S

Рассмотрим правило S -> L. Заменить LS вместо L.

S -> LS

Заменить S на первый L.

S -> S S

Замена «a» на крайнюю левую букву S даст следующий результат.

S -> а S

Замена "а" на S даст следующее.

S -> а а

Следовательно, строка имеет единственный крайний левый вывод. Итак, это однозначная грамматика.

Разница между неоднозначной и однозначной грамматикой

Определение

Неоднозначная грамматика - это контекстно-свободная грамматика, для которой существует строка, которая может иметь более одного левого дерева вывода или синтаксического анализа. Однозначная грамматика - это контекстно-свободная грамматика, для которой каждая допустимая строка имеет уникальное самое левое дерево производных или синтаксического анализа.

Количество крайних левых производных

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

Заключение

Грамматика, свободная от контекста, может быть неоднозначной или однозначной. Разница между неоднозначной и однозначной грамматикой заключается в том, что неоднозначная грамматика - это контекстно-свободная грамматика, для которой существует строка, которая может иметь более одного самого левого производного, в то время как однозначная грамматика - это контекстно-свободная грамматика, для которой каждая допустимая строка имеет уникальное крайнее левое происхождение..

Ссылка:

1. «Неоднозначная грамматика». Википедия, Фонд Викимедиа, 17 июля 2018 г., доступно здесь 2. «Дизайн компилятора | Неоднозначная грамматика ». GeeksforGeeks, 10 февраля 2018 г., доступно здесь 3. «Неоднозначная грамматика», Академия Несо, 29 марта 2017 г., доступно здесь.

Изображение предоставлено:

1. «Самые левые производные jaredwf» Джаредвф в английской Википедии - перенесено из en.wikipedia в Commons Эдвардом Хейдсом (общественное достояние) через Commons Wikimedia