Обычные грамматики против контекстно-свободных

StackOverflow https://stackoverflow.com/questions/559763

Вопрос

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

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

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

Кто-нибудь может помочь мне собрать все это воедино?

Это было полезно?

Решение

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

Так, например, для палиндрома имеет вид, 

S->ABA
A->something
B->something

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

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

Другие советы

Я думаю, то, о чем вы хотите подумать, - это различные леммы прокачки.Обычный язык может быть распознан конечным автоматом.Для контекстно-свободного языка требуется стек, а для контекстно-зависимого языка требуется два стека (что эквивалентно утверждению, что для него требуется полноценная машина Тьюринга).

Итак, если мы подумаем о лемма о прокачке для обычных языков, по сути, это говорит о том, что любой обычный язык может быть разбит на три части, x, y, и z, где все экземпляры языка находятся в xy *z (где * - повторение Клина, т.е. 0 или более копий y.) По сути, у вас есть один "нетерминал", который можно расширить.

Теперь, как насчет контекстно-свободных языков?Есть аналогичный лемма о прокачке для контекстно-свободных языков это разбивает строки в языке на пять частей, uvxyz, и где все экземпляры языка находятся в уф-излучениеixyiz, для i ≥ 0.Теперь у вас есть два "нетерминалы", которые могут быть реплицированы или перекачаны, до тех пор, пока у вас один и тот же номер.

Разница между обычной и контекстно-свободной грамматикой: (N, Σ, P, S) :терминалы, нетерминалы, производства, символы терминала начального состояния

● элементарные символы языка , определенные формальной грамматикой

● азбука

Нетерминальные символы (или синтаксические переменные)

● заменяется группами терминальных символов в соответствии с правилами производства

● АЗБУКА

обычная грамматика:правильная или левая обычная грамматика правильная обычная грамматика, все правила подчиняются формам

  1. B → a где B - нетерминал в N , а a - терминал в Σ
  2. B → aC , где B и C находятся в N, а a - в Σ
  3. B → ε, где B находится в N, а ε обозначает пустую строку, т. е.строка длиной 0

оставлена обычная грамматика, все правила подчиняются формам

  1. A → a , где A - нетерминал в N , а a - терминал в Σ
  2. A → Ba , где A и B находятся в N, а a - в Σ
  3. A → ε , где A находится в N, а ε - пустая строка

контекстно-свободная грамматика (CFG)

○ формальная грамматика , в которой каждое производственное правило имеет вид V → w

○ V - единственный нетерминальный символ.

○ w - строка терминалов и / или нетерминалов (w может быть пустым)

Регулярные выражения

  • Основы лексического анализа
  • Представляют обычные языки

Контекстно - свободные Грамматики

  • Основа синтаксического анализа
  • Представляют собой языковые конструкции

enter image description here

Обычная грамматика:- грамматика, содержащая следующую продукцию, является RG:

V->TV or VT
V->T

где V= переменная и T= терминал

RG может быть левой линейной грамматикой или Правой линейной Грамматикой, но не Средней линейной Грамматикой.

Как мы знаем, все RG являются Линейной грамматикой, но только Левая линейная или Правая линейная грамматика являются RG.

Обычная грамматика может быть неоднозначной.

S->aA|aB
A->a
B->a

Двусмысленная Грамматика:- для строки x существует более одного LMD или более RMD, или более одного дерева синтаксического анализа, или Один LMD и Один RMD, но оба они создают разное дерево синтаксического анализа.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

эта грамматика является неоднозначной грамматикой, потому что два дерева синтаксического анализа.

CFG:- Грамматика называется CFG, если ее создание выполняется в форме:

   V->@   where @ belongs to (V+T)*

DCFL:- как мы знаем, все DCFL являются грамматикой LL (1), а все LL (1) - LR (1), поэтому это никогда не будет двусмысленным.так что DCFG никогда не будет двусмысленным.

Мы также знаем, что все RL являются DCFL, поэтому RL никогда не бывает двусмысленным.Обратите внимание, что RG может быть неоднозначным, а RL - нет.

КЛЛ: CFl Может быть неоднозначным, а может и не быть.

Примечание: RL никогда не бывает изначально двусмысленным.

Грамматика является контекстно-свободной, если все производственные правила имеют вид:A (то есть левой частью правила может быть только одна переменная;правая сторона не ограничена и может представлять собой любую последовательность терминалов и переменных).Мы можем определить грамматику как 4-кортеж, где V - конечное множество (переменные), _ - конечное множество (терминалы), S - начальная переменная, а R - конечный набор правил, каждое из которых является отображением V
обычная грамматика является линейной либо справа, либо слева, тогда как контекстно-свободная грамматика - это, по сути, любая комбинация терминалов и нетерминалов.следовательно, мы можем сказать, что обычная грамматика - это подмножество контекстно-свободной грамматики.После этих свойств мы можем сказать, что набор контекстно-свободных языков также содержит набор обычных языков

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top