Большинство формальных систем представления грамматических правил основано на идее структуры словосочетаний, согласно которой строки состоят из подстрок, называемых словосочетаниями, которые относятся к различным категориям. Например, словосочетания "the wumpus", "the king" и "the agent in the comer" представляют собой примеры категории именного словосочетания, или сокращенно NP (Noun Phrase). Есть две причины, по которым целесообразно классифицировать словосочетания именно таким образом. Во-первых, словосочетания обычно соответствуют естественным семантическим элементам, из которых можно конструировать смысл фрагмента; например, именные словосочетания указывают на объекты в рассматриваемом мире. Во-вторых, классификация словосочетаний позволяет описывать строки, допустимые в данном языке. В частности, можно утверждать, что любое из именных словосочетаний может комбинироваться с глагольным словосочетанием (или сокращенно VP— Verb Phrase), таким как "is dead" (мертв), для формирования словосочетания, относящегося к категории предложения (или сокращенно S— Sentence). Без таких вспомогательных понятий, как именное словосочетание и глагольное словосочетание, было бы трудно объяснить, почему строка, состоящая из слов "the wumpus is dead", представляет собой предложение, a "wumpus the dead is" — нет.

Такие имена категорий, как NP, VP и S, называются нетерминальными символами. В формальных грамматиках нетерминальные символы определяются с использованием правил подстановки. Авторы приняли в качестве системы обозначений для правил подстановки форму Бэкуса-Наура (Backus-Naur Form — BNF), которая описана в приложении Б. В этой системе обозначений смысл приведенного ниже правила состоит в том, что конструкция S может состоять из любой конструкции NP, за которой следует любая конструкция VP:

Порождающая способность

Грамматические формальные системы можно классифицировать по их порождающей способности — по тому множеству языков, которое они позволяют представить. Ноам Хомский [251] описал четыре класса грамматических формальных систем, которые различаются только по форме правил подстановки. Эти классы можно расположить в виде иерархии, в которой каждый класс может использоваться для описания всех языков, которые могут быть описаны с помощью менее мощного класса, а также некоторых дополнительных языков. Ниже приведен список классов этой иерархии, в котором вначале приведен наиболее мощный класс.