Алгоритм нисходящего разбора. Нисходящие распознаватели

1. Задача разбора

Разбор сентенциальной формы означает построение вывода и, возможно

синтаксического дерева для нее. Программу разбора называют также рас-

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

мой грамматики. Именно это и является нашей задачей в данный момент.

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

тмами слева направо ввиду того, что они обрабатывают сначала самые ле-

вые символы обрабатываемой цепочки и продвигаются по цепочке только

тогда, когда это необходимо. Можно подобным способом определить разбор

справа налево, но он менее естественен. Инструкции в программе выполня-

ются слева направо, да и мы читаем слева направо.

Различают две категории алгоритмов разбора: нисходящий (сверху вниз)

и восходящий (снизу вверх). Их называют также разверткой и сверткой.

( В данном реферате будет рассмотрен процесс только нисходящего раз-

бора. ) Соотетственно, эти термины соответствуют и способу построения

синтаксического дерева. При нисходящем разборе дерево строится от корня

( начального символа ) вниз к концевым узлам. Метод восходящего разбора

состоит в том, что отправляясь от заданной цепочки, пытаются привести ее

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

предложение (1) в следующей грамматике целых чисел ( последовательностей,

состоящих из одной и более цифр ):

N ::= D | ND

D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1)

На первом шаге непосредственный вывод N => ND будет строиться так,

как показано в первом дереве на рис. 1. На каждом последующем шаге

самый левый нетерминал V текущей сентенциальной формы xVy заменяется

на правую часть u правила V ::= u, в результате чего получается сле-

дующая сентенциальная форма. Этот процесс для предложения (1) предс-

тавлен на рис. 1. в виде пяти деревьев. Фокус в том, конечно, что

надо получить ту сентенциальную форму, которая сопадает с заданной

цепочкой.

N N N N N

| | | |

*-------* *-------* *-------* *-------*

| | | | | | | |

N D N D N D N D

| | | |

D D D 5

| |

3 3

N => N D => D D => 3 D => 3 5

Рис. 1. Нисходящий разбор и построение

вывода

2. Нисходящие разбор с возвратами

Алгоритм нисходящего разбора строит синтаксическое дерево, как уже

было сказано, начиная с корня, постепенно опускаясь до уровня предло-

жения, как было показано ранее. Описание усложняется главным образом

из-за необходимости вспомогательных операций, которые необходимы гла-

вным образом для того, чтобы выполнять возвраты с твердой уверенностью,

что все возможные попытки построения дерева были предприняты.

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

бора образно. Вообразим, что на любом этапе разбора, в каждом узле уже

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

находятся в терминальных узлах, занимают места соответственно символам

предложения.

Некоему человеку надлежит провести разбор предложения x. Прежде все-

го ему необходимо отыскать вывод Z => +x, где Z - начальный символ; сле-

довательно первым непосредственным выводом должен будет быть вывод

Z => y где Z ::= y - правило. Пусть для Z существуют правила

Z ::= X X .. X | Y Y .. Y | Z Z .. Z

1 2 n 1 2 m 1 2 1

Сначала человек пытается определить правило Z ::= X X .. X . Если

1 2 n

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

нить второе правило Z ::= Y Y ... Y . В случае неудачи он переходит к

1 2 m

следующему правилу и т.д.

Как ему определить, правильно он выбрал непосредственный вывод

Z => X X .. X ? Заметим, что если вывод правилен, то для некоторых

1 2 n

цепочек x будет иметь место x=x x .. x , где X => *x для i=1,...,n.

i 1 2 n i i

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

M , который должен будет найти вывод X =>*x для любого x , такого,

1 1 1 1

что x = x ... Если сыну M удастся найти такой вывод, он (и любой из

1 1

сыновей, внуков и т.д.) закрывает цепочку x в предложении x и сообща-

ет своему отцу об успехе. Тогда его отец усыновит M , чтобы тот нашел

вывод X => *x , где x = x x ... и ждет ответа от него и т.д. Как толь-

2 2 1 2

ко сообщил об успехе сын M ,он усыновит еще и M , чтобы тот нашел

