°Фу [1974] (Fu К. S.), Syntactical metliods in pattern recognition, Academic Press, New Yorl<.

"Фуксмап A. Л. [1968], О некоторых грамматиках для описания коитекстио-свободных языков, Труды 1-й Всесоюзной конференции по программированию, А 135-143.

"Фуксман А. Л. [1976], Слаборазделенные грамматики, ЖВМ и МФ, 16:5, 1293-1304.

Халмош [1960] (Halmos Р. R.), Naive set theory, Van Nostrand Reinhold, New York.

Халмош [1963] {Halmos P. R.), Lectures on Boolean algebras, Van Nostrand

Reinhold, New York. , "Хаммер [1974] jHammer M.), A new grammatical transformation into LL (j)

form, Proc. 6th Annual ACM Symposium on Theory of Computing, 266-275. °Хант и др. [1975] (Hunt Н. В., Szymansky Т. G., Ullman J. D.), On the

complexity of LR (fe) testing, Comm. ACM, 18:12, 707-716. Харари [1969] (Harary F.), Graph theory, Addison-Wesley, Reading, Mass.

(Русский перевод: Харари Ф., Теория графов, изд-во „Мир", М., 1973.) Харрисон [1965] (Harrison М. А.), Introduction to switching and automata

theory, McGraw-Hill, New York. Харрисон 11973] (Harrison M. A.), On covers and precedence analysis, Lecture

Notes in Computer Science, 1, 2-17. "Харрисон, Хавел [1973] (Harrison M. A., Havel I. M.), Strict deterministic

grammars, J. Сотр. Syst. Sci., 7:3, 237-277. "Харрисон, Хавел [1974] (Harrison M. A., Havel I. M.), On the parsing of

deterministic languages, J. ACM, 21:4, 525-548. "Хартманис [1970) (Hartmanis J.), A note on one-way and two-way automata,

Math. System Theory, 4:1, 24-28. Хартманис, Хопкрофт [1970] (Hartmanis J., Hopcroft J. E.), An overview of

the theory of computational complexity, J. ACM, 18:3, 444-475. (Русский

перевод: Хартманис Ю., Хопкрофт Дж., Обзор теории сложности вычислений, Кибернетический сборник, новая серия, вып. 11, изд-во „Мир",

М., 1974, стр. 131 - 176.) Хартманис и др. [1965] (Hartmanis J., Lewis P. М. 11, Stearns R. E.), Classifications of computations by time and memory requirements. Information

Processing-65 (IFIP Congress), 31-35. Хафмен [1954] (Huffman D. A.), The synthesis of sequential switching circuits,

/. Franklin Inst., 257, 3-4, 161, 190, 275-303. Хейнс [1970] (Haines L. H.), Representation theorems for context-sensitive

languages. Dept. of Electrical Engineering and Computer Sciences, Univ. of

California, Berkeley. Хсйс [1967] (Hays D. G.), Introduction to computational linguistics, American

Elsevier, New York. Хекст, Роберте [1970] (Hext J. В., Roberts P. S.), Syntax analysis by Domolkis

algorithm. Computer J., 13:3, 263-271. Хомский [1956] (Chomsky N.), Three models for the description of language,

JEEE Trans. Inform. Theory, 2:3, 113-124. (Русский перевод: Хомский Н.,

Три модели для описания языка. Кибернетический сборник, вып. 2, ИЛ,

М., 1961, стр. 237-266.) Хомский [1957] (Chomsky N.), Syntactic structures, Mouton and Co., The Hague.

