В таком случае выражение

MeHbme{hd {1),симв) в нашем алгоритме может быть заменено на

f(hd{I))<g{cuMe)

и т. д.

Флойд [11] предложил алгоритм исследования грамматики с целью выяснения, является ли она грамматикой с операторным предшествованием, алгоритмы построения матрицы отношений, а также вычисления f -я g, если это возможно. Он также доказал теоремы, обосновывающие эти алгоритмы.

Чтобы показать, что для грамматики с операторным предшествованием не всегда можно подобрать fug, рассмотрим грамматику

S-aX\Yd

X-bcb

Y-cda

для которой, в частности, справедливы следующие отношения

а<Ь с = Ь а> d c = d

Грамматика с операторным предшествованием может оказаться неопределенной. Процесс грамматического разбора только определяет дерево, но не идентифицирует вершины.

Хотя этот способ грамматического разбора очень быстр и весьма широко применяется в компиляторах, особенно для разбора арифметических выражений, множество грамматик, к которым он применим, все же слишком ограничено. Основная трудность состоит в том, что отношения между словами должны выполняться всегда, в любом контексте. Так в Алголе

else >:

потому что в описаниях массивов : разделяет арифметические выражения. Однако в то же время

else <:

потому что в условных операторах : указывает метку. Поэтому Алгол не является грамматикой с операторным предшествованием. Впрочем, контексты этих двух применений разделителя : совершенно различны, так что это противоречие является кажущимся. Разумеется, в процессе предварительного просмотра программы можно было бы заменить : в описаниях массивов на некий новый символ.

5.3. ГРАММАТИКИ С ПРЕДШЕСТВОВАНИЕМ

Один тип грамматик с предшествованием, выходящий за

!)амки операторных грамматик, применялся Виртом и Вебером 33]. В их методе отношения =, < и > определяются между парами элементов как слов, так и классов. При этом, если существует правило подстановки

I: = ПУСТО;

пЗ: симв: = следующий;

nl:if/ = ПУСТО V равно (hd{l), симв) V меньше {hd (I), симв) then /: = cons(cuMe,I) else if 6oAbme{hd{l),cuMe) then begin W: = hd{I);

n2:I: = tl{I); if/ = ПУСТО V мeньшe{hd(I),W) then go to nl else go to п2

else отказ; go to n3;

Информацию об отношениях между словами можно хранить в виде матрицы, но часто оказывается возможным определить для каждого слова два веса, fug, таким образом, чтобы

!{р) = ё{я) выполнялось при p = q f{p)<g{q) выполнялось при p<q f{p)>g(q) выполнялось при р> q

Для предыдущего примера мы можем выбрать

мы будем говорить, что /i = /2. Если существует правило подстановки

А - аВ/аР

и вывод

B-*aIi

или если существует правило подстановки

А аВСр

и выводы

В -> а/,

то будем говорить, что /, > /2.

Если же существует правило подстановки

Л^а/,Вр

и вывод

В->/2а

то будем говорить, что h < h. Если между каждой парой элементов выполняется не более чем одно из этих отношений и если никакие два правила подстановки не имеют одинаковых правых частей, то такая грамматика является грамматикой с предшествованием.

Предположим, что в частично сведенном предложении элемент /) непосредственно предшествует элементу /2. Они принадлежат одной и той же простой фразе тогда и только тогда, когда /1 -- h. Если h <. h, то h принадлежит какой-то простой фразе, не содержащей /j. А если /, > /2, то /1 принадлежит какой-то простой фразе, не содержащей /2. Как и для грамматик с операторным предшествованием, для рассматриваемых грамматик легко определять фразовую структуру предложений. Однако в этом случае удается построить полный разбор, так как правила подстановки оказываются единственными. Можно организовать матрицу отношений и использовать ее в алгоритме разбора аналогично тому, как это делается для грамматик с операторным предшествованием. Иногда удается построить и функции / и g, обеспечивающие представление отношений. Вирт и Вебер предлагают алгоритмы для выявления отношений.

Заметим, что обычно оказывается необходимым преобразовать грамматику. Например, в грамматике

5-745+ Т

Т->Р\ТХР

P-*ud\{S)

5.4. Матрицы переходов

