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

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

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

A → α {\ displaystyle A \ \ to \ alpha}A \ \ to \ alpha

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

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

Stmt⟩ → ⟨Id⟩ = ⟨Expr⟩; {\ displaystyle \ langle {\ text {Stmt}} \ rangle \ to \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}{\ displaystyle \ langle {\ text {Stmt}} \ rangle \ to \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}

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

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

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

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

Содержание

  • 1 Предпосылки
  • 2 Формальные определения
    • 2.1 Обозначение производственных правил
    • 2.2 Применение правил
    • 2.3 Повторяющееся применение правил
    • 2.4 Контекстно-свободный язык
  • 3 Примеры
    • 3.1 Слова, объединенные их обратной стороной
    • 3.2 Правильно сформированные круглые скобки
    • 3.3 Правильно сформированные вложенные скобки
    • 3.4 Соответствующие пары
    • 3.5 Различное количество букв a и b
    • 3.6 Второй блок b двойного размера
    • 3.7 Логические формулы первого порядка
  • 4 Примеры языков, являющихся контекстно-свободными
  • 5 Регулярные грамматики
  • 6 Производные и синтаксические деревья
    • 6.1 Пример: Алгебраические выражения
  • 7 Нормальные формы
  • 8 Свойства замыкания
  • 9 Решаемые проблемы
    • 9.1 Синтаксический анализ
    • 9.2 Достижимость, продуктивность, допустимость пустых значений
    • 9.3 Проверки регулярности и LL (k)
    • 9.4 Пустота и конечность
  • 10 Неразрешимые проблемы ы
    • 10.1 Универсальность
    • 10.2 Языковое равенство
    • 10.3 Включение языка
    • 10.4 Находиться на более низком или более высоком уровне иерархии Хомского
    • 10.5 Неоднозначность грамматики
    • 10.6 Несвязанность языка
  • 11 Расширения
  • 12 Подклассы
  • 13 Лингвистические приложения
  • 14 См. Также
  • 15 Ссылки
  • 16 Примечания
  • 17 Дополнительная литература
  • 18 Внешние ссылки

Предпосылки

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

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

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

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

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

Контекстно-свободные грамматики - это особая форма систем Semi-Thue, которые в своей общей форме восходят к работе Axel Thue.

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

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

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

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

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

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

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

A правило производства в R математически формализовано как пара (α, β) ∈ R {\ displaystyle (\ alpha, \ beta) \ in R}(\ alpha, \ beta) \ in R , где α ∈ V {\ displaystyle \ alpha \ in V}\ alpha \ in V - нетерминал, а β ∈ (V ∪ Σ) ∗ {\ displaystyle \ beta \ in (V \ cup \ Sigma) ^ {*}}\ beta \ in (V \ cup \ Sigma) ^ {*} - это строка число и / или терминалов; вместо использования нотации упорядоченной пары производственные правила обычно записываются с использованием использования стрелок с α {\ displaystyle \ alpha}\ alpha в качестве левой части и β в качестве правой. side: α → β {\ displaystyle \ alpha \ rightarrow \ beta}\ alpha \ rightarrow \ beta .

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

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

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

Для любых строк u, v ∈ (V ∪ Σ) ∗ {\ displaystyle u, v \ in (V \ cup \ Sigma) ^ {*}}и, v \ in (V \ чашка \ Sigma) ^ {*} , мы говорим, что u непосредственно дает v, записанное как u ⇒ v {\ displaystyle u \ Rightarrow v \,}u \ Rightarrow v \, , если ∃ (α, β) ∈ R {\ Displaystyle \ существует (\ альфа, \ бета) \ in R}\ exists (\ alpha, \ beta) \ in R с α ∈ V {\ displaystyle \ alpha \ in V}\ alpha \ in V и u 1, u 2 ∈ (В ∪ Σ) ∗ {\ displaystyle u_ {1}, u_ {2} \ in (V \ cup \ Sigma) ^ {*}}u_ {1}, u_ {2} \ in (V \ cup \ Sigma) ^ {*} такой, что U = U 1 α U 2 {\ Displaystyle U \, = U_ {1} \ alpha u_ {2}}u \, = u_ {1} \ альфа u_ {2} и v = U 1 β U 2 {\ Displaystyle v \, = u_ {1} \ beta u_ {2}}v \, = u_ {1} \ beta u_ {2} . Таким образом, v является результатом применения правил (α, β) {\ displaystyle (\ alpha, \ beta)}(\ alpha, \ beta) к u.

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

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

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

Язык грамматики G = (V, Σ, R, S) {\ displaystyle G = (V, \ Sigma, R, S)}G = (V, \ Sigma, R, S) - это множество

L (G) = {w ∈ Σ ∗: S ⇒ ∗ w} {\ displaystyle L (G) = \ {w \ in \ Sigma ^ {*}: S {\ stackrel {*} {\ Rightarrow}} w \}}L (G) = \ {w \ in \ Sigma ^ {*}: S {\ stackrel {*} {\ Rightarrow}} w \}

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

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

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

Примеры

Слова, соединенные их обратной стороной

Грамматика G = ({S}, {a, b}, P, S) {\ displaystyle G = (\ {S \}, \ {a, b \}, P, S)}G = (\ {S \}, \ {a, b \}, P, S) , с продукцией

S → aSa,
S → bSb,
S → ε,

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

S → aSa → aaSaa → aabSbaa → aabbaa.

Отсюда ясно, что L (G) = {ww R: w ∈ {a, b} ∗} {\ Displaystyle L (G) = \ {ww ^ {R}: w \ in \ {a, b \} ^ {*} \}}L (G) = \ {ww ^ {R}: w \ in \ {a, b \} ^ {*} \} . Язык не зависит от контекста, однако можно доказать, что он не обычный.

