Формальная грамматика: различия между версиями
Содержимое удалено Содержимое добавлено
+ {{Википедия}} |
Нет описания правки |
||
Строка 2:
{{Википедия}}
'''Формальная грамматика''' или просто '''грамматика''' в теории [[w:формальный язык|формальных языков]]
выделения некоторого подмножества из множества всех слов некоторого конечного
[[w:алфавит|алфавит]]a. Различают ''порождающие'' и ''распознающие'' (или
''аналитические'') грамматики
построить любое слово языка, а вторые позволяют по данному слову определить,
входит оно в язык или нет.
Строка 20:
числа состоят из цифр и могут объединяться с помощью знаков арифметических
действий в формулы (например, формулой будет цепочка <tt>2+3</tt>). Формулы
можно заключать в скобки, а также складывать, вычитать, умножать и делать
есть объединять друг с другом (и с числами) в более сложные формулы. Например,
<tt>(2+3)*(5+7)</tt>
можно символически записать следующим образом: <tt>ФОРМУЛА ЗНАК ФОРМУЛА</tt>.
Заметим, что вместо слов <tt>ФОРМУЛА</tt> можно подставить любую корректную
формулу, а вместо слова <tt>ЗНАК</tt>
и эта строка останется правильной формулой.
Идея теории порождающих формальных грамматик, разработанной [[w:Хомский, Аврам Ноам|Н.Хомским]], состоит в том, чтобы описывать язык через правила
подстановок, которые позволяют строить слова языка из
с помощью других
указывая, какие цепочки
простых можно записать следующим образом (такая запись называется ''правилом
вывода''
: 1. <tt>ФОРМУЛА <math>\Rightarrow\!\,</math> ФОРМУЛА ЗНАК ФОРМУЛА</tt>
Правило нужно читать так: «вместо слова <tt>ФОРМУЛА</tt> можно подставить
Строка 41:
<tt>ЗНАК</tt> можно подставлять один из четырех символов алфавита <math>\Sigma</math>:
(+,-,*./). Это можно записать с помощью следующих четырех правил.
: 2. <tt>ЗНАК <math>\Rightarrow\!\,</math> +</tt>
: 3. <tt>ЗНАК <math>\Rightarrow\!\,</math> -</tt>
: 4. <tt>ЗНАК <math>\Rightarrow\!\,</math> *</tt>
: 5. <tt>ЗНАК <math>\Rightarrow\!\,</math> /</tt>
Такая запись обычно сокращается до следующей (символ
<math>\Sigma</math>).
: 6. <tt>ЗНАК <math>\Rightarrow\!\,</math> + | - | * | / </tt>
«Кирпичики», обозначаемые нами большими буквами (например, <tt>ЗНАК</tt>), не являются
Строка 57:
других символов (как в случае с нетерминалом <tt>ФОРМУЛА</tt>), в то время
как терминал уже ни на что заменен быть не может и является своеобразным
«пунктном назначения» наших замен (от англ. terminal
пункт). Чтобы получить слово языка, мы должны все нетерминалы в конечном
итоге заменить на терминалы, а для этого в описание языка должны входить соответствующие
Строка 63:
В рассмотренном примере для определения нетерминала <tt>ЧИСЛО</tt> можно ввести такие правила
: 7. <tt>ЧИСЛО <math>\Rightarrow\!\,</math> ЦИФРА | ЧИСЛО ЦИФРА</tt>
: 8. <tt>ЦИФРА <math>\Rightarrow\!\,</math> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tt>
Иными словами, если к числу приписать справа еще одну цифру, то получится снова
число. Одно число
образом:
: 9. <tt>ФОРМУЛА <math>\Rightarrow\!\,</math> ЧИСЛО</tt>
Для полного описания грамматики нам требуется также разрешить заключать
формулы в скобки. Это делается с помощью правила
: 10. <tt>ФОРМУЛА <math>\Rightarrow\!\,</math> ( ФОРМУЛА )</tt>
Надо отметить, что нетерминал <tt>ФОРМУЛА</tt> в нашем случае является
выделенным
время как, например, нетерминал <tt>ЗНАК</tt> не задает слово языка. В таком
случае говорят, что нетерминал <tt>ФОРМУЛА</tt> является ''начальным''.
Строка 87:
== Пример вывода ==
Выведем формулу <tt>(12+5)</tt> с помощью перечисленных правил вывода:
Строка 99:
<math>{\Rightarrow_7\!\,}</math> (ЧИСЛО ЦИФРА + 5)
<math>{\Rightarrow_7\!\,}</math> (ЦИФРА ЦИФРА + 5)
<math>{\Rightarrow_8\!\,}</math> (12+5)</tt>
В приведенном примере с левой стороны от стрелки <math>\Rightarrow</math> в
Строка 107:
программированию. В отличие от порождающих грамматик, пример которой был
рассмотрен выше, распознающая грамматика задает алгоритм, позволяющий
определить, принадлежит ли данное слово языку. Например, любой [[w:регулярный язык|регулярный язык]] может быть распознан при помощи грамматики, задаваемой [[w:конечный автомат|конечным автоматом]], а любая контекстно-свободная грамматика
помощью [[w:автомат со стековой памятью|автомата со стековой памятью]]. Если
слово принадлежит языку, то такой автомат строит его вывод в явном виде, что
Строка 114:
== Типы грамматик ==
По [[w:иерархия Хомского|иерархии Хомского]], грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
* тип 0. [[w:неограниченные грамматики|неограниченные грамматики]]
* тип 1. [[w:контекстно-зависимые грамматики|контекстно-зависимые грамматики]]
* тип 2. [[w:контекстно-свободная грамматика|контекстно-свободные грамматики]]
* тип 3. [[w:регулярная грамматика|регулярные грамматики]]
== Применение ==
* [[w:контекстно-свободная грамматика|Контекстно-свободные грамматики]] широко применяются для определения грамматической структуры в [[w:грамматический анализ|грамматическом анализе]].
* [[w:регулярные грамматики|регулярные грамматики]] (в виде [[w:регулярные выражения|регулярных выражений]]) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в
==
* [[w:Грамматический анализ]]
| |||