Главная arrow книги arrow Копия Глава 22. Общение arrow Основные понятия языка
Основные понятия языка

•    Рекурсивно перечислимые грамматики имеют неограниченные правила; по обе стороны правил подстановки может находиться любое количество терминальных и нетерминальных символов, как в правиле. Эти грамматики по своей выразительной мощи эквивалентны машинам Тьюринга.

•    Контекстно-зависимые грамматики ограничены лишь тем, что в правой части правил должно находиться по меньшей мере столько же символов, сколько и в левой части. Определение "контекстно-зависимый" связано с тем фактом, что в правиле, подобномι, указано, что вместо символа S может быть выполнена подстановка символа X в контексте предшествующего символа А и следующего символа В. Контекстно-зависимые грамматики способны представлять такие языки, как (последовательность из n копий а, за которой следует такое же количество копий b, а затем с).

•    В контекстно-свободных грамматиках (или сокращенно CFG — Context-Free Grammar) левая часть каждого правила состоит из одного нетерминального символа. Таким образом, каждое правило обеспечивает подстановку вместо нетерминального символа правой части правила в любом контексте. Грамматики CFG широко применяются для описания естественных языков и представления в виде программ грамматик формальных языков, хотя теперь широко признано, что некоторые естественные языки включают конструкции, которые не являются контекстно-свободными [1242]. Контекстно-свободные грамматики позволяют представить язык

, но не

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

Грамматики, расположенные выше в этой иерархии, имеют большую выразительную мощь, но алгоритмы для работы с ними являются менее эффективными. Вплоть до середины 1980-х годов усилия лингвистов были в основном сосредоточены на контекстно-свободных и контекстно-зависимых языках. Но в дальнейшем стали шире применяться регулярные грамматики, что было вызвано необходимостью очень быстро обрабатывать мегабайты и гигабайты текста в оперативном режиме, даже за счет менее полного анализа. Как сказал Фернандо Перейра: "Чем старше я становлюсь, тем ниже спускаюсь по иерархии Хомского". Чтобы узнать, что он имел в виду, сравните его книгу, которая вышла в 1980 году [1208], с книгой, выпущенной в 2002 году [1069].