Приложение 1

Косая черта представляет специальный атом, называемый ПУСТО. Структуры любой сложности могут быть построены по следующему образцу:

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

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

(а. +, Ь)

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

(а. +, {Ь, +, с))

представляет список

1Е>ЕО-Ш

Программы написаны на Алголе, в который включены дополнительно переменные, принимающие списковые значения. Для выполнения элементарных операций обработки списков используются три функции. Если л; -список, то hd{x) представляет собой значение начального элемента этого списка. Аналогично й{х) задает остаток списка х. Значением функции cons {х, у) является ячейка, содержащая х в своей начальной части v у ъ остатке. Заметим, что для построения списка

пишем

[а, Ь, с)

cons {а, соц8(Ь., cons {с, ПУСТО)))

Элементарная обработка списков Заметим также, что

но неверно, что

hd{cons(x, у)) = х tl{cons{x, у)) = у

cons{hd{x), tl{x)) = x

потому что функция cons образует новую ячейку. Значение cons {hd{x), tl{x)) представляет собой копию ячейки х, но это не сама ячейка х.

В качестве примера рассмотрим программу, которая переворачивает список m и помещает результат на место п:

п: = ПУСТО;

г: итф ПУСТО then begin п: = cons{hd (т), п)\

т: = и [т); go to г

ПРИЛОЖЕНИЕ 2

АЛГОРИТМ

ГРАММАТИЧЕСКОГО РАЗБОРА СВЕРХУ ВНИЗ

Функции hd, и и cons описаны в приложении 1. Функция следующий считывает следующее слово из предложения; терминальный - логическая функция, которая является истиной, если ее аргумент - слово, и ложью, если ее аргумент - класс. Функция априори принимает значение истина, если ее аргумент, являющийся правилом подстановки, удовлетворяет априорным критериям.

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

S-a\bTTd T-bc \а

переменная предложение содержит список