i-1 i

вывод X => *x . Сообщение об успехе, пришедшее от сына M , означает

i i n

что разбор предложения закончен.

Как быть, если сыну M не удается найти вывод X =>*x ? В этом

i i i

случае M сообщает о неудаче своему отцу; тот от него отрекается и

дает старшему брату M ,M такое распоряжение: "Ты уже нашел вывод,

i i-1

но этот вывод неверен. Найди-ка мне другой". Если M сумеет найти

i-1

другой вывод, он вновь сообщит об успехе, и все продолжится по-пре-

жнему. Если же M сообщит о неудаче, отец отречется и от него, и

i-1

тогда уже старшего брата M , попросят предпринять еще одну попыт-

i-2

ку. Если придется отречься даже от M , значит, непосредственный вы-

вод Z => X X .. X был неверен, и человек, начинавший разбор, попы-

1 2 n

тается воспользоваться другим выводом Z => Y .. Y .

1 m

Как же действует каждый из M ? Положим, его целью является тер-

минал X . Входная цепочка имеет вид x=x x ..x T.. ,где символы в

1 2 i-1

x ,x ,...,x уже закрыты другими людьми. M проверяет, совпадает

1 2 i-1 i

ли очередной незакрытый символ T с его целью X . Если это так, он

закрывает этот символ и сообщает об успехе. Если нет, сообщает об

неудаче.

Если цель M - нетерминал X , то M поступает точно так же, как

1 1

и его отец. Он начинает проверять правые части правил, относящихся к

нетерминалу, и, если необходимо, тоже усыновляет или отрекается от

сыновей. Есливсе его сыновья сообщают об успехе то M в свою очередь

сообщает об успехе отцу. Если отец просит M найти другой вывод, а це-

лью является нетерминальный символ, то M сообщает о неудаче, так как

другого такого вывода не существует. В противном случае M просит своего

младшего сына найти другой вывод и реагирует на его ответ также, как и

раньше. Если все сыновья сообщат о неудаче, он сообщит о неудаче свое-

му отцу.

Теперь, наверное, понятно, почему этот метод называется прогнозиру-

ющим или целенаправленным. Используется и название "нисходящий" из-за

способа построения синтаксического дерева. При разборе отправляются от

начального символа и нисходят к предложению (см рис. 2)

*---*-------*

| | |

F | T

| | |

T |

| |

F |

| |

i + i * i

Рис. 2. Частичный нисходящий разбор предложения i+i*i.

Привлекательность этого метода (и его представления) в том и сос-

тоит, что каждый человек должен помнить лишь о своей цели, о своем от-

це, о своих сыновьях, а также о своем месте в грамматике и выходной це-

почке. И никому не нужны точные сведения о том, что происходит в других

местах. Это как раз и есть то, к чему мы вообще стремимся в программиро-

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

титься о собственной входной и выходной информации и ни о чем более.

Для имитации усыновления и отречения сыновей в программах использу-

ют стек типа LIFO (последний вошел - первый вышел), или, как его иногда

называют, "магазин".

Опишем алгоритм в более явном виде:

Положим, во-первых, что грамматика задана списком в одномерном мас-

сиве GRAMMAR таким образом, что каждое множество правил

U ::= x|y|...|z

представлено, как Ux|y|...|z|$. То есть каждый символ занимает одну

ячейку, за каждой правой частью следует вертикальная черта "|", а за

последним символом следует "|$". Таким образом, грамматика

Z ::= E#

E ::= T+E|T

T ::= F*T|F

F ::= (E)|i

будет выглядеть как

ZE#|$ET+E|T|$TF*T|F|$F(E)|i|$

Каждый элемент стека соответствует человеку и состоит из пяти

компонент

(GOAL,i,FAT,SON,BRO)

которые означают следующее:

1. GOAL - цель, т.е. символ, который человек ищет. Таким обра-

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

найти такую голову, которая приводится к GOAL, и закрыть ее. GOAL

передается ему отцом.

2. i - индекс в массиве GRAMMAR, указывающий на тот символ в

правой части для GOAL, с которым человек работает в данный момент.

