Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Можно представлять себе работу МП-машины еще и следующим образом: при создании рабочей ячейки перед обозреваемым в данный момент входным символом ставится помеченная левая скобка — меткой служит соответствующий рабочий символ, — а при уничтожении рабочей ячейки после обозреваемого входного символа ставится правая скобка. Таким способом мы получим скобочное изображение соответствующей размеченной системы составляющих — правда, с той особенностью, что одна составляющая может оказаться ограниченной несколькими парами скобок, и внутри некоторых пар скобок может не содержаться входных символов.
Лингвистически МП-машины интерпретируются как «предсказуемостные процедуры синтаксического анализа», или «предсказуемостные анализаторы». В таком анализаторе предложение («содержимое входной ленты») просматривается слева направо, и при просмотре слова (входного символа) может вырабатываться предположение («предсказание») о его синтаксической роли (это соответствует созданию рабочей ячейки) или проверяться его совместимость с последним из уже выработанных, но еще не проверенных предположений (соответствует уничтожению рабочей ячейки). Результатом работы анализатора является размеченная система составляющих (отвечающая дереву вычисления). Подробнее см. [Гладкий — Мельчук 1969, стр. 136—148.]
Отметим две особенности деревьев вычисления, отличающие их от деревьев вывода.
1) Между полными вычислениями нормальной МП-машины и их деревьями имеется очевидное взаимно однозначное соответствие.
2) В то время как для всякой Б-грамматики Г существует постоянная d такая, что ширина дерева вывода в Г никогда не превосходит d, для деревьев вычислений в МП-машине такой постоянной может не быть (упражнение 4.24).
142 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
Впрочем, для любой МП-машины можно построить эквивалентную, обладающую такой постоянной; ее даже можно сделать равной двум. Это непосредственно вытекает из доказываемых ниже лемм 4.13 и 4.14.
Докажем теперь следующую основную теорему.
Теорема 4.9. а)Для всякой ОЪ-грамматики можно построить эквивалентную ей МП-машину. б) Для всякой МП-машины можно построить эквивалентную ей ОЪ-грамматику.
Для доказательства введем некоторые понятия и обозначения.
Назовем простейшей окрестностной Д-грамматикой с порядком*) (ПО-г р а м м а т и-к о й) упорядоченную четверку G = (V,W,I,S), где V и W — непересекающиеся конечные множества, / — элемент W и S — конечное множество «окрестностей» — /V деревьев с пометками из V {] W, состоящее из «одноэтажных» деревьев вида
(отношение изображается здесь и далее отношением «левее») и «единичных» деревьев вида »а; при этом метки из V могут быть только у висячих узлов. Крайний слева висячий узел неединичного дерева может быть помечен еще* дополнительным символом [_, а крайний справа — символом J. (Если висячий узел единственный, то он может нести обе дополнительные метки.)
ПО-грамматика будет называться ограниченной, если в каждой ее неодноэлементной окрестности крайние слева и справа висячие узлы несут соответственно метки L и _)•
Будем обозначать через L\ (G) множество всевозможных Pi-деревьев Т, удовлетворяющих следующим условиям: 1) Если s — некоторый невисячий узел Т, s 1 ... sp — все подчиненные ему узлы и р, рь ...
..., рР — метки при s, Si, , sp соответственно, то найдутся такие ii, ..., »'*, 1 = i'i ^ k ^ ^ ih = р, что
.А
OCj осг Oth
/
*) Д — от 6ev6pov — «дерево».
МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
143
каждое дерево
принадлежит S, и при этом крайний слева висячий узел первого из этих деревьев, рассматриваемого как окрестность из S, несет добавочную метку |_ , а крайний справа висячий узел последнего — метку J, и никакие другие узлы деревьев Tj меток (_ и J не несут. 2) Если s — висячий узел Т с меткой а, то дерево *а принадлежитS. 3) Корень Т несет метку /.
Будем полагать далее L(G) = {Пруг^Г) | Ге?д (G)}.
Будем, наконец, обозначать множество всех деревьев полных выводов в ОБ-грамматике Г, соответственно всех упрощенных деревьев полных вычислений нормальной МП-машины М, через (Г),соответственно LA (М).
Теорема 4.9 непосредственно вытекает из следующих трех лемм.
Лемма 4.12. а) Для всякой ОЪ-грамматики Г можно построить такую ограниченную ПО-грамматику G, что La(G) = ?д(Г). б) Для всякой ограниченной ПО-грамматики G можно построить такую ОЪ-грамматику Г, что 1Л (Г) = La (G).
Лемма 4.13. а) Для всякой нормальной МП-машины М можно построить такую ПО-грамматику G, что L\(G) = La(M). б) Для всякой ПО-грамматики G можно построить такую нормальную МП -машину М, что L&(M)=L&(G).
Лемма 4.14. 'Для всякой ПО-грамматики G можно построить такую ограниченную ПО-грамматику G', что L(G')=L(G).
Д ок а з а те л ьс тв о леммы 4.12. Для произвольной ОБ-грамматики Г = (К, W, /, R) положим G(r) = (V, W, /, S), где S состоит из всевозможных окрестностей вида
А
144 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
таких, что А -> ... afe е R, и • а таких, что а
или цеК. Ясно, что таким образом устанавливается взаимно однозначное и эффективное в обе стороны соответствие между ОБ-грамматиками и ограниченными ПО-грамматиками. Равенство ?д(0(Г)) = ?д(Г) очевидно.
