Разработка компиляторов

       

Определение грамматики


Грамматики представляют собой наиболее распространенный класс описаний языков. При описании грамматики необходимо начать с определения алфавита языка, который задается как набор допустимых терминальных символов. Кроме того, необходимо определить набор правил вывода вида , с помощью которых строятся все цепочки языка. В левой и правой части этих правил могут встречаться специальные нетерминальные символы; в процессе вывода нетерминальные символы заменяются с помощью соответствующих правил до полной замены на соотвествующие терминалы. Наконец, грамматика должна включать в себя начальный символ , или аксиому, с которой начинается получение любого предложения языка.

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

Итак, грамматика определяется как следующая четверка: , где

  • - конечное множество терминальных символов;
  • - не пересекающееся с конечное множество нетерминальных символов;
  • - конечный набор порождающих правил вида (, ), где ,
  • - начальный символ, где

Например, грамматикой, порождающей язык , является , где . Другой пример: рассмотрим грамматику, порождающую язык . Такая грамматика имеет вид , где набор правил определяется следующим образом:

.

Определим также понятие выводимости: если - цепочка, состоящая из символов языка , а - правило языка , то непосредственно выводима из в G). Рефлексивное и транзитивное замыкание этого отношения обозначим как

(цепочка выводима из ; имя грамматики можно опускать для краткости).



Содержание раздела