Бесконтекстная грамматика

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален Поиск источников:  «Контекстно-свободная грамматика»  -  новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Упрощенный отрывок из формальной грамматики ^[1] для языка программирования C (слева) и вывод фрагмента кода C (справа) из нетерминального символа . Нетерминальные и терминальные символы показаны синим и красным соответственно.${\ displaystyle \ langle {\ text {Stmt}} \ rangle}$

В формальной теории языка контекстно-свободная грамматика ( CFG ) - это формальная грамматика , правила производства которой имеют вид

${\ Displaystyle А \ \ к \ \ альфа}$

с в одном нетерминального символа и строки терминалов и / или нетерминалов ( может быть пустым). Формальная грамматика является «контекстной», если ее производственные правила могут применяться независимо от контекста нетерминала. Независимо от того, какие символы окружают его, единственный нетерминал в левой части всегда можно заменить правой частью. Это то, что отличает его от контекстно-зависимой грамматики .${\ displaystyle A}$ ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

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

${\ displaystyle \ langle {\ text {Stmt}} \ rangle \ to \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}$

заменяется на . Для данного нетерминального символа может быть несколько правил замены. Язык, сгенерированный грамматикой, - это набор всех строк терминальных символов, которые могут быть получены с помощью повторяющихся приложений правил из некоторого конкретного нетерминального символа («начального символа»). Нетерминальные символы используются в процессе вывода, но могут не появляться в строке окончательного результата. ${\ displaystyle \ langle {\ text {Stmt}} \ rangle}$${\ displaystyle \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}$

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

Бесконтекстные грамматики возникают в лингвистике, где они используются для описания структуры предложений и слов на естественном языке , и фактически они были изобретены лингвистом Ноамом Хомски для этой цели. Напротив, в информатике по мере роста использования рекурсивно определенных понятий они использовались все больше и больше. В ранних приложениях грамматики используются для описания структуры языков программирования . В новом приложении они используются в важной части расширяемого языка разметки (XML), называемой определением типа документа . ^[2]

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

Фон [ править ]

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

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

можно заключить в логические скобки (с помощью логических метасимволов [] ) следующим образом:

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

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

Бесконтекстные грамматики - это особая форма систем Semi-Thue, которые в своей общей форме восходят к работам Акселя Туэ .

Формализм контекстно-свободных грамматик был разработан в середине 1950 - х годов Хомского , ^[3] , а также их классификация как особый тип из формальной грамматики (которую он назвал фразу-структуры грамматики ). ^[4] То, что Хомский называл грамматикой фразовой структуры, теперь известно также как грамматика избирательного округа, в которой грамматика избирательного округа отличается от грамматики зависимости . В рамках генеративной грамматики Хомского синтаксис естественного языка описывался контекстно-независимыми правилами в сочетании с правилами преобразования.

Блочная структура была введена в языки программирования в рамках проекта Algol (1957–1960), который, как следствие, также включал контекстно-свободную грамматику для описания синтаксиса Algol. Это стало стандартной функцией компьютерных языков, и обозначение грамматик, используемых в конкретных описаниях компьютерных языков, стало известно как форма Бэкуса-Наура в честь двух членов комитета по разработке языков Алгола. ^[3]Аспект «блочной структуры», который фиксируют контекстно-свободные грамматики, настолько фундаментален для грамматики, что синтаксис и грамматика терминов часто отождествляются с правилами контекстно-свободной грамматики, особенно в информатике. Формальные ограничения, не охваченные грамматикой, в этом случае считаются частью «семантики» языка.

Бесконтекстные грамматики достаточно просты, чтобы позволить создавать эффективные алгоритмы синтаксического анализа, которые для заданной строки определяют, можно ли и как ее сгенерировать из грамматики. Эрли анализатор является примером такого алгоритма, в то время как широко используемые LR и LL - парсеры более простые алгоритмы , которые имеют дело только с более ограничительными подмножеств контекстно-свободных грамматик.

Формальные определения [ править ]

Контекстно-свободная грамматика G определяется 4- кортежем , где ^[5]${\ Displaystyle G = (V, \ Sigma, R, S)}$