мы имеем + = Г, так как S -> S + 7, и в то же время + < 7, так как S-vS-f-Ги Т -> Т X Р- Имеется также противоречие в том, что одновременно выполняются отношения ( =S и ( < S. Эта грамматика может быть преобразована путем добавления дополнительных классов

и

>т\и-{-т

>P\VXP

P-*ud\{S)

В результате получаем грамматику с предшествованием.

На примере этой модифицированной грамматики на следующей странице показан разбор слева направо с использованием данного метода; построение дерева анализа исключается из рассмотрения.

Рассмотренный способ оказывается вполне удовлетворительным, хотя он и требует использования специального метода отыскания классов, соответствующих той или иной подстановке.

5.4. МАТРИЦЫ ПЕРЕХОДОВ

Этот метод грамматического разбора, описанный в работе [31], весьма напоминает метод разбора для грамматик с операторным предшествованием. Разбор производится тоже снизу вверх. Используются два магазинных списка. В один из них заносятся операторы, такие, как -- и Х- В другой заносятся операнды. Предполагается, что операторы и операнды различимы между собой. Оператор с вершины магазинного списка и очередной оператор из предложения служат для выбора из матрицы программы для выполнения.

Такая программа обычно либо добавляет новый оператор к операторному магазинному списку, либо исключает операторы из операторного магазинного списка и операнды из списка операндов, формируя из них новый операнд, который добавляется к списку операндов.

Все это очень близко к методу операторного предшествования, причем два магазинных списка служат для того, чтобы не иметь дела с классами. Методы обработки грамматик с целью получения матрицы переходов на подпрограммы описаны в статье [9].

а + b X ( с + d ) >

Р + b X { с + d ) >

У + b X ( с + d ) >

Т + b X ( с + d ) >

и + b X ( с + d ) = < >

и + Р X ( с + d )

и + у X ( с + d ) < = < < >

и + у X ( Р + d ) =<-<<>

u+vxiv+d) < = << >

U+VX(T+d) U+yxiU+d)

=<=<<=<>

и + у X ( и + Р )

- < = << = <>

U+Vx(U+V)

= < = << = <>

U+Vx(U+T)

=<=<<-=>

и + V X ( и )

=<=<<>

и + у X i S ) и + V X Р и + V

= < и + т

и

ПРЕОБРАЗОВАНИЯ ГРАММАТИК

Нам уже известны различные причины, по которым может оказаться желательным преобразование заданной грамматики в другой эквивалентный вид. Например, может возникнуть необходимость исключить левую рекурсию, или привести грамматику в нормальную форму, или преобразовать ее в грамматику с предшествованием. Однако применение исходной грамматики, вероятно, определяется в терминах структуры разбора, порождаемой именно этой грамматикой, а не в терминах структуры разбора, порождаемой измененной грамматикой. Поэтому необходимы методы возвращения к разбору в рамках исходной грамматики. Описываемый ниже метод такого возвращения использовался в одной системе построения компиляторов [14].

Введем третий тип элементов и будем называть элементы этого типа действиями. Для обозначения действий будем употреблять жирный шрифт. Действия похожи на слова тем, что они являются терминальными и к ним неприменимы дальнейшие подстановки, но их следует интерпретировать несколько иначе. Предложение, порожденное грамматикой с действиями, будет содержать смесь слов и действий, однако грамматическому разбору будет подлежать предложение, состоящее только из слов. Во время процесса сопоставления при разборе действия исключаются из рассмотрения. Например, грамматика

T\S+T Ud\TXud

порождает разбор

г

а + b X а

хс sq

Поскольку различные действия отнесены в конец каждого правила подстановки, то при заданной последовательности слов и действий

агр + *г X esq

не представляет труда построить дерево грамматического разбора.

Предложение просматривается слева направо, и каждый раз, когда встречается действие, соответствующее правило подстановки применяется к элементам, находящимся слева.

Однако совершенно необязательно использовать в разных правилах подстановки разные действия или помещать действия в конец правил подстановки. Если вместо того, чтобы преобразовать некую грамматику, мы преобразуем ту же грамматику, но с действиями в конце правил подстановки, то получим новую грамматику, в которой те же действия будут занимать другие места. Например, приведенная выше грамматика может быть преобразована в грамматику

