Порождающие грамматики Хомского служат для точного формального задания языков. На практике часто ставится обратная задача: построить грамматику языка на основе некоторого числа примеров "правильных" цепочек языка и интуитивных представлений о правильности некоторых языковых конструкций. Разработка грамматики – это неформальный акт, которому можно научиться на примерах. Рассмотрим задачу построения грамматик для всех языков, перечисленных в примере 2.1. Пример 2.1.1. V1={a,b}; L1={aabb, baa, aaba}. Порождающие грамматики разработаны для задания бесконечных языков. Для простейшего частного случая конечных языков построение порождающих грамматик должно быть весьма простым. Действительно, для этого языка грамматика G1 имеет вид: G1: S→ aabb S→ baa S→ aaba Применение любого из трех правил при порождении из начального символа сразу завершит вывод с получением соответствующей цепочки языка. Пример 2.1.2. V2={a,b}; L2={anbn | n≥0}. Любая цепочка языка L 2, порождаемая искомой грамматикой, имеет структуру: АВ, где А – цепочки, состоящие только из а, а В – цепочка из b, причем количества символов в группах А и В равны. При порождении удобно одновременно порождать и а, и b, тогда это требование будет выполнено автоматически. Если одним из правил грамматики будет S → aSb, то многократным его применением можно построить: S⇒ aSb ⇒ aaSbb ⇒... ⇒ aa...aSb... bb. Все промежуточные цепочки вывода не являются цепочками языка, порождаемого G 2, поскольку эти цепочки не терминальные. Для получения терминальных цепочек требуемого вида достаточно в этих промежуточных цепочках убрать S, что может быть сделано при наличии в грамматике правила S → ε. Окончательно: G2: S→ aSb S→ ε Вывод a3b3: S⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb. Пример 2.1.3. V3={a,b,c}; L3={anbcm| n, m>0}. Структура любой цепочки языка L3 – АВС (А – цепочки из а, С – цепочки из с), и поскольку количества символов а в начале цепочек языка и с в конце цепочек могут не совпадать, отдельные части структуры цепочек можно генерировать независимо. Искомая грамматика: G3: S→ ABC A→ aA A→ a B→b C→ Cc C→ c Введем небольшое упрощение при записи правил грамматики. Все альтернативные замены одного и того же нетерминала (т.е. различные правые части правил с одинаковой левой частью) будем записывать в одну строку через знак альтернативы '|': G3: S→ ABC A→ aA | a B→b C→ Cc | c
Пример вывода в грамматике G3: S ⇒ ABC ⇒ aABC ⇒ aaABC ⇒ aaaBC ⇒ aaabC ⇒ aaabCc ⇒ aaabcc. Здесь на каждом шаге вывода в промежуточной цепочке заменялась самая левая подцепочка, которую можно было заменить в соответствии с правилами грамматики. Такой вывод называется левым. Ту же цепочку языка можно породить в этой грамматике и с помощью другого вывода – например, заменяя самый правый нетерминал в промежуточной цепочке вывода. Такой вывод называется правым: S ⇒ ABC ⇒ ABCс ⇒ ABcс ⇒ Abcс ⇒ aAbcc ⇒ aaAbcc⇒ aaabcc. Наконец, можно породить ту же цепочку ни левым, ни правым выводом, произвольно выбирая заменяемую подстроку: S⇒ ABC ⇒ ABCс ⇒ aABСс ⇒ aAbСс ⇒ aaAbСс ⇒ aaAbcс ⇒ aaabcc. Построенные нами грамматики G 1-G3 имеют особый вид правил "A→ α " – цепочка левой части, определяющая заменяемую подцепочку, содержит только один единственный символ нетерминального словаря. Такие грамматики – по сути, частный подкласс грамматик Хомского – являются наиболее интересными в теории трансляции, они называются "контекстно-свободными (КС) грамматиками". Для таких грамматик вывод цепочки порождаемого языка можно более удобно представить графически деревом, показывая, как нетерминалы, стоящие в узлах дерева, заменяются цепочками правых частей соответствующих продукций. Для всех трех различных выводов цепочки aaabcc, приведенных выше, дерево вывода в грамматике G3 одно и то же (рис. 2.2). Для КС-грамматик вывод удобно характеризовать именно деревом, а не линейной последовательностью шагов подстановок. Деревья вывода цепочек языка, порождаемого КС-грамматикой, имеют следующую структуру. Корень дерева помечен начальным символом грамматики, в каждом внутреннем узле дерева стоит нетерминал, листья помечены терминальными символами так, что читаемые слева направо, они представляют терминальную цепочку, выведенную из начального символа. Из любого узла дерева, помеченного нетерминальным символом Q, идут вниз ветви к узлам, помеченным Х1Х2... Хк, если Q→Х1Х2... Хк – это одно из правил грамматики.
Таким образом, вывод любой цепочки языка, порождаемой КС-грамматикой из ее начального символа, может быть экономно представлен деревом вывода. Очевидно, что как правый, так и левый выводы цепочки языка единственные в КС-грамматике, они однозначно восстанавливаются по дереву вывода (так же, как дерево вывода однозначно строится по любому выводу цепочки). В связи с этим правый и левый выводы называются каноническими выводами цепочки в КС-грамматике. Можно предположить, что именно дерево вывода цепочки языка в КС-грамматике и представляет ту искомую структуру цепочки,, с которой мы связывали надежды на построение алгоритмов трансляции языков. Именно это предположение и сделал Н.Хомский. Согласно предположению Хомского, нетерминалы грамматики представляют собой языковые конструкции (классы), играющие определенные роли в предложениях языка, а дерево вывода связывает эти роли и их смысловые нагрузки, что позволяет построить, "вычислить" смыслы более общих конструкций из смыслов их составляющих конструкций и, в конце концов, смысл всего предложения. Все эти понятия и идеи будут объектом нашего дальнейшего исследования и формализации.
