Грамматика

Материал из WikiGrapp
Перейти к:навигация, поиск

Грамматика(Grammar) — один из основных методов описания формального языка. Имеет вид четверки G = (N, \Sigma,  P, S), в которой

(1) N — алфавит нетерминальных символов, или нетерминалов (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями);

(2) \Sigma — не пересекающийся с N алфавит терминальных символов, или терминалов;

(3) P — конечное множество так называемых правил (или продукций) — слов вида \alpha\longrightarrow\beta , где \alpha\in(N\cup\Sigma)^*N(N\cup\Sigma)^*заменяемая цепочка, \beta\in(N\cup\Sigma)^*заменяющая цепочка и "\longrightarrow" — символ, не принадлежащий ни N, ни \Sigma;

(4) S — выделенный символ из N, называемый начальным (или исходным) символом.

Важным преимуществом данного метода описания формального языка является то, что в отличие от распознавателя грамматика придает цепочкам (предложениям) языка полезную структуру, которая может использоваться, например, для придания смысла предложениям языка. Из терминальных символов образуются цепочки определяемого языка L, а нетерминальные символы используются при порождении языка L как вспомогательные. Сердцевину грамматики составляет конечное множество правил, которые могут использоваться в процессе получения цепочек языка, или, как говорят, их вывода. Если установлено, что некоторая цепочка \gamma порождается грамматикой (или, как говорят, выводится в ней), то также выводимой в данной грамматике является любая цепочка, которая получается из \gamma заменой в ней подцепочки, являющейся заменяемой цепочкой некоторого правила грамматики, на заменяющую цепочку соответствующего правила.

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

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

См. также


Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986..