Редактирование: Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
==Основные определения==
 
 
{{Определение
 
{{Определение
|id=csgrammar
 
 
|definition=
 
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется [[Формальные грамматики|грамматика]], у которой в левых частях всех правил стоят только одиночные нетерминалы.
+
'''Контекстно-свободной грамматикой''' называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. <br>
 +
Язык, задаваемый контекстно-свободной грамматикой называется '''контекстно-свободным языком'''.
 
}}
 
}}
{{Определение
 
|id=lang
 
|definition=
 
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
 
}}
 
 
==Лево- и правосторонний вывод слова==
 
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.  
+
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово <tex>\alpha</tex>.  
 
}}
 
}}
'''Пример:'''
 
 
Рассмотрим грамматику, выводящую все правильные скобочные последовательности.
 
:<tex>(</tex> и <tex>)</tex> {{---}} терминальные символы
 
:<tex>S</tex> {{---}} стартовый нетерминал
 
 
Правила:
 
#<tex>S\rightarrow (S)S</tex>
 
#<tex>S\rightarrow S(S)</tex>
 
#<tex>S\rightarrow \varepsilon</tex>
 
 
Выведем слово <tex>(()(()))()</tex>:
 
  
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>
+
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности. Терминальные символы "(" и ")", нетерминал <tex>S</tex>, он же стартовый нетерминал, правила:<br>
 +
<tex>S\rightarrow (S)S</tex><br>
 +
<tex>S\rightarrow S(S)</tex><br>
 +
<tex>S\rightarrow \varepsilon</tex><br>
 +
Выведем слово "(()(()))()":<br>
 +
<tex>\boldsymbol{S}\rightarrow (S)\boldsymbol{S} \rightarrow (S)(\boldsymbol{S})S\rightarrow(S)()\boldsymbol{S}\rightarrow(\boldsymbol{S})()\rightarrow(\boldsymbol{S}(S))()\rightarrow(S(S)(\boldsymbol{S}))()\rightarrow(S(S)(\boldsymbol{S}(S)))()\rightarrow (S(\boldsymbol{S})((S)))()\rightarrow(\boldsymbol{S}()((S)))()\rightarrow(()((\boldsymbol{S})))()\rightarrow(()(()))()</tex>
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Левосторонним выводом слова''' (англ. ''leftmost derivation'') <tex>\alpha</tex> называется такой вывод слова <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
+
'''Левосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
 
}}
 
}}
 +
Аналогичным образом определяется ''правосторонний вывод''.
 +
<br>
 +
Рассмотрим левосторонний вывод нашей скобочной последовательности:<br>
 +
<tex>\boldsymbol{S}\rightarrow (\boldsymbol{S})S \rightarrow ((\boldsymbol{S})S)S\rightarrow (()\boldsymbol{S})S\rightarrow(()\boldsymbol{S}(S))S\rightarrow(()(\boldsymbol{S}))S\rightarrow(()(\boldsymbol{S}(S)))S\rightarrow(()((\boldsymbol{S})))S\rightarrow(()(()))\boldsymbol{S}\rightarrow(()(()))(\boldsymbol{S})S\rightarrow(()(()))()\boldsymbol{S}\rightarrow(()(()))()</tex>
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Правосторонним выводом слова''' (англ. ''rightmost derivation'') <tex>\alpha</tex> называется такой вывод слова <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
+
'''Деревом разбора грамматики''' называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей.
 
}}
 
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера:
 
 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>
 
 
==Дерево разбора==
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
+
'''Кроной''' дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня.
 
}}
 
}}
 +
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.<br>
 +
Рассмотрим, как будет выглядеть дерево разбора нашей скобочной последовательности.<br>
 +
[[Файл:derivation_tree.png]]
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Крона дерева разбора''' (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
+
Грамматика называется '''однозначной''', если у каждого слова имеется не более одного дерева разбора в этой грамматкие.
}}
 
 
 
Построим дерево разбора скобочной последовательности из примера.
 
 
 
[[Файл:BracketsSequenceParsingTree1.png]]
 
 
 
