Грамматика: различия между версиями
KEV (обсуждение | вклад) (Создана новая страница размером '''Грамматика'''(''Grammar'') - один из основных методов описания [[формальны...) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
(1) <math>N</math> --- алфавит [[нетерминальный символ|''нетерминальных символов'']], или [[нетерминал|''нетерминалов'']] (иногда называемых вспомогательными символами, синтаксическими переменными или [[понятие|''понятиями'']]); | (1) <math>N</math> --- алфавит [[нетерминальный символ|''нетерминальных символов'']], или [[нетерминал|''нетерминалов'']] (иногда называемых вспомогательными символами, синтаксическими переменными или [[понятие|''понятиями'']]); | ||
(2) <math>\Sigma</math> --- не пересекающийся с <math>N</math> алфавит [[терминальный символ|''терминальных символов'']], или [[терминал|''терминалов'']]; | (2) <math>\Sigma</math> --- не пересекающийся с <math>N</math> алфавит [[терминальный символ|''терминальных символов'']], или [[терминал|''терминалов'']]; | ||
(3) <math>P</math>~--- конечное множество так называемых [[правило|''правил'']] (или [[продукция|''продукций'']])~--- слов вида <math>\alpha\longrightarrow\beta ,</math> где | (3) <math>P</math>~--- конечное множество так называемых [[правило|''правил'']] (или [[продукция|''продукций'']])~--- слов вида <math>\alpha\longrightarrow\beta ,</math> где | ||
<math>\alpha\in(N\cup\Sigma)^*N(N\cup\Sigma)^*</math> --- ''заменяемая'' [[цепочка|''цепочка'']], | <math>\alpha\in(N\cup\Sigma)^*N(N\cup\Sigma)^*</math> --- ''заменяемая'' [[цепочка|''цепочка'']], | ||
<math>\beta\in(N\cup\Sigma)^*</math> --- ''заменяющая'' цепочка и <math> | <math>\beta\in(N\cup\Sigma)^*</math> --- ''заменяющая'' цепочка и <math>\longrightarrow</math> --- символ, не принадлежащий ни <math>N</math>, ни <math>\Sigma</math>; | ||
(4) <math>S</math> --- выделенный символ из <math>N</math>, называемый начальным (или 'исходным'') символом. | (4) <math>S</math> --- выделенный символ из <math>N</math>, называемый начальным (или 'исходным'') символом. | ||
Версия от 12:33, 28 мая 2009
Грамматика(Grammar) - один из основных методов описания формального языка. Имеет вид четверки [math]\displaystyle{ G = (N, \Sigma, }[/math] [math]\displaystyle{ P, S) }[/math], в которой
(1) [math]\displaystyle{ N }[/math] --- алфавит нетерминальных символов, или нетерминалов (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями);
(2) [math]\displaystyle{ \Sigma }[/math] --- не пересекающийся с [math]\displaystyle{ N }[/math] алфавит терминальных символов, или терминалов;
(3) [math]\displaystyle{ P }[/math]~--- конечное множество так называемых правил (или продукций)~--- слов вида [math]\displaystyle{ \alpha\longrightarrow\beta , }[/math] где [math]\displaystyle{ \alpha\in(N\cup\Sigma)^*N(N\cup\Sigma)^* }[/math] --- заменяемая цепочка, [math]\displaystyle{ \beta\in(N\cup\Sigma)^* }[/math] --- заменяющая цепочка и [math]\displaystyle{ \longrightarrow }[/math] --- символ, не принадлежащий ни [math]\displaystyle{ N }[/math], ни [math]\displaystyle{ \Sigma }[/math];
(4) [math]\displaystyle{ S }[/math] --- выделенный символ из [math]\displaystyle{ N }[/math], называемый начальным (или 'исходным) символом.
Важным преимуществом данного метода описания формального языка является то, что в отличие от распознавателя грамматика придает цепочкам ("предложениям") языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка. Из терминальных символов образуются цепочки определяемого языка [math]\displaystyle{ L }[/math], а нетерминальные символы используются при порождении языка [math]\displaystyle{ L }[/math] как вспомогательные. Сердцевину грамматики составляет конечное множество правил, которые могут использоваться в процессе получения цепочек языка, или, как говорят, их вывода. Если установлено, что некоторая цепочка [math]\displaystyle{ \gamma }[/math] порождается грамматикой (или, как говорят, выводится в ней), то также выводимой в данной грамматике является любая цепочка, которая получается из [math]\displaystyle{ \gamma }[/math] заменой в ней подцепочки, являющейся заменяемой цепочкой некоторого правила грамматики, на заменяющую цепочку соответствующего правила.
Язык, определяемый (порождаемый) грамматикой [math]\displaystyle{ G }[/math] (обозначается [math]\displaystyle{ L(G) }[/math]), --- это множество цепочек, которые состоят только из терминальных символов и выводятся, начиная с цепочки, состоящей из одного начального символа.
Другие названия --- Грамматика без ограничений, Грамматика составляющих, Грамматика с фразовой структурой, Грамматика типа 0, Порождающая грамматика.
Литература
[Ахо-Ульман],
[Касьянов/95],
[Касьянов-Поттосин]