(Русский перевод: Хомский Н., Синтаксические структуры, в сб. „Новое

в лингвистике", вып. 11, ИЛ, М., 1962, стр. 412-527.) , Хомский [1959а] fCliomsky N.), On certain formal properties of grammars,

Inform, and Control, 2:2, 137-167. (Русский перевод: Хомский Н.,

О некоторых формальных свойствах грамматик. Кибернетический сборник,

вып. 5, ИЛ, М., 1962, стр. 279-311.) Хомский [19596] (Chomsky N.), А note on phrase structure grammars, Inform. -

and Control, 2:4, 393-395. (Русский перевод: Хомский Н., Заметка

о грамматиках непосредственно составляющих, Кибернетический сборник, вып. 5, ИЛ, М., 1962.) Хомский [1962] (Chomsky N.), Context-free grammars and pushdown storage, Quarterly Progress Report, № 65, Research Laboratory of Electronics, / Massachusetts Institute of Technology, Cambridge, Mass.

XoMCKHi [1963] (Chomsky N.), Formal properties of grammars. Handbook of Aathematical Psycliologv, 2, под ред. Luce R. D., Bush R. R.,, Galanter.E., Wiley, New York. (Русский перевод: Хомский Н., Формальные свойства грамматик Кибернетический сборник, новая серия, вып. 2, нзд-во „Мир", М., 19G6, стр. 121-230.) -f Хомский [IG65] (Chomsky N.), Aspects of the theory of syntax, M. 1. T. Press, Cambridge Mass. (Русский перевод: Хомский Н., Аспекты теории синтаксиса, Изд-во МГУ, М,, 1972.) Хомский, Миллер [1958] (Chomsky N., Miller G. А.), Finite state languages, Inform, and Control, 1:2, 91-112. (Русский перевод: Хомский Н., Миллер Дж Языки с конечным числом состояний. Кибернетический сборник, вып. 4, ИЛ, М,, 1962, стр. 233-255.) Хомский, Шютценберже [1963] (Chomsky N., Schutzcnberger М. Р.), Tlie al-1 gebraic tlieorv of context-free languages, в сб. „Computer Programming and

Formal Systems", под ред. Braffort P., Hirschberg D., North-Holland, Amsterdam. (Русский перевод; Хомский Н,, Шютценберже М. П., Алгебраическая теория контекстно-свободных языков, Кибернетический сборник, новая серия, вып. 3, изд-во „Мир", М., 1966, стр. 195-242.) Хопгуд [1969] (Hopgood F. R. А.), Compiling techniques, American Elsevier,

..... New York. (Русский перевод: Хо!1гудФ., Методы компиляции, изд-во „Мир",

М., 1972.)"

-Хопкрофт [1971] (Hopcroft J. е.). An п logn algorithm for minimizing states in a finite automaton, CS71-190, Computer Science Dept., Stanford Univ., Stanford, Calif. (Русский перевод; Хопкрофт Дж., Алгоритм для минимизации конечного автомата, Кибернетический сборник, новая серия, оьш. 11, изд-во „Мир", М., 1974, стр. 177-184.)

Хопкрофт, Ульман [1967] (Hopcroft J. е., Ullman J. D.). An approach to a unified theory of automata. Bell System Tech. J., 48:8, 1763-1829.

Хопкрофт, Ульман fI969] (Hopcroft J. E,, Ullman J. D.), Formal languages and their relation to automata, Addison-Wesley, Reading, Mass.

"Хориииг 119741 (Horning J. J.), LR grammars and analysers. Compiler Construction, Lecture Notes in Computer Science, 21, 85-108.

"Цейтин Г. С. fl97l]. Алгоритм для упрощенного синтаксического анализа, Проблемы кибернетики, 24, нзд-во „Наука", М., стр. 227-242.

"Цейтлин Г. е., Ющенко е. Л. [1975], Некоторые вопросы теории параметрических моделей языков и параллельный синтаксический анализ, Труды Всесоюзного симпозиума по методам реализации новых алгоритмических языков, часть 2, 61-73.

Чёрч [19411 (Church А.), The calculi of lambda conversion, Ann. Math. Stud., 6.

Чёрч [1956] fChurch A.), Introduction to mathematical logic, Princeton University Press, Princeton, N. J. (Русский перевод: Чёрч A., Введение в ма-тсмагическЮ логику, ИЛ, М., 1961.)

Читэм [1965] (Cheatham Т. е.), The TGS-II translator-generator system. Information Processing-65 (IFIP Congress), 592-593.

Читэм [1966] (Cheatham T. E.), The introduction of definitional facilities into higher level programming languages, Proc. AFIPS Fait Joint Computer Conference, 30, 623-637.

Читэм [1967] (Cheatham T. E,), The theory and construction of compilers (2nd ed.). Computer Associates, Inc., Wakefield, Mass.

Читэм Стэндиш 11970] (Cheatham Т. E., Standish Т.), Optimization aspects of compiler-compilers, ACM SlGPLAN Notices, 5:10, 10-17.

