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

Упрощенный отрывок из формальной грамматики для языка программирования C (слева) и получение фрагмента кода C (справа) из нетерминального символа $\langle {\text{Stmt}}\rangle$. Нетерминальные символы обозначены синим цветом, а терминальные символы — красным.

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

$A\ \to \ \alpha$

с $A$ одиночный нетерминальный символ и $\alpha$ строка терминалов и/или нетерминалов ( $\alpha$ может быть пустым). Независимо от того, какие символы его окружают, единственный нетерминал $A$ слева всегда можно заменить на $\alpha$ с правой стороны. Это отличает ее от контекстно-зависимой грамматики , которая может иметь правила продукции в виде $\alpha A\beta \rightarrow \alpha \gamma \beta$ с $A$ нетерминальный символ и $\alpha$, $\beta$, и $\gamma$ строки терминальных и/или нетерминальных символов.

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

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

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

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

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

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

Фон

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

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

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

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

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

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

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

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

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

Формальные определения

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

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

Обозначение производственного правила

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

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

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

Применение правил

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

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

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

Контекстно-свободный язык

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

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

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

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

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

Примеры

Слова, объединенные в обратную сторону

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

С → аСа ,

S → bSb ,

S → ε ,

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

S → aSa → aaSaa → отецSbaa → отец

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

Если произведения

С → а ,

С → б ,

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

Правильно построенные скобки

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

С → СС ,

С → ( S ) ,

С → ()

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

Правильно сформированные вложенные скобки и квадратные скобки

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

С → СС

С → ()

С → ( С )

С → []

С → [ С ]

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

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

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

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

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

S → аСб

С → аб

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

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

S → аСб

С → е

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

Отдельное количество букв a и b

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

С → Т | ты

Т → НДС | ВаВ | ТаВ

У → ВбУ | ВбВ | УбВ

В → аВбВ | бВаВ | ε

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

Второй блок букв двойного размера.

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

С → bSbb | А

А → аА | ε

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

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

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

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

[ ( ] )

или

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

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

Регулярные грамматики

Основная статья: Регулярная грамматика

Каждая регулярная грамматика является контекстно-свободной, но не все контекстно-свободные грамматики являются регулярными. Например, следующая контекстно-свободная грамматика также является регулярной.

С → а

С → аС

С → бС

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

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

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

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

С → а | АС | бакалавриат

Выводы и синтаксические деревья

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

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

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

Для ясности обычно также указывается промежуточная строка.

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

1. С → С + С
2. С → 1
3. С → а

строка

1 + 1 + а

может быть получен из начального символа 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 (по правилу 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 (по правилу 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 (по правилу 1 на крайнем правом S )

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

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

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

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

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

{{{1} _S + {1} _S } _S + { a } _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 ),

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

Нормальные формы

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

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

Свойства замыкания

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

• объединение К ∪ L ; конкатенация К ∘ L ; Клини Стар Л ^*
• подстановка (в частности гомоморфизм )
• обратный гомоморфизм
• пересечение с обычным языком

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

Решаемые проблемы

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

Разбор

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

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

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

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

Пример грамматики:
С → Бб | копия | Ээ
Б → Бб | б
С → С
Д → Бд | компакт- диск | д
Е → Ээ

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

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

• непродуктивные символы,
• недостижимые символы,
• ε-продукции, за одним возможным исключением, и
• циклы.

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

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

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

регулярности и LL( k ) Проверка

Можно решить, ли данная грамматика является регулярной грамматикой . а также является ли это LL( k ) грамматикой для данного k ≥0. Если k не задано, последняя проблема неразрешима.

Учитывая контекстно-свободную грамматику, невозможно решить, является ли ее язык регулярным. и не является ли это языком LL( k ) для данного k .

Пустота и конечность

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

Неразрешимые проблемы

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

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

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

Учитывая CFG, генерирует ли он язык всех строк в алфавите терминальных символов, используемых в его правилах?

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

Языковое равенство

Учитывая два CFG, генерируют ли они один и тот же язык?

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

Языковое включение

Учитывая два CFG, может ли первый сгенерировать все строки, которые может сгенерировать второй?

Если бы эта проблема была разрешима, то можно было бы решить и равенство языков: две CFG $G_{1}$ и $G_{2}$ сгенерировать тот же язык, если $L(G_{1})$ является подмножеством $L(G_{2})$ и $L(G_{2})$ является подмножеством $L(G_{1})$.

Нахождение на более низком или более высоком уровне иерархии Хомского

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

• Учитывая контекстно-зависимую грамматику , описывает ли она контекстно-свободный язык?
• Учитывая контекстно-свободную грамматику, описывает ли она обычный язык ?

Грамматическая неоднозначность

Учитывая CFG, является ли это двусмысленным ?

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

Языковая разобщенность

Учитывая две CFG, существует ли какая-либо строка, выводимая из обеих грамматик?

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

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

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

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

Тогда экземпляр PCP, заданный $\alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}$ имеет решение тогда и только тогда, когда ⁠ $L(G_{1})$⁠ и ⁠ $L(G_{2})$⁠ поделиться производной строкой. Слева от строки (перед $b$) будет представлять верхнюю часть решения для экземпляра PCP, а правая сторона будет нижней, наоборот.

Расширения

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

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

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

Подклассы

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

• LR( k ) Грамматики (также известные как детерминированные контекстно-свободные грамматики ) позволяют выполнять синтаксический анализ (распознавание строк) с помощью детерминированных автоматов с выталкиванием (PDA), но они могут описывать только детерминированные контекстно-свободные языки .
• Простые 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 и по сей день.

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

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

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

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

См. также

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

Дальнейшее чтение

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

Внешние ссылки

• Программисты могут найти ответ на обмен стеком полезным.
• Разработчик CFG, созданный Кристофером Вонгом из Стэнфордского университета в 2014 году; изменен Кевином Гиббонсом в 2015 году.