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

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

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

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

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

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

Так, например, палиндром имеет форму

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

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

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

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

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

А что насчет контекстно-свободных языков? Для контекстно-свободных языков существует аналогичная лемма о перекачке, которая разбивает строки в языке на пять частей, uvxyz , и где все экземпляры языка находятся в uv ⁱ xy ⁱ z для i ≥ 0. Теперь у вас есть два "нетерминала". "которые можно воспроизвести или прокачать, если у вас будет то же самое число .

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

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

● abc

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

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

● ABC

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

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 может быть пустым)

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

V->TV or VT
V->T

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

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

Как мы знаем, все RG являются линейной грамматикой, но только Left Linear или Right Linear Grammar являются 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 никогда не бывает неоднозначным по своей сути.

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

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

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

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

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

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

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