Читэм, Сэттли [1964] (Cheatham Т. Е., Sattiey К.), Syntax directed compiling, Proc. AFIPS Spring Joint Computer Conference, 25, 31-57.

"Чулик [1966] (Culik K.). Well-translatable languages and ALGOL-like languages, в сб. „Formal Language Description Languages for Computer Programming", под ред. Steel Т. В., North-Holland, Amsterdam, 76-85. (PyccKHili перевод: Чулик Хорошо переводимые языки и языки типа АЛГОЛ, Научио-техн. информ., сер. 2, № 3, 21-23.)

Чулик [1968] (Culik К-, И), Contribution to deterministic top-down analysis of context-free languages, Kybernetika, 4:5, 422-431.

°Чулик, Кохеп [f973] (Culik K-, 11, Cohen R.),, LR regular grammars-an extension of LR (fe) grammars, J. Сотр. Syst. Sci., 7:1, 66-96.

Шварц [1967] (Schwartz J. T. (ed.)). Mathematical aspects of computer science, Proc. Symp. Appl. Math., 19.

"Шевченко В. В. [1974], Об одном подходе к проблеме синтаксического анализа. Кибернетика, 4, 30-38.

Шеннон, Мак-Карти [1956] (Shannon С. Е., McCarthy J. (eds.)), Automata studies, Princeton University Press, Princeton, N. J. (Русский перевод: Автоматы (сб. статей), ИЛ, М., 1956.)

Шепердсон [1959] (Shepherdson J. С), The reduction of two-way automata to one-way automata, IBM J. Res., 3, 198-200. (Русский перевод: Шепердсон Дж., Сведение двусторонних автоматов к односторонним автоматам, Кибернетический сборник, вып. 4, ИЛ, М., 1962, стр. 92-98.)

"Школьник [1973] (Schkolnik М.), Labelled precedence parsing, Q)nf. Record ACM Symposium on Principles of Programming Languages, 33-40.

"Школьник [1974] (Schkolnik M.), The equivalence of reducing transition languages and deterministic languages, Comm. ACM, 17:9, 517-519.

Шорре [1964] (Schorrc D. V.), META II, a syntax oriented compiler writing language, Proc. ACM National Conference, 19, pp. Dl.3-1 -Dl.3-11.

Шоу [1970] (Shaw A. C), Parsing of graph-representable pictures, J. ACM, 17:3, 453-481.