3. FAT - имя отца (номер элемента стека, соответствующего от-

цу).

4. SON - имя самого последнего (младшего) из сыновей.

5. BRO - имя его старшего брата.

Нуль в любом из полей означает, что данная величина отсутствует.

В программе значение переменной v равно количеству участвующих в

разборе людей (количеству элементов в стеке в текущий момент), c -

имя (номер элемента в стеке) человека, работающего в данный момент.

Остальные ожидают конца его работы. Индекс j относитстя к самому ле-

вому (незакрытому) символу входной цепочки INPUT(1),...,INPUT(n).

а) Z б) СТЕК ЦЕЛЬ i FAT SON BRO

*---------*------* 1 Z 4 0 15 0

| | 2 E 10 1 7 0

E # 3 T 20 2 4 0

| 4 F 28 3 5 0

*--*------* 5 i 0 4 0 0

| | | 6 + 0 2 0 3

T | E 7 E 12 2 8 6

| + | 8 T 18 7 12 0

F T 9 F 28 8 10 0

| | 10 i 0 9 0 0

i *---*---* 11 * 0 8 0 9

| | | 12 T 20 8 13 11

F * T 13 F 28 12 14 0

| | 14 i 0 13 0 0

i F 15 # 0 1 0 2

Рис 3. Стек после нисходящего разбора i+i*i

а) - синтаксическое дерево б) - стек после разбора

Поле SON используется для хранения ссылки на последнего (младше-

го) сына. Тогда поле BRO элемента, соответствующего этому сыну, укажет

на старшего брата. В качестве иллюстрации расмотрим изображенное на

рис .3 а) синтаксическое дерево для предложения i+i*i вышеописанной

грамматики. Состояние стека после окончания работы показано на рис.3 б).

Теперь у человека 2(S (2)) есть цель E; предполагается, что он в соотве-

тствии с синтаксическим деревом использует правило E ::= T+E. Таким

образом, ему для того, чтобы найти символы T,+,E потребуется три сына.

Значение поля S(2).SON=7, так что младшим сыном является человек, c

номером 7, цель которого E. Имя среднего сына - число 6, определяется

значением поля S(7).BRO; - цель этого сына - символ +. Имя старшего

сына находится в поле BRO человека 6 и равно 3.

Очевидно, что у нас имеется список сыновей каждого человека и

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

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

дерева.

Рассмотрим теперь сам алгоритм нисходящего разбора. Для удобства

чтения разделим его на шесть поименованных частей.

1. НАЧАЛЬНАЯ УСТАНОВКА

S(1) := (Z,0,0,0,0); c:=1; v:=1; j:=1; переход на НОВЫЙ ЧЕЛОВЕК

(первое усыновление. Цель усыновления - начальный символ Z.)

2. НОВЫЙ ЧЕЛОВЕК

IF GOAL терминал THEN Новый человек изучает свою цель.

IF INPUT (j)=GOAL THEN Цель - терминал.

BEGIN j:=j+1; Если GOAL совпадает с символом из

GO TO УСПЕХ; предложения, человек закрывает этот

ELSE GO TO НЕУДАЧА символ и сообщает об успехе.

i:= индекс в GRAMMAR правой Не совпадает - сообщает об неудаче.

части для GOAL; Цель нового человека - нетерминал.

GO TO ЦИКЛ Подготовка к просмотру правых частей

в правилах для GOAL

3. ЦИКЛ

IF GRAMMAR(i)="|" Просмотр правой части

THEN IF FAT=/=0 Достигли конца правой части, поэтому

THEN GO TO УСПЕХ сообщаем об успехе. Если нет отца,

ELSE STOP - предложение; то останов - окончен разбор

предложения

IF GRAMMAR(i )="$" Нет больше правых частей, которые

THEN IF FAT=/=0 можно было бы попробовать, поэтому

THEN GO TO НЕУДАЧА сообщение о неудаче или, если нет отца

ELSE STOP - не остановка, не распознав предложения

предложение;

v:=v+1; GRAMMAR(i) - другая цель, которую

