Разработка компиляторов
Определение грамматики
Грамматики представляют собой наиболее распространенный класс описаний языков. При описании грамматики необходимо начать с определения алфавита языка, который задается как набор допустимых терминальных символов. Кроме того, необходимо определить набор правил вывода вида , с помощью которых строятся все цепочки языка. В левой и правой части этих правил могут встречаться специальные нетерминальные символы; в процессе вывода нетерминальные символы заменяются с помощью соответствующих правил до полной замены на соотвествующие терминалы. Наконец, грамматика должна включать в себя начальный символ , или аксиому, с которой начинается получение любого предложения языка.
Для формального определения грамматики нам потребуются следующие обозначения. Если есть алфавит, то обозначает множество всех строк (включая пустую строку ), составленных из символов, входящих в . Аналогично, определяет множество всех строк, составленных из символов, входящих в , но без пустой строки. Нетерминалы мы будем обозначать прописными буквами, а терминалы - строчными.
Итак, грамматика определяется как следующая четверка: , где
- - конечное множество терминальных символов;
- - не пересекающееся с конечное множество нетерминальных символов;
- - конечный набор порождающих правил вида (, ), где ,
- - начальный символ, где
Например, грамматикой, порождающей язык , является , где . Другой пример: рассмотрим грамматику, порождающую язык . Такая грамматика имеет вид , где набор правил определяется следующим образом:
.
Определим также понятие выводимости: если - цепочка, состоящая из символов языка , а - правило языка , то непосредственно выводима из в G). Рефлексивное и транзитивное замыкание этого отношения обозначим как
(цепочка выводима из ; имя грамматики можно опускать для краткости).
