75 <основ перем>=

<переменная> <список переменных) ( ) 78 <список переменных)

(переменная) (список переменных) vl (переменная)

Регулярные определения

(пропис буква) =

ABC...1Z (строч буква)=

a(bc...z (цифра)=

012...19 (буква)=

(пропис буква) I (строч буква) (буквоцифра)

(буква) I (цифра) (знач истин) -

true I false (голова перем)=

(цифра)+ ((буква) ) [

(строч буква)+ ((Пропис буква) (цифра) I )

(пропис буква) I

(переменная)= - -

(строч буква) ( (голова перем) ((буквоцифра) 1 )* (целое)-

(цифра)+ (вещественное) -

(цифра)+. (цифра)- (заковыч элемент) =

(любой знак отличный от * и )

* rt I * /1» Ь I * S I *я-1 I * I » г (заковыченное) =

(заковыч элемент)* (константа)=

(целое) I (вещественное) (заковыченное)

(знач истин) I е (функтор отнош) =

gr I ge I eq I пе I Is 11е

список ЛИТЕРАТУРЫ )

"Абрахам (1965] (Abraham S.), Some questlonsof phrase slruciure grammars, I, Comput. Linguist., 4, 61-70.

Абрахаме 11972] (Abrahams P. W.), A syntax directed parser for recalcitrant grammars, Intern. J. Computer Math., 3:2/3, 105-J15.

®Абэ и др. [1973] (Abe N., Mlzumoto M., Toyoda J,, Tanaka K.), Web grammars and several graphs, J. Comput. System Sci., 7:1, 37-68.

Автоматический перевод [1971], Сборник статей, изд-во „Прогресс", М.

Айронс [1961] (Irons Е. Т.), А syntax directed compiler for ALGOL 60, Comm. ACM, 4:1, 51-55.

Айронс {I9fi3a] (Irons E. Т.), An error correcting parse algorithm, Comm. ACM, 6:11. 669-073.

Айронс [19636] (Irons E. Т.), The structure and use of the syntax directed

compiler, Ann. Rev. Autom. Program., 3, 207-227. Айроис [1964] (Irons E. Т.), StructuraT connections in formal languages. Comm.

ACM, 7:2, 62-67.

АЛГОЛ 68 [1976], Алгол 68. Методы реализации, под ред. Г. С. Цейтина, изд-во ЛГУ.

Ангер [1968] (Unger S. Н.), А global parser for context-free phrase structure grammars, Comm. ACM, 11:4, 240-246; !l:6, 427.

°Андерсои и др. [1973] (Anderson Т., Eve G., Horning I. I.), Efficient LR (I) parsers, Acta Informatica, 2:1, 12-39.

Аиисимов A. B. [1974а], Формальные грамматики, учитывающие внешние терминальные контексты, Кибернетика, 3, 81-88.

Анисимов А. В. [19746], Об аппарате управления в синтаксических анализаторах, Кибернетика, в, 57- 59.

АНС [1966] (Ans Х3,9), American National Standards FORTRAN, American National Standards Institute, New York.

ABC Подкомитет [1971] (Ansi Subcommittee X3J3), Clarification of FORTRAN Standards -Second Report, Comm. ACM, (4:10, 628-642.

Арбиб [1970] (Arbib M. A.), Theories of abstract automata, Prentice-Hall, Inc., Englewood Giffs, N. J.

Axo [1968] (Aho A. V.), Indexed grammars -an extention of context-free grammars, ACM, 15:4, 647-671. (Русский перевод: Axo A., Индексные грамматики -расширение контекстно-свободных грамматик, в сб. „Языки и автоматы", изд-во „Мир", М., 1975, стр. 130-165.)

Ахо [1973] (Aho А. V. (ed.)), Currents in the theory of computing, Prentice-Hall, Englewood Cliffs, N. J.

Кружочком ° отмечена литература, добавленная при переводе. - Лрил,

Language and information, Addison- Wesley,

=*Axo, Джонсон [1974] (Aho A. V., Johnson S. C), LR-parsing, Comput. Sur• veys, e, 99-124.

Axo, Ульман [19G9al {Aho A. V., Ullman J. D.), Syntax directed translations

and the pushdown assembler, J. Comput. Syst. ScL, 3:1, 37-56. Axo, Ульман [19G96] (Aho A, V., Ullman J. D.), Propertiesof syntax directed

translations, Comput. Syst. ScL, 3:3, 319-334. Axo, Ульман [1971] (Aho A. V., Ullman J. D.), The care and feeding of LR(ft)

grammars, Proc, of 3rd Annual ACM Symposium on Theory of Computing,

159-170.

"Axo, Ульман (1973J (Aho A. V.. Ullman J. D.), Error detection in precedence parsers, Math. Syst. Theory, 7:2, 97-113.

Axo и др. [1968] (Aho A. V., Hopcroft J. E., Ullman J. D.). Time and tape complexity of pushdown automaton languages, Inform, and Control, 13:3, 186-206. (Русский перевод: Axo A., Хопкрофт Дж., Ульман Дж., Временная и ленточная сложности языков, допускаемых магазинными автоматами, в сб. „Языки и автоматы", изд-во „Мир", М., 1975. стр. 185-!97.)

Ахо н др. [1972] (Aho А. V., Denning Р. Ullman J. D.), Weak and mixed strategy precedence parsing, J. ACM, 19:2, 225-243.

Axo и др. 11975] (Aho A. V., Johnson S. C, Ullman J. D.). Deterministic parsing of ambiguous grammars, Comm. ACM, 18:8, 441-453.

Бабинов Ю. П. [197G], Два к.пасса нсукорачивающих грамматик предшество вания, ЖВМ и МФ, 1в:4, 1027-1037.

Барнет, Футрель [1962] (Barnett М. Р., Futrelie R. Р.), Syntactic analysis by digital computer, Comm. ACM, 5:10, 51Г»-

Бар-Хиллел [1964] (Bar-HJllel Y.; Reading, Mass.

Бар-Хиллел и др. [I96I[(Bar-Hillcl У., Pcrles М., Shamir E.), On formal properties of simple phrase .structure grammars, Z. Phonetlk, Sprachwissenschaft und Kommunikationsforschung, 14, 143-172.

Бауэр и др. [1968] (Bauer Н., Becker S., Graham S. L.), ALGOL W Implementation, CS98, Computer Science Dept., Stanford Univ., Stanford, Calif.

Берж [1958] (Berge C), The theory of graph.- and its applications, Wiley, New-York. (Русский перевод: Берж К., Теория графов и ее применения, ИЛ, М., 1962.)

Бжозовскик [19б2( (Brzozovvski J. А.), А survey of regular expressions and their

applications, lE Trans., on Electr. Compat., JI:3, 324-335. Лжо.овскии [1964] (Brzozowski J. A.), Derivatives of regular expressions, J. ACM, " 11:4. 481-494. *

Бирман, Ульман [1970] (Birman A., Ullman J. D.), Parsing algorithms with backtrack, IEEE Conf. Record of 11th Annual $)П1ро5!ия1 on Switching and Automata Theory, 153-174. (Расширенный вариант этой работы см. в Inform, and Control, 23:1, 1-34 (1973).)

Блатнер 11972J (Blattner М.), Tlie unsolvability of the equality problem for sentential forms of context-free languages, неопубликованное сообщение, UCLA, Los Angeles, Calif.

Бобров [1963] (Bobrow D. G.), Syntactic analysis of English by computer -a survey, Proc. AFIPS Fall Joint Computer Conference, 24, 365-387.

Бородин [1970] (Borodin A.), Computational complexity-a survey, Proc, 4th Annual Princeton Conference on Information Sciences and Systems, 257- 262.

"Бородин [1973] (Borodin Л.), Cumputationa) complexity; theory and practice, в сб. „Currents in the tlieory of computing" под ред. Aho A., Prentice-Hall, Englewood Cliffs, N, J., 35-89.

Братчиков И. Л. [1975], Синтаксис языков программирования, изд-во „Наука", Ы.

Браффорт, Хиршберг [1963] (Braffort Р., Hirschberg D. (eds.)), Computer programming and formal sybtems North-Holland, Amsterdam..

Брукер. MoppHC [1963] {Brooker R. A., Morris D.), The compiler-compiler, Лпп.

* Aulok Program., 3, 229-275.

Бук [1970] (Book R. V.), Problems in formal language theory, Proc. 4th Annual

Princeton Conference on Inforniation Sciences and Systems, 253-256. Бут [I967[ (Booth T. L.), Sequential machines and automata theory, Wiley,

New York.

Бэкус и др. [1957] (Backus J. W. et aL). The FORTRAN automatic coding system, Proc. Western Joint Computer Conference, II, 188-198.

Вайз (I97I] (Wise D. S.), Domdikis algorithm applied to generalized overlap resolvable grammars, Proc. 3rd Annual ACM Symposium on Theory of Computing, 171 - 184.

°Вайз [1972] (Wise D. S.), Generalized overlap resolvable grammars and their parsers, J. Сотр. Syst. Set., 6:G, 538-572.

Валиант [1975] (Valiant L. G.), General context-free recognition in less than cubic time, J. Сотр. Syst. Sci., 10:8, 308-315.

Ван Вейнгаарден 1969] (Van Wijngaarden A. (ed.)), Report on the algorithmic language ALGOL 68, Numer. Math., 14, 79-218. {Русскийперевод; Алгоритмический язык АЛГОЛ 68, Кибернетика, в, 1969; 1, 1970.)

Вегбрейт [1970] (Wegbreit В.), Studies in extensible programming languages, Ph. D. Tiiesis, Harvard Univ.. Cambridge, Mass.

"Вельбицкий И. В. {1973}, Метаязык R-грамматик, Кибернетика, 3, 47-63.

Вельбицкнй И. В., Ющенко Е. Л. [1970], Метаязык, ориентированный на синтаксический анализ и контроль, Кибернетика, 2 , 50-53.

Виноград [1965] (Wiriograd S.), On the time required to perform addition, J. ACM, 12:2, 277-285. (Русский перевод; Виноград С. О времени, требующемся для выполнения сложения, Кибер!7етический сборник, новая серия, вып. 6, изд-во „Мир", М., 1969, стр. 41-54.)

Виноград [1967] (Winograd S.), On the time required to perform multiplication, J. ACM, 14:4, 793-802. (Русский перевод: Виноград С, О времени, требующемся для выполнения умножения. Кибернетический сборник, новая серия, вып. 6, изд-во „Мир", М., 19о9, стр. 55-71.)

"Виноград [1972] (Winograd Т.), Understanding natural language, Academic Press, New York, Edinburgh Univ. Press, Edinburgh. (Русский перевод: Виноград Т., Программа, понимающая естественный язык, изд-во „Мир", М.. 1976.)

Вирт [i968 (Wirth N.), PL 360 -a programming language for the 360 computers, J. ACM, 15:1, 37-54.

Вирт, Вебер [1966] (Wirth N., Weber H.), EULER- a generalization of ALGOL and its formal definition, Parts 1 and 2, Comm. ACM, 9:1, 13-23; 9:2, 89-99.

Возенкрафт, Эванс [1969] (Wozencraft J. M., Evans A., Jr.), Notes on programming languages, Dept. of Electrical Engineering, Massachusetts Institute of Techrtoiogy, Cambridge, Mass.

Вуд [1969a] (Wood D.), The theory of left factored languages, Comput. 7., 12:4, 349-356; 13:1, 55-62.

Вуд [19696] (Wood D.), A note on fop-down deterministic languages, B/T, 9:4,

387-399.

Вуд [1970] (Wood D.), Bibliography 23: Formal language theory and automata theory, Comput. Rev., 11:7, 417-430.

"Вудс (1970] (Woods W. A.), Transition network grammars for natural language analysis, Comm. ACM, 13:10, 591-606. (Русский перевод: Вудс В. А., Сетевые грамматики для анализа естественных языков, Кибернетический сборник, новая серия, вып. 13, изд-во „Мир", М., 1976, стр. 120-158.)

Галлер, Перлис [1967] (Galler В. А., Perils А. J.), А proposal for definitions in ALGOL, Comm. ACM, 10:4, 204-219.

Гарвик [1964] (Garwick J. V.), GARGOYLE, a language for compiler writing. Comm. ACM, 7:1, 16-20.

Тецци [1975] (Ghezzi С), LL(1) grammars supporting an efficient error handling, Inform. Proces. Letters, 3:G, 174-176.

Гилл [1962] (Gill A.), Introduction to the theory of finite state machines, McGraw-Hill, New York. (Русский перевод: Гилл A., Введение в теорию конечных автоматов, изд-во „Наука", М., 1966.)

Гинзбург А. [1968] (Ginzburg А.), Algebraic theory of automata, Academic Press, New York.

Гинзбург С. [1962] (Ginsburg S.), An introduction to mathematical machine theory, Addison-Wesley, Reading, Mass.

Гинзбург С. [1966] (Cinsburg S.), The mathematical theory of context-free languages, McGraw-Hill, New York. (Русский перевод: Гинзбург С, Математическая теория коитекстио-свободных языков, изд-во „Мир", М., 1970.)

Гинзбург, Грейбах [1966] (Ginsburg S., Greibach S.), Deterministic context-free languages, Inform, and Control, 9:6, 620-648.

Гинзбург, Грейбах [1969] (Ginsburg S., Greibach S.), Abstract families of languages, Memoir Amer. Math. Soc, 87. (Русский перевод: Гинзбург С., Грейбах Ш., Абстрактные семейства языков, в сб. „Языки и автоматы", изд-во „Мир", М., 1975, стр. 233-281.)

Гинзбург, Ране [1962J (Ginsburg S., Rice Н. G.), Two families of languages related lo ALGOL, J. ACM, 9:3, 350-371. (Русский перевод: Гинзбург С., Райе X., Два класса языков типа АЛГОЛ, Кибернетический сборник, новая серия, вып. 6, изд-во „Мир", М., 1969, стр. 184-216,)

Тинзбург, Уллиан [1966] (Ginsburg S., Ullian J. S.), Ambiguity in context-free languages, J. ACM, 13:3, 364-368.

"Гладкий A. B. [ 1965], Алгоритмическая нераспозиаваемость существенной неопределенности КС-языков, Алгебра и логика, 4:4, 53-64.

Тладкий А. В. [1973], Формальные грамматики и языки, изд-во „Наука", М.

Тлушков Б. М. [19G2], Синтез цифровых автоматов, Физматгиз, М.

Тончарова Л. И. (1975], Приоритетный анализ и контекстные условия, ЖВМ и МФ, 15:3, 719-727.

Грау и др. [1967] (Grau А. А., Hill U., Langmaack В.), Translation of ALGOL 60, Springer, Berlin.

Грейбах [1965] (Greibach S.), A new normal form theorem for context-free phrase structure grammars, J. ACM, 12:1, 42-52.

Грейбах, Хопкрофт [1969] (Greibach S.. Hopcroft J.), Scattered context grammars, /. Сотр. Syst. Sci., 3:3, 233-247. (Русский перевод: Грейбах Ш-, Хопкрофт Дж., Грамматики с рассеянным контекстом, в сб. „Языки и автоматы", изд-во „Мир", М., 1975, стр. 160-184.)

ГрисПЭТН (Gries D.), Compiler construction for digital computers, Wiley, Tvlew Tork. (Русский перевод: Грис Д., Конструирование компиляторов для цифровых вычислительных машии, изд-во „Мир", М., 1975.)

Грисволд и др. [1971] (Griswold R. Е., Poage J. F., Polonsky 1. P.), The SNOBOL 4 programming language (2nd ed.), Prentice-Hall, Inc., Englewood Cliffs, N. J.

Гриффите [1968] (Griffiths T. V.), The unsolvability of the equivalence problem for A-free nondeterministic generalized machines, J. ACM, 15;3 , 409-413. (Русский перевод: Гриффите Т. В., Неразрешимость проблемы эквивалентности для Л-свободных обобщенных машин, Кибернетический сборник, новая серия, вып. 8, изд-во „Мир", М., 1971.)

Триффнтс [1974] (Griffiths Т. V.), LL(1) grammars and analysers. Compiler

Construction, Lecture Notes in Computer Science, 21, 57-84. Гриффите, Петрик [1965] (Griffiths Т. V., Petrick S. R.), On the relative

efficiencies of context-free grammar recognizers, Comm. ACM, 8:5, 289-300. Тряффитс, Петрик [1968] (Griffiths Т. V., Pel rick S. R.), Top-down versus

bottom-up analysis, Information Processing -68 (IFIP Congress), Booklet B,

80-85.

Гросс, Лантен [1970} (Gross M., Lentin A.), Introduction to formal grammars, 578

Springer, Berlin. (Русский перевод: Гросс М., Лантен А., Теория формальных грамматик, изд-во „Мир", М.. 1971,) Трушецкнй В. В. [ 1972], Синтаксические структуры, в сб. ..Системное и

теоретическое программирование", ВЦ СО АН СССР, Новосибирск. Грэй [1969] (Gray J. N.), Precedence parsers for programming languages,

Ph. D. Thesis, Univ. of California, Berkeley. Грэй, Харрисон [1969] (Gray J. N., Harri.son M. A.), Single pass precedence

analysis, IEEE Conf. Record of 10th Annual Symposium on Switching and

Automata Theory, lOG-117. Трэй, Харрисон [1972] (Gray J. N., Harrison M. A.), On the covering and

reduction problems for context-free grammars, J. ACM, 19:4, 675-698. Трэй, Харрисон [1973] (Gray J. N., Harrison M. A.), Canonical precedence

schemes, J. ACM, 20:2, 214-234. Грэй и др. [1967] (Gray J. N., Harrison M. A., Ibarra O.), Two way pushdown

automata, Inform, and Control., 11:1, 30-70. Грэхем P. [1964] (Graham R. M.), Bounded context translation, Proc. AF/PS

Spring Joint Computer Conference, 25, 17-29. Грэхем С. [1970] (Graham S. L.), Extended precedence languages, hounded right

context languages and deterministic languages, IEEE Conf. Record of 11th

Annual Symposium on Switching and Automata Theory, 175-180. Трэхем С. (1974] (Graham S, L.),On bounded right context languages and grammars, SIAM J. Computing, 3:2, 224-254. Трэхем е., Роудз [1975] (Graham S. L., Rhodes E. M ), Practical syntactic error

recovery, Comm. ACM, 18:11, 639-650. Трэхем С. и др. [1976] (Graham S. L., Harrison M. A., Ruzzo W. L.), On-line

context-free language recognition in less than cubic time, Proc. 8th Annual

ACM Symposium on Theory of Computing, 112-120. Де Ремер 119G9] (DeRemer F. L.), Practical iranslalors for LR(k) languages.

Ph. D. Thesis, Massachusetts Institute of Technology, Camoridge, Mass, Де Ремер [1971] (DeRemer F. L.), Simple LRik) grammars, Comm. ACM, 14:7,

453-460.

Джентльмен [1971] (Gentleman W. M), A portable coroutine system. Information Processing-71 (IFIP Congress), TA-3, 94-98.

Джонсон и др. [1968] (Johnson W. L., Porter J. H., Ackiey S. I., Ross D. Т.), Automatic generation of efficient lexical processors using finite state techniques. Comm. ACM, 11:12, 805-813.

Домёлки [1964] (Domolki В.), An algorithm for syntactic analysis, Comput Linguist., 3, 29-46.

Домёлки Б. (1965], Алгоритмы для распознавания свойств последовательностей символов, ЖВМ и МФ, 5:1, 77-97.

Дьюар и др. [1969] (Dewar R. В. К-, Hochsprung R. R., Worley W. S.), The IITRAN programming language, Comm. ACM, 12:10, 569-575,

Давне [1958] (Davis M.), Computability and unsolvability, McGraw-Hill, New York.

Дэвис [1965] (Davis M. (ed.)), The undecidable, Basic papers in undecidable propositions, unsolvable problems and computable functions, Raven Press, New York.

""Жоголев E, A. [1965], Алгоритм выделения понятий с помощью синтаксической таблицы, ЖВМ и МФ, 5:4, 689-698.

"Зыков А. А. [1969], Теория конечных графов, нзд-во „Наука", Новосибирск.

Ингермаи [1966] (Ingerman Р. Z.), Л syntax oriented translator. Academic

~ press. New York. (Русский перевод: Ингерман П., Синтаксически ориентированный транслятор, изд-во „Мир", М., 1969.)

Ихбиа, Морзе [1970] (Ichbiah J. D,, Morse S. P.), A technique for generating almost optimal Floyd-Evans productions for precedence grammars, Comm. ACM, 13:8, 501-508.

Камеда, Вайнер 11968J (Kameda Т., Weiner P.), On the reduction of nondeter-