((а'), (6, ((Ь\ с'), (а')), {{Ь\ с'), (а')), (d))

Разумеется, двум вхождениям Т будут соответствовать указатели на один и тот же подсписок:

az ЕЕЬШ-СЕЗЧШ!

□

Алгорит.\1 грамматического разбора сверху вниз

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

В описываемой программе переменная la служит для хранения списка всех текущих частично проведенных вариантов разбора; в переменной симв хранится текущее слово. В результате сопоставления текущего слова и частичных разборов некоторые варианты разбора отпадают и забываются, некоторые переносятся в список lb, состоящий из вариантов частичного разбора, подготовленных для сопоставления со следующим словом, а остальные порождают более развитые варианты разбора, которые снова помещаются в /а и далее обрабатываются аналогичным образом. Когда список la окажется пустым, в него будет перенесен список lb и весь процесс повторится. Варианты разбора, которые завершаются в конце предложения, являются правильными грамматическими разборами данного предложения.

Каждый частичный разбор представляется списком концов правил подстановки. Этот список указывает структуру, которую должен иметь остаток предложения для того, чтобы соответствовать этому варианту разбора. Например, если мы анализируем предложение babcd в грамматике

S-*a\bTTd T-*bc \а

и уже обработали bab, то останется частичный разбор

означающий, что остаток предложения должен состоять из слова с, а следом за ним d. Запись

остается после подстановки Т-->-Ьс, а запись

СПИСОК ЛИТЕРАТУРЫ

Принятые сокращения:

ACM Association for Computing Machinery

AFIPS American Federation of Information Processing Societies

CACM Communications of the Association for Computing Machinery

IEEE Institute of Electrical and Electronic Engineers

IFIP International Federation for Information Processing

JACM Journal of the Association for Computing Machinery

SJCC Spring Joint Computer Conference

1. Bar Hillel Y., Language and information, Addison-Wesley, 1964.

2. Brooker R. A., CACM, 10 (April 1967), 223.

3. Brooker R. A., Morris D., An assembly program for a phrase structure language. Computer Journal, 3 (1960), 168.

4. Brooker R. A., Morris D., A general translation program for phrase structure languages, JACM, 9 (Jan. 1962), 1.

5. Brooker R. A., Morris D., Rohl J. S., Experience with the compiler-compiler. Computer Journal, 9 (1967), 345.

6. Cheatham T. E., Satley K., Syntax directed compiling, Proc. AFIPS, 1964 (SJCC), 31.

7. Chomsky N., Formal properties of grammars. Handbook of Mathematical Psychology, 2, Wiley, 1963, p. 323.

8. Chomsky N., Aspects of the theory of syntax, MIT Press, 1965.

9. Eichel J., Paul M., Bauer F. L., Samelson K., A syntax controlled generator of formal language processors, CACM, 6 (Aug. 1963), 451.

10. Feldman J., Cries D., Translator writing systems, CACM, 11 (Feb. 1968), 77.

11. Floyd R. W., Syntactic analysis and operator precedence, JACM, 10 (July 1963), 316.

12. Floyd R. W., Bounded context syntactic analysis, CACM, 7 (Feb. 1964), 62.

13. Floyd R. W., The syntax of programming languages -a survey, IEEE Trans., EC13, 4 (Aug. 1964), 346.

14. Foster J. M., A syntax improving program. Computer Journal, 11 (May 1968), 31.

15. Ginsburg S., The mathematical theory of context-free languages, McGraw-Hill Inc., 1966.

16. Ginsburg S., Greibach S., Deterministic context-free languages, Information and Control, 9 (1960), 620.

17. Greibach S., Formal Parsing Systems, CACM, 7 (Aug. 1964), 499.

18. Griffiths T. v., Petrick S. R., On the relative efficiency of context-free grammar recognisers, CACM, 8 (May 1965), 289.

19. Griffiths T. V., Petrick S. R., Top-down versus bottom-up analysis, IFIP Congress 68, B80.

80. Ingerman P. Z., A syntax oriented translator, Academic Press, 1966,

остается после подстановки S-*bTTd.

la: = cons {cons {cons {предложение, ПУСТО), ПУСТО), ПУСТО);

24:/6: = ПУСТО; симв: = следующий; zz:ii /а ПУСТО then

begin Ic: = hd {la); la: = tl (la);

z\ :if /с = ПУСТО then begin if последнее слово

then успех end else go to zz;

ld:hd{lc); tc:tl{lc);

if/d = ПУСТО then go to zl;

le: = hd{td); ld: = tl{ld);

if терминальный {le) then begin if 1е = симв

then lb: = cons {cons {Id,

Ic). lb);

go to zz

end;

23: if /6=7 ПУСТО then

begin if not априори {hd{le)) then go to 2з; la: = cons {cons {hd{le), cons {Id, le)), la); le:=tl{le); go to 2з end;

go to z2

end;

if lb = ПУСТО then отказ;

la:=lb;

go to 24;

21. Irons Е. Т., А syntax directed compiler for Algol 60, CACM, 4 (Jan. 1961), 51.

22. Irons E. Т., Tlie structure of tlie syntax-directed compiler. Annual Review in Automatic Programming, 3 (1963), 207.

23. Irons E. Т., An error correcting parse algoritlim, CACM, 6 (Nov. 1965), 669.

24. Kuno S., Oettinger A. G., Multiple patli syntactic analyser, IFIP Congress 62, p. 306.

25. Kuno S., Tlie predictive analyser and a patli elimination technique, CACM,

8 (July 1965), 453.

26. Kurki-Suonio R., On top-to-bottom recognition and left-recursion, CACM

9 (July 1966), 527.

27. Landweber P. S., Decision problems of phrase structure grammars IEEE Trans., EC13 (Aug. 1964), 354.

28. Ledley R. S., Wilson J. В., Automatic programming language translation trough syntactical analysis, CACM, 5 (March 1962), 145.

29. Narasimhan R., Syntax directed translation of classes of pictures. CACM 9 (March 1966), 166.

30. Reynolds J. C, An introduction to the COGENT programming system ACM 20th National Conference, 1965, p. 422. s ,

31. Samelson K., Bauer F. L., Sequential formula translation, CACM, 3 (Feb 1960), 76. , , к eo.

32. Unger S. H., A global parser for context-free phrase structure erammars СЛСЛ1, 11 (April 1968), 240.

33. Wirth N., Weber H., EULER -a generalisation of Algol, and its formal definition. Part 1, CACM. 9 (Jan. 1966), 13; Part 2, CACM, 9 (Feb. 1966), 89.

34. Amarel S. Готовится к печати.

ОГЛАВЛЕНИЕ

1. Введение........................

2. Контекстно-свободные грамматики..............9

2.1. Терминология....................

2.2. Примеры грамматик и их свойств............

3. Грамматический разбор..................

4. Универсальные методы грамматического разбора.........21

4.1. Разбор сверху вниз.................

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

4.3. Грамматический разбор снизу вверх...........

4.4. Априорные критерии для анализа снизу вверх.......

4.5. Общая программа грамматического разбора........

4.6. Сравнения.....................

5. Специальные методы грамматического разбора..........33

5.1. Методы разбора снизу вверх..............39

5.2. Грамматики с операторным предшествованием.......

5.3. Грамматики с предшествованием............

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

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

6.1. Преобразования для исключения левой рекурсии 5

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

7. Использование грамматического анализа для компиляции.....57

7.1. Недопустимые предложения..............

Приложение 1. Элементарная обработка списков..........63

Приложение 2. Алгоритм грамматического разбора сверху вниз . . . , 66 Список литературы.....................

УВАЖАЕМЫЙ ЧИТАТЕЛЬ!

Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва, И-110, ГСП, 1-й Рижский пер., д. 2, издательство Мир .

Дж. Фостер

АВТОМАТИЧЕСКИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ

Редактор Л. И. Вабынняа Художественный редактор В.

Художник в. М. Новоселова И. Шаповалов Технический редактор Н. И. МанохиВа Корректор Т. с. Лаврова

Сдано в набор17/Х 1974 г. Подписано к печати 24/III 1975 г. Бумага тип. № 1 60 X90Vu = 2,25 бум. л. 4.50 усл. печ. л. Уч.-изд. л. 3.02, Изд. Nn 1/7554. Цена 23 к. Зак. 392

ИЗДАТЕЛЬСТВО МИР Москва, 1-й Рижский пер., 2

Ордена Трудового Красного Знамени Ленинградская типография Д6 2 имени Евгении Соколовой Союзполнграфпрома прн Государственном комитете Совета Министров СССР по делам издательств, полиграфии н книжной торговли 198052, Ленинград, Л-52, Измайловский пр., 29.