Штрассен [1969] (Strassen V.), Gaussian elimination is not optimal, Numer. Math., 13:4, 354-356. (Русский перевод: Штрассен Ф., Алгоритм Гаусса не оптимален. Кибернетический сборник, новая серия, вып. 7, „Мир", М., 1970, стр. 67-70.)

"Шумей А. С. [1975], Об использовании слабых отношений предшествования между определяющими символами в синтаксическом анализаторе. Кибернетика, 5, 69-76.

"Шумей А. С, Зонис В. С. [1975], О синтаксическом анализе по однозначным грамматикам, Программирование, 3, 22-29.

Шютценберже [1963] (Schutzenberger М. Р.), Оп context-free languages and pushdown automata, Inform, and Control, 6:3, 246-264.

Эваис [1964] (Evans A., Jr.), An ALGOL 60 compiler, Ann. Rev. Autom. Program., 4, 87-124.

Эви [1963] (Evcy R. i.). Applications of pushdown-store machines, Proc. AFIPS Fall Joint Computer Conference, 24, 215-227.

Эйкель [1973] (Eickel J.), Methoden der syntaktischen Analyse be{ formalen Sprachen, Lecture Notes in Econom. and Math. Systems, 78, 37-53.

Эйкель и др. [1963] (Eickel J., Paul M., Bauer F. L., Samelson K-). syntax-controlled generator of formal language processors, Comm. ACM, 6:8, 451-455.

Элспас и др. [1971] (Elspas В., Green М. W., Levitt К. N.), Software relia-bility. Computer, 1, 21-27.

Эигелер [1971] (Engeler E., ed.). Symposium on semantics of algorithmic languages, Lecture Notes in Mathematics, Springer, Berlin.

Эрланд, Фишер [1970] (Irland M. I., Fischer P. C), A bibliography on computational complexity, CSRR 2028, Dept. of Applied Analysis and Computer Science, Univ. of Waterloo, Waterloo, Ontario.

Эрли [1968] (Earley J.), An efficient context-free parsing algorithm. Ph. D. Thesis, Carnegie-Mellon Univ., Pittsburgh, Pa. См. также Comm. ACM, 13:2, (1970), 94-102. (Русский перевод: Эрли Дж., Эффективный алгоритм анализа контекстно-свободных языков, в сб. „Языки и автоматы", изд-во „Мир", М., 1975, стр. 47-70.)

"Эрли [1975] (Eariey J.), Ambiguity and precedence in syntax description, Acta Inform., 4:2, 183-192.

Эттингер [1961] (Oettinger A.), Automatic syntactic analysis and the pushdown store, в сб. Structure of Language and its Mathematical Concepts, Proc. 12th Symposium on Applied Mathematics, 104-129.

"Яжабек и Кравчик [1975] (Jarzabek S., Krawczyk Т.), LL-regular grammars. Inform. Proces. Letters, 4:2, 31-37.

Яигер [1967] (Younger D. H.), Recognition and parsing of context-free languages in time n. Inform, and Control, 10:2, 189-208. (Русский перевод: Янгер Д. X., Распознавание и анализ контекстно-свободных языков за время п, в сб. „проблемы математической логики", изд-во ,iMHp", М., 1970, стр. 344-362.)

УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ

а £ А, аА П 0 12 44: Л !3

ЛВ, AczB 13 {xP(x)}3

A\JB. АГ\В, А-В, А 14

SiA) 15 АхВ 16

R+, R* 18, 19 /: Л-22 Л, А, А* 24 i?,oi?3, 25 е 27 а 27

\х\ 28

L» L+, Z.* 29 Л-1 30 Р vQ, PaQ,

Р, P--*Q 33

a-f 6 a-ft, a (булевы операции) 36 fl 48

afP 49, 515. 534

irep (T), rrep (Г) 61

LOAD, ADD, MPY, STORE 83

G = (N, 2, P, S) 105

L(G) 106, 121, 516. 527

120. 121, 515, 516, 526 Л -PilPal • i06.

Go 108

n-l-n, p*, 0, e (регулярные выражения) 124. 125

1 „ l / P 135. 136, 194,

199, 255, 258, 302, 326. 327, 340 -342 379, 404, 409, 412,415,417- 419, 453, 534, 545

L{M) 136, 195, 409, 412, 416, 419, 535

qp, q=p 148 Da 160, 161

Li/[-2 160 =Ф„ 167

P = iQ, 2, Г, 6, q„ Zo, F) !93 L-(P) 201

r = (N, S, Д, i?, 5) 248 Л-a, fi 249

=>?, =>i =r 249 т(Г) 249

M-IQ.S, Д, 6, F) 254 t(M) 255, 258, 545 M{L), M~L) 257 тЛР) 258

.Ts, Гг 373 iR*", i?", i?ii2 284 ,-=ф. =ф,-, „=Ф, =»п 297. 307

rf, Г; 298 Ajf, Мг 299 Г?, Г;. 302 Д1?. М;. 302 Lp, Lf 307

Tic 314 FlRSTft(a), FlRST{a) 337 /(n)-0 {.?(«)) 355 (A a.p, ll 359

FOLLOWi?(P). FOLLOW(P) 383 Lie ft La 388

=ф„ zJc 403 Wi (V) k~a->X 4!1

„+a.p, u] 433 EFF?{a), EFF(a) 433

GOTO (V, X) 438

< •> 456, 457, 547, 549

jlLBC/D 513

Л->B[C, />] 525

УКАЗАТЕЛЬ ЛЕММ, ТЕОРЕМ И АЛГОРИТМОВ

Номер леммы

2.10

2.11

2.12

2.13

2.14

2.15

2.16

2.17

2.18

Стр.

125 129 129 130 131 131 132 141 141 142 149 166 166 175 178 182 185 186

Номер леммы

2.19

2.20

2.21

2.22

2.23

2.24

2.25

2.20

2.27

2.28

2.29

2.30

2.31

Стр.

186 198 200 201 202 203 207 209 212 215 228 229 229 260 260 262 269 275

Номер леммы

3.10

3.11

3.12

3.13

3.14

3.15

Стр.

275 275 276 276 278 278 279 280 280 308 331 332 332 334 343 364 389 434

Номер леммы

6.10

6.11

6.12