![]() |
|
Главная Промышленная автоматика. Грамматика 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.002 |