5->ГрГрХ X- + rq+7qX Т->идг \udrY Y-i-XudslXud &Y

Используя эту грамматику для разбора того же самого предложения, мы получаем

orp4-6rxcsq

т. е. совсем другую структуру разбора, но действия встречаются на тех же местах, что и прежде. Поэтому, оперируя действиями в преобразованной грамматике, мы можем восстановить исходное дерево грамматического разбора.

Заметим, что в этом случае мы преобразовали грамматику с левой рекурсией в грамматику без левой рекурсии.

В гл. 7 будет показано, что процесс компиляции часто может быть описан с помощью действий в некоторой грамматике, причем эти действия выполняются над стеком результатов. При этом не возникает необходимости строить дерево, а действия в преобразованной грамматике применяются непосредственно для компиляции.

6.1. ПРЕОБРАЗОВАНИЯ ДЛЯ ИСКЛЮЧЕНИЯ ЛЕВОЙ РЕКУРСИИ

Грейбах показал, что для любой заданной грамматики всегда найдется эквивалентная грамматика без левой рекурсии. В литературе описаны различные преобразования, обеспечивающие удаление левой рекурсии [14, 19, 26, 35]. Ниже излагается такое преобразование, опубликованное ранее в работе [14].

Будем обозначать пустую фразу через 0, а недопустимую фразу через е. Если в предложении встречается символ 0, он может быть исключен; если же встречается символ е, то предложение некорректно. Разумеется, можно установить соответствие между символами 0 и е, с одной стороны, и символами О и 1, с другой. Мы будем использовать символ вместо 0, если г = S, и вместо е, если г Ф s. Рассмотрим сначала очень простое рекурсивное слева описание

R соответствующей грамматике с действиями

S-TplSi-Tq T->udr\TXuds

соответствующий разбор имеет вид

определяющее предложения, которые начинаются с символа а и далее содержат любое количество символов Ь. Грамматика

аУ

0 \bY

определяет те же предложения. Здесь Y - вспомогательный класс, введенный при преобразовании. В общем случае производится аналогичное построение.

Предположим, что имеется п классов Ц и что все они образуют цикл левой рекурсии. Это означает, что для любых L,-, Lj существует вывод Ц -* La. Если i = j, то заведомо а ф 0, но при i ф j допускается а = 0. Будем пользоваться сокращенным обозначением

Li-* All LjBif

которое означает

L2 -* Л2 I 112 I 222 I

LnBn2

Ln- Ап\1хВ,п\ЦВ2п\

Собираем вместе все правила подстановки для Li и по мере необходимости определяем новые вспомогательные классы, чтобы привести правила подстановки в вид

Li-Ai\L,B,i

где Ai не может начинаться с какого-либо класса Lj и не существует вывода Ai -* Lja. Может потребоваться, чтобы правила подстановки для Л,- или Bji содержали 0 или е.

После этого эквивалентное множество подстановок для без рекурсивных слева классов задается так:

Li-AiXn

где Xrs - вспомогательные классы, число которых равно п^.

Во-первых, заметим, что любая фраза, выводимая из L, в первой грамматике, выводима из и во второй грамматике и наоборот. В самом деле, фразы, выводимые из Lj в первой грамматике, имеют вид

АрВрдВдг ... Bi (без повторения сокращенных обозначений)

и то же самое справедливо для второй грамматики. Более того, если все Bj,- и Ai различны между собой, то обе грамматики не

содержат двусмысленностей. Если же среди них есть повторения и при этом существуют d выводов некой фразы в одной грамматике, то существуют d различных способов ее вывода и в другой грамматике.

Во-вторых, не существуют выводы

Xif-Xij

так как такой вывод смог бы возникнуть, только если бы существовал вывод

BlpBpqBf. . .Вг1-* Q!)

Но это невозможно, так как при этом существовал бы вывод Li-* Li в первой грамматике. Вывод Li-* Li во второй грамматике повлек бы за собой аналогичный вывод в первой, что исключено.

В-третьих, вторая грамматика может содержать правила подстановки, содержащие е. Можно исключить эти правила подстановки, не оставив никаких классов, для которых были бы невозможны терминальные выводы). В первой грамматике существует вывод

