Главная Промышленная автоматика.

Грамматика LR{k) 304, 373, 421, 423-452, 478, 482, 484, 503

- LR(1) 424, 463, 503, 504

- неоднозначная (ambiguous) [68, 189, 231-236, 239, 317, 546 см. также Гра.мма-тика однозначная

- не укорачивающая см. Грамматика контекстно-зависимая и Грамматика без е-правил

- общего вида (unresfricted) [05-112, П8-120, 122

- обратимая (unique invertible) 422, 450, 457, 503-506, 547, 557

- ограниченного контекста (bounded context) 505, 507

- ограниченного правого контекста (bounded riglit context) 481-488, 503-507

- однозначная (unambiguous) [19, 168. 231-233, 240, 364-366, 384, 447, 449, 460 . 476 . 485, 549

- операторная (operator) 190, 492

- операторного предшествования (operator precedence) 493-497, 503. 504, 507

- (1,1)-0ПК ((I,I)-bounded-right-contexl) 484, 503

- остовная (skeletal) 496, 507

- (2,1)-предшествования ((2,!)-precedence) 480. 503

- правоанализируемая (right parsable) 304-306, 450

- праволинейная (right linear) III, 119, 131-133, 143-145, 230, 237

- праворекурсивная (right recursive) 178

- порождающая графы (graph, web) 98-102

- нополиеииая (augmented) 424, 481

- предшествования (precedence) 456, 457, 463, 480

- приведенная (proper) 175

- простая LL(1) (simple LL(!)) 376, 408, 409

- простая смешанной стратегии предшествования (simple mixed-strategy precedence) 491, 503, 507

- простого предшествования (simple precedence) 455-463, 474-479, 549, 565

- псевдоразделенная 409, 410, 414, 420

- разделенная см. Грамматика простая LL(1)

- расширенного предшествования (extended precedence) 463-469, 478-480, 484, 505

- регулярная (regular) 145, 557

- рекурсивная (recursive) 178

- сильно LL(k) (strong LL(*)) 384, 388

- слабого предшествования (weak precedence) 469-477, 479, 491, 492, 503-506

- слаборазделенная 410, 411, 414

- смешанной стратегии преднгествования (mixed-strategy precedence) 488-492, 503, 507

- с самовставлеиием (self-embedding) 240

- Г-каионического предшествования {Г-canonical precedence) 507-510

- Г-остовная (T-skeletal) 509

- Хомского (Chomsky) см. Грамматика Граф (graph) 52-68

- ациклический (ориентированный), (directed acyclic, dag) 54, 138

- нагруженный см. Граф помеченный

- иеориентироваииьш (undirected) 66

- переходов (автомата) (transition) см. Диаграмма конечного автомата

- помеченный (labelled) 53, 57

- связный (неориентироваиный) (connected) 66

- сильно связный (strongly connected) 54

- упорядоченный (ordered) 56 --ациклический (dag) 57

Дерево (tree) 55, 61, 62, 71-73, 81-87, 100, 10!, 319, 487-490

- вывода (derivation) см. Дерево разбора

- неориентированное (undirected) 66, 67

- разбора (parse) 164-168,- 205-207, 250-252, 307, 43!, 432, 519-521

Дерево синтаксическое (syntax) см. Дерево разбора

- упорядоченное (ordered) 57, 58 Диаграмма

- конечного автомата (transition graph) 138, 255, 256

- синтаксическая {syntactical diagram) 414, 415 Диаграммер (diagrammer) 415-418

Длина (length)

- вывода (of а derivation) 107

- цепочки (of а string) 28

ДМП-автомат см. Автомат с магазинной памятью детерминированный Дополнение (множества) (complementation) 14, 216, 226, 237, 541 Допускать (цепочку, язык) (accept) 115, 136, 195, 201 Дуга (в графе) (arc, edge) 53

е-правило (грамматики) {е-production) 111, 177, 178, 340, 402 е-такт (распознавателя) (e-move) 194, 218

Заглядывание вперед (lookahead) 337, 344. 370,371, 373-375, 378,402, 421,424,450 Законы де Моргана (Dc Morgans laws) 23

Замкнутость (относительно операций) (closure) 152, 224-226, 257, 266 Замыкание (отиошеиия) (closure)

- рефлексивное и транзитивное (reflexive and transitive) 19

- транзитивное (transitive) 18, 62-65, 68

Запись польская (Polish notation) см. Выражение префиксное

Идентификатор (indentifier) 76-80. 116, 286, 287, 289-293

Иерархия Хомского (Chomsky hierarchy) 112

Индекс

- грамматики, языка 239, 240

- отноп1ения эквивалентности (index) 17

Исправление ошибок (error correction) 75, 90-93, 96, 337, 338 , 407, 446, 451, 452, 480

Исчисление высказываний (propositional calculus) 35, 50 Итерация (языка) (closure) 29, 225

- маркирований (marked) 240

- позитивная (positive) 29

КЗ-грамматика см. Грамматика контекстно-зависимая Код (code)

- объектный (object) 75, 82, 242

- промежуточный (intermediate) 75, 82-87 Компилятор (compiler) 75-96, 351. 408

- компиляторов (compiler-compiler) 96, 351 Композиция (отношений) (composition) 25, 281 Конкатенация {concatenation) 27, 29, 225, 238

- маркированная (marked) 240

Конфигурация (configuration) 49, 115, 135, 194, 254, 258, 326, 340, 378,379, 404. 411, 412, 415, 418. 422, 423, 453, 534, 545

- допускающая (accepting) см. Конфигурация заключительная

- заключительная (final) U5, 135, 195, 201, 255, 258, 259, 379

- зацикливающая (looping) 213-216

- начальная (initial) 115, 135, 194, 326, 340, 379



Грамматика LR(k) 304, 373, 421, 423-452, 478, 482, 484, 503

- LR{!) 424, 463, 503. 504

- неоднозначная (ambiguous) 168, 189. 231-236, 239, 317, 546 слг. также Грамматика однозначная

- неукорачнвающая см. Грамматика контекстно-зависимая и Грамматика без е-правнл

- общего вида (unrestricted) !05-!12, 118-120, 122

- обратимая (unique invertible) 422, 450, 457, 503-506, 547, 557

- ограниченного контекста (bounded context) 505, 507

- ограниченного правого контекста (bounded right context) 481-488, 503-507

- однозначная (unambiguous) !19, 168, 231-233, 240, 364-366, 384, 447, 449, 460, 476, 485, 549

- операторная (operator) !90, 492

- операторного предшествования (operator precedence) 493-497, 503, 504, 507

- (1,1)-0ПК ((I,I)-bounded-right-context) 484, 503

- остовная (skeletal) 496, 507

- (2,1)-предшествования ((2,l)-precedence) 480, 503

- правоаналнзируемая (right parsable) 304-306, 450

- праволинейная (right linear) lU. !19, 131-133, 143-145, 230, 237

- праворекурснвная (right recursive) 178

- порождающая графы (graph, web) 98-102

- пополненная (augmented) 424, 481

- предшествования (precedence) 456, 457, 463, 480

- приведенная (proper) !75

- простая LL(1) (simple LL(1)) 376, 408 , 409

- простая смешанной стратегии предшествования (simple mixed-strategy precedence) 491, 503, 507

- простого предшествования (simple precedence) 455-463, 474-479, 549, 565

- псевдоразделенная 409, 4!0. 414, 420

- разделенная см. Грамматика простая LL(1)

- расширенного предшествования (extended precedence) 463-469, 478-480, 484, 505

- регулярная (regular) !45, 557

- рекурсивная (recursive) 178

- сильно LL{k) (strong LL{k)) 384, 388

- слабого предшествования (weak precedence) 469-477, 479, 49!, 492, 503-506

- слаборазделснная 410, 4!1, 414

- смешанной стратегии предшествования (mixed-strategy precedence) 488-492, 503, 507

- с самовставлен нем (self-embedding) 240

- Т"-канонического предшествования (T-canonical precedence) 507-5!0

- Г-остовиая (Г-skeletal) 509

- Хомского (Chomsky) см. Грамматика Граф (graph) 52-68

- ациклический (ориентированный) (directed acyclic, dag) 54, !38

- нагруженный см. Граф помеченный

- неориентированный (indirected) 66

- переходов (автомата) (transition) см. Диаграмма конечного автомата

- помеченный (labelled) 53, 57

- связный (неориентированный) (connected) 66

- сильно связный (strongly connected) 54

- упорядоченный (ordered) 56 --ациклический (dag) 57

Дерево (tree) 55, 61, 62, 7!-73, 81-87, 100, 101, 319, 487-490

- вывода (derivation) см. Дерево разбора

- неориентированное (undirected) 66, 67

- разбора (parse) 164-168, 205-207, 250-252, 307, 431, 432, 519-52! 598

Дерево синтаксическое (syntax) см. Дерево разбора

- упорядоченное (ordered) 57, 58 Диаграмма

- конечного автомата (transition graph) 138, 255, 256

- синтаксическая (syntactical diagram) 414, 415 Диаграммер (diagrammcr) 415-418

Длина (length)

- вывода (of а derivation) !07

- цепочки (of а string) 28

ДМП-автомат см. Автомат с магазинной памятью детерминированный Дополнение (множества) (complementation) 14, 216, 226, 237, 541 Допускать (цепочку, язык) (accept) 115, 136, 195, 201 Дуга (в графе) (arc, edge) 53

е-правило (грамматики) (e-production) 111, 177, 178 , 340, 402 с-тпкт (распознавателя) (e-move) 194, 2!8

Заглядывание вперед (lookahead) 337, 344, 370,371, 373-375, 378,402, 421,424,450 Законы де Моргана (De Morgans laws) 23

Замкнутость (относительно операций) (closure) 152, 224-226, 257, 266 Замыкание (отношения) (closure)

- рефлексивное и транзитивное (reflexive and transitive) 19

- транзитивное (transitive) 18, 62-65, 68

Запись польская (Polish notation) см. Выражение префиксное

Идентификатор (indentifier) 76-80, !16, 286, 287, 289-293

Иерархия Хомского (Chomsky hierarchy) 112

Индекс

- грамматики, языка 239, 240

- отношения эквивалентности (index) 17

Исправление ошибок (error correction) 75, 90-93, 96, 337, 338, 407, 446, 451, 452, 480

Исчисление высказываний (propositional calculus) 35, 50 Итерация (языка) (closure) 29, 225

- маркирования (marked) 240

- позитивная (positive) 29

КЗ-грамматнка см. Грамматика контекстно-зависимая Код (code)

- объектный (object) 75, 82, 242

- промежуточный (intermediate) 75, 82-87 Компилятор (compiler) 75-96, 351, 408

- компиляторов (compiler-compiler) 96, 35! Композиция (отношений) (composition) 25, 28! Конкатенация (concatenation) 27, 29, 225, 238

- маркированная (marked) 240

Конфигурация (configuration) 49, 115, 135, 194, 254, 258, 326, 340, 378,379, 404, 411, 412, 415, 418 , 422, 423 , 453, 534 , 545

- допускающая (accepting) см. Конфигурация заключительная

- заключительная (final) 115, 135, 195, 201, 255, 258, 259, 379

- зацикливаюн1,ая (looping) 2!3-216

- начальная (initial) 115, 135, 194, 326, 340, 379



Конфликт

- oTHOiueiiHH предшествования (precedence conflict) 472, 473

- правил 389, 393

Крона (дерева разбора) (frontier) 165-168 КС-грамматика см. Грамматика контекстно-свободная Куст (в дереве) 206

Лексема (token) 76-79, 283-296 Лемма Огдена (Ogdens lemma) 220-223

- о разрастании (pumping lemma)

- (для КС-языков) 223, 224

- (для регулярных множеств) 152

Лента входная (распознавателя) (input tape) 113-115 Лист (в графе) (leaf) 54

ЛО-автомат см. Автомат линейно ограниченный

Магази[[ (pushdown list) 114,. 192-194, 378

Макрос синтаксический (syntax macro) 265, 266, 559-562

Маркер концевой (endmarker) ИЗ, 304, 326, 378, 381, 409, 412, 415, 418, 457, 522,

525, 541 Матрица (matrix)

- предшествования (precedence) 457-459

- смежностей (adjacency) 62, 63 Машина (machine)

- анализирующая (parsing) 533-538, 540

- Тьюринга (Turing) 42, 49-51, 120, 123 --универсальная (universal) 50

- с произвольным доступом к памяти (random access) 154, 189, 354, 355, 372, 528, 530, 531 см. такоюе Операция элементарная (алгоритма)

Множество (set) 11-30

- -бесконечное (infinite) 22, 26

- вполне упорядоченное (well ordered) 24, 30

- знаменательных символов (token) 508

- конечное (finite) !2, 22

- линейное (linear) 239

- непротиворечивое LR(ft)-ситуаций (consistent set of LR(ft) items) 442, 443

- полулинейное (semi-linear) 239

- пустое (empty) 12

- регулярное (regular) 124-163, 218, 219, 225, 236-238, 257, 266, 269, 270 400. 478

- рекурснннсе (recursive) 42, 48, 112, 119, 120

- рекурсивно перечислимое (recursively enumerable) 42, 48, 111, 112, 118, 268, 558

- счетное (coimtable) 22, 26

- универсальное (universal) 14 --упорядоченное (ordered) 20 МГ1-автомат сл. Автомат с магазинной памятью

Неоднозначность (ambiguity) 231-236 см. также Грамматика неоднозначная Язык неоднозначный

- конечной степени (finite) 371

- семаитячсская (semantic) 307, 308

Неодиозначпость существенная (inherent) см. Язык неодиозиачиый Нетерминал (nonterminal) 105, 120, 248, 512-514

Обратимость (unique invertibility) см. Грамматика обратимая Обращение

- гомоморфизма (inverse homomorphism) 30

- цепочки или языка (reversal) 27, 144, 153 Объединение (union) !4, 225, 229-231, 238, 541

- маркированное (marked) 240

ОК-грамматика см. Грамматика ограиичеииого контекста

Операция элементарная (алгоритма) (elementary operation) 355, 357, 364-366, 447

ОПК-грамматика см. Грамматика ограниченного правого контекста Определение регулярное (regular definition) 285, 286 Оптимизация кода (code optimization) 75, 88-90

Основа (правовыводимой цепочки) (handle of а right sentential form) 205, 206, 429.

431-434, 455-457, 543 Остов (rpacfta) (spanning tree) 67 Отображение (mapping) см. Функция Отношение (relation) 16-26

- антисимметричное (antisymmetric) 21

- асимметричное (asymmetric) 20

- иррефлексивное (irreflexive) 20

- конгруэнтности (congruence) 158

- обратное (inverse) 16, 22

- операторного предшествования (operator precedence) 493

- предшествования Вирта-Вебера (Wirth-Weber precedence) 456, 457 --Колмерауэра (Colmerauer precedence) 547-549

- рефлексивное (reflexive) 17

- симметричное (symmetric) 17

- транзитивное (transitive) 17

- эквивалентности (equivalence) 17, 18, 24, 149-151, 157, 158 ---правоинвариантное (right invariant) 157, 158

Память (распознавателя) (memory) 113-115 Пара цепочек выводимая (translation form) 246-249 Перевод (translation) 71, 242-245, 258, 379, 380, 545

- регулярный (regular) см. Преобразование конечное

- синтаксически управляемый (syntax directed) 74, 83-88, 246-253, 260-282, 499, 569-574

--простой (simple) 253, 260-263, 271-274, 282, 298, 569-574

Пересечение (множеств) (intersection) 14, 225, 226, 230, 237, 54!

ПЛ/1 (PL/1) 74, 76, 78, 559

ПЛ 360 (PL 360) 565-569

Подстановка (языков) (substitution) 224, 225

Позиция (в цепочке) (position) 220

Покрытие (грамматики) (cover) 309-311, 314, 315

- левое (left) 310, 314, 315, 345

- правое (right) 310, 314, 315, 345 Порядок (как отношение) (order) 20, 21

- лексикографический (Icxicografic) 25, 331, 343

- линейный (linear) 21, 25, 59, 60

- обратный (вершин дерева) (postorder) 59

- полный (well) 24, 30

- прямой (вершин дерева) (preorder) 58





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 [99] 100 101

0.0021