1. V - конечное множество; каждый элемент называется нетерминальным символом или переменной . Каждая переменная представляет отдельный тип фразы или предложения в предложении. Переменные также иногда называют синтаксическими категориями. Каждая переменная определяет язык суб-языка , определенного G .${\ displaystyle v \ in V}$
2. Σ - конечный набор терминалов s, не пересекающихся с V , которые составляют фактическое содержание предложения. Множество терминалов алфавит языка , определяемого грамматикой G .
3. R - конечное отношение в , где звездочка представляет операцию звезды Клини . Члены R называются правилом (перезаписи) или продукцией грамматики. (также обычно обозначается буквой P )${\ Displaystyle V \ раз (V \ чашка \ Sigma) ^ {*}}$
4. S - это начальная переменная (или начальный символ), используемая для представления всего предложения (или программы). Он должен быть элементом V .

Обозначение производственных правил [ править ]

Правило производства в R формализуется математически в виде пары , где находится нетерминальный и является строкой переменных и / или терминалов; а не с помощью упорядоченной пары обозначения, правила производства, как правило , написаны с использованием оператора со стрелкой с , как ее левой стороны и р в его правой части: .${\ Displaystyle (\ альфа, \ бета) \ в R}$${\ displaystyle \ alpha \ in V}$${\displaystyle \beta \in (V\cup \Sigma )^{*}}$${\displaystyle \alpha }$${\displaystyle \alpha \rightarrow \beta }$

Допускается, чтобы β была пустой строкой , и в этом случае ее принято обозначать ε. Форма называется ε-продукцией . ^[6]${\displaystyle \alpha \rightarrow \varepsilon }$

Обычно перечисляют все правые части одной и той же левой части в одной строке, используя | ( символ трубы ), чтобы разделить их. Rules и, следовательно, может быть записано как . В этом случае и называются первой и второй альтернативой соответственно.${\displaystyle \alpha \rightarrow \beta _{1}}$${\displaystyle \alpha \rightarrow \beta _{2}}$${\displaystyle \alpha \rightarrow \beta _{1}\mid \beta _{2}}$${\displaystyle \beta _{1}}$${\displaystyle \beta _{2}}$

Применение правила [ править ]

Для любых строк мы говорим, что u напрямую дает v , записанное как , if with и такое, что and . Таким образом, v является результатом применения правила к u .${\displaystyle u,v\in (V\cup \Sigma )^{*}}$${\displaystyle u\Rightarrow v\,}$${\displaystyle \exists (\alpha ,\beta )\in R}$${\displaystyle \alpha \in V}$${\displaystyle u_{1},u_{2}\in (V\cup \Sigma )^{*}}$${\displaystyle u\,=u_{1}\alpha u_{2}}$${\displaystyle v\,=u_{1}\beta u_{2}}$${\displaystyle (\alpha ,\beta )}$

Применение повторяющихся правил [ править ]

Для любых строк мы говорим , у дает V или V имеет производный от U , если существует целое положительное число к и строки таким образом, что . Это отношение обозначается или в некоторых учебниках. Если , соотношение выполняется. Другими словами, и являются рефлексивным транзитивным замыканием (позволяющим строке уступить сама себе) и транзитивным замыканием (требующим хотя бы одного шага) соответственно.${\displaystyle u,v\in (V\cup \Sigma )^{*},}$ ${\displaystyle u_{1},\cdots ,u_{k}\in (V\cup \Sigma )^{*}}$${\displaystyle u=u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}=v}$${\displaystyle u{\stackrel {*}{\Rightarrow }}v}$${\displaystyle u\Rightarrow \Rightarrow v}$${\displaystyle k\geq 2}$${\displaystyle u{\stackrel {+}{\Rightarrow }}v}$${\displaystyle ({\stackrel {*}{\Rightarrow }})}$${\displaystyle ({\stackrel {+}{\Rightarrow }})}$${\displaystyle (\Rightarrow )}$

Бесконтекстный язык [ править ]

Язык грамматики - это набор${\displaystyle G=(V,\Sigma ,R,S)}$

${\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}$

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

Язык L называется контекстно-свободным языком (CFL), если существует CFG G , такой что .${\displaystyle L\,=\,L(G)}$

Недетерминированные автоматы pushdown точно распознают контекстно-свободные языки.

Примеры [ править ]

Слова, соединенные с их реверсом [ править ]

Грамматика , с постановками${\displaystyle G=(\{S\},\{a,b\},P,S)}$