Lt-*Lja

для каждой пары i, j. Поэтому для любых i, j найдется последовательность индексов р, q.....2, такая, что для строки

BipBpg ... Bi

существует терминальный вывод.

Поэтому для любого класса Xrs найдется вывод

а поскольку Xs -* 0, то для Х„ существует корректный терминальный вывод.

Следовательно, данные грамматики эквивалентны. Используя введенные действия, можно восстановить разбор в соотвег ствии с первой грамматикой, так как

Li-*Aipi\ L{Bjiq,t

преобразуется в

Lt-AjPiXji

Путем такого последовательного удаления рекурсивных слева правил можно изменять грамматику до тех пор, пока она ие освободится от левой рекурсии.

) Тр ecTi) выводы терминальных последовательностей. - Прим. перев.

6. Преобразования грамматик

6.2. ДРУГИЕ ПРЕОБРАЗОВАНИЯ

Оба метода разбора сверху вниз и снизу вверх, по-видимому, наиболее эффективны тогда, когда правила подстановки для каждого класса начинаются, по мере возможности, с различных и непересекающихся наборов слов. Очевидно, что в таком случае априорные критерии, оперирующие с набором возможных начальных слов для правил подстановки, будут отсекать больше правил подстановки. Предельным является описанный в гл. 5 случай, когда каждому классу соответствуют только свои индивидуальные слова, начинающие соответствующие правила подстановки. В этом случае методы разбора сверху вниз и снизу вверх сливаются в один метод и анализ производится исключительно быстро. Поэтому целесообразно рассмотреть преобразования, приводящие к такому результату.

Мы можем применять к правилам подстановки дистрибутивные преобразования совершенно аналогично дистрибутивным преобразованиям выражений, содержащих знаки + и X. Грамматика

эквивалентна грамматике а грамматика эквивалентна грамматике

YA\B

XAZ\BZ X-CD\CE

X-Y-

CY DIE

Последовательным применением таких преобразований к заданной грамматике обычно можно сократить совпадения начальных элементов в правилах подстановки, а нередко удается совсем исключить такие совпадения [14]. В самом деле, если для некоего класса имеются два правила подстановки, начинающиеся с одинаковых элементов

X->ABiB2 ... I ЛСА ... то мы можем ввести новый класс и записать X-AY

У->В,Вг ...С,С2 ...

Если же для некоего класса имеются два правила подстановки, в которых нет явного совпадения, но которые могут на-

6.2. Другие преобразования

чинаться с одного и того же слова, например Х- -ЛВ,В2 ... \CDiD2... A-PIQ C-P\R

PD1D2 ... I RDyD2...

то мы можем сначала записать

Х-->-РВф2 ... \QBiB2 .

а затем

Х->РУ QB,fi2 ... \RD1D2... Y->BiB2... \DiD2...

К сожалению, существуют два затруднения, которые препятствуют тому, чтобы этот метод всегда исключал такие совпадения. Первое состоит в необходимости использовать пустую фразу 0, а тем самым включать в рассмотрение слова, следующие за начальным классом. Имея исходную грамматику

С-*В \D

мы получаем из нее

Х-Z-У-

>AZ

01В

и возникает трудность в связи с правилом

Z-*0\B

так как за классом Z может следовать В.

Второе затруднение возникает из-за того, что процесс преобразования может оказаться бесконечным циклом. Рассмотрим грамматику

X-*B\LX Y-*C\LY

Сначала мы получаем из нее

A-*B\C\LX\LY

X-B\LX

Y-*C\LY

а затем

6. Преобразования грамматик

A-B\C\LZ Z-*X\Y X-B\LX Y->C\LY

Теперь мы находимся в таком же положении относительно классов Z, X и Y, в каком были первоначально относительно Л, J и У, и поэтому процесс никогда не закончится. В данном случае мы могли бы заметить аналогию и записать

Л-X-Y-

B\C\LA B\LX C\LY

Другой пример неудачного преобразования возникает при исходной грамматике

S->a\aSa

Для получения грамматик с операторным предшествованием или грамматик с предшествованием используются сравнительно простые преобразования. Обычно они сводятся к исключению нерекурсивных классов или к введению новых классов, как показано в гл. 5.

