Понятие грамматики

Одним из методов описания формального языка таким образом, чтобы это описание было конечным, является использование порождающей системы, называемой грамматикой. Одно из преимуществ определения языка с помощью грамматики состоит в том, что операции, производимые в ходе синтаксического анализа (т.е. анализа внутренней структуры текста на соответствие правилам языка, на котором написан этот текст), можно сделать проще, если воспользоваться структурой, которую грамматика приписывает цепочкам языка.

Грамматикой называется четверка G=<N, T, P, S>, где

· N – конечное множество нетерминальных символов (их также называют вспомогательными символами, синтаксическими переменными или, коротко, нетерминалами);

· T – не пересекающееся с N конечное множество терминальных символов (терминалов);

· P – конечное подмножество декартова произведения , где пары , в которых a содержит хотя бы 1 нетерминальный символ, называются правилами подстановки (или просто правилами, или продукцией) и записываются в виде ;

· S – выделенный символ из N, называемый начальным (или исходным) символом (start symbol).