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

Тип формальной грамматики

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

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

${\displaystyle A\ \to \ \alpha }$

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

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

${\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]

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

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обычно все правые стороны для одной и той же левой стороны перечисляются на одной строке, используя | ( вертикальную черту ) для их разделения. Правила и, следовательно, могут быть записаны как . В этом случае и называются первой и второй альтернативой соответственно. ${\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 , что записывается как , если с и такими, что и . Таким образом, 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 )}$

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

Для любых строк мы говорим, что u дает v или v выводится из u , если существует положительное целое число k и строки такие, что . Это отношение обозначается , или в некоторых учебниках. Если , отношение выполняется. Другими словами, и являются рефлексивным транзитивным замыканием (позволяющим строке дать себя) и транзитивным замыканием (требующим по крайней мере одного шага) , соответственно. ${\displaystyle u,v\in (V\cup \Sigma )^{*},}$ ${\displaystyle u_{1},\ldots ,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)}$

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

Примеры

Слова, соединенные в обратном порядке

Грамматика с постановками ${\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\}^{*}\}}$

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

С → а ,

С → б ,

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

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

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

С → СС ,

С → ( С ) ,

С → ()

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

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

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

С → СС

С → ()

С → ( С )

С → []

С → [ С ]

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

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

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

Совпадающие пары

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

S → aSb

С → аб

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

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

S → aSb

С → ε

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

Различное количество букв «a» и «b»

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

С → Т | У

T → НДС | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

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

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

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

С → бСбб | А

А → аА | ε

Формулы логики первого порядка

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

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

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

[ ( ] )

или

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

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

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

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

С → а

С → аС

С → бС

Терминалами здесь являются a и b , а единственным нетерминалом является S. Описанный язык — это все непустые строки s и s, которые заканчиваются на . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 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} _С + {{1} _С + { а } _С } _С } _С

где {...} _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} _С + {1} _С } _С + { а } _С } _С

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

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

С

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

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

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

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

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

Разбор

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

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

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

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

Нетерминальный символ называется продуктивным , или порождающим , если существует вывод для некоторой строки терминальных символов. называется достижимым , если из начального символа существует вывод для некоторых строк нетерминальных и терминальных символов. называется бесполезным, если он недостижим или непродуктивен. называется обнуляемым, если существует вывод . Правило называется ε-производством . Вывод называется циклом . ${\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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Равенство языков

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

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

Включение языка

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

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

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

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

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

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

Если задан CFG, является ли он неоднозначным ?

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

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

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

Если бы эта проблема была разрешима, неразрешимая проблема почтовой корреспонденции (PCP) также могла бы быть решена: даны строки в некотором алфавите , пусть грамматика ⁠ ⁠ состоит из правила ${\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}^{rev}|\cdots |a_{k}Ta_{k}^{rev}|b}$;

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

Расширения

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

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

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

Подклассы

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

1. Брайан В. Керниган и Деннис М. Ритчи (апрель 1988 г.). Язык программирования C. Серия Prentice Hall Software (2-е изд.). Энглвуд Клиффс/Нью-Джерси: Prentice Hall. ISBN 0131103628.Здесь: Приложение А
2. Введение в теорию автоматов, языки и вычисления , Джон Э. Хопкрофт, Раджив Мотвани, Джеффри Д. Ульман, Эддисон Уэсли, 2001, стр. 191
3. Hopcroft & Ullman (1979), стр. 106.
4. Chomsky, Noam (сентябрь 1956 г.), «Три модели описания языка», IEEE Transactions on Information Theory , 2 (3): 113–124, doi :10.1109/TIT.1956.1056813, S2CID  19519474
5. Jurafsky, Daniel; Martin, James H. (29 декабря 2021 г.). "Constituency Grammars" (PDF) . Stanford University . Архивировано (PDF) из оригинала 2017-03-14 . Получено 28 октября 2022 г. .
6. Бэкус, Дж. В. (1959). «Синтаксис и семантика предложенного международного алгебраического языка Цюрихской конференции ACM-GAMM». Труды Международной конференции по обработке информации . ЮНЕСКО. С. 125–132.
7. Здесь используются обозначения Sipser (1997), стр. 94. Hopcroft & Ullman (1979) (стр. 79) определяют контекстно-свободные грамматики как 4-кортежи таким же образом, но с другими именами переменных.
8. Хопкрофт и Ульман (1979), стр. 90–92.
9. Хопкрофт и Ульман (1979), Упражнение 4.1а, стр. 103.
10. Хопкрофт и Ульман (1979), Упражнение 4.1b, стр. 103.
11. Ахо, Альфред Вайно ; Лам, Моника С.; Сетхи , Рави ; Ульман, Джеффри Дэвид (2007). "4.2.7 Контекстно-свободные грамматики против регулярных выражений" (печать) . Компиляторы: принципы, методы и инструменты (2-е изд.). Бостон, Массачусетс, США: Pearson Addison-Wesley. стр. 205–206. ISBN 9780321486813. Каждая конструкция, которая может быть описана регулярным выражением, может быть описана [контекстно-свободной] грамматикой, но не наоборот.
12. Хопкрофт и Ульман (1979), стр. 131, Теорема 6.1
13. Хопкрофт и Ульман (1979), стр. 131–132, Теорема 6.2
14. Хопкрофт и Ульман (1979), стр.132–134, Теорема 6.3
15. Хопкрофт и Ульман (1979), стр. 135–136, Теорема 6.5
16. Хопкрофт и Ульман (1979), стр.134–135, Теорема 6.4
17. Лесли Валиант (январь 1974 г.). Общее контекстно-свободное распознавание за время, меньшее, чем кубическое (технический отчет). Университет Карнеги-Меллона. стр. 11.
18. Лесли Г. Валиант (1975). «Общее контекстно-свободное распознавание за время, меньшее, чем кубическое». Журнал компьютерных и системных наук . 10 (2): 308–315. doi : 10.1016/s0022-0000(75)80046-8 .
19. Лиллиан Ли (2002). «Быстрый контекстно-свободный анализ грамматики требует быстрого умножения булевых матриц» (PDF) . J ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242. S2CID  1243491. Архивировано (PDF) из оригинала 27.04.2003.
20. Хопкрофт и Ульман (1979), Лемма 4.1, стр. 88.
21. Эйкен, А.; Мерфи, Б. (1991). «Реализация регулярных древовидных выражений». Конференция ACM по языкам функционального программирования и компьютерной архитектуре . стр. 427–447. CiteSeerX 10.1.1.39.3766 . ; здесь: Раздел 4
22. Хопкрофт и Ульман (1979), Лемма 4.2, стр. 89.
23. Хопкрофт, Мотвани и Ульман (2003), Теорема 7.2, Раздел 7.1, стр. 255 и далее
24. Хопкрофт и Ульман (1979), Теорема 4.3, стр. 90.
25. Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли.; здесь: Раздел 7.1.1, стр.256
26. Нийхолт, Антон (1980), Контекстно-свободные грамматики: оболочки, нормальные формы и синтаксический анализ , Lecture Notes in Computer Science, т. 93, Springer, стр. 8, ISBN 978-3-540-10245-8, МР  0590047.
27. Это легко увидеть из грамматических определений.
28. DJ Rosenkrantz и RE Stearns (1970). "Свойства детерминированных нисходящих грамматик". Информация и управление . 17 (3): 226–256. doi : 10.1016/S0019-9958(70)90446-8 .
29. Хопкрофт и Ульман (1979), упражнение 8.10a, стр. 214. Проблема остается неразрешимой, даже если язык создается с помощью «линейной» контекстно-свободной грамматики (т. е. с максимум одним нетерминалом в правой части каждого правила, см. упражнение 4.20, стр. 105).
30. Хопкрофт и Ульман (1979), стр.137–138, Теорема 6.6
31. Сипсер (1997), Теорема 5.10, с. 181.
32. Хопкрофт и Ульман (1979), стр. 281.
33. Хазевинкель, Михиль (1994), Энциклопедия математики: обновленный и аннотированный перевод советской «Математической энциклопедии», Springer, т. IV, стр. 56, ISBN 978-1-55608-003-6.
34. Хопкрофт и Ульман (1979, стр. 200–201, Теорема 8.9)
35. Огден, Уильям (сентябрь 1968 г.). «Полезный результат для доказательства неотъемлемой неоднозначности». Математическая теория систем . 2 (3): 191–194. doi :10.1007/bf01694004. ISSN  0025-5661. S2CID  13197551. Здесь: стр.4
36. Норвелл, Теодор. «Краткое введение в регулярные выражения и контекстно-свободные грамматики» (PDF) . стр. 4. Архивировано (PDF) из оригинала 2005-03-24 . Получено 24 августа 2012 г.
37. Shieber, Stuart (1985), «Доказательства против контекстно-свободного характера естественного языка» (PDF) , Linguistics and Philosophy , 8 (3): 333–343, doi :10.1007/BF00630917, S2CID  222277837, архивировано (PDF) из оригинала 2004-04-15.
38. Pullum, Geoffrey K.; Gerald Gazdar (1982), «Естественные языки и контекстно-свободные языки», Linguistics and Philosophy , 4 (4): 471–504, doi :10.1007/BF00360802, S2CID  189881482.
39. Кули, Кристофер (1985), «Сложность словарного запаса языка бамбара», Лингвистика и философия , 8 (3): 345–351, doi :10.1007/BF00630918, S2CID  189881984.

Примечания

1. В работах Валианта указана O ( n ^{2.81 ), тогдашняя лучшая известная верхняя граница. См.} Matrix multiplication#Computational difficulty для улучшений границ с тех пор.
2. Для регулярных древовидных грамматик Эйкен и Мерфи предлагают алгоритм фиксированной точки для обнаружения непродуктивных нетерминалов. ^[21]
3. Если грамматика может порождать , то правила нельзя обойти. ${\displaystyle \varepsilon }$ ${\displaystyle S\rightarrow \varepsilon }$
4. Это следствие теоремы об исключении единичного производства в Hopcroft & Ullman (1979), стр. 91, теорема 4.4.

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

• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979), Введение в теорию автоматов, языков и вычислений , Эддисон-Уэсли. Глава 4: Контекстно-свободные грамматики, стр. 77–106; Глава 6: Свойства контекстно-свободных языков, стр. 125–137.
• Hopcroft; Motwani, Rajeev; Ullman, Jeffrey D. (2003). Введение в теорию автоматов, языки и вычисления (2-е изд.). Upper Saddle River: 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.
• J. Berstel, L. Boasson (1990). Jan van Leeuwen (ред.). Context-Free Languages . Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 59–102.

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

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