S(v):=(GRAMMAR (i),0,c,0, можно попытаться найти. Берем сына.

SON); Тогда старший брат - тот, кто был до

этого младшим сыном

Переключить внимание на младшего сына

SON:=v; c:=v; и ждать от него ответа

GO TO НОВЫЙ ЧЕЛОВЕК

4. УСПЕХ

c:=FAT; Сообщить об успехе своему отцу. Он

i:=i+1; GO TO ЦИКЛ предпримет следующий шаг.

5. НЕУДАЧА

c:=FAT; Сообщить о неудаче своему отцу. Он

v:=v-1; отречется от сына и попросит его

SON:=S(SON).BRO; старшего брата предпринять еще одну

GO TO ЕЩЕ РАЗ попытку.

6. ЕЩЕ РАЗ

IF SON=0 THEN Есть ли еще сын, который может пред-

BEGIN WHILE GRAMMAR(i) принять еще одну попытку? Нет.

=/="|" Тогда пропускается правая часть -

DO i:=i+1; Это не та, которая нужна - переход к

i:=i+1 GO TO ЦИКЛ следующей.

END;

i:=i-1; c:=SON; Есть сын. Его просят повторить попытку

IF GOAL нетерминал Его цель - нетерминал, так что он по-

THEN GO TO ЕЩЕ РАЗ пытается еще раз добиться успеха.

j=j-1 Его цель терминал. Попытка не приведет

GO TO НЕУДАЧА к успеху. Поэтому он открывает свой

символ и сообщает о неудаче.

Блок схема данного алгоритма приведена ниже.

*---------*

| 1 |

*----*----*

*---------------------------->| *------*

| * *----->| |<------*

| Нет / \ | | | |

| *-----------< 2 > | | * |

| Нет / \ А \ / | | Д / \ |

| *----------< 4 > | * | *-------< 9 > |

| | \ / | | | | | \ / |

| | * | | | | | * |

| | | Да | | Да | | | | Нет |

| | * | | | | | *---*---* |

| | *---* Н / \ | | | | | | 10 | |

| | | 6 |--< 5 > | * | | | *---*---* |

| | *---* \ / | / \ | | | | |

| | * | *-< 3 > | | | * |

| | | Да | | \ / | | | / \ Да |

| *-* | | | * | | | <1 1>-----*

*-|7| | | | *-----* | | \ /

*-* | | | Нет | | *

| *--|-------------* | | Нет

| | А | *---*---*

|<--------* | *--| 1 2 |

*---*---* | *-------*

| 8 |-------*

*-------*

Рис 4. Блок-схема алоритма нисходящего разбора

1. S(1) := (Z,0,0,0,0); c:=1; v:=1;

2. GOAL - терминал ?

3. j:=j+1; INPUT(j)=GOAL ?

4. GRAMMAR(i)="Конец" ?

5. FAT =/= 0 ?

6. STOP - Конец работы;

7. v := v+1; S(v) := (GRAMMAR (i),0,c,0,SON);

SON := v; c := v;

8. c := FAT; i := i+1;

9. SON = 0 ?

10. Пока GRAMMAR (i) =/= "Конец":

i := i+1,

j:=j+1;

i :=i -1;

c := SON;

11. GOAL - нетерминал ?

12. C := FAT ; v := v-1; SON := S (SON) * BRO.

3. Проблемы нисходящего разбора

Прямая левосторонняя рекурсия

В алгориме, описанном ранее, есть один серьезный недостаток,

который проявляется, когда цель определена с использованием левосто-

ронней рекурсии. Если X - наша цель, а первое же правило имеет вид

X ::= X ..., то мы незамедлительно усыновляем того, кто будет искать

X. Он в свою очередь немедленно заведет себе сына, чтобы тот искал

X. Таким образом, каждый будет сваливать ответственность на своего сы-

на, и для решения задачи не хватит населения Китая.

По этой причине правила грамматики написаны с применением право-

сторонней рекурсии вместо более привычной левосторонней. Лучший способ

избавиться от прямой левосторонней рекурсии - записывать правила, ис-

пользуя итеративные и факультативные обозначения. Запишем правила

