15.1. Естественный язык: математическая модель
15.1.0. Замечания о контекстно-свободных грамматиках составляющих
Идея формальных грамматик в книге уже рассматривалась. В гл. 2 были введены структура составляющих и контекстно-свободные языки и было указано, что обычно стараются строить языки
программирования для ЭВМ так, чтобы они носили структуру составляющих и, если возможно, имели контекстно-свободные грамматики. Это соответствует истине даже в том случае, когда предлагается определить язык на основе демонстрации примера. Во всех алгоритмах грамматического вывода, обсуждавшихся в гл. 7, предполагалось, что язык контекстно-свободен.
Рис. 15.1. Пример грамматического анализа в НС-грамматике.
Покажем на примере, почему такие языки удобны для специалиста по вычислительным машинам. Пусть язык определен словарем
и грамматикой 
состоящей из продукций
Такой язык будет порождать цепочки вида 
Это язык непосредственно составляющих (НС-язык), поскольку можно построить дерево разбора для любой цепочки в языке, начиная с нее и заменяя в ней любую подцепочку, соответствующую правой части одной из продукций в 
на левую часть этой продукции, пока не получится символ 
На рис. 15.1 изображено дерево разбора простой цепочки из языка, определенного с помощью (7) и (8). Говорят, что проведен грамматический анализ цепочки, если для нее построено дерево разбора. Успешный грамматический анализ эквивалентен обнаружению того, что существует способ,
которым язык мог бы породить эту цепочку. Кроме того, существует прямой путь перевода дерева разбора в семантику операций ЭВМ. Это также видно из рис. 15.1. Этот рисунок дает схему анализа в виде дерева, которое очень легко перевести в префиксную бесскобочную запись. Заключим в скобки цепочку, соответствующую каждому вхождению Е в цепочку, подлежащую разбору. Это можно сделать без труда. В нашем примере скобочной структурой будет
Эта информация позволяет применить хорошо известные механические процедуры для замены ее на бесскобочную запись
которую можно вычислить последовательностью вызовов и сложений в порядке справа налево, т. е.
Вызвать а
Вызвать 
Сложить два последних вызванных символа, сумму запомнить Вызвать с
Сложить с суммой
Точный механизм выполнения этих операций зависит, конечно, от используемой ЭВМ. Реальные языки программирования, разумеется, гораздо сложнее. Тем не менее основные принципы остаются теми же. Дополнительная сложность этих языков обусловлена практически полностью тем, что их грамматики гораздо шире.
Итак, языки программирования, основанные на контекстно-свободной модели непосредственно составляющих, действительно дают разумный язык для разговора об арифметических и алгебраических операциях. Люди могут освоить эти языки, и они легко переводятся в машинные команды. Поэтому для некоторых целей они чрезвычайно полезны. С другой стороны, легко показать, что эти языки не позволяют работать с определенными конструкциями естественного языка. Мы не будем пытаться подробно охарактеризовать эту задачу. Лучше проиллюстрируем ее, заметив, что в рамках грамматик непосредственно составляющих нельзя обнаружить, что два предложения
эквивалентны, и это объясняется тем, что они, несомненно, породили бы два разных грамматических анализа. Ясно, однако, что распознавание таких случаев тождества — важный аспект понимания.