ИСПОЛЬЗОВАНИЕ ГРАММАТИЧЕСКОГО АНАЛИЗА ДЛЯ КОМПИЛЯЦИИ

В этой Книге речь идет 6 основном О грамматическом анализе предложений, а не о сопутствующей этому анализу последовательной компиляции. Последнему вопросу посвящен целый ряд статей [4, 6, 10, 20, 21, 28, 30, 31]. Можно дождаться завершения построения полного дерева грамматического анализа, а затем обрабатывать его. Другой возможный вариант состоит в том, чтобы выполнять действия компиляции непосредственно в процессе грамматического анализа. Краткое описание такого способа приводится ниже.

Рассмотрим некую грамматику с действиями в концах правил подстановки. В процессе разбора слева направо у нас формируется магазинный список. Рассматриваемые действия либо добавляют нечто к этому магазинному списку, либо извлекают из него некоторые элементы и помещают результат снова в магазинный список. Предположим сначала для простоты, что мы хотим преобразовывать выражения вида

a+ft+c+d

в такую форму'):

ВЫВ, а СЛ, b СЛ, с СЛ, d

Будем использовать грамматику

5->ыдр IS + mq

Предполагается, что интерпретация ид добавляет имя идентификатора к магазинному списку. Действие р выполняется после первого идентификатора следующим образом 2):

р означает х: = извлечь; поместить (сочленить (ВЫБ', х))

) ВЫБ - занесение содержимого ячейки памяти в сумматор; СЛ -прибавление к сумматору содержимого ячейки памяти. - Я/7иж перев.

2) Операция извлечь означает выборку из магазинного списка, а поместить - занесение в магазинный список; операция сочленить применяется к двум или более операндам и сцепляет эти операнды в одну строку. - Прим. перев.

Действие q выполняется, когда двум верхним элементам магазинного списка соответствуют S и ид:

q означает х : = извлечь; у: - извлечь;

поместить (сочленить (у, сочленить (СЛ, д;)))

Будем использовать эту грамматику в преобразованном виде:

S->udpX Х->0 l + MqX

Ниже перечисляются последовательные шаги:

А если бы мы захотели, чтобы из выражения

a+b+c+d

получалось

ВЫБ, d СЛ, с СЛ, b СЛ, а

то мы воспользовались бы грамматикой

S-*udp\ud-\-ST

в которой ид и р действуют так же, как в предыдущем примере. Действие же г над двумя верхними элементами магазинного списка, соответствующими классам ид и S, выполняется следующим образом:

г означает х: = извлечь; у: = извлечь; поместить (сочленить (х, сочленить (СЛ, у)))

7. Использование арамматического анализа для компиляции Теперь последовательность шагов имеет следующий вид:

Предложение Используемог Магазинный список

действие

a+b+c+d -

-- ft + с -f ид

-f с + d ид

