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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.  
+
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.  
 
}}
 
}}
  
−
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности.  
+
'''Пример:'''
 +
 
 +
Грамматика, выводящая все правильные скобочные последовательности.  
  
 
Терминальные символы {{---}} <tex>"("</tex> и <tex>")"</tex>;  
 
Терминальные символы {{---}} <tex>"("</tex> и <tex>")"</tex>;  
Строка 29: Строка 31:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Левосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
+
'''Левосторонний вывод слова''' (англ. ''leftmost derivation'')<tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Правосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
+
'''Правосторонним выводом слова''' (англ. '' rightmost derivation'') <tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
 
}}
 
}}
 
<br>
 
<br>
−
Рассмотрим левосторонний вывод нашей скобочной последовательности:<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>
 
<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'') называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей.
+
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня.
+
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
 
}}
 
}}
−
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.<br>
+
<br>
−
Рассмотрим, как будет выглядеть дерево разбора нашей скобочной последовательности.<br>
+
Построим дерево разбора скобочной последовательности из примера.<br>
−
[[Файл:derivation_tree.png]]
+
[[Файл:ParsingTree.png|350px]]
 +
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 59: Строка 62:
 
|id=lemma-
 
|id=lemma-
 
|statement=
 
|statement=
−
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод <tex>\omega</tex>.
+
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
 
|proof=
 
|proof=
−
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова.
+
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Формальные грамматики]]
 +
* [[Иерархия Хомского формальных грамматик]]
 +
* [[Замкнутость КС-языков относительно различных операций]]
  
 
== Литература ==
 
== Литература ==
−
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
+
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
 +
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]

Версия 02:16, 25 ноября 2014

Определение:
Контекстно-свободной грамматикой (англ. сontext-free grammar) называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.


Определение:
Контекстно-свободный язык (англ. context-free language) — язык, задаваемый контекстно-свободной грамматикой.


Определение:
Выводом слова (англ. derivation of a word) [math]\alpha[/math] называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово [math]\alpha[/math].


Пример:

Грамматика, выводящая все правильные скобочные последовательности.

Терминальные символы — [math]"("[/math] и [math]")"[/math];

[math]S[/math] — стартовый нетерминал;

Правила:
[math]S\rightarrow (S)S[/math]
[math]S\rightarrow S(S)[/math]
[math]S\rightarrow \varepsilon[/math]
Выведем слово [math]"(()(()))()"[/math]:
[math]\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(()(()))()[/math]


Определение:
Левосторонний вывод слова (англ. leftmost derivation)[math]\alpha[/math] — вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.


Определение:
Правосторонним выводом слова (англ. rightmost derivation) [math]\alpha[/math] — вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.


Рассмотрим левосторонний вывод скобочной последовательности из примера:
[math]\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(()(()))()[/math]


Определение:
Деревом разбора грамматики (англ. parse tree) называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.


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


Построим дерево разбора скобочной последовательности из примера.
ParsingTree.png


Определение:
Грамматика называется однозначной (англ. unambiguous grammar), если у каждого слова имеется не более одного дерева разбора в этой грамматике.


Лемма:
Пусть [math]\Gamma[/math] — однозначная грамматика. Тогда [math]\forall \omega \in \mathbb{L}(\Gamma)[/math] существует ровно один левосторонний (правосторонний) вывод.
Доказательство:
[math]\triangleright[/math]
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
[math]\triangleleft[/math]

См. также

Литература

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора&oldid=41088»