Бесконтекстная грамматика - Context-free grammar

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

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

${displaystyle A o alpha }$

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

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

${displaystyle langle { ext{Stmt}}angle o langle { ext{Id}}angle =langle { ext{Expr}}angle ;}$

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

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

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

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

Фон

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

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

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

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

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

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

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

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

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

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

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

1. V - конечное множество; каждый элемент ${displaystyle vin V}$ называется нетерминальный персонаж или Переменная. Каждая переменная представляет отдельный тип фразы или предложения в предложении. Переменные также иногда называют синтаксическими категориями. Каждая переменная определяет подъязык языка, определяемого грамм.
2. Σ конечный набор Терминалs, не пересекается с V, которые составляют фактическое содержание предложения. Набор терминалов - это алфавит языка, определенный грамматикой грамм.
3. р конечное отношение из V к ${displaystyle (Vcup Sigma )^{*}}$, где звездочка обозначает Клини звезда операция. Члены р называются (переписать) правилоs или производствоs грамматики. (также обычно обозначается п)
4. S - это начальная переменная (или начальный символ), используемая для представления всего предложения (или программы). Это должен быть элемент V.

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

А правило производства в р математически формализована как пара ${displaystyle (alpha ,eta )in R}$, куда ${displaystyle alpha in V}$ нетерминал и ${displaystyle eta in (Vcup Sigma )^{*}}$ это нить переменных и / или терминалов; вместо использования упорядоченная пара обозначение, производственные правила обычно записываются с использованием оператора стрелки с ${displaystyle alpha }$ как его левая сторона и β как его правая сторона:${displaystyle alpha ightarrow eta }$.

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

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

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

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

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

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

Бесконтекстный язык

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

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

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

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

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

Примеры

Слова, соединенные с их реверсом

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

S → как,

S → bSb,

S → ε,

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

S → как → aaSaa → aabSbaa → Aabbaa.

Это дает понять, что ${displaystyle L(G)={ww^{R}:win {a,b}^{*}}}$. Язык не зависит от контекста, однако можно доказать, что это не так. обычный.

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

S → а,

S → б,

добавлены контекстно-независимая грамматика для набора всех палиндромы по алфавиту { а, б } получается.^[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}:ngeq 1}}$, который не обычный (согласно лемма о накачке для регулярных языков ).

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

S → aSb

S → ε

получаем грамматику, порождающую язык ${displaystyle {a^{n}b^{n}:ngeq 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 {{ ext{b}}^{n}{ ext{a}}^{m}{ ext{b}}^{2n}:ngeq 0,mgeq 0}}$. Он не зависит от контекста, так как может быть сгенерирован следующей контекстно-свободной грамматикой:

S → bSbb | А

А → аА | ε

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

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

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

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

[ ( ] )

или же

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

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

Обычные грамматики

Основная статья: Обычная грамматика

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

S → а

S → в качестве

S → bS

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

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

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

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

S → а | в качестве | 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 + а (по правилу 3. на третьем S)

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

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

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

S

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

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

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

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

→ 1 + 1 + а (по правилу 3 слева S),

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

Правило 1

Правило 2

Правило 1

Правило 2

Правило 3.

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

S

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

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

→ S + S + а (по правилу 3 справа S)

→ S + 1 + а (по правилу 2 справа S)

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

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

Правило 1

Правило 1

Правило 3

Правило 2

Правило 2.

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

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

{{1}_S + {{1}_S + {а}_S}_S}_S

куда {...}_S указывает подстроку, распознанную как принадлежащую S. Эту иерархию также можно рассматривать как дерево:

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

S

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

→ S + а (по правилу 3 справа S)

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

→ S + 1 + а (по правилу 2 справа S)

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

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

{{{1}_S + {а}_S}_S + {а}_S}_S

и другое дерево синтаксического анализа:

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

S

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

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

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

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

→ 1 + 1 + а (по правилу 3 слева S),

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

Пример: алгебраические выражения

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

1. S → Икс
2. S → у
3. S → z
4. S → S + S
5. S → S – S
6. S → S * S
7. S → S / S
8. S → (S)

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

(Икс + у) * Икс – z * у / (Икс + Икс)

следующее:

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)

→ (Икс + S) * S – S * S / (S + S) (так далее.)