{{Теорема
 
|id=t1
 
|statement=Пусть <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным <tex>A</tex>, и кроной <tex>\omega</tex>, где <tex>\omega \in N^{*}</tex>. Тогда в грамматике <tex>\Gamma</tex> существует левое порождение <tex>A \Rightarrow^{*}_{lm} \omega</tex>
 
|proof=
 
Используем индукцию по высоте дерева.
 
 
 
'''База:''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной.
 
:Поскольку это дерево является деревом разбора, <tex>A \rightarrow \omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} \omega</tex> есть одношаговое левое порождение <tex>\omega</tex> из <tex>A</tex>.
 
 
 
'''Индукционный переход:''' Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2 \ldots X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.
 
# Если <tex>X_i</tex> — терминал, то определим <tex>\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.
 
# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} \omega_i</tex>.
 
 
 
Заметим, что <tex>\omega = \omega_1\omega_2 \ldots \omega_k</tex>.
 
Построим левое порождение цепочки <tex>\omega</tex> следующим образом:
 
:Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\ldots X_k</tex>.
 
:Затем для <tex>i = 1, 2, \ldots, k \ </tex> покажем, что имеет место следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>
 
 
 
Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>.
 
Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\ldots X_k</tex>.
 
 
 
Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k</tex>
 
 
 
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения. <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>
 
# Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения. Таким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2\ldots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:
 
 
 
::<tex>\omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k \Rightarrow_{lm}</tex>
 
 
 
::<tex>\omega_1\omega_2\ldots\omega_{i–1}\alpha_1X_{i+1}\ldots X_k \Rightarrow_{lm}</tex>
 
 
 
::<tex>\omega_1\omega_2\ldots\omega_{i–1}\alpha_2X_{i+1}\ldots X_k  \Rightarrow_{lm}</tex>
 
 
 
::<tex>\ldots</tex>
 
 
 
::<tex>\omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>
 
 
 
Результатом является порождение <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>.
 
Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>\omega</tex> из <tex>A</tex>.
 
 
}}
 
}}
 
{{Теорема
 
|id=t2
 
|statement=Для каждой грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> и <tex>\omega</tex> из <tex>N^{*}</tex> цепочка <tex>\omega</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>\omega</tex> имеет два разных левых порождения из <tex>P</tex>.
 
|proof=
 
<tex>\Longrightarrow</tex>
 
 
:Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве [[#t1|теоремы]]. В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.
 
 
<tex> \Longleftarrow </tex>
 
 
:Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной. По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора.
 
}}
 
 
==Однозначные грамматики==
 
 
{{Определение
 
|definition=
 
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
 
}}
 
 
 
{{Лемма
 
{{Лемма
 
|id=lemma-
 
|id=lemma-
 
|statement=
 
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
+
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод.
 
|proof=
 
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
+
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова.
 
}}
 
}}
 
+
== Литература ==
{{Утверждение
+
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
|statement=Грамматика из примера не является однозначной.
 
|proof=Выше уже было построено дерево разбора для слова <tex>(()(()))()</tex>.
 
Построим еще одно дерево разбора для данного слова.
 
 
 
Например, оно будет выглядеть так:
 
 
 
[[Файл:BracketsSequenceParsingTree2.png]]
 
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
 
}}
 
 
 
{{Утверждение
 
|statement=Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
 
|proof=Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).
 
 
 
Рассмотрим грамматику:
 
:<tex>(</tex> и <tex>)</tex> {{---}} терминальные символы
 
:<tex>S</tex> {{---}} стартовый нетерминал
 
 
 
Правила:
 
#<tex>S\rightarrow (S)S</tex>
 
#<tex>S\rightarrow \varepsilon</tex>
 
 
 
Покажем, что эта грамматика однозначна.
 
Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.
 
 
 
'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.
 
 
 
'''Индукционный переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность, у которой <tex>\exists!</tex> дерево разбора.
 
 
 
:Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0 \ldots i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0 \ldots i]=(\alpha)\ </tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и  <tex>\beta=\omega[i+1 \ldots n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.
 
 
 
:Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).
 
 
 
:Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0 \ldots j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.
 
 
 
:Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0 \ldots j] \ </tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0 \ldots i]=(\alpha) \ </tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.
 
 
 
:Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0 \ldots i] \Rightarrow \omega \ </tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.
 
 
 
Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
 
}}
 
 
 
Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют '''существенно неоднозначными'''.
 
{{main|Существенно неоднозначные языки}}
 
 
 
==См. также==
 
* [[Формальные грамматики]]
 
* [[Иерархия Хомского формальных грамматик]]
 
* [[Замкнутость КС-языков относительно различных операций]]
 
* [[Существенно неоднозначные языки]]
 
 
 
== Источники информации ==
 
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
 
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)