(3.1) E ::= E+T | T как E ::= T { +T }

T ::= T*F | T/F | F как T ::= F { *F | /F }

Сейчас будут сформулированы два основных принципа, на основании

которых правила языка, включающие прямую левостороннюю рекурсию, пре-

оьразуются в эквивалентные правила, использующие итерацию.

(3.2 ) Факторизация. Если существуют правила вида

U ::= xy | xw | ... |xz, то их надо заменить на

U ::= x(y|w|...|z), где скобки являются метасимволами

Допустима факторизация в более общей форме, такая как в арифметиче-

ских выражениях. Например, если в (3.2) y=y y и w=y w , мы могли бы за-

1 2 1 2

менить U ::= x (y|w|...|z) на

U ::= x(y (y |w )|...|z).

1 2 2

Заметим, что исходные правила U ::= x|xy мы преобразуем к виду

U ::= x(y|Л), где Л - пустая цепочка. Когда бы ни использовалось по-

добное преобразование, Л всегда помещается как последняя альтернати-

ва, так как мы принимаем условие, что если цель - Л, то эта цель все-

гда сопоставляется.

Помимо того что факторизация позволяет нам исключить прямую реку-

рсию, использование этого приема сокращает размеры грамматики и позво-

ляет проводить разбор более эффективно. В этом мы убедимся позже.

После факторизации (3.2) в грамматике останется не более одной пра-

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

Если такая правая часть есть, мы делаем следующее:

(3.3) Пусть U ::= x|y|...|z|Uv - правила, у которых осталась леворе-

курсивная правая часть. Эти правила означают, что членом син-

таксического класса U является x, y или z, за которыми либо ни-

чего не следует, либо следует только v. Тогда преобразуем эти

правила к виду U ::= (x|y| ... |z) {v}.

Мы использовали (3.3) чтобы сделать преобразование в (3.1),

позволяющее избавиться от ненужных скобок заключающихся в T. В качес-

тве другого примера преобразуем A ::= BC|BCD|Axz|Axy

а) Z б) Z

| |

*----*-* *-*-*-*-*-*-*

| | | | | | | | | |

E + T T + T + T + T

*--*-*

| | |

E + T

*-*-*

| | |

E + T

Рис 5. Деревья, использующие рекурсию и итерацию

Применив правило (3.2) получим A ::= BC(D|Л)|Ax(z|y); Применив

(3.3), получим A ::= BC(D|Л){x(z|y)}. Можно избавиться от одной па-

ры скобок, после чего получим A ::= BC(D|Л){x(z|y)}.

После таких изменений мы, конечно, должны изменить и наш алгоритм

нисходящего разбора. Теперь алгоритм должен уметь обрабатывать альтер-

нативы не только в одной правой части, но и в ее подцепочках, должен

учитывать в своей работе существование пустой цепочки Л, должен уметь

обрабатывать итерацию.

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

деревьев. Таким образом, рис 3.а должен был бы походить на рис. 3.б. Но

эти два дерева следует рассматривать как эквивалентные; операторы "плюс"

должны заменяться слева направо.

Общая левосторонняя рекурсия

Мы не решили всей проблемы левосторонней рекурсии: с прямой лево-

сторонней рекурсией покончено, но общая левосторонняя рекурсия еще ос-

талась. Таким образом, правила

U ::= Vx и V ::= Uy|v

дают вывод U => +Uyx. Избавиться от этого не так просто, но обнаружить

ситуацию можно. Исключим из исходной грамматики все правила с прямой

левосторонней рекурсией. Символ U, получившейся в результате этих пре-

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

когда U FIRST+ U. Как проверить это отношение, нам уже известно.

Представление грамматики в оперативной памяти

Одной из проблем, возникающих при реализации нисходящих методов,

является представление грамматики в вычислительной машине. Одно из

возможных представлений уже использовалось ранее. Очевидно, что оно

неудачно из-за обьема работы необходимой для поиска правил, соответст-

вующих каждому нетерминалу. Речь пойдет о другом представлении. Прежде