→ (Икс + у) * S – S * S / (S + S)

→ (Икс + у) * Икс – S * S / (S + S)

→ (Икс + у) * Икс – z * S / (S + S)

→ (Икс + у) * Икс – z * у / (S + S)

→ (Икс + у) * Икс – z * у / (Икс + S)

→ (Икс + у) * Икс – z * у / (Икс + Икс)

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

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

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

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

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

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

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

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

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

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

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

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

Т → Икс

Т → у

Т → z

S → S + Т

S → S – Т

S → S * Т

S → S / Т

Т → (S)

S → Т,

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

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

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

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

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

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

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

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

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

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

Парсинг

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

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

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

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

Пример грамматики:
S → Bb | Копия | Ee
B → Bb | б
C → C
D → Bd | CD | d
E → Ee

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

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

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

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

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

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

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

Разрешаемо ли данное грамматика это регулярная грамматика,^[26] а также является ли это LL (k) грамматика для данного 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},eta _{1},ldots ,eta _{N}}$ над некоторым алфавитом ${displaystyle {a_{1},ldots ,a_{k}}}$, пусть грамматика ${displaystyle G_{1}}$ состоят из правила

${displaystyle S o alpha _{1}Seta _{1}^{rev}|cdots |alpha _{N}Seta _{N}^{rev}|b}$;

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

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

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

Расширения

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

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

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

Подклассы

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

• LR (k) грамматики (также известные как детерминированные контекстно-свободные грамматики ) позволять разбор (распознавание строки) с детерминированные автоматы выталкивания (КПК), но они могут только описать детерминированные контекстно-свободные языки.
• Простой 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] и дублирование в Бамбара^[36]), подавляющее большинство форм на естественном языке действительно контекстно-независимы.^[35]

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

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

Рекомендации