-{-d ид

- Р

- г

- г

- г

(Ь\ а') Сс\ ft, а') Cd\ с', & а') (ВЫБ. d\ с', Ь\ а') (ВЫБ, d СЛ, с' Ь\ а') (ВЫБ, d С Л, с С Л, Ь', а') (ВЫБ, d СЛ, с СЛ, b СЛ, а')

В качестве более сложного примера рассмотрим грамматику

S-yud: = E Е--уТ\Е+ Т\Е-Т Т-ид\ТХид\Т1ид

Мы можем ввести компилирующие действия

S-yud:-=E; р

E-T\Ei-Tq\E-Tr

T-->-uds\TXudt\Tluda

р означает поместить (сочленить (извлечь, сочленить (ЗАП', извлечь)))

q означает поместить (сочленить (извлечь, сочленить

(ЗАО, WV, сочленить (извлечь, СЛ, WV))))

г означает поместить (сочленить (извлечь, сочленить

(ЗАО, WV, сочленить (извлечь, ВЫЧ, WV))))

S означает поместить (сочленить (ВЫБ', извлечь))

t означает г: = извлечь; поместить (сочленить (извлечь,

сочленить (УМ, г)))

U означает г: = извлечь; поместить (сочленить

(извлечь, сочленить (ДЕЛ', г)))

) ЗАП - запись содержимого сумматора в ячейку памяти; ДЕЛ - деление; УМ -умножение содержимого сумматора на содержимое ячейки па мяти; ВЫЧ - вычитание. - Прим. перев.

Например, это обеспечит трансляцию формулы g: = a-{-bXcld-\-eXf в фрагмент программы:

ВЫБ, е УМ, f ЗАП, WI ВЫБ, b УМ, с ДЕЛ, d С Л, WI ЗАП, WI ВЫБ, а СЛ, WI ЗАП, g

Преобразуем эту грамматику и получим новую грамматику:

S-yud:=Ep Е-*ТХ

X-*0\-\-TqX\~TrX T-*udsY

Y-*0\XudtY\luduY

Эта новая грамматика может быть оттранслирована методом, описанным в начале гл. 5. В результате получаем программу

procedure S;

begin if not ид (симв) then отказ] симв: = следующий , if симв ф': then отказ; симв: = следующий; if симв ф = then отказ; симв: = следующий; Е;

if симв ф ; then отказ;

р; comment вызов действия для р;

end;

procedure Я;

begin Т;

па: if симв = + then begin симв: следующий;

go to па

else if симв = ~ then begin симв: = следующий',

go to па

end;

procedure T;

begin if not ид [симв) then отказ; s;

nb: if симв = X then begin симв: = следующий;

if not ид {симв) then огказ; t;

go to nfr

else if симв -I then begin симв: = следующий;

if not Mf? (силе) then отказ; и;

go to nb end

end;

силе: = следующий; S

Эта программа выполняет требуемую функцию, и процесс трансляции данной грамматики в программу полностью автоматизируется.

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

7.1. НЕДОПУСТИМЫЕ ПРЕДЛОЖЕНИЯ

Если программа грамматического разбора сталкивается с предложением, которое не принадлежит данной грамматике, то она, конечно, обнаружит ошибку. Однако желательно

указывать такую ошибку наглядно, и хотелось бы продолжать разбор, чтобы найти последующие ошибки. Автору неизвестны публикации, в которых предлагались бы какие-нибудь вполне удовлетворительные методы, обеспечивающие такие возможности в общем случае.

Если грамматический анализ осуществляется последовательным просмотром предложения, по одному слову слева направо, то можно указывать место в предложении, где произошел заключительный отказ. Однако человек не всегда согласится с такой локализацией места ошибки. Например, пропущенная закрывающая скобка в арифметическом выражении не проявится как ошибка, пока не закончится все выражение. Тем не менее обычно оказывается достаточным указать место, где при анализе произошел отказ, и, по возможности, слово, наличие которого позволило бы благополучно провести анализ. Если же алгоритм грамматического анализа основан на том, что каждый вариант разбора исследуется, пока нет отказов, а в случае отказа происходит возврат и выбирается другой вариант разбора, то указание ошибок может оказаться более затруднительным. В этом случае можно было бы указывать место, где произошел отказ при самом продолжительном варианте разбора.

Более значительные трудности вызывает проблема возобновления разбора после обнаружения ошибки, с тем чтобы попытаться довести его до завершения. Маловероятно, чтобы для этого пригодились универсальные общие методы. В большинстве компиляторов производится переход к некоей опознаваемой позиции вроде конца оператора и разбор проводится далее с этого места. Обычно выбор таких позиций производится применительно к конкретной ситуации.

Если алгоритм грамматического анализа способен выполнять одновременно несколько вариантов разбора, иногда можно сделать несколько различных предположений об ошибках и, прокорректировав их соответствующим образом^ продолжать различные варианты разбора. Например, можно предположить, что в точке обнаружения ошибки пропущено слово, или вставлено лишнее слово, или неправильно? слово стоит на месте нужного. В литературе описаны такие методы, но они применимы только в простых случаях, а в более сложных ситуациях они могут оказаться непригодными.

ЭЛЕМЕНТАРНАЯ ОБРАБОТКА СПИСКОВ

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

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

а элементы ячейки, являющиеся адресами других ячеек, представляются стрелками, направленными в эти ячейки.

Атомы представляются путем записи их внутри прямоугольников

И