Грамматика: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показано 5 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
'''Грамматика'''([[Grammar|''Grammar'']]) | '''Грамматика'''([[Grammar|''Grammar'']]) — один из основных методов описания [[формальный язык|''формального языка'']]. Имеет вид четверки <math>G = (N, \Sigma,</math> <math> P, S)</math>, в которой | ||
(1) <math>N</math> | (1) <math>N</math> — алфавит [[нетерминальный символ|''нетерминальных символов'']], или [[нетерминал|''нетерминалов'']] (иногда называемых вспомогательными символами, синтаксическими переменными или [[понятие|''понятиями'']]); | ||
(2) <math>\Sigma</math> | (2) <math>\Sigma</math> — не пересекающийся с <math>N</math> алфавит [[терминальный символ|''терминальных символов'']], или [[терминал|''терминалов'']]; | ||
(3) <math>P</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>\beta\in(N\cup\Sigma)^*</math> — ''заменяющая'' цепочка и "<math>\longrightarrow</math>" — символ, не принадлежащий ни <math>N</math>, ни <math>\Sigma</math>; | ||
(4) <math>S</math> | (4) <math>S</math> — выделенный символ из <math>N</math>, называемый ''начальным'' (или ''исходным'') символом. | ||
Важным преимуществом данного метода описания [[формальный язык|''формального языка'']] является то, что в отличие от [[распознаватель|''распознавателя'']] грамматика придает цепочкам ( | Важным преимуществом данного метода описания [[формальный язык|''формального языка'']] является то, что в отличие от [[распознаватель|''распознавателя'']] грамматика придает цепочкам (''предложениям'') языка полезную структуру, которая может использоваться, например, для | ||
придания смысла предложениям языка. Из терминальных символов образуются цепочки определяемого языка <math>L</math>, а нетерминальные символы используются при порождении языка <math>L</math> как вспомогательные. Сердцевину грамматики составляет конечное множество правил, которые могут | придания смысла предложениям языка. Из терминальных символов образуются цепочки определяемого языка <math>L</math>, а нетерминальные символы используются при порождении языка <math>L</math> как вспомогательные. Сердцевину грамматики составляет конечное множество правил, которые могут | ||
использоваться в процессе получения цепочек языка, или, как говорят, их ''вывода''. Если установлено, что некоторая цепочка <math>\gamma</math> порождается грамматикой (или, как говорят, ''выводится'' в ней), то также выводимой в данной грамматике является любая цепочка, которая | использоваться в процессе получения цепочек языка, или, как говорят, их ''вывода''. Если установлено, что некоторая цепочка <math>\gamma</math> порождается грамматикой (или, как говорят, ''выводится'' в ней), то также выводимой в данной грамматике является любая цепочка, которая | ||
получается из <math>\gamma</math> заменой в ней подцепочки, являющейся заменяемой цепочкой некоторого правила грамматики, на заменяющую цепочку соответствующего правила. | получается из <math>\gamma</math> заменой в ней подцепочки, являющейся заменяемой цепочкой некоторого правила грамматики, на заменяющую цепочку соответствующего правила. | ||
''Язык, определяемый (порождаемый) грамматикой <math>G</math>'' (обозначается <math>L(G)</math>), | ''Язык, определяемый (порождаемый) грамматикой <math>G</math>'' (обозначается <math>L(G)</math>), — это множество цепочек, которые состоят только из терминальных символов и выводятся, | ||
начиная с цепочки, состоящей из одного начального символа. | начиная с цепочки, состоящей из одного начального символа. | ||
Другие названия | Другие названия — ''[[Грамматика без ограничений]], [[Грамматика составляющих]], [[Грамматика с фразовой структурой]], [[Грамматика типа 0]], [[Порождающая грамматика]].'' | ||
==См. также== | |||
* [[Автоматная грамматика]], | |||
* [[Грамматика без е-правил]], | |||
* [[Контекстно-свободная грамматика]], | |||
* [[Контекстно-зависимая грамматика]], | |||
* [[Праволинейная грамматика]], | |||
* [[Регулярная грамматика]] | |||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
[ | [[Категория: Теория формальных языков]]. | ||
Текущая версия от 13:25, 15 декабря 2010
Грамматика(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, Порождающая грамматика.
См. также
- Автоматная грамматика,
- Грамматика без е-правил,
- Контекстно-свободная грамматика,
- Контекстно-зависимая грамматика,
- Праволинейная грамматика,
- Регулярная грамматика
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986..