1. Брайан В. Керниган и Деннис М. Ричи (апрель 1988 г.). Язык программирования C. Серия программного обеспечения Prentice Hall (2-е изд.). Englewood Cliffs / NJ: Prentice Hall. ISBN  0131103628. Здесь: App.A
2. Введение в теорию автоматов, языки и вычисления, Джон Э. Хопкрофт, Раджив Мотвани, Джеффри Д. Уллман, Эддисон Уэсли, 2001, стр.191
3. Хопкрофт и Ульман (1979), п. 106.
4. Хомский, Ноам (сентябрь 1956 г.), «Три модели для описания языка», IEEE Transactions по теории информации, 2 (3): 113–124, Дои:10.1109 / TIT.1956.1056813
5. Обозначения здесь - это Сипсер (1997), п. 94. Хопкрофт и Ульман (1979) (стр. 79) определяют контекстно-свободные грамматики как 4-кортежи таким же образом, но с разными именами переменных.
6. Хопкрофт и Ульман (1979) С. 90–92.
7. Хопкрофт и Ульман (1979), Упражнение 4.1а, с. 103.
8. Хопкрофт и Ульман (1979), Упражнение 4.1b, с. 103.
9. Ахо, Альфред Вайно; Лам, Моника С.; Сетхи, Рави; Ульман, Джеффри Дэвид (2007). «4.2.7 Контекстно-свободные грамматики и регулярные выражения» (Распечатать). Компиляторы: принципы, методы и инструменты (2-е изд.). Бостон, Массачусетс, США: Пирсон Аддисон-Уэсли. стр.205–206. ISBN  9780321486813. Каждая конструкция, которая может быть описана регулярным выражением, может быть описана [контекстно-свободной] грамматикой, но не наоборот.
10. Хопкрофт и Ульман (1979), стр.131, теорема 6.1
11. Хопкрофт и Ульман (1979), стр.131–132, теорема 6.2
12. Хопкрофт и Ульман (1979), стр.132–134, теорема 6.3
13. Hopcroft & Ullman (1979), стр.135–136, теорема 6.5
14. Хопкрофт и Ульман (1979), стр. 134–135, теорема 6.4.
15. Лесли Валиант (январь 1974 г.). Общее бесконтекстное распознавание менее чем за кубическое время (Технический отчет). Университет Карнеги Меллон. п. 11.
16. Лесли Г. Валиант (1975). «Общее бесконтекстное распознавание менее чем за кубическое время». Журнал компьютерных и системных наук. 10 (2): 308–315. Дои:10.1016 / s0022-0000 (75) 80046-8.
17. Лилиан Ли (2002). «Быстрый анализ грамматики без контекста требует быстрого умножения логической матрицы» (PDF). J ACM. 49 (1): 1–15. arXiv:cs / 0112018. Дои:10.1145/505241.505242.
18. Хопкрофт и Ульман (1979), Лемма 4.1, с. 88.
19. Aiken, A .; Мерфи, Б. (1991). «Реализация регулярных древовидных выражений». Конференция ACM по языкам функционального программирования и компьютерной архитектуре. С. 427–447. CiteSeerX  10.1.1.39.3766.; здесь: Раздел 4
20. Хопкрофт и Ульман (1979), Лемма 4.2, с. 89.
21. Хопкрофт, Мотвани и Ульман (2003) Ошибка harvtxt: нет цели: CITEREFHopcroftMotwaniUllman2003 (помощь), Теорема 7.2, раздел 7.1, стр.255ff
22. (PDF) https://www.springer.com/cda/content/document/cda_downloaddocument/9780387202488-c1.pdf?SGWID=0-0-45-466216-p52091986. Отсутствует или пусто | название = (помощь)
23. Хопкрофт и Ульман (1979), Теорема 4.3, с. 90.
24. Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления. Эддисон Уэсли.; здесь: раздел 7.1.1, стр.256
25. Нейхольт, Антон (1980), Грамматики, не зависящие от контекста: обложки, нормальные формы и синтаксический анализ, Конспект лекций по информатике, 93, Springer, стр. 8, ISBN  978-3-540-10245-8, МИСТЕР  0590047.
26. Это легко увидеть из определений грамматики.
27. Д.Дж. Розенкранц и Р. Стернс (1970). «Свойства детерминированных грамматик сверху вниз». Информация и контроль. 17 (3): 226–256. Дои:10.1016 / S0019-9958 (70) 90446-8.
28. Хопкрофт и Ульман (1979), Упражнение 8.10а, с. 214. Проблема остается неразрешимой, даже если язык создается с помощью «линейной» контекстно-свободной грамматики (то есть с не более чем одним нетерминалом в правой части каждого правила, см. Упражнение 4.20, стр. 105).
29. Хопкрофт и Ульман (1979), стр.137–138, теорема 6.6
30. Сипсер (1997), Теорема 5.10, с. 181.
31. Хопкрофт и Ульман (1979), п. 281.
32. Hazewinkel, Michiel (1994), Энциклопедия математики: обновленный и аннотированный перевод советской "Математической энциклопедии", Springer, Vol. IV, стр. 56, ISBN  978-1-55608-003-6.
33. Норвелл, Теодор. «Краткое введение в регулярные выражения и контекстно-свободные грамматики» (PDF). п. 4. Получено 24 августа, 2012.
34. Шибер, Стюарт (1985), «Свидетельства против контекстной свободы естественного языка» (PDF), Лингвистика и философия, 8 (3): 333–343, Дои:10.1007 / BF00630917.
35. Пуллум, Джеффри К .; Джеральд Газдар (1982), «Естественные языки и контекстно-свободные языки», Лингвистика и философия, 4 (4): 471–504, Дои:10.1007 / BF00360802.
36. Кули, Кристофер (1985), "Сложность словаря бамбара", Лингвистика и философия, 8 (3): 345–351, Дои:10.1007 / BF00630918.

Примечания

1. В бумагах Валианта О(п^2.81) дана наиболее известная на тот момент верхняя оценка. Видеть Умножение матриц # Алгоритмы эффективного умножения матриц и Алгоритм Копперсмита – Винограда для связанных улучшений с тех пор.
2. За регулярные древовидные грамматики, Айкен и Мерфи предлагают алгоритм фиксированной точки для обнаружения непродуктивных нетерминалов.^[19]
3. Если грамматика может генерировать ${displaystyle varepsilon }$, правило ${displaystyle Sightarrow varepsilon }$ нельзя избежать.
4. Это следствие теоремы об исключении единичного производства в Hopcroft & Ullman (1979), стр.91, теорема 4.4.

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

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

внешняя ссылка

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