Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 123
Текст из файла (страница 123)
Дерева разбора — пеориентированнос (ппб(гсс(еб) 66, 67 — разбора (рагье) 164 — 168, 205 — 207, 250 — 252, 307, 431, 432, о|9 — 52! 598 Дерево скнтакснческое (ьуп1ах) сн. Дерево разбора — упорядоченное (огбегеб) 57, 58 Диаграмма — конечного автомата (|гапьйюп йгарЬ) $38, 255, 256 — синтаксическая (ьуп|зсИса! 6(айгзгп) 414, 415 Дкагрэммср (В(эйгапппсг) 415 — 4!8 Длина (1епй!Ь) — вывода (о$ а депчаИоп) 107 — цепочкн (о$ а Мппй) 28 ДМП-автомат си.
Автомат с магазноной памятью детерминированный Дополнение (множества) (сошр|епюп$аИоп) 14, 216, 226, 237, 541 Допускать (цспочку, язык) (ассер1) $15, $36, !95, 201 Дуга (в графе) (агс, ег|йе) 53 з-правила (грзмматкки) (е-ргог$псИоп) 111, $77, !78, 340, 402 е-такт (распознавателя) (е-пюче) $94, 218 Заглндыванис вперед (|оо1гаЬсаг|) 337, 344, 370, 37 $, 373 — 375, 378, 402, 421, 424, 450 Законы де Моргана (Г|е Могйап'ь |зчь) 23 Замкнутость (относительно операций) (с!омпе) 152, 224 — 226, 257, 266 Замыкание (отношсния) (с!гпг1гс) — рефлекснзное н трзнэнтивпое (гойех|ке апб |гапь1Иче) 19 — транзктивное (|гапьШте) !8, 62 — 65, 68 Запись польская (РоИьЬ по$апоп) гл. Выражение префикснов Идеитнфикатор (1пбеп$гйег) 76 — 80, ! 16, 286, 287, 289 — 293 Иерархия Хгэиского (Спошьйу ЫегагсЬу) 1$2 Индекс — грамматики, языка 239, 240 — отношеннн эквнвалентностн ((пг(ех) 17 Исправление ошибок (еггог сопесИоп) 75, 90 93, 96, 337, 338, 407, 446, 451, 452, 480 Исчисление вьюкаэываннй (ргороИИопа! са|сц|пь) 35, 50 Итерация (языка) (с|оьпге) 29, 225 — маркирования (гпагйед) 240 — позитивная (роз|1(че) 29 КЗ-грамматнка см.
Грамматика контекстно-зависимая Код (сопе) — объектный (оЬ|ес1) 75, 82, 242 — промежуточный ((п(егшеб(а(с) 75, 82 — 87 Компилятор (сагпр||ег) 75 — 96, 351, 408 — компиляторов (сошрйег-сошр||ег) 96, 351 Композиция (отношсннй) (сошроь|Иоп) 25, 281 Конкатенация (сопса1епаИоп) 27, 29, 225, 238 — маркированная (шэгйеб) 240 Конфигурация (соп!!йога((оп) 49, 1! 5, !35, 194, 254, 258, 326, 340, 378, 379, 404, 4!1, 412, 415, 418, 422, 423, 453, 534, 545 — допускающая (эссер((пй) сл.
Конфигурация заключительная — заключительная (Ипа1) 1 16, !35, 195, 2($1, 255, 258, 259, 379 — зацнилнзз|ощзя (|оор|пй) 213 — 2$6 — начальнан (шй|а1) 115, 135, $94, 326, 340, 379 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Конфликт — отношений предшествовзння (ргсссдспсс сопй)с1) 472, 473 — правил 389, 393 Крона (дерева разбора) (1гапИег) !65 — !68 КС.грамматика см. Грамматика контекстно. свободная Куст (в дереве) 206 Лексема ()о1сеп) 76 — 79, 283 — 296 Лемма Огдена (Ойбеп'в 1епкпа) 220 — 223 — о разрастании (рнвр!пй 1епнпа) — (для КС-языков) 223, 224 — (для рсгулярных множеств) !52 Лента входная (распознавателя) (!прн! )аре) ! 13 — ! 15 Лист (в графе) (1еа1) 54 ЛО-автомат см.
Автомат линейно ограниченный Магаэкп (рцвйбояп 1пй) 114,,!92 — !94, 378 Макрос синтаксический (вуп1ах пшсго) 265, 266, 559 — 562 5!эркер концевой (епбвагйег) 1!3, 304, 326, 3?В, 381, 409, 412, 415. 418, 457, 522, 52о, 541 Матрица (гпа1г)х) — предшествования (ргесебепсе) 457 — 459 — смежностей (зб!зсспсу) 62, 63 Машина (васЫпе) — анализирующая (ранйпй) 533 — 538, 540 — Тыарипга (Тнппй) 42, 49 — 51, !20, 123 — — универсальнэя (нпгчегвз!) 50 — с произвольным доступом к памяти (гзпбов асеев) 154, 189, 354, 355, 372, 528, 530, 531 см. также Операция элементарная (алгорнтма) Миакество (веЦ 11 — -30 —.
бесконечное ()пПш!е) 22, 26 — вполне упорядочсниас (веИ агдегеб) 24, ЗΠ— знаменательных символов (1ойеп) 508 — конечное (ИпИе) )2, 22 — линейное (Ипсаг) 239 — непротиворечивое 1 ))(й)ситуаций (сопвпйеп! ве1 Ы 1К(!г) Иевв) 442, 443 — полулинейное (вев)-Ипеаг) 239 — пустое (евр)у) 12 — регулярное (гейц!аг) 124 — !63, 2!8, 219, 225, 236 — 238, 25?, 266, 269, 270, 400, 478 — рекурснннсе (гссцгвгче) 42, 48, 112, 119, 120 — рекурсивно перечнслимае (гесшзгче)у епцвегаЫс) 42, 48, 111, )12, 118, 268, 558 — счетное (сони)аЫе) 22, 26 — универсальное (ггп!чепэ)) 14 — упорядочекное (отбегай) 20 М)1-автомат см.
Автомат с магазинной памятью Неоднозначность (агпЬ1)цИу) 231 — 236 см. пикжз Грамматика неоднозначная и Язык неоднозначный — конечной степени (ИпИе) 371 — семнптячсская (юпапИс) 307, 308 Неоднозначность сущсственная (!пйегеп1) см. Язык неоднозначный Нетерминал (поп)егпцпа)) 105, )20, 248, 512 — 514 Обратимость (цпнйне !пчегПЬ!ГИу) см.
Грамматика обратимая Обращение — гомоморфизма (!пчегве ЬововогрЫмп) ЗΠ— цепочки или языка (гечегва1) 27, 144, 153 Объединение (цпюп) 14, 225, 229 — 231, 238, 541 — маркированное (вагйеб) 240 ОК-грамматика см. Грамматика ограниченного коитеиста Операция элементарная (алгоритма) (е)сгпсп!эту орегаИоп) 355, 357, 364 — Збб, 447 ОПК.грамматика см. Грамматика ограниченного правота контекста Определенно регулярное (геди)ш беИпИ)ап) 285, 286 Оптимизация хода (сабе орИгп)кабан) 75, 88 — 90 Основа (правовыводимой цепочки) (Ьапд!е о1 а пйЫ зеп1епИа! )агв) 205, 206, 429, 431 — 434, 455 — 457, 543 Остов (графа) (врали)пй 1гее) 67 Отображение (варр!нй) см.
функция Отношение (ге)аИоп) 16 — 26 — аятисимметричнас (апИвупцпщпс) 21 — асимметричное (авупцпе1пс) 20 — иррефлексивное ()гге)!ех!че) 20 — кангруэнтнасти (сапдгнспсе) !58 — обратное ()пчегве) !6, 22 — операторного предшествозания (орегэ1аг ргесебепсе) 493 — предшествовання Вирта †Вебе (Ттг)г)Ь-1)геЬег ргесебепсе) 456, 457 — — Колмерауэра (Са!гпегэцег ргесес1епсе) 547 †5 — рефлексивное (геИехгче) !7 — симметричное (вуптше!пс) 17 — транэитивнае (1гапвгИче) 17 — эквивалентности (ейшча)енсе) 17, !8, 24, 149 †1, 157, 158 — — правоннзариантное (г!8)в) )пчаг)ап1) 157, 158 Намять (распознавателя) (вевогу) 113 — 115 Пара цепочек выводимая (1гапв!аИоп )огв) 246 — 249 Перевод (1гапв)аНоп) 71, 242 — 245, 258, 379, 380, 545 — рсгуляриый (тейп!аг) см.
Преобразование конечное — синтаксически управляемый (вуп)ах д)тес!еб) 74, 83 — 88, 246 — 253, 260 — 282, 499, 569 †5 — — простой (вцпр!е) 253, 260 †2, 271 †2, 282, 298, 569 †5 Пересечение (множеств) ()п)егвесИоп) 14, 225, 226, 230, 237, 541 ПЛ?1 (Р1.Л) 74, 76, 78, 559 ПЛ 360 (Р!. 360) 565 — 569 Подстановка (языков) (зпЬвГИабоп) 224, 225 Позиция (в цепочке) (ровИюп) 220 Покрытис (грамматики) (сочег) 309 — 311, 314, 3!Б — левое (!еИ) 3!О, 314, 315, 346 — правое (г!ВЫ) 3!О, 314, 315, 34о Порядок (как отношение) (агбег) 20, 21 — лексикографнческнй ()сх!сойгабс) 25, 331, 343 — линейный (1гпещ) 21, 25, о9, 60 — обратный (вершин дерева) (ров!агбег) 59 — полный (же11) 24, 30 — прямой (вершин дерева) (ргеогбег) 58 60! ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Список (1|й) — магазинный (риьЬВочгп) см. Магазин — разбора (рагье) 359 ССП-грамматика, см.
Грамматика смешанной стратегии предшествовання Степень (вершины графа) (бейгее) — по входу (|п-) 54 — — выходу (ои|-) 54 СУ-перевод см. Перевод синтаксически управляемый Суффикс (цепочки) (зиЯ|х) 28 Схема перевода ((гапз!аИоп ьсЬепе) см. Перевод Сцепление (сопса1епаИоп) см. Конкатенация Таблица (|аЫе) — идентификаторов (ьупЬа|) см. Таблица имен — инеи (ьугпЬо1) 75, 79, 80, 92, 93, 287 — разбора (рагье) 352 — управляющая разбором (рагйпй) 379, 385 — 387, 391 — 395, 404, 405 гм. также 19(А)-таблица — (.(.((г) 389 — 391, 394, 395 — 1.9(А) 426, 427, 444 — 446, 451 ТАГ-система (Тай эуз1еп) 42, 122 Такт (распознавателя) (шоче) 115, 136, 194 Тезис Черча — Тьюринга (СЬигсЬ-Тип|пй гйедь) 43 Теорема (1Ьеогеп) 32 — Парика (Раг!ЬЬ'ь) 239, 241 Терминал (в грамматике) (1егпипа|) 106, 120, 514 Тачка наименьшая неподвижная (п1п|па! 11хеь( роьп1) 127, 129 — 131, !44 — 146, 185, 186 Транслятор (Иапь!а1ог) 77, 246, 247 см.
также Преобразователь Трансляция (1гапь1аИап) см. Перевод Узел (графа) (паг1е) см. Вершина (графа) Упорядочение (огбег!пд) см. Порядок (как отношение) Уравнения (еь(иайапь) — определяющие (для КС-языков) (беИп!пй) !85, 186 — с ре~улярными коэффициентами (гейи1аг ехргеьь(аьь) 126 — 133, 144, 146 Уровень (вершины дерева) (!ече!) см. Высота (вершины дерева) Устройство управляющее с конечной памятью (1(пИе сап!го1) 114, 498 см, ьлнкже Состояние (распознавателя) Факторизация левая (!еЦ 1ас(опий) 385 Форма (1опп) — Бахуса — Наура (Васйиь — Ыаиг) 74 — нормальная Грейбах (Оге!Ьасб попив!) 182 — 188, !90, 274, 315, 402, 406 — — слабая 409 — нормальная Хамского (Спошьйу пагпа1) 176, 177, |90, 273, 274, 310, 311, 314, 352, 40! Фортран (ВОЙТЫЛЫ) 70, 74, 77, 79, 236, 286, 346, 347, 559 Функция (|ипсИоп) 21, 22, 25 — бнектнвная (ЬцесИче) 22 — взаимно однозначная см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