Если сложить продукцию

S → a,
S → b,

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

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

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

S → SS,
S → (S),
S → ()

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

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

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

S → SS
S → ()
S → (S)
S →
S → [S]

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

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

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

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

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

S → aSb
S → ab

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

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

S → aSb
S → ε

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

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

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

S → Т | U
T → VaT | VaV | TaV
U → VbU | VbV | UbV
V → aVbV | bVaV | ε

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

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

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

S → bSbb | A
A → aA | ε

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

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

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

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

[(])

или

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

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

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

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

S → a
S → aS
S → bS

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

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

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

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

S → a | aS | bS

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

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

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

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

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

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

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

строка

1 + 1 + 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)

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

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

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

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

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

правило 1
правило 2
правило 1
правило 2
правило 3.

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

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

, можно обобщить как

правило 1
правило 1
правило 3
Правило 2
Правило 2.

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

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

{{1} S + {{1} S + {a} S}S}S

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

Крайний правый вывод от `1 + 1 + a`

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

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

, который установить с другой структурой

{{{1} S + {a} S}S+ {a} S}S

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

Крайний левый вывод `1 + 1 + a`

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

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

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

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

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

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

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

(x + y) * x - z * y / (x + x)

следующим образом:

S
→ S - S (по правиламу 5)
→ S * S - S (по правиламу 6, примененному к крайний левый S)
→ S * S - S / S (по правилам 7 применяемого к крайнему правому S)
→ (S) * S - S / S (по правилам 8, имеющему к крайнему левому S))
→ (S) * S - S / (S) (по правилам 8 применяемого к крайнему правому S)
→ (S + S) * S - S / (S) ( по правиламу 4, примененному к крайнему левому S)
→ (S + S) * S - S * S / (S) (по правиламу 6, примененному к четвертому S)
→ (S + S) * S - S * S / (S + S) (по правилу 4, применяемому к крайнему правому S)
→ (x + S) * S - S * S / (S + S) (и т. Д.)
→ (x + y) * S - S * S / (S + S)
→ (x + у) * х - S * S / (S + S)
→ (x + y) * x - z * S / (S + S)
→ (x + y) * x - z * y / (S + S)
→ (x + y) * x - z * y / (x + S)
→ (x + y) * x - z * y / (x + x)

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

→ 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 (нетерминалы). Выбор другого порядка раскрытия к другому производному, но к тому же дереву синтаксического анализа. Дерево синтаксического анализа изменится только в том случае, если мы выберем другое правило для применения в некоторой позиции в дереве.

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

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

Два разных дерева синтаксического анализа из одного и того же входа

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

T → x
T → y
T → z
S → S + T
S → S - T
S → S * T
S → S / T
T → (S)
S → T,

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

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

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

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

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

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

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

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

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

Анализ

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

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

Достижимость, продуктивность, допустимость значений NULL

Пример грамматика:
S → Bb | Cc | Ee
B → Bb | b
C → C
D → Bd | CD | d
E → Ee

Нетерминальный символ X {\ displaystyle X}X называется продуктивным или генерирующим, если существует производное X ⇒ ∗ w {\ displaystyle X {\ stackrel { *} {\ Rightarrow}} w}{\ displaystyle X {\ stackrel {*} {\ Rightarrow}} w} для некоторой строки w {\ displaystyle w}w терминальных символов. Икс {\ Displaystyle X}X называется достижимым, если есть производное S ⇒ ∗ α X β {\ Displaystyle S {\ stackrel {*} {\ Rightarrow}} \ alpha X \ beta }{\ displaystyle S {\ stackrel {*} {\ Rightarrow}} \ альфа X \ beta} для некоторых строк α, β {\ displaystyle \ alpha, \ beta}\ альфа, \ бета нетерминальных и конечных символов от начального символа. X {\ displaystyle X}X называется бесполезным, если он недоступен или непродуктивен. X {\ displaystyle X}X называется допускающим значением NULL, если есть производное X ⇒ ∗ ε {\ displaystyle X {\ stackrel {*} {\ Rightarrow}} \ varepsilon}{\ displaystyle X {\ stackrel {*} {\ Rightarrow}} \ varepsilon} . Правило X → ε {\ displaystyle X \ rightarrow \ varepsilon}{\ displaystyle X \ rightarrow \ varepsilon} называется ε-продукцией. Производная X ⇒ + X {\ displaystyle X {\ stackrel {+} {\ Rightarrow}} X}{\ displaystyle 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 G1 и G2 генерируют один и тот же язык, если L (G1) подмножеством L (G2), а L (G2) является подмножеством L (G1).

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

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

двусмысленность грамматики

Имеет ли CFG неоднозначность ?

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

Несвязанность языка

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

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

S → α 1 S β 1 об. | ⋯ | α N S β N r e v | б {\ displaystyle S \ to \ alpha _ {1} S \ beta _ {1} ^ {rev} | \ cdots | \ alpha _ {N} S \ beta _ {N} ^ {rev} | b}S \ to \ alpha _ {1} S \ beta _ {1} ^ {rev} | \ cdots | \ alpha _ {N} S \ beta _ {N} ^ {rev}} | b ;

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

T → a 1 T a 1 | ⋯ | а к т а к | б {\ displaystyle T \ to a_ {1} Ta_ {1} | \ cdots | a_ {k} Ta_ {k} | b}T \ к _ {1} Ta_ {1 } | \ cdots | a_ {k} Ta_ {k} | б ;

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

Расширения

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

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

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

Подклассы

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

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

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

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

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

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

См. Также

Ссылки

Примечания

Дополнительная литература

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

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

Последняя правка сделана 2021-05-15 10:52:32
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте