Аноним

Грамматика: различия между версиями

Материал из WikiGrapp

Грамматика (посмотреть исходный код)

Версия от 13:23, 15 декабря 2010

233 байта добавлено ,  15 декабря 2010
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Грамматика'''([[Grammar|''Grammar'']]) - один из основных методов описания [[формальный язык|''формального языка'']]. Имеет вид четверки <math>G = (N, \Sigma,</math> <math> P, S)</math>, в которой
'''Грамматика'''([[Grammar|''Grammar'']]) — один из основных методов описания [[формальный язык|''формального языка'']]. Имеет вид четверки <math>G = (N, \Sigma,</math> <math> P, S)</math>, в которой


(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>\longrightarrow</math> --- символ, не принадлежащий ни <math>N</math>, ни <math>\Sigma</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>, называемый ''начальным'' (или ''исходным'') символом.


Важным преимуществом данного метода описания [[формальный язык|''формального языка'']] является то, что в отличие от [[распознаватель|''распознавателя'']] грамматика придает цепочкам (''предложениям'') языка полезную структуру, которая может использоваться, например, для
Важным преимуществом данного метода описания [[формальный язык|''формального языка'']] является то, что в отличие от [[распознаватель|''распознавателя'']] грамматика придает цепочкам (''предложениям'') языка полезную структуру, которая может использоваться, например, для
Строка 16: Строка 16:
получается из <math>\gamma</math> заменой в ней подцепочки, являющейся заменяемой цепочкой некоторого правила грамматики, на заменяющую цепочку соответствующего правила.
получается из <math>\gamma</math> заменой в ней подцепочки, являющейся заменяемой цепочкой некоторого правила грамматики, на заменяющую цепочку соответствующего правила.


''Язык, определяемый (порождаемый) грамматикой <math>G</math>'' (обозначается <math>L(G)</math>), --- это множество цепочек, которые состоят только из терминальных символов и выводятся,
''Язык, определяемый (порождаемый) грамматикой <math>G</math>'' (обозначается <math>L(G)</math>), — это множество цепочек, которые состоят только из терминальных символов и выводятся,
начиная с цепочки, состоящей из одного начального символа.
начиная с цепочки, состоящей из одного начального символа.


Другие названия --- [[Грамматика без ограничений|''Грамматика без ограничений'']], [[Грамматика составляющих|''Грамматика составляющих'']], [[Грамматика с фразовой структурой|''Грамматика с фразовой структурой'']], [[Грамматика типа 0|''Грамматика типа 0'']], [[Порождающая грамматика|''Порождающая грамматика'']].
Другие названия — ''[[Грамматика без ограничений]], [[Грамматика составляющих]], [[Грамматика с фразовой структурой]], [[Грамматика типа 0]], [[Порождающая грамматика]].''


==См. также==
==См. также==
[[Автоматная грамматика]], [[Грамматика без е-правил]], [[Контекстно-свободная грамматика]], [[Контекстно-зависимая грамматика]], [[Праволинейная грамматика]], [[Регулярная грамматика]]  
* [[Автоматная грамматика]],
* [[Грамматика без е-правил]],
* [[Контекстно-свободная грамматика]],
* [[Контекстно-зависимая грамматика]],
* [[Праволинейная грамматика]],
* [[Регулярная грамматика]]  




==Литература==
==Литература==
[Ахо-Ульман],
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.


[Касьянов/95],
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений.  — Новосибирск: НГУ, 1995.
 
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.


[Касьянов-Поттосин]






[[Категория: Теория формальных языков]].
[[Категория: Теория формальных языков]].
Источник — http://pco.iis.nsk.su/grapp/index.php/Служебная:Сравнение_версий/5873