Регулярные против контекстно-свободных Грамматик



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

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

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

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

208   8  

8 ответов:

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

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

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

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

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

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

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

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

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

● abc

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

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

● ABC

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

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

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

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

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

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

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

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

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

  • основы лексического анализа
  • представляют регулярные языки

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

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

enter image description here

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

регулярные грамматики:- грамматика, содержащая производство следующим образом является 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: CFl может быть или не быть двусмысленным.

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

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

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

    Ничего не найдено.

Добавить ответ:
Отменить.