чем начать изложение, стоит упомянуть о том что написать конструктор,

который воспринимает грамматику, проводит любые из преобразований, о

которых только что говорилось, проверяет не являются ли правила рекур-

сивными, и составляет таблицы для грамматики в одной из описываемых да-

лее форм довольно легко.

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

зываемая синтаксическим графом. Каждый узел представляет символ S из

правой части и состоит из четырех компонент: ИМЯ, ОПРЕДЕЛЕНИЕ (ОПР),

АЛЬТЕРНАТИВА (АЛТ) и ПРЕЕМНИК (ПРЕМ), где

1. ИМЯ - это сам символ S в некоторой внутренней форме.

2. ОПРЕДЕЛЕНИЕ равно 0, если S - терминал; в противном случае эта

компонента указывает на узел соответствующий первому символу в

перво правой части для S.

3. АЛЬТЕРНАТИВА указывает на первый символ той альтернативы пра-

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

узел (0, если такой правой части нет). Это только для символов

в правых частях.

4. ПРЕЕМНИК указывает на следующий символ правой части (0, если

такого символа нет).

Кроме того, каждый нетерминальный символ представлен узлом, состо-

ящим из одной компоненты, которая указывает а первый символ в первой

правой части, относящейся к этому символу. Примером может служить

рис. 4, на котором изображено расположения компонент узла синтаксическо-

го графа грамматики:

*---------------------------*

| ИМЯ |

*--------*---------*--------*

| ОПР | АЛТ | ПРЕМ |

*--------*---------*--------*

Рис 6. Расположение компонент узла синтаксического

графа грамматики

Подробно о синтаксических графах см. в книге Д.Гриса "Конструи-

рование компиляторов для цифровых вычислительных машин"

Разбор без возвратов

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

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

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

семантику с синтаксисом, и по мере того, как мы будем прогнозировать и

находить цели, эти символы будут обрабатываться семантически. Вот неко-

торые примеры "обработки": 1) при обработке описаний переменных иденти-

фикаторы помещаются в таблицу символов; 2) при обработке арифметических

выражений проверяют, совместимы ли типы операндов.

Если возврат произошел из-за того, что прогнозируемая цель неверна,

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

время поисков этой цели. Сделать это не так -то просто, поэтому постара-

емся провести грамматический разбор без возвратов.

Для того, чтобы избавиться от возвратов, в компиляторах в качестве

контекста обычно используется следующий "незакрытый" символ исходной про-

граммы. Тогда на грамматику налагается следующее требование: если есть

альтернативы x|y|...|z, то множества символов, которыми могут начинаться

выводимые из x,y,..,z слова, должны быть попарно различны. То есть если

x => *Au и y => *Bv то A =/= B. если это требование выполнено, можно

довольно просто определить, какая из альтернатив x,y или z - наша цель.

Заметим, что факторизация оказывает здесь большую помощь. Если есть пра-

вило U ::= xy|xz, ео преобразование этого правила к виду U ::= x(y|z)

помогает сделать множесва первых символов для разных альтернатив непе-

ресекающимися.

4. Заключение

В данном реферате рассматривались нисходящие распознаватели,

алгоритм нисходящего разбора и проблемы связанные с нисходящим

разбором. Одна из первых статей, рассматривающих фиксированный ал-

горитм нисходящего разбора, принадлежит Айронсу. Но его метод не

являлся нисходящим разбором в чистом виде, а являлся смешением нис-

ходящих и восходящих разборов. Алгоритм, приведенный в данном рефе-

рате, впервые был предложен в обзоре Флойда. Он же ввел и понятия

"отец - сын - брат". Способы избавления от возвратов описаны Унге-

ром.

5. Список литературы

1. Грисс. Конструирование компиляторов для цифровых вы-

числительных машин. М., Мир, 1975г.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, пере-

вода и компиляции. М. Мир 1978г.

3. Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы

проектирования компиляторов. М., Мир, 1979г.

4. Фельдман Дж., Грис Д. Системы построения трансляторов.

Сб. Алгоритмы и алгоритмические языки, вып.5, ВЦ АН СССР, 1971г.