Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора — различия между версиями
(→Лево- и правосторонний вывод слова) |
м (rollbackEdits.php mass rollback) |
||
(не показано 15 промежуточных версий 5 участников) | |||
Строка 3: | Строка 3: | ||
|id=csgrammar | |id=csgrammar | ||
|definition= | |definition= | ||
− | '''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. | + | '''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется [[Формальные грамматики|грамматика]], у которой в левых частях всех правил стоят только одиночные нетерминалы. |
}} | }} | ||
{{Определение | {{Определение | ||
+ | |id=lang | ||
|definition= | |definition= | ||
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой. | '''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой. | ||
Строка 19: | Строка 20: | ||
Рассмотрим грамматику, выводящую все правильные скобочные последовательности. | Рассмотрим грамматику, выводящую все правильные скобочные последовательности. | ||
− | :<tex> | + | :<tex>(</tex> и <tex>)</tex> {{---}} терминальные символы |
:<tex>S</tex> {{---}} стартовый нетерминал | :<tex>S</tex> {{---}} стартовый нетерминал | ||
Строка 27: | Строка 28: | ||
#<tex>S\rightarrow \varepsilon</tex> | #<tex>S\rightarrow \varepsilon</tex> | ||
− | Выведем слово <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>\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> | ||
Строка 57: | Строка 58: | ||
Построим дерево разбора скобочной последовательности из примера. | Построим дерево разбора скобочной последовательности из примера. | ||
− | [[Файл: | + | [[Файл:BracketsSequenceParsingTree1.png]] |
{{Теорема | {{Теорема | ||
Строка 65: | Строка 66: | ||
Используем индукцию по высоте дерева. | Используем индукцию по высоте дерева. | ||
− | '''База''' | + | '''База:''' Базисом является высота <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 \ | + | Заметим, что <tex>\omega = \omega_1\omega_2 \ldots \omega_k</tex>. |
Построим левое порождение цепочки <tex>\omega</tex> следующим образом: | Построим левое порождение цепочки <tex>\omega</tex> следующим образом: | ||
− | :Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\ | + | :Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\ldots X_k</tex>. |
− | :Затем для <tex>i = 1, 2, \ | + | :Затем для <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</tex>. | ||
− | Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\ | + | Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\ldots X_k</tex>. |
− | Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ | + | Для индукции предположим, что существует следующее порождение: <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\ | + | # Если <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\ | + | # Если <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\ | + | ::<tex>\omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k \Rightarrow_{lm}</tex> |
− | ::<tex>\omega_1\omega_2\ | + | ::<tex>\omega_1\omega_2\ldots\omega_{i–1}\alpha_1X_{i+1}\ldots X_k \Rightarrow_{lm}</tex> |
− | ::<tex>\omega_1\omega_2\ | + | ::<tex>\omega_1\omega_2\ldots\omega_{i–1}\alpha_2X_{i+1}\ldots X_k \Rightarrow_{lm}</tex> |
− | ::<tex>\ | + | ::<tex>\ldots</tex> |
− | ::<tex>\omega_1\omega_2\ | + | ::<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\ | + | Результатом является порождение <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>. | Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>\omega</tex> из <tex>A</tex>. | ||
}} | }} | ||
Строка 130: | Строка 130: | ||
{{Утверждение | {{Утверждение | ||
|statement=Грамматика из примера не является однозначной. | |statement=Грамматика из примера не является однозначной. | ||
− | |proof=Выше уже было построено дерево разбора для слова <tex> | + | |proof=Выше уже было построено дерево разбора для слова <tex>(()(()))()</tex>. |
Построим еще одно дерево разбора для данного слова. | Построим еще одно дерево разбора для данного слова. | ||
Например, оно будет выглядеть так: | Например, оно будет выглядеть так: | ||
− | [[Файл: | + | [[Файл:BracketsSequenceParsingTree2.png]] |
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной. | Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной. | ||
}} | }} | ||
Строка 144: | Строка 144: | ||
Рассмотрим грамматику: | Рассмотрим грамматику: | ||
− | :<tex> | + | :<tex>(</tex> и <tex>)</tex> {{---}} терминальные символы |
:<tex>S</tex> {{---}} стартовый нетерминал | :<tex>S</tex> {{---}} стартовый нетерминал | ||
Правила: | Правила: | ||
− | + | #<tex>S\rightarrow (S)S</tex> | |
− | + | #<tex>S\rightarrow \varepsilon</tex> | |
Покажем, что эта грамматика однозначна. | Покажем, что эта грамматика однозначна. | ||
Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</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 | + | :Найдем в слове <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>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора). |
− | Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0 | + | :Пусть из <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 | + | :Аналогично из <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 | + | :Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0 \ldots i] \Rightarrow \omega \ </tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная. |
Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики. | Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики. | ||
}} | }} | ||
− | Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют | + | Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют '''существенно неоднозначными'''. |
+ | {{main|Существенно неоднозначные языки}} | ||
==См. также== | ==См. также== |
Текущая версия на 19:39, 4 сентября 2022
Содержание
Основные определения
Определение: |
Контекстно-свободной грамматикой (англ. сontext-free grammar) называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. |
Определение: |
Контекстно-свободный язык (англ. context-free language) — язык, задаваемый контекстно-свободной грамматикой. |
Лево- и правосторонний вывод слова
Определение: |
Выводом слова (англ. derivation of a word) | называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово .
Пример:
Рассмотрим грамматику, выводящую все правильные скобочные последовательности.
- и — терминальные символы
- — стартовый нетерминал
Правила:
Выведем слово
:
Определение: |
Левосторонним выводом слова (англ. leftmost derivation) | называется такой вывод слова , в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
Определение: |
Правосторонним выводом слова (англ. rightmost derivation) | называется такой вывод слова , в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
Рассмотрим левосторонний вывод скобочной последовательности из примера:
Дерево разбора
Определение: |
Деревом разбора грамматики (англ. parse tree) называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила. |
Определение: |
Крона дерева разбора (англ. leaves of the parse tree) — множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево. |
Построим дерево разбора скобочной последовательности из примера.
Теорема: |
Пусть — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным , и кроной , где . Тогда в грамматике существует левое порождение |
Доказательство: |
Используем индукцию по высоте дерева. База: Базисом является высота , наименьшая из возможных для дерева разбора с терминальной кроной.
Индукционный переход: Существует корень с отметкой и сыновьями, отмеченными слева направо . Символы могут быть как терминалами, так и переменными.
Заметим, что . Построим левое порождение цепочки следующим образом:
Данное доказательство использует в действительности еще одну индукцию, на этот раз по . Для базиса мы уже знаем, что .Для индукции предположим, что существует следующее порождение:
Результатом является порождение Когда . , результат представляет собой левое порождение из . |
Теорема: |
Для каждой грамматики и из цепочка имеет два разных дерева разбора тогда и только тогда, когда имеет два разных левых порождения из . |
Доказательство: |
|
Однозначные грамматики
Определение: |
Грамматика называется однозначной (англ. unambiguous grammar), если у каждого слова имеется не более одного дерева разбора в этой грамматике. |
Лемма: |
Пусть — однозначная грамматика. Тогда существует ровно один левосторонний (правосторонний) вывод. |
Доказательство: |
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова. |
Утверждение: |
Грамматика из примера не является однозначной. |
Выше уже было построено дерево разбора для слова . Построим еще одно дерево разбора для данного слова.Например, оно будет выглядеть так: Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике эта грамматика не является однозначной. |
Утверждение: |
Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками. |
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше). Рассмотрим грамматику:
Правила: Покажем, что эта грамматика однозначна. Для этого, используя индукцию, докажем, что для любого слова , являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.База: Если , то оно выводится только по второму правилу для него существует единственное дерево разбора.Индукционный переход: Пусть и : и — правильная скобочная последовательность, у которой дерево разбора.
|
Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют существенно неоднозначными.
См. также
- Формальные грамматики
- Иерархия Хомского формальных грамматик
- Замкнутость КС-языков относительно различных операций
- Существенно неоднозначные языки
Источники информации
- Wikipedia — Context-free grammar
- Википедия — Контекстно-свободная грамматика
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)