Грамматика типа 2 - это контекстно-свободная грамматика (КС-грамматика). Правила этой грамматики не зависят от контекста, т. е. в левой части каждого правила находится топью один нетерминальный символ, а в правой части цепочка терминальных и/или нетерминальных символов. Продукции этой грамматики имеют вид: A ::= βгде β V*. Каждый шаг вывода связан с заменой в цепочке одного нетерминального символа на цепочку терминальных и/или нетерминальных символов. Множество КС-языков при выполнении условий ω1 = ε, ω2 = ε и β ≠ ε является подмножеством HC-языков. КС-грамматики наиболее эффективно описывают состав и структуру формального языка. Поэтому они нашли применение в большинстве языков программирования. Для унификации языков программирования были разработаны метаязыковые средства описания синтаксических конструкций. Особое место среди этих средств занимают формулы Бэкуса-Наура (БНФ). Основные правила и условные обозначения приведены в вопросе 31. Для КС-грамматик также удобен фиксированный способ вывода (лево- или правосторонний). Пример. Пусть дана грамматика G6 = ,где VT = {буква; цифра} VN = {А, В; J};Р ={р1: J ::= JAIJBIA;р2: А ::= буква;р3: В ::= цифра }. Какие цепочки терминальных символов формирует грамматика? Для удобства доказательства сохраним левосторонний вывод:J => А => буква,J => JA => АА => буква буква;J => JB => АВ => буква цифра;J => JA => JAA => ААА =>. . . => буква буква буква;J => JA => JBA => АВА =>. . . => буква цифра буква;J => JB => JAB => ААВ => . . . => буква буква цифра;J => JB => JBB => АВВ => . . . => буква цифра цифра и т. д. Грамматика G6 формирует следующие цепочки терминальных символов:L(G 6) = { буква { буква 1 цифра}}. Такова грамматика для формирования идентификаторов большинства языков программирования.