S → aSa ,

S → bSb ,

S → ε ,

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

S → Asa → aaSaa → aabSbaa → aabbaa .

Это дает понять, что . Язык не зависит от контекста, однако можно доказать, что он не является регулярным .${\displaystyle L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}}$

Если постановки

S → а ,

S → b ,

добавлены, получается контекстно-свободная грамматика для множества всех палиндромов над алфавитом { a , b } . ^[7]

Круглые скобки правильного формата [ править ]

Каноническим примером контекстно-свободной грамматики является сопоставление скобок, которое характерно для общего случая. Есть два терминальных символа "(" и ")" и один нетерминальный символ S. Правила производства:

S → SS ,

S → ( S ) ,

S → ()

Первое правило позволяет символу S умножаться; второе правило позволяет заключить символ S в соответствующие круглые скобки; а третье правило завершает рекурсию. ^[8]

Правильные вложенные круглые и квадратные скобки [ править ]

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

S → SS

S → ()

S → ( S )

S → []

S → [ S ]

с терминальными символами [] () и нетерминальным S.

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

([[[() () [] []]] ([])])

Соответствующие пары [ править ]

В контекстно-свободной грамматике мы можем объединять символы в пары так же, как в скобках . Самый простой пример:

S → aSb

S → ab

Эта грамматика порождает язык , который не является регулярным (согласно лемме о накачке для регулярных языков ).${\displaystyle \{a^{n}b^{n}:n\geq 1\}}$

Специальный символ ε обозначает пустую строку. Изменив указанную выше грамматику на

S → aSb

S → ε

вместо этого мы получаем грамматику, порождающую язык . Он отличается только тем, что он содержит пустую строку, а исходная грамматика - нет.${\displaystyle \{a^{n}b^{n}:n\geq 0\}}$

Различное количество знаков "а" и "б" [ править ]

Контекстно-свободная грамматика для языка, состоящая из всех строк над {a, b}, содержащих неравное количество букв a и b:

S → T | U

T → VaT | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

Здесь нетерминал T может генерировать все строки с большим количеством a, чем b, нетерминал U генерирует все строки с большим количеством b, чем a, а нетерминал V генерирует все строки с равным количеством a и b. Отсутствие третьей альтернативы в правилах для T и U не ограничивает язык грамматики.

Второй блок двойных букв [ править ]

Другой пример нерегулярного языка - это . Он не зависит от контекста, так как может быть сгенерирован следующей контекстно-свободной грамматикой:${\displaystyle \{{\text{b}}^{n}{\text{a}}^{m}{\text{b}}^{2n}:n\geq 0,m\geq 0\}}$

S → bSbb | А

A → aA | ε

Логические формулы первого порядка [ править ]

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

Примеры языков, которые не являются контекстно-свободными [ править ]

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

[(])

или же

[[[[(((((]]]]])))) (([)) (([)) ([) (]) (]) (])

Тот факт, что этот язык не является контекстно-свободным, может быть доказан с помощью леммы о накачке для контекстно-свободных языков и доказательства от противного, наблюдая, что все слова формы должны принадлежать языку. Вместо этого этот язык принадлежит к более общему классу и может быть описан конъюнктивной грамматикой , которая, в свою очередь, также включает другие неконтекстно-свободные языки, такие как язык всех слов формы .${\displaystyle {(}^{n}{[}^{n}{)}^{n}{]}^{n}}$${\displaystyle {\text{a}}^{n}{\text{b}}^{n}{\text{c}}^{n}}$

Обычные грамматики [ править ]

Каждая обычная грамматика контекстно-свободна, но не все контекстно-свободные грамматики являются регулярными. ^[9] Однако следующая контекстно-свободная грамматика также является регулярной.

S → а

S → aS

S → bS

Терминалы здесь и б , в то время как только нетерминал является S . Описанный язык - это все непустые строки s и s, заканчивающиеся на .${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$

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

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

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

S → a | aS | bS

Производные и синтаксические деревья [ править ]

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

Вывод полностью определяется путем предоставления для каждого шага:

• правило, примененное на этом этапе
• наличие его левой части, к которой он применяется

Для наглядности обычно дается и промежуточная струна.

Например, с грамматикой:

1. S → S + S
2. S → 1
3. S → а

Струна

1 + 1 + а

может быть получено из начального символа S следующим образом:

S

→ S + S (по правилу 1. на S )

→ S + S + S (по правилу 1. на втором S )

→ 1 + S + S (по правилу 2. на первой S )

→ 1 + 1 + S (по правилу 2. на второй S )

→ 1 + 1 + a (по правилу 3. на третьей S )

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

• в крайнем левом выводе это всегда крайний левый нетерминал;
• в крайнем правом выводе это всегда крайний правый нетерминал.

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

S

→ S + S (по правилу 1 на крайнем левом S )

→ 1 + S (по правилу 2 на крайнем левом S )

→ 1 + S + S (по правилу 1 на крайнем левом S )

→ 1 + 1 + S (по правилу 2 на крайнем левом S )

→ 1 + 1 + a (по правилу 3 на крайней левой S ),

который можно резюмировать как

Правило 1

Правило 2

Правило 1

Правило 2

Правило 3.

Один крайний правый вывод:

S

→ S + S (по правилу 1 на самой правой S )

→ S + S + S (по правилу 1 на самой правой S )

→ S + S + a (по правилу 3 на самой правой S )

→ S + 1 + a (по правилу 2 на крайнем правом S )

→ 1 + 1 + a (по правилу 2 на самой правой S ),

который можно резюмировать как

Правило 1

Правило 1

Правило 3

Правило 2

Правило 2.

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

Вывод также в некотором смысле накладывает иерархическую структуру на выводимую строку. Например, если строка «1 + 1 + a» получена в соответствии с крайней левой производной, описанной выше, структура строки будет следующей:

{{1} _S + {{1} _S + { a } _S } _S } _S

где {...} _S обозначает подстроку признанную за S . Эту иерархию также можно рассматривать как дерево:

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

S

→ S + S (по правилу 1 на самой правой S )

→ S + a (по правилу 3 на крайнем правом S )

→ S + S + a (по правилу 1 на самой правой S )

→ S + 1 + a (по правилу 2 на крайнем правом S )

→ 1 + 1 + a (по правилу 2 на самой правой S ),

который определяет строку с другой структурой

{{{1} _S + { a } _S } _S + { a } _S } _S

и другое дерево разбора:

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

S

→ S + S (по правилу 1 на крайнем левом S )

→ S + S + S (по правилу 1 на крайнем левом S )

→ 1 + S + S (по правилу 2 на крайнем левом S )

→ 1 + 1 + S (по правилу 2 на крайнем левом S )

→ 1 + 1 + a (по правилу 3 на крайней левой S ),

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

Пример: алгебраические выражения [ править ]

Вот контекстно-свободная грамматика для синтаксически правильных инфиксных алгебраических выражений в переменных x, y и z:

1. S → х
2. S → y
3. S → z
4. S → S + S
5. S → S - S
6. S → S * S
7. S → S / S
8. S → ( S )

Эта грамматика может, например, генерировать строку

( х + у ) * х - г * у / ( х + х )

следующее:

S

→ S - S (по правилу 5)

→ S * S - S (по правилу 6, примененному к крайнему левому S )

→ S * S - S / S (по правилу 7, примененному к крайнему правому S )

→ ( S ) * S - S / S (по правилу 8 применяется к крайнему левому S )

→ ( S ) * S - S / ( S ) (по правилу 8, примененному к крайнему правому S )

→ ( S + S ) * S - S / ( S ) (по правилу 4, примененному к крайнему левому S )

→ ( S + S ) * S - S * S / ( S ) (по правилу 6 применяется к четвертому S )

→ ( S + S ) * S - S * S / ( S + S ) (по правилу 4, примененному к крайнему правому S )

→ ( x + S ) * S - S * S / ( S + S ) (и т. Д.)

→ ( х + у ) * S - S * S / ( S + S )

→ ( х + у ) * х - S * S / ( S + S )

→ ( х + у ) * х - z * S / ( S + S )

→ ( х + у ) * х - г * у / ( S + S )

→ ( х + у ) * х - г * у / ( х + S )

→ ( х + у ) * х - г * у / ( х + х )

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

→ S * S - S (по правилу 6, примененному к крайнему левому S )

→ S * S - S / S (по правилу 7, примененному к крайнему правому S )

можно сделать в обратном порядке:

→ S - S / S (по правилу 7 применительно к самой правой S )

→ S * S - S / S (по правилу 6, примененному к крайнему левому S )

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

Давайте рассмотрим это более подробно. Рассмотрим дерево синтаксического анализа этого вывода:

Начиная с вершины, шаг за шагом, S в дереве расширяется до тех пор, пока не останется нерасширенных S es (нетерминалов). Выбор другого порядка раскрытия приведет к другому производному, но к тому же дереву синтаксического анализа. Дерево синтаксического анализа изменится только в том случае, если мы выберем другое правило для применения в некоторой позиции в дереве.

Но может ли другое дерево синтаксического анализа по-прежнему создавать ту же строку терминала, которая в данном случае равна ( x + y ) * x - z * y / ( x + x ) ? Да, для данной грамматики это возможно. Грамматики с этим свойством называются неоднозначными .

Например, x + y * z можно получить с помощью этих двух разных деревьев синтаксического анализа:

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

Т → х

Т → у

Т → г

S → S + Т

S → S - Т

S → S * Т

S → S / Т

Т → ( S )

S → T ,

еще раз выбирая S в качестве начального символа. Эта альтернативная грамматика будет производить x + y * z с деревом синтаксического анализа, аналогичным левому выше, т.е. неявно предполагая ассоциацию ( x + y ) * z , которая не соответствует стандартному порядку операций . Могут быть созданы более сложные, однозначные и контекстно-свободные грамматики, которые будут создавать деревья синтаксического анализа, которые подчиняются всем желаемым правилам приоритета операторов и ассоциативности.

Нормальные формы [ править ]

Каждая контекстно-свободная грамматика без ε-продукции имеет эквивалентную грамматику в нормальной форме Хомского и грамматику в нормальной форме Грейбаха . «Эквивалент» здесь означает, что две грамматики генерируют один и тот же язык.

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

Свойства закрытия [ править ]

Контекстно-свободные языки закрыты для различных операций, то есть, если языки K и L контекстно-независимы, то это является результатом следующих операций:

• объединение K ∪ L ; конкатенация K ∘ L ; Клини звезда L ^{* [10]}
• подстановка (в частности гомоморфизм ) ^[11]
• обратный гомоморфизм ^[12]
• пересечение с регулярным языком ^[13]

Они не замкнуты относительно общего пересечения (следовательно, и при дополнении ) и разности множеств. ^[14]

Решаемые проблемы [ править ]

Ниже приведены некоторые разрешимые проблемы контекстно-свободных грамматик.

Разбор [ править ]

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

• Алгоритм CYK (для грамматик в нормальной форме Хомского )
• Парсер Эрли
• Парсер GLR
• Анализатор LL (только для соответствующего подкласса грамматик LL ( k ))

Лесли Г. Валиант показал, что контекстно-свободный синтаксический анализ грамматик нормальных форм Хомского сводится к логическому умножению матриц , тем самым наследуя верхнюю границу сложности O ( n ^2.3728639 ). ^{[15] [16] [примечание 1]} И наоборот, Лилиан Ли показала, что умножение логических матриц O ( n ^{3 − ε} ) сводится к ^{разбору} CFG O ( n ^3−3ε ), тем самым устанавливая некоторую нижнюю границу для последнего . ^[17]

Достижимость, продуктивность, возможность обнуления [ править ]

Нетерминальный символ называется продуктивным или порождающим , если есть производная для некоторой строки терминальных символов. называется достижимым, если есть производные для некоторых строк нетерминальных и терминальных символов от начального символа. называется бесполезным, если он недоступен или непродуктивен. называется обнуляемым, если есть деривация . Правило называется ε-продукцией . Деривация называется циклом .${\displaystyle X}$${\displaystyle X{\stackrel {*}{\Rightarrow }}w}$${\displaystyle w}$${\displaystyle X}$${\displaystyle S{\stackrel {*}{\Rightarrow }}\alpha X\beta }$${\displaystyle \alpha ,\beta }$${\displaystyle X}$${\displaystyle X}$${\displaystyle X{\stackrel {*}{\Rightarrow }}\varepsilon }$${\displaystyle X\rightarrow \varepsilon }$${\displaystyle X{\stackrel {+}{\Rightarrow }}X}$

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

• непродуктивные символы, ^{[18] [примечание 2]}
• недостижимые символы, ^{[20] [21] [22]}
• ε-продукций, за одним возможным исключением, ^{[примечание 3] [23]} и
• циклы. ^{[примечание 4]}

В частности, альтернатива, содержащая бесполезный нетерминальный символ, может быть удалена из правой части правила. Такие правила и альтернативы называются бесполезными . ^[24]

В изображенном примере грамматики нетерминал D недоступен, а E непродуктивно, а C → C вызывает цикл. Следовательно, опуская последние три правила не меняет язык , порождаемый грамматикой, и не опуская альтернативы «| Cc | Ee » из правой части правила для S .

Контекстно-свободная грамматика называется правильной, если в ней нет ни бесполезных символов, ни ε-продукций, ни циклов. ^[25] Комбинируя вышеуказанные алгоритмы, любую контекстно-свободную грамматику, не генерирующую ε, можно преобразовать в слабо эквивалентную правильную.

Регулярность и проверки LL ( k ) [ править ]

Это разрешимо ли данная грамматика является регулярной грамматикой , ^[26] , а также является ли это LL ( K ) грамматика для данных к ≥ 0. ^{[27] : 233} Если k не задано, последняя проблема неразрешима. ^{[27] : 252}

Учитывая контекстно-свободный язык , не разрешимо, является ли он регулярным ^[28], или является ли он языком LL ( k ) для данного k . ^{[27] : 254}

Пустота и конечность [ править ]

Существуют алгоритмы, позволяющие определить, является ли язык данного контекстно-свободного языка пустым, а также конечным. ^[29]

Неразрешимые проблемы [ править ]

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

Однако многие проблемы неразрешимы даже для контекстно-свободных грамматик. Примеры:

Универсальность [ править ]

Учитывая CFG, генерирует ли он язык всех строк в алфавите терминальных символов, используемых в его правилах? ^{[30] [31]}

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

Языковое равенство [ править ]

Имея два CFG, генерируют ли они один и тот же язык? ^{[31] [32]}

Неразрешимость этой проблемы является прямым следствием предыдущей: невозможно даже решить, эквивалентен ли CFG тривиальному CFG, определяющему язык всех строк.

Включение языка [ править ]

Учитывая два CFG, может ли первый сгенерировать все строки, которые может сгенерировать второй? ^{[31] [32]}

Если бы эта проблема была разрешимой, то можно было бы решить и языковое равенство: два CFG G1 и G2 порождают один и тот же язык, если L (G1) является подмножеством L (G2), а L (G2) является подмножеством L (G1).

Находиться на более низком или более высоком уровне иерархии Хомского [ править ]

Используя теорему Грейбаха , можно показать, что две следующие проблемы неразрешимы:

• Описывает ли он контекстно-зависимый язык с учетом контекстно-зависимой грамматики ?
• Описывает ли он обычный язык с учетом контекстно-свободной грамматики ? ^{[31] [32]}

Грамматическая двусмысленность [ править ]

Учитывая CFG, это неоднозначно ?

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

Несвязанность языков [ править ]

Имеются ли для двух CFG какие-либо строки, производные от обеих грамматик?

Если бы эта проблема была разрешимой, то можно было бы решить и неразрешимую проблему корреспонденции Поста : учитывая строки над некоторым алфавитом , пусть грамматика состоит из правила${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$${\displaystyle \{a_{1},\ldots ,a_{k}\}}$${\displaystyle G_{1}}$

${\displaystyle S\to \alpha _{1}S\beta _{1}^{rev}|\cdots |\alpha _{N}S\beta _{N}^{rev}|b}$;

где обозначает перевернутую строку и не встречается среди ; и пусть грамматика состоит из правила${\displaystyle \beta _{i}^{rev}}$${\displaystyle \beta _{i}}$${\displaystyle b}$${\displaystyle a_{i}}$${\displaystyle G_{2}}$

${\displaystyle T\to a_{1}Ta_{1}|\cdots |a_{k}Ta_{k}|b}$;

Тогда проблема Post, заданная с помощью, имеет решение тогда и только тогда, когда и имеет производную строку.${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$${\displaystyle L(G_{1})}$${\displaystyle L(G_{2})}$

Расширения [ править ]

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

Расширенная контекстно-свободная грамматика (или регулярная правая часть грамматики ) является тот , в котором правая часть правил производства разрешено быть регулярным выражением над терминалами и нетерминалами грамматики в. Расширенные контекстно-свободные грамматики точно описывают контекстно-свободные языки. ^[33]

Другое расширение - позволить дополнительным терминальным символам появляться в левой части правил, ограничивая их применение. Это создает формализм контекстно-зависимых грамматик .

Подклассы [ править ]

Есть ряд важных подклассов контекстно-свободных грамматик:

• Грамматики LR ( k ) (также известные как детерминированные контекстно-свободные грамматики ) позволяют выполнять синтаксический анализ (распознавание строк) с помощью детерминированных автоматов выталкивания (PDA), но они могут описывать только детерминированные контекстно-свободные языки .
• Грамматики Simple LR , Look-Ahead LR являются подклассами, которые позволяют еще больше упростить синтаксический анализ. SLR и LALR распознаются с использованием того же КПК, что и LR, но в большинстве случаев с более простыми таблицами.
• Грамматики LL ( k ) и LL ( * ) позволяют выполнять синтаксический анализ путем прямого построения самого левого вывода, как описано выше, и описывают еще меньше языков.
• Простые грамматики являются подклассом грамматик LL (1), которые наиболее интересны своим теоретическим свойством, согласно которому языковое равенство простых грамматик разрешимо, а включение языка - нет.
• Грамматики в квадратных скобках обладают тем свойством, что терминальные символы делятся на пары левой и правой скобок, которые всегда совпадают в правилах.
• В линейных грамматиках нет правил с более чем одним нетерминалом в правой части.
• Регулярные грамматики являются подклассом линейных грамматик и описывают регулярные языки, т. Е. Соответствуют конечным автоматам и регулярным выражениям .

LR-синтаксический анализ расширяет LL-синтаксический анализ для поддержки более широкого диапазона грамматик; в свою очередь, обобщенный анализ LR расширяет анализ LR для поддержки произвольных контекстно-свободных грамматик. В грамматиках LL и LR он по существу выполняет анализ LL и LR, соответственно, в то время как на недетерминированных грамматиках он настолько эффективен, насколько и можно ожидать. Хотя синтаксический анализ GLR был разработан в 1980-х годах, многие определения новых языков и генераторы синтаксических анализаторов по сей день продолжают основываться на анализе LL, LALR или LR.

Лингвистические приложения [ править ]

Первоначально Хомский надеялся преодолеть ограничения контекстно-свободных грамматик, добавив правила преобразования . ^[4]

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

Общая позиция Хомского в отношении неконтекстной свободы естественного языка с тех пор не изменилась ^[34], хотя его конкретные примеры относительно неадекватности контекстно-свободных грамматик с точки зрения их слабой порождающей способности были позже опровергнуты. ^[35] Джеральд Газдар и Джеффри Пуллум утверждали, что, несмотря на несколько неконтекстно -свободных конструкций в естественном языке (например, кросс-последовательные зависимости в швейцарском немецком ^[34] и дублирование в Bambara ^[36] ), подавляющее большинство форм на естественном языке действительно контекстно-независимы. ^[35]

См. Также [ править ]

• Разбор грамматики выражений
• Стохастическая контекстно-свободная грамматика
• Алгоритмы контекстной генерации грамматики
• Лемма о накачке для контекстно-свободных языков

Ссылки [ править ]

Примечания [ править ]

Дальнейшее чтение [ править ]

• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979), Введение в теорию автоматов, языки и вычисления , Addison-Wesley. Глава 4: Контекстно-свободные грамматики, стр. 77–106; Глава 6: Свойства контекстно-свободных языков, стр. 125–137.
• Сипсер, Майкл (1997), Введение в теорию вычислений , PWS Publishing, ISBN 978-0-534-94728-6. Глава 2: Контекстно-свободные грамматики, стр. 91–122; Раздел 4.1.2: Решаемые проблемы, касающиеся контекстно-свободных языков, стр. 156–159; Раздел 5.1.1: Редукции через истории вычислений: стр. 176–183.
• Дж. Берстел, Л. Боассон (1990). Ян ван Леувен (ред.). Контекстно-свободные языки . Справочник по теоретической информатике. B . Эльзевир. С. 59–102.

Внешние ссылки [ править ]

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