Англо-русский глоссарий по методам грамматического разбора

© П.Н.Дубнер, 2000

absolute address
абсолютный адрес
Число, адресующее реальную физическую ячейку памяти компьютера.
См. тж. относительный адрес.

absolute code
абсолютный код
Программа, которую можно выполнить без дополнительной обработки, поскольку все адреса в ней являются абсолютными.
См. тж. перемещаемый код.

accept action
допускающее действие
Одно из четырех действий, производимых во время восходящего разбора, которое выполняется, когда ему удалось вывести целевую лексему грамматики. В этом случае парсер возвращает в целевую программу семантическое значение выведенной лексемы (проще говоря, всевозможные структуры, которые он настроил в процессе вывода). Таким образом, допускающее состояние – последнее действие, выполняемое при разборе, причем лишь один раз.
Другое название – принимающее.

accepting state
допускающее состояние
Состояние конечного автомата, при достижении которого входная строка объявляется принадлежащей языку, распознаваемому этим автоматом.
Другое название состояния – принимающее. Для краткости иногда говорят допуск.

action
действие
При описании грамматики в правила включают фрагменты кодов на целевом языке, которые выполняются тогда, когда обнаружена цепочка, соответствующая очередному элементу правила. Эти коды в YACC'е и называют действиями. Между прочим, действия, указанные в начале правила, выполняются до начала разбора.

action (of a parser)
действие (парсера)
Во время разбора парсер производит одно из следующих четырех принципиальных действий: сдвиг, свертка, принятие и отвержение. Конечно, в любой практической реализации их гораздо больше.

actual parameter
фактический параметр
Параметр, который использован в вызове подпрограммы.
См. тж. формальный параметр.

address space
адресное пространство

1. Совокупность адресов памяти, с которыми может работать программа.
2. Память, отведенная программе или пользователю.
3. Память, которую можно адресовать при имеющемся формате команд.

alias
псевдоним
Дополнительное имя объекта. Всякий раз, когда объект обозначается более, чем одним именем, все имена являются псевдонимами.

aliasing
создание псевдонима
Создание еще одного имени объекта в тексте программы или во время ее исполнения.

alphabet
алфавит
Совокупность литер, или символов, используемых при определении языка: язык – множество цепочек надалфавитом.
Термин литераиспользуется при работе с «обычными» алфавитами, состоящими из букв, цифр, знаков пунктуации и т.д. Термин символ употребляется в более абстрактных ситуациях, например, для обозначения нетерминала.

ambiguity
неоднозначность
Ситуация неоднозначна, если возможна не одна ее интерпретация.

ambiguous grammar
неоднозначная грамматика
Грамматика неоднозначна, если предложение языка можно вывести, или разобрать, не единственным способом. Это проявляется, в частности, в том, что в ней найдется по крайней мере одно предложение, для которого имеется более одного дерева разбора.

ancestor
предок
Узел дерева, который расположен на пути от корня дерева к данному узлу. Непосредственный предшественник узла или непосредственный предшественник одного из его предков.
См. потомок.

assembler
ассемблер
Программа, предназначенная для трансляции с языка, близкого к машинному.
См. транслятор.

associativity
ассоциативность
Характеристика порядка, в котором нужно выполнять операции, когда рядом располагаются операции с одинаковым приоритетом (старшинством); в некотором смысле – способ расстановки группирующих скобок. Большинство операций левоассоциативны, скажем, выражение a*b*c интерпретируется как ((a*b)*c). Но, скажем, операция “возведение в степень” правоассоциативна: a^b^c=(a^(b^c)).

ATN
ATN Аббревиатура: augmented transition net

augmented transition net
расширенная сеть переходов
Формализм, используемый при описании парсеров, особенно для естественных языков. Такая сеть аналогична конечному автомату, расширение состоит в том, что с дугами, задающим переходы, могут быть сопоставлены произвольные проверки. В результате появляется возможность рекурсивно вызывать подграмматики и строить необходимые структуры по мере перехода от узла к узлу.

available
готовый
Эпитет, характеризующий выражение, значение которого было вычислено на пути графа вычислений, предшествующем текущему узлу.

backpatching
доопределение
Уточнение адреса метки, которая была упомянута до ее фактического определения.

Backus-Naur form
форма Бэкуса-Наура
Форма Бэкуса-Наура – это синтаксис, который изобретен для представления контекстно-свободных грамматик, описывающих языки программирования. Изобретен (как легко догадаться, Бэкусом и Науром) для описания языка АЛГОЛ-60.

bag
мультимножество
Примерно то же, что и обычное множество. Отличие состоит в том, что одинаковые элементы могут входить в мультимножество несколько раз.

base address
базовый адрес
Адрес начала области данных. К этому адресу прибавляют относительный адрес, или смещение, и получают абсолютный адрес.

basic block
базовый блок
Кусок программы, в котором инструкции исполняются только последовательно: внутри куска отсутствуют метки (могут быть только в самом начале) и ветвления (могут быть только в самом конце).

benchmark
батарея тестов
Совокупность задач и/или программ, используемых для тестирования производительности компьютера. Как водится, имеется несколько таких совокупностей, одна хлеще другой. Перефразировка известной шутки: “В компьютерной индустрии имеется три вида лжи: просто ложь, ложь наглая и, наконец, батареи тестов”. К числу наиболее известных батарей относятся: whetstone, dhrystone, rhealstone. О происхождении буквы ‘h’ в этих названиях см. в статье о whetstone.
 

bignum
bignum
Сокращение от big number (большое число). Часто, используется для обозначения результата выполнения арифметических операций с произвольной точностью.

binary operator
бинарная операция
Операция называется бинарной, если для получения результата ей нужны два операнда. Ну, и как, стало понятнее?
На самом деле, подобные фразы произносятся не в качестве определения, а для того, чтобы проиллюстрировать словоупотребление.
Само же понятие объясняется с помощью примеров. Так, в приличных языках программирования непременно имеются операции сложения (‘+’) и вычитания (‘-‘), которые, как рассказывали в школе, работают с двумя числами.

binding
связывание
В большинстве языков программирования при вычислении выражений исполнение арифметических операций следует стандартным алгебраическим соглашениям: при отсутствии скобок возведение в степень производится до умножения (и деления), умножение до сложения (и вычитания), сложение до сравнения. В таких случаях говорят, что возведение в степень связывает сильнее умножения, которое, в свою очередь, связывает сильнее сложения, которое, в свою очередь, связывает сильнее сравнения. Имеется в виду, что операция объединяет операнды в некий целостный объект.
Операнд, находящийся между двумя операциями, относится к той из них, которая связывает сильнее. Про нее говорят еще, что ее старшинство выше.
Есть языки (например, знаменитый APL), в которых все операции равноправны и выполняются в порядке встречаемости, слева направо.
См. тж. ассоциативность.

bit vector
битовый вектор
Последовательность булевских значений (0 и 1), представленных битами одного или нескольких слов. Является эффективным представлением подмножеств не слишком обширного множества.

block
блок
См. базовый блок.

BNF
БНФ
Аббревиатура: форма Бэкуса-Наура.

bottom-up parsing
восходящий разбор
Метод грамматического разбора, при котором слова из входного потока сравниваются с правыми частями продукций грамматики. При этом дерево разбора строится снизу вверх (к верху, к корню).
В некоторых источниках так и говорят: разбор снизу-вверх.

BSS
BSS
В некоторых ассемблерах директива (иногда говорят – псевдооперация), используемая для выделения блока памяти (сокращение от Block Starting with Symbol – блок, начинающийся с символа) .

busy
занятая
Эпитет, применяемые к переменной, значение которой понадобится позже – во время исполнения программы. Происхождение названия ясно: такую переменную нельзя использовать как временную, для хранения промежуточных значений.

call by name
вызов по имени
Способ передачи параметра (в функцию/подпрограмму), при котором достигается эффект текстуальной подстановки фактического параметра на место формального.

call by reference
вызов по ссылке
Способ передачи параметра (в функцию/подпрограмму), при котором в подпрограмму передается адрес фактического параметра. Благодаря этому изменения параметра “видны” вне подпрограммы.

call by value
вызов по значению
Способ передачи параметра (в функцию/подпрограмму), при котором в подпрограмму передается копия фактического параметра. Из-за этого изменения параметра “не видны” вне подпрограммы.

canonical form
каноническая форма
Стандартизованная форма представления чего-либо. Например, для логических формул каноническими являются дизъюнктивная и конъюнктивная нормальные формы.
Применяется как одна из реализаций принципа “экономии мышления” Маха.

cascading errors
каскад ошибок
Так говорят, когда какая-либо ошибка является причиной возникновения множества других. Скажем, если забыть описать переменную, то всякий раз, когда эта переменная встречается в тексте, компилятор должен индицировать ошибку. Некоторые компиляторы так и делают. Другие, более интеллектуальные, стараются указать лишь ошибку источник.
Часто в подобных ситуациях говорят о наведенных ошибках.

character
литера
Элемент алфавита.

Chomsky hierarchy
иерархия Хомского
Иерархия формальных языков: регулярные, контекстно-свободные, контекстно-зависимые, без ограничений. Каждый следующий член иерархии включает предыдущий.

CISC
CISC
Аббревиатура: complex instruction set computer (что часто переводят как “компьютер с полным набором команд”).

class
класс
В объектно-ориентированном программировании множества аналогичных объектов объединяются в класс. Скажем, рубль у меня в кармане представляется объектом, который является членом класса ДенЗнак.
В современных языках программирования (ну, конечно, в первую очередь имеются в виду С++ и Java), понятию “класс” придается более ограничительный, скорее грамматический, смысл. Это является постоянным источником множества недоразумений и служит любимым объектом разнообразной критики.

class variable
переменная класса
В объектно-ориентированных языках так называют переменную, которая служит именем объекта (конкретного экземпляра) класса. Иногда имеют в виду переменную, сопоставленную со всем классом объектов, скажем, хранящую количество объектов класса.
Но никогда не имеют в виду переменную, локальную для класса. Почему?..

closed procedure
замкнутая процедура
Процедура, коды которой отделены от остального текста программы; процедура активизируется вызовом, по окончании ее работы происходит возврат к месту вызова.
См. открытая процедура. Ср. встраивание кода.

code generation
генерация кода
Фаза работы компилятора, на которой генерируется исполнимый код.

code motion
перенос кода
Так говорят, когда компилятор переносит код с того места, где он находится в тексте программы. Стандартный пример: некое вычисление, не зависящее от параметра цикла, естественно выполнить за его пределами.

column-major order
расположение по столбцам
Метод расположения массива в памяти, при котором в последовательных ячейках сначала последовательно располагаются элементы первого столбца, затем второго и т.д.
См. расположение по строкам.

compiler
компилятор
Транслятор, предназначенный для языков высокого уровня.

compiler-compiler
компилятор компиляторов
Программа, на входе которой – формальное описание синтаксиса и семантики языка, на выходе – компилятор с этого языка. Стандартный пример: YACC.

compile-time
время компиляции
Относящийся к тому, что происходит во время компиляции программы, уж извините. В частности, здесь может происходить частичная оптимизация.

complement of a set
дополнение множества
В теории множеств дополнением множества A называется совокупность всех элементов, не принадлежащих A. Обратите внимание: чтобы это определение было осмысленным, необходимо иметь “совокупность всехэлементов”. Дополнение множества A обозначается множеством разных способов. Вот два из них: ~A, S\A (S – так называемый универсум, т.е. та самая “совокупность всех возможных элементов”). Старшинство операции дополнения выше, чем у разности, пересечения и, тем более, объединения..

complex instruction set computer
CISC-архитектура
См. CISC

compiler compiler
компилятор компиляторов
Система, предназначенная для (полу)автоматической подготовки компилятора по формальным спецификациям. Наиболее известным таким средством (хотя, как известно, и не вполне отвечающим называнию) является YACC.
За годы, прошедшие с момента его появления, были разработаны многие другие компиляторы компиляторов, с более удобными и более мощными входными языками, с развитой диагностикой и средствами отладки.

concatenation
конкатенация; катенация
Операция над двумя строками, результат которой – строка, состоящая из литер первой строки, за которыми следуют литеры второй.

concatenation of languages
конкатенация языков
Язык, каждое предложение которого образовано конкатенацией предложений из первого и второго.

condition code register
регистр кодов условий
Регистр центрального процессора, описывающий результат последней операции – арифметической или сравнения. Содержит, как правило, биты для >0, =0, <0, а кроме того – бит переноса и бит переполнения.

conflict
конфликт
Конфликты возникают во время грамматического анализа , когда парсер не может принять однозначное решение об интерпретации очередного входного символа.
Наиболее изученными являются конфликты, возникающие при восходящем разборе : сдвиг-свертка и свертка-свертка.
Конфликты возникают либо потому, что грамматика и в самом деле неоднозначна, либо потому, что парсер «не умеет» заглянуть достаточно далеко, чтобы разрешить его. В последнем случае грамматику, как правило, можно переписать так, чтобы избежать конфликта. Стандартным источником конфликтов являются пустые продукции.
Придумано множество способов разрешения конфликтов, среди них наиболее известным способом является, по-видимому, введение правил старшинства.

context-free grammar
контекстно свободная грамматика
Формальная грамматика со следующим характеристическим свойством: в левой части любой продукции может встретиться лишь один нетерминал. То же самое по-другому: смысл нетерминала не зависит от контекста, в котором он используется.
См. иерархия Хомского.

context-free language
контекстно свободный язык
Язык, для описания которого можно построить контекстно-свободную грамматику.
См. иерархия Хомского.

context-sensitive grammar
контекстно зависимая грамматика
Формальная грамматика, продукции которой имеют вид , где A – нетерминал,. Цепочки изадают контекстправила, они не изменяются при его применении.
См. иерархия Хомского.

directed acyclic graph
направленный ацикличный граф
Как следует из названия, направленный граф (совокупность узлов и направленных дуг) без циклов (последовательности дуг, которая начинается и заканчивается в одном узле).
Стандартная аббревиатура: DAG.

dangling reference
висячая ссылка
Так называют переменную (как правило, указатель), содержащую адрес памяти, которая уже возвращена системе. Чтобы не говорить о семействе alloc из стандартной библиотеки Си, рассмотрю другой стандартный пример, который также является «вечно зеленым» источником ошибок: в подпрограмме мы создаем автоматический объект, после чего передаем «наружу» его адрес.

data area
область данных
Непрерывная область памяти, задаваемая адресом начала (иногда говорят: базовый адрес) и длиной. Доступ к ней осуществляется по так называемому относительному адресу, образуемому из базового адреса и смещения.

dead code
“мертвый код”; недостижимый код
Часть программы, которая не исполняется никогда. Как правило, появляется при использовании конструкций типа IF (FALSE) …

defined
(пред)определенная
Так говорят о переменной, которая получила значения до обсуждаемой точки программы.

dereference
разыменование
Операция, применяемая к указателям, т.е. переменным, предназначенным для хранения адресов. Ее результат – данные, адресуемые указателем.

derivation
вывод
Список шагов – последовательность применений грамматических правил, в результате которой предложение языка выводится из грамматики.

derivation tree
дерево вывода
Помеченное дерево представляет вывод в КС-грамматике, если: (а) корень дерева помечен начальным символом S; (б) если узел помечен символом A, а его сыновья - символами X₁, ..., X_n, то AX₁ | ... | X_n является продукцией грамматики.
Для КЗ-грамматик вывод изображается, вообще говоря, не деревом, а более сложным орграфом.
См. тж. дерево разбора.

descendant
потомок
Процитирую Кнута [т.1, п. 2.3]:
“Стандартная терминология для структур типа дерева обязана своим происхождением …родовой схеме. Говорят, что каждый корень является отцом корней своих поддеревьев и что последние являются братьями между собой и сыновьями своего отца. Корень же всего дерева не имеет отца. …Ясно, что можно распространить эту терминологию и далее… Некоторые авторы используют “женскую” терминологию: “мать, дочь, сестра” вместо “отец, сын, брат”, но по некоторым причинам слова мужского рода предпочтительнее. Другие авторы, желая поддержать равенство полов, пользуются нейтральными словами “родитель, отпрыск, сородич”. В любом случае мы употребляем слова предок и потомок для обозначения родства, которое может простираться на несколько уровней дерева.” (стр. 385 русского издания 1976 года)

deterministic finite automaton
детерминистский конечный автомат
Классический конечный автомат: входной алфавит, множество состояний, функция переходов (по текущему состоянию и входному символу выдает вполне определенное новое состояние).
Аббревиатура: ДКА.

DFA
ДКА
См. детерминистский конечный автомат

dhrystone
dhrystone
Батарея тестов, используемая для проверки производительности процессора на операциях со строками.
В некоторых словарях предлагается смешной перевод “тест сухая точилка”.
См. whetstone.

difference of two sets
разность двух множеств
Разность двух множеств A и B есть множество A-B, состоящее из тех элементов A, которые не принадлежат B.

disambiguating rules
правила разрешения неопределенностей
Правила, которые в ситуации неоднозначности позволяют выбрать одну из альтернатив. Стандартный пример: правила, задающие приоритет операций.

discipline
дисциплина
Совокупность правил, позволяющая определить последовательность действий для достижения штатных целей. Пример: для получения расходных материалов необходимо заполнить известный список запросов, после чего передать их в известную службу. Этот же термин применяется в программировании – для характеристики процесса обработки запросов, например.

display
дисплей
В записи активации – массив указателей на записи активации включающих блоков. Используется для доступа к переменным, определенным в этих блоках. С очевидными изменениями та же идея используется при организации доступа к процедурам/функциям.

dominator
доминатор
Базовый блок A программы является доминатором блока B, если любой путь от входа программы к блоку B проходит через блок A.

dynamic scope
динамическая область видимости
Соглашение языка, согласно которому время “жизни” переменной (когда к ней можно обращаться из любой процедуры) зависит от последовательности исполняемых операторов (что бы это ни значило). Стандартный пример такого языка – Лисп.
Ср. лексическая область видимости.

dynamic type checking
динамическая проверка типа
Проверка типов значений переменных во время исполнения. Так делается в старом добром ЛИСПе и в современных объектно-ориентированных языках.
См. статическая проверка типов.

embedded language
встроенный язык
Язык, исполнение операторов которого активизируется из другого языка – путем запуска интерпретатора или компилятора. Стандартный пример: SQL, встраиваемый куда попало.

encapsulation
инкапсуляция
Способ программирования, при котором структура объекта остается “невидимой” пользователю, а доступ к его “частям” осуществляется путем вызова специальных функций, совокупность которых принято называть интерфейсом объекта. Основным достоинством при этом объявляется то, что программа, оперирующая с объектом лишь через его интерфейс, не зависит от его структуры. Считается необходимым свойством качественного программирования. Более чем спорно!
См. упрятывание информации.

enumerate
перечислять
Как правило, речь идет о порождении всех элементов некоего множества.

error action
действие при (по) ошибке
Одно из стандартных действий парсера.
Предпринимается им, когда встречена лексема, не допустимая в текущем состоянии. Дальнейшее поведение парсера теория не определяет, хотя есть некоторые наработки о восстановлении после ошибки.

error recovery
восстановление при ошибке
Действия, предпринимаемые парсером в случае обнаружения ошибки. Общая теория на данный момент отсутствует. Одна из возникающих проблем – каскад ошибок.

event driven parser
парсер, управляемый событиями
Стандартный подход состоит в том, что вызывающая программа передает правление парсеру и ждет, когда он закончит работу, расправившись с фразой, данной ему в качестве параметра.
Парсер, управляемый событиями, не обрабатывает фразу целиком. Взамен, вызывающая программа инициализирует его, после чего вызывает, задавая очередную лексему в качестве входного параметра. При каждом вызове парсер соответствующим образом меняет свое состояние (вызывает нужные продукции, достаивает дерево разбора, пополняет таблицы символов и т.д.) и возвращает управление вызывающей программе, когда ему понадобится следующая лексема. Этот подход очень удобен при организации взаимодействия с лексическим анализатором.
Говорят, он пригодился в параллельных архитектурах.

execution stack
стек исполнения
Стек, куда помещаются записи о процедурах или блоках, активированных во время исполнения программы, написанной на языке программирования, допускающем рекурсию и/или блочную структуру.

external fragmentation
фрагментация внешней памяти
Так говорят, когда внешняя (по отношению к программе) память, используемая в качестве источника при динамических запросах, состоит из свободных блоков, перемежающихся занятыми. Опасность связана с тем, что суммарный объем свободной памяти может быть достаточно велик, но на очередной запрос памяти придется ответить отказом из-за отсутствия свободного блока нужной длины.

FA
КА
См. конечный автомат

FAR
КА-распознаваемый
Распознаваемый конечным автоматом. Регулярный язык.

finite automaton
конечный автомат
Абстрактная конструкция, задаваемая совокупностью входных символов, множеством состояний, правилами перехода из состояния в состояние в зависимости от очередного входного символа, а также (не всегда и не обязательно) алфавитом выходных символов и правилом "выдачи" такого символа в зависимости от очередного состояния. Функционирует, как легко догадаться, в дискретном времени.
Используется как модель компиляции: считаем, что множество выходных состояний включает лишь два символа "допускаю" и "отвергаю", фиксируем начальное состояние, для каждого символа фразы делаем переходы в соответствии с конструкцией автомата. Если в конце достигаем символа "допускаю", считаем входную фразу распознанной, в противном случае – содержащей ошибки. Конечно, можно обойтись и без выходного алфавита, объявив какие-то из состояний автомата допускающими, какие-то – отвергающими.
Аббревиатуры: русская – КА, английская – FA.

finite automaton recognizable
распознаваемый конечным автоматом
См. КА-распознаваемый.

finite state machine
машина с конечным числом состояний
См. конечный автомат.

flush
выгрузить
Очистка буфера путем записи или передачи его содержимого.

formal grammar
формальная грамматика
Формальная спецификация языка.
Традиционно формальная грамматика задается непересекающимися множествами терминальных T и нетерминальных N символов, начальным нетерминальным символом S и множеством правил, позволяющих из терминальных и нетерминальных символов строить (синоним: выводить) фразы языка. Традиционно правила имеют вид продукций.
Традиционные вопросы: полнота грамматики (позволяет ли она получить все фразы языка), ее специфичность (позволяет ли она вывести только фразы, входящие в язык), эквивалентность двух грамматик (одинаковы ли языки, определяемые ими) и т.д. Традиционные ответы: эти задачи алгоритмически неразрешимы.
В компиляторах компиляторов формальное описание грамматики дополняется разнообразной информацией – о том, что нужно сделать, когда очередной символ распознан; о том, что делать, когда закончен анализ очередного правила и т.п.

formal parameter
формальный параметр
Параметр, фигурирующий в списке аргументов при определении процедуры/функции.
См. фактический параметр.

forward reference
ссылка вперед
Ссылка на метку, которая еще не появилась в тексте программы.

fragmentation
фрагментация
Термин, относящийся к (системной) памяти, которая в процессе работы оказывается разбитой на блоки, сумма которых может быть достаточной, но каждый из них слишком мал.
См. внешняя фрагментация.

fringe
листва; крона
Совокупность листьев (концевых, или терминальных, узлов) дерева.

garbage collection
сборка мусора
Действия с памятью, в результате которых в систему возвращаются ее освободившиеся куски. При этом стараются добиться, чтобы подсистема сборки мусора боролась с фрагментацией.
Этим термином обозначается: 1. собственно сборка мусора; 2. вызов подсистемы, занимающейся сборкой мусора; 3. Выполнение сборки мусора.

GC
GC
Аббревиатура для garbage collection.

generator
генератор
Процедура, результатом работы которой являются элементы последовательности. При каждом вызове она возвращает очередной элемент. Пример: генераторы (псевдо-)случайных чисел.

grammar
грамматика
Способ описания языка.
См. формальная грамматика.

granularity
детализация
Уровень модульности разработки или программы.

graph
граф
Граф – это пара <S, T>, где S – множество узлов, T – совокупность переходов между узлами. Вы, конечно, понимаете, что предыдущая фраза не является полноценным определением!
Переходы могут считаться направленными (граф в этом случае тоже называется направленным [ordered или, иногда, directed]), или ненаправленными. В теоретических работах предпочитают прилагательное oriented (ориентированный) и перевод орграф.

graph coloring
раскраска графа
Алгоритм присваивания "цветов" узлам графа так, чтобы: (а) любые два непосредственно связанных узла были разных "цветов"; (б) количество использованных "цветов" было минимальным.
Используется в компиляторах при разнообразных оптимизациях. Пример: использование регистров – цвета при этом соответствуют регистрам, узлы графа – переменным.

groupware
групповая разработка
Название процесса разработки программ группой людей, которые работают одновременно, причем могут находиться в разных местах и общаются через сеть.

handle
основа
В методах восходящего разбора так называют (под)строку, которую предстоит свернуть.

handle pruning
отсечение основы
При восходящем разборе так называют процесс удаление основы из стека и ее замены на нетерминал или структуру данных, представляющую фразу.

higher-order logic
логика высшего порядка
В логике предикатов первого порядка квантификация возможна только по элементам универсума (так, мы говорим: "для всех элементов …, обладающих свойством …). Более мощная (часто говорят, выразительная) логика получается, если допустить выражения типа "для всех свойств …, таких что …". Еще более мощные логики пока что не известны общественности.

implicit parameter
неявный параметр
Параметр, передаваемый в подпрограмму, но не задаваемый программистом явно. Пример: адрес возврата.

information hiding
упрятывание информации
Способ писать программы, при котором общение с объектами производится лишь через функции, прямой доступ к частям (полям) объекта запрещается. Его достоинством объявлено то, что разработанная программа оказывается не зависящей от деталей реализации. Считается, что этот способ – один из признаков объектно-ориентированного подхода и что он позволяет добиваться истинной модульности программ.
На мой взгляд, достоинства упрятывания сильно преувеличены, а уж независимость сколько-нибудь сложного алгоритма от деталей реализации – это просто миф.
См. тж. инкапсуляция.

inheritance
наследование
Наличие процедуры или поля данных благодаря определению в объемлющем класса.

inherited attribute
наследуемые атрибуты
Атрибуты узла в дереве разбора, которые выведены из контекста, в котором возник этот узел.
См. тж. синтезируемые атрибуты.

inlining
встраивание кода
Вставка кода подпрограммы прямо в место вызова. Так поступают для ускорения работы подпрограммы, поскольку не тратится время на ее вызов. Имеет смысл, когда подпрограмма очень проста – настолько, что длина ее кода сравнима с кодами, организующими ее вызов.

inorder
слева направо
Порядок прохождения бинарного дерева, рекурсивно определяемый следующим образом: сначала проходится левое поддерево, затем – корень, после чего – правое поддерево. В переводе книги Кнута (т.1) назван обратным.

insertion
вставка
Действие, в результате которого новый элемент оказывается на нужном месте в упорядоченной последовательности – массиве, списке или чем-нибудь аналогичном.

insertion sort
сортировка вставками
Метод сортировки, в котором элементы последовательно просматриваются слева направо и каждый элемент вставляется на нужное место в отсортированной (левой) части, а правая не отсортированная сдвигается вправо. Хорош для почти сортированных множеств.

intermediate code
промежуточный код
См. промежуточный язык .

intermediate language
промежуточный язык
Язык представления программы во время компиляции; примеры: деревья и тетрады . Из промежуточного языка производится преобразование в целевой .

interpreted code
интерпретируемый код
Форма представления программы, которую читает и исполняет интерпретатор. Ну, как? Боюсь, яснее не стало.

intersection
пересечение
Пересечение множеств A и B, A&B или просто AB, это множество, элементы которого принадлежат как A, так и B. Приоритет этой операции ниже, чем у дополнения, но выше, чем у объединения и разности. Операция левоассоциативна .

interval
интервал
Совокупность операторов программы, исполняемых последовательно.

intrinsic function
встроенная функция
Простая функция, код которой встраивается в нужное место, а не вызывается из него. Стандартный пример: абсолютное значение.

keyword
ключевое слово
Слова, используемые для обозначения лексем с специфическим смыслом, как правило, терминалов. Пример: зарезервированные слова языка программирования.

killed
битый
Подвыражение, ранее вычисленное значение которого, изменилось в результате изменившегося определения какой-либо из его частей.

language
язык
Подмножество слов в данном алфавите. См. формальная грамматика.

lambda calculus
лямбда-исчисление
Формализм, придуманный А.Черчем для работы с рекурсивными функциями. Считается основой LISP’а, одного из старинных языков программирования, особенно популярного среди специалистов по искусственному интеллекту.

LALR
LALR
Происходит от “Look Ahead Left Recursive” (леворекурсивный с заглядыванием).
Метод грамматического разбора, считается менее мощным, чем «чистый» LR, зато нуждается в таблицах меньшего размера. Из-за этого практически во всех генераторах парсеров используется именно LALR. Имеются LR-грамматики, которые не поддаются LALR-разбору, однако, их, как правило, легко преобразовать.

last-in, first-out
стек
Структура, реализующая дисциплину обслуживания «первым вошел – последним вышел». Стандартная аббревиатура: LIFO (=first in last out).
См. очередь .

left associative operator
левоассоциативный оператор
Оператор (арифметический, логический), обладающий следующим свойством: если в выражении встречаются два оператора подряд (разделенных подвыражениями, конечно), первым выполняется тот, который левее.
См. право-ассоциативный оператор .

left factoring
левая факторизация
Способ преобразования грамматики, позволяющий избавиться от левосторонней рекурсии .

left recursion
левосторонняя рекурсия
При нисходящем разборе продукция , правая часть которой (консеквент, помните?) начинается с нетерминала, располагающегося слева(антецедент!), вызывает бесконечный рекурсивный цикл, который и называется левосторонней рекурсией. Иногда так же называют и саму продукцию.
Для простоты часто говорят о левой рекурсии.

left-most derivation
лево-ориентированный вывод
Способ вывода, при котором на каждом шаге заменяется самый левый нетерминал.
Некоторые авторы используют эпитеты левый и левосторонний .

left-sentential form
левосторонняя сентенциальная форма
Сентенциальная форма , полученная лево-ориентированным выводом.

LEX
LEX
Популярная программа, предназначенная для построения лексических анализаторов по совокупностям регулярных выражений . Предназначена в пару еще более знаменитой программе YACC . Имеется целый класс ее наследников.

lexeme
цепочка
Цепочка литер, отнесенная к одному из грамматических классов. Скажем, имя переменной.
Иногда – имеют в виду то же, что и token. См. обсуждение русского (ха-ха!) термина лексема .

lexical
лексический
1. Информация о словах и/или символах в словаре или таблице символов. 2. Информация, которую можно получить статическим анализом программы, т.е. не запуская ее.

lexical analysis
лексический анализ
Сканирование входного потока литер и выделение из него базисных элементов языка (идентификаторов переменных, чисел и т.п.). Подготовка информации для грамматического разбора. Как правило, при этом используется регулярная грамматика .

lexical analyzer
лексический анализатор
См. сканер .

lexical scoping
лексическая область видимости
В языках с блочной структурой переменная «видна» (т.е. ее имя может фигурировать в тексте) только в блоке, где она определена, и во вложенных в него блоках. Кроме того, если в блоке определена переменная с тем же именем, что и в объемлющем, то «видимой» является та, которая определена позже. Когда закончится область ее видимости, переменная из объемлющего блока снова станет «видимой».
Ср. динамическая область видимости .

linear grammar
линейная грамматика
Почти регулярная грамматика : у нее нетерминал в правой части продукции не обязательно расположен в конце.

link editor
редактор связей
Программа, которая переводит переместимые коды в абсолютные. Часто ее объединяют с загрузчиком.

live variable
<хороший перевод???>
Переменная, значение которой понадобится где-нибудь позже во время исполнения программы.

load time
время загрузки
1. относится к тому, что происходит во время редактирования связей и загрузки (ошибка загрузки); ср. время компиляции , время исполнения . 2. ну, и конечно, время, уходящее на редактирование связей и загрузку.

loader
загрузчик
Системная программа, которая читает программу в абсолютных кодах, загружает ее в память и запускает, передавая управление на ее входную точку. Часто объединяется с редактором связей .

location counter
счетчик памяти
Счетчик, используемый для последовательной адресации памяти под коды или данные во время ассемблирования или компиляции программы.

logic
логика
В прикладных областях употребляется в фразах типа: «логика работы алгоритма/программы» или «Твоя логика подобна…» (продолжение фразы придумайте сами). Не путать с математической логикой!

lookahead token
текущая лексема
Текущая входная лексема. Часто ее не сдвигают в входной буфер сразу же – предварительно она действует как «катализатор», вызывая свертку множества правил.

look up
просмотр
Поиск в таблице символов. Думаю, слово search здесь не используется по историческим причинам.

LR parsing
LR разбор
Парсер типа LR(k) осуществляет восходящий грамматический анализ, используя для определения следующего действия не более k основ. Когда k=1, пишут просто LR.

marked rule
помеченное правило
Имеется в виду самое обычное правило (правая часть продукции), с которым связан маркер, позволяющий узнать, какая часть правила уже сопоставлена и какой должна быть очередная лексема, если ожидается сопоставление всего правила.

mask out
замаскировать; отключить
1. Обнулить ненужные биты, выполнив операцию AND с подходящей маской.
2. Запретить прерывание, очистив (обнулив) соответствующие биты в регистре маскировки прерываний.

match
отождествлять; сопоставлять
Так говорят о процессе проверки совпадения (двух) строк символов (произвольных, не обязательно букв). Далеким обобщением этого процесса является унификация в ПРОЛОГе.

materialize
сохранить
Записать в память. Как правило, относится к разрушаемым данным – например, к содержимому регистров.

memory leak
утечка памяти
Так называют процесс потери динамической памяти из-за того, что программист забывает вернуть ее системе. Она, естественно, становится недоступной, в результате чего программа может "вывалиться" из-за нехватки памяти, хотя на самом деле памяти - немеренно.

metaclass
мета-класс
В объектно-ориентированном подходе так иногда называют класс, задающий структуру нескольких классов. В С++ ему соответствует шаблон класса.

method
метод
В объектно-ориентированном подходе – связанная с классом процедура, которая выполняет действия, предписанные при поступлении определенного сообщения. Метафора, оказавшаяся, на мой взгляд, не слишком полезной.

MIMD
MIMD
Векторно-конвейерная архитектура процессора: с множеством потоков данных и множеством потоков команд. Разные инструкции могут производится над разными действиями одновременно.
См. тж.. SIMD .

modularity
модульность
Мечта! Попытка разбить проблему или программу на обозримые куски, с которыми легко обращаться.

multiset
мультимножество
Множество, в котором каждый элемент может встретиться несколько раз.
Синоним: bag (не bug!).

name equivalence
эквивалентность по имени
Согласно некоторым определениям два типа считаются эквивалентными тогда и только тогда, когда совпадают их имена.
Ср. структурная эквивалентность.

negative zero
отрицательный нуль
Когда числа представляются в обратном двоичном коде, число нуль задается совокупностью единичных битов.

non-associative
неассоциативный
Бинарный операторназывается неассоциативным, если последовательность x y z не поддается разумной интерпретации. Если эта последовательность означает (xy)z, оператор называется лево-ассоциативным, а если x(yz), то право-ассоциативным .
См. еще ассоциативность .

nondeterministic
недетерминистский
Эпитет, характеризующий ситуацию, в которой можно поступать множеством способов.

nondeterministic finite automaton
недетерминистский конечный автомат
Конечный автомат, функция переходов которого с каждым состоянием сопоставляет подмножество состояний. См. детерминистский конечный автомат .

nonterminal symbol
нетерминальный символ; нетерминал
Символ, используемый при определении грамматики, не входящий в алфавит, над которым строится язык; переменная.

nonterminal token
нетерминальная лексема
Лексема, которая получается в результате свертки последовательности лексем, которые сопоставимы с грамматическим правилом, и замены их подходящей лексемой. Нетерминальные лексемы не следует путать с терминальными и/или входными литерами.

nonvolatile register
защищенный регистр
Регистр, значения которого должны быть сохранены во время вызова подпрограммы.

null production
пустая продукция
Продукция с пустой правой частью. Часто их называют еще-продукциями (читается «эпсилон-продукция»).
Такие продукции чрезвычайно удобны, когда нужно сказать, что некоторый элемент необязателен. Поскольку, однако, они усложняют разбор, их часто запрещают. Грамматику всегда можно переписать без пустых продукций, заплатив за это ясностью текста и естественностью интерпретации продукций.

object
объект
Основное (а, значит, неопределимое) понятие объектно-ориентированного программирования. Как правило, означает структуру данных, представляющую объект "реального мира", и/или указатель на класс, к которому принадлежит этот объект.

object language
целевой язык
Выходной язык компилятора. Скажем, для знаменитого YACC 'а целевым языком является Си, а для большинства компиляторов – ассемблер.

offset
смещение
Положение элемента относительно начала области данных.

open coding
открытое кодирование
См. встраивание кода .

open procedure
открытая процедура
Процедура, тело которой прямо вставляется в место вызова. Ср. замкнутая процедура. .

operator
оператор
Символ, обозначающий операцию в выражении.

optimization
оптимизация
Преобразование программы, в результате которого надеются добиться кода с тем же поведением, но требующего меньшей памяти и/или меньше времени выполнения.

oracle
оракул
Процедура (как правило, увы, воображаемая) которая дает верные ответы на верно заданные вопросы.
Ну, конечно, не забудьте про известную СУБД с этим именем.

overloading
перегрузка
Процесс введения омонимов операторов, в результате которого область действия оператора расширяется. В конкретном месте программы будет выбран смысл оператора, наилучшим образом подходящий для конкретных типов данных. Так, одной и той же литерой ‘+’ обозначается как сложение разных типов чисел, так и конкатенация строк.
Не уверен, что повышение читабельности программ компенсирует трудности тонкого контекстного анализа текста программы при поиске интерпретации операции, особенно при возникновении ошибок.

padding
выравнивание
Вставка неиспользуемых кусков для получения кусков памяти одинаковой длины.

parse tree
дерево разбора
Структура данных, которая позволяет увидеть, каким образом предложение выводится, проследить происхождение каждого символа в нем.
Компиляторы расширяют его вспомогательной информацией, необходимой для генерации промежуточного представления.
См. тж. дерево вывода.

parser
парсер
Программа или, чаще, процедура, осуществляющая грамматический анализ фразы.

parser generator
генератор парсеров
Программа, которая по грамматике языка, написанной на специальном языке, генерирует парсер, позволяющий провести грамматический разбор входного предложения. Наиболее известным генератором до сих пор является YACC , за ним следует его чуть более новая (но тоже древняя) версия BISON. В них описание грамматики сопровождается описанием действий, которые нужно предпринять, когда распознана очередная фраза языка.
В последние двадцать лет появилось несколько систем, позволяющих генерировать парсеры, куда более изощренные. Целевым языком большинства является Си. Впрочем, сейчас практически все они переделаны так, что целевыми являются С++ и Java.

parsing
(грамматический) разбор
Процесс чтения предложения исходного языка и определения его структуры. Является одной из фаз компиляции .

partial correctness
частичная корректность
Свойство программы: гарантируется выдача правильного результата, если выполнение программы завершится. Ср. сугубая корректность .

partial evaluation
частичное оценивание
Способ оптимизации, при котором программа становится длиннее (скажем, за счет разворачивая циклом) и оцениваются (вычисляются) объекты, которые оказываются константными уже на этапе компиляции. В итоге получается, быть может, более длинная программа, но зато работающая быстрее и/или лучше подходящая для распараллеливания.

partition
разбиение
Разбиение множества – это совокупность его непересекающихся подмножеств, которые в сумме дают исходное множество. Между прочим, один из способов задать его – построить дерево, листья (терминальные узлы) которого будут соответствовать элементам разбиения; должно быть ясно, такое дерево не единственно.
При разработке компиляторов это понятие применяется, как правило, при работе с множествами литер.

pass
проход
Фаза работы компилятора или ассемблера, в течение которой обрабатывается весь текст программы (в исходном виде или в одном из промежуточных представлений).

PC
СК; ПС
1. счетчик команд (program counter). 2. персональный компьютер (personal computer).

peephole optimization
локальная оптимизация
Вид оптимизации, выполняемый на сгенерированным кодом. Производится линейный проход, в котором исследуются короткие куски кода. При этом оптимизация достигается довольно ограниченная; например, можно убрать инструкции перехода к следующей команде или заменить инструкцию перехода более короткой «пустой» (NOP).

phase of compiler
фаза компиляции
Большой кусок работы компилятора, как правило, включающий в себя анализ всей программы. Примеры: синтаксический анализ, оптимизация, генерация кода.

phrase
фраза
Цепочка терминалов , которая принадлежит языку, определяемому грамматикой с фразовой структурой .

phrase structure grammar
грамматика с фразовой структурой
См. грамматика .

polymorphic function
полиморфная функция
Функция, которая «умеет» работать с несколькими типами данных.

polymorphic type
полиморфный тип
Абстрактный тип данных, например, список, который можно реализовать множеством способов (скажем, как массив, или и в самом деле список – односвязный или двусвязный), который, к тому же может применяться для представления элементов разной природы (скажем, список целых чисел, или список объектов, представляющих сотрудников фирмы).

postcondition
постусловие
Совокупность утверждений, которые должны стать истинными после того, как закончено выполнение оператора, функции в программе, правила грамматики и т.д. Часто бывает выражено в виде формулы логики первого порядка.

postincrement
<НЕ ЗНАЮ ХОРОШЕГО ПЕРЕВОДА>
Свойство процессора: значение индексного регистра автоматически увеличивается на фиксированную величину после чтения. В результате он указывает на следующий элемент массива.

postorder
снизу вверх
Порядок прохождения бинарного дерева, рекурсивно определяемый так: сначала проходится левое поддерево, затем – правое поддерево, после чего – корень. В переводе книги Кнута (т.1) назван концевым.

precedence
старшинство
Упорядочение бинарных и унарных операций, используемое при их выполнении для разрешения конфликтов. Часто его называют предшествованием и приоритетом. Про операцию с более высоким приоритетом говорят также, что она связывает сильнее.
Предположим, что  и обозначают две бинарные операции. Как следует интерпретировать (вычислять!) выражение xyz? Если операция  предшествует операции , выражение означает (xy)z. Если старше операция , оно принимает вид x(yz). Если же их приоритет операций одинаков, выражение вычисляется в соответствии с их ассоциативностью . Обратите внимание: у операций с одинаковым приоритетом должна быть одна и та же ассоциативность.
Ситуация слегка проще для унарных операций. Если  и обе префиксные или обе суффиксные, проблем с интерпретацией нет, поскольку как x, так и x допускают лишь одну интерпретацию. Проблема возникает с выражением x. Если приоритет выше у операции , оно вычисляется так: (x). Если приоритет  ниже, чем у , то получаем (x). Если же приоритеты операций совпадают, проблема решается в соответствии с ассоциативностью операций.

precedence relations
отношения старшинства (операторов)
Спецификация относительного приоритета совокупности операций.

precondition
предусловие
Совокупность утверждений, в случае истинности которых выполняются оператор, функция в программе, правило грамматики и т.д. Часто бывает выражено в виде формулы логики первого порядка.

predecrement
<не знаю хорошего перевода>
Свойство процесса, в соответствии с которым содержимое индексного регистра автоматически уменьшается на фиксированную величину до его использования, так что он теперь указывает на очередной элемент.

predictive parsing
разбор с предсказанием
Вид грамматического разбора, при котором грамматическое правило используется для предсказания следующих допустимых лексем. Скажем, если обнаружено ключевое слово integer, то далее должен следовать идентификатор, поскольку разбирается объявление.

prefix
префикс
Подстрока, располагающаяся в начале строки.

preorder
прямой порядок
Порядок прохождения бинарного дерева сверху вниз, рекурсивно определяемый так: сначала проходится корень, затем – левое поддерево, после него – правое поддерево. Порядок назван прямым в переводе т.1 знаменитой монографии Д.Кнута.

production
продукция
Продукции стали стандартным и основным механизмом определения грамматик. Они описывают способ, которым сложные входные структуры строятся из более простых.
Каждая продукция состоит из левой и правой частей (совсем научные названия – антецедент и консеквент; впрочем, они практически не используются). Правая часть продукции – последовательность терминалов и нетерминалов. Слева стоит аналогичная конструкция, ее и заменяют тем, что стоит справа. При этом применяется процесс отождествления , далекое обобщение которого в ПРОЛОГе названо унификацией.
В контекстно-свободных грамматиках слева стоит единственный нетерминал.

program mode
пользовательский режим
Режим работы центрального процессора, в котором не допустимы некоторые операции (скажем, ввод-вывод).

programming environment
интегрированная среда разработки программ
Другое название: операционное окружение . Имеется в виду совокупность взаимоувязанных программ, необходимы при программировании – редактор, компиляторы, отладчики, профайлеры и т.д.

proper prefix
собственный префикс
Непустой префикс , не равный всей строке.

protocol
протокол
Многозначное слово. В объектном ориентировании является синонимом интерфейса класса, т.е. способов взаимодействия с объектами. Классическим, но практически неиспользуемым, протоколом является совокупность сообщений, опознаваемых членами класса.

pumping lemma
лемма о разрастании
Другой перевод - лемма о накачке (pump=насос, накачивать).
Утверждения о структуре длинных фраз контекстно-свободных и регулярных языков, используемый для доказательства того, что конкретный язык не относится к данному классу.

queue
очередь
Структура, реализующая дисциплину обслуживания «первым вошел – первым вышел». Стандартная аббревиатура: FIFO (=first in first out).
См. стек.

quadruple
тетрада
Вид промежуточного представления кодов, выглядит так: R = X op Y, где R – результат, X и Y – операнды, op – код операции. Обратите внимание: здесь фигурируют три адреса.

RE
РВ

Аббревиатура для термина «регулярное выражение » [regular expression].

recognizer
распознаватель
Абстракция (часто реализуемая в виде программы), на входе которой – строка символов, а на выходе – решение, является ли она фразой некоего конкретного языка. Скажем, для регулярных языков распознаватель можно построить в виде КА .

recursive descent
рекурсивный спуск
Грамматический разбор, реализованный в виде совокупности процедур, рекурсивно вызываемых при распознавании подфраз. В результате, конечно, будет построено дерево разбора.

recursively enumerable language
рекурсивно перечислимый язык
Язык, предложения которого можно перечислить рекурсивной программой. Другими словами, любой язык, описанный формальной грамматикой. Сокращение: РП-язык.

reduce action
свертка
Одно из четырех стандартных действий стандартного парсера, осуществляющего восходящий разбор. Выполняется, когда парсер сопоставил все элементы грамматического правила, причем следующая лексема на входе не оказалась ошибочной. Пополняется дерево вывода (если оно строится), производится разнообразная коррекция внутренних структур парсера и т.п. В результате стек уменьшается, поскольку из него убирается информация о сопоставленном правиле, а соответствующая лексема (выведенная правилом) сдвигается на его вершину.

reduce-reduce conflict
конфликт типа свертка-свертка
Этот тип конфликта в грамматике возникает в некотором состоянии парсера , если некая лексема оказывается свертывающей для более, чем одного правила.

reduction in strength
редукция цены
Оптимизация, состоящая в том, что операция заменяется эквивалентной, не столь «дорогой». Классический пример: умножение/деление на 2 заменяется сдвигом на 1.

referenced
упомянутая
О переменной, значение которой считывается в последовательности кодов.

regular expression
регулярное выражение
Выражение, задающее регулярный язык.

regular grammar
регулярная грамматика
Контекстно-свободная грамматика , правые части продукций которой могут содержать либо терминал , либо терминал, за которым следует единственный нетерминал .
Задает регулярный язык .

regular language
регулярный язык
Язык, описываемый регулярной грамматикой (распознаваемый конечным автоматом). Типичный пример: регулярные выражения в программах типа grep.

rehash
рехеширование
При работе с хеш-методами так называют вычисление нового значения, когда старое вызвало коллизию. Так же характеризуют и алгоритм вычисления этого нового значения.

relation
отношение
С точки зрения высокой науки – подмножество декартова произведения двух множеств. Простому программисту отношения также известны: больше, меньше, старшинствоопераций.

relative address
относительный адрес
Адрес, являющийся смещением относительно некоторого другого адреса.

relocatable code
перемещаемый код
Готовая программа может быть помещена для запуска в разные места оперативной памяти. Конечно, для этого нужна деятельность, которую традиционно выполняют загрузчики. Чтобы их работа стала возможной, специфицируются адреса, подлежащие изменению при перемещении программы, а также имена внешних (например, системных) процедур.

relocation
перемещение
Процесс, выполняемый загрузчиком. Производится преобразование перемещаемого кода в абсолютный. Скажем, настраиваются адреса памяти, отводимой для данных.

remote procedure call
вызов удаленной процедуры
Вызов процедуры, которая должна работать на другом компьютере, скажем, сервере, с которым у вызывающего компьютера установлена связь. Аббревиатура: RPC .

resolve ambiguity
разрешение неопределенности, двусмысленности
См. неоднозначность.

reserved word
зарезервированное слово
Слово, смысл которого фиксирован в данном языке и которое нельзя использовать для других целей. Практически всегда к ним относятся ключевые слова , хотя имеются языки (старинный PL/1, например), в которых ключевые слова не являются зарезервированными.

resynchronization
ресинхронизация
Один из способов восстановления после ошибки . Состоит в откате работы парсера и последующем пропуске части входного текста.

reuse
повторное использование
Мечта менеджеров в фирмах, разрабатывающих программное обеспечение.

reverse Polish
обратная польская запись
Способ записи (конечно, не только арифметических!) выражений без скобок, в которой операторы размещаются за операндами (скажем, 5 6 + обозначает сложение чисел 5 и 6). Придумал польский логик Лукасевич (в некоторых источниках – Лукашевич), откуда и название.

right associative operator
право-ассоциативный оператор
Оператор (обозначим его литерой '') обладающий следующим свойством: выражение вида abc интерпретируется как a(bc). Как правило, имеются в виду арифметические операторы.

rightmost derivation
правосторонний вывод
Вывод , в котором на каждом шаге заменяется самый правый нетерминал.

row-major order
расположение по строкам
Метод хранения многомерных массивов, согласно которому сначала располагают элементы первой строки, затем – элементы второй и т.д. Ср. расположение по столбцам .

RPC
RPC
Вызов удаленной процедуры (аббревиатура от remote procedure call ).

rule
правило
См. продукция
Иногда правилом называют лишь правую часть продукции.

rule element
элемент правила
Что бы ни называли правилом, оно, конечно, состоит из частей, сиречь, элементов.
Элементы правила задают лексемы, (под)множества символов, ключевые слова, действия на целевом языке программирования и т.д.

run-time
время исполнения
Относящийся к тому, что происходит во время исполнения программы. Скажем, вызовы библиотек, которые при этом так и называются библиотеки времени исполнения.
Ср. время компиляции , время загрузки .

scalability
расширяемость; модульность
Термин, применяемый к методу, подходу, программе, которые сохраняют работоспособность с ростом размера проблемы (как бы ни определялся этот самый «размер»).

scanner
сканер
Другое название – лексический анализатор . Программа, используемая в качестве «препроцессора» для парсера . Она просматривает литеры входной фразы последовательно, «сканирует» их, и делает из них лексемы. Сканеры разработаны для многих генераторов парсеров; например, для знаменитого YACC а сканером является LEX – не менее знаменитый, но гораздо менее применяемый.

seamless
заподлицо???
Так говорят, когда что-нибудь не требует от пользователя или программы специальных усилий при выходе за границы. Например, файловая система, так спроектированная, позволяет пользователю не заботиться и не знать, где именно расположен нужный ему файл – на его локальном диске или где-нибудь на сети.

semantic value
семантическое значение
С символами, терминальными и нетерминальными, связываются значения. Для терминалов это могут быть значения, присваиваемые сканером, значения же нетерминалов создаются при свертке очередной продукции.

semantics
семантика
Значение оператора в языке.

sentence symbol
<перевод??>
Выделенный нетерминал грамматики, который представляет завершенное предложение (или оператор) языка.

sentential form
сентенциальная форма
Строка, состоящая из терминалов и нетерминалов, которая выведена из исходной в соответствии с грамматикой. Является «полуфабрикатом» для производства фраз языка.
См. тж. фраза.

shared variable
общая, разделяемая переменная
Переменная или область данных, которая доступна более чем одним процессом.

shift action
сдвиг
Одно из четырех традиционных действий традиционного парсера. Выполняется в ситуации, когда входная лексема оказалась допустимой для текущего состояния парсера. В этом случае она (вместе с сопровождающей ее информацией) помещается на стек – сдвигается. Ясное дело, состояние парсера меняется, разнообразная служебная информация корректируется и т.п.

shift-reduce conflict
конфликт типа сдвиг-свертка
Этот тип конфликта означает, что в некотором состоянии имеется лексема, которая оказывается сворачивающей для одного правил и сдвигающей для другого.

shift-reduce parser
парсер типа сдвиг-свертка
Парсер, который во время разбора сдвигает лексемы (кладет их на стек) и сворачивает группы лексем, находящихся в стеке.

sibling
братья (часто – сестры)
Узлы дерева с одним и тем же отцом (непосредственным предшественником).
См. потомок .

SIMD
SIMD
Векторная архитектура: с одним потоком команд и многими потоками данных. Одна инструкция может одновременно применяться к нескольким данным.
См. тж. MIMD .

SIMULA
СИМУЛА
Язык программирования, много лет назад разработанный для программирования моделей с дискретными временем. С ним связывают возникновение объектно-ориентированного программирования. Поверьте, он не виноват!

software reusability
повторная используемость программного обеспечения
1. коды, подходящие для повторного использования (кто бы сказал, что это такое!); 2. изучение соответствующих проблем (кто может – пишет подходящие коды, кто не может – изучает требования к ним).

software reuse
повторное использование программного обеспечения
Использование программ в приложениях, отличных от того, для которого они были написаны.
Мечта!

son
сын
См. потомок.

sort
сорт
Этим словом иногда характеризуют класс абстрактных объектов. Фраза может звучать примерно так: “Рассмотрим все объекты сорта X”.
В обычной практике это слово может также означать сортировку.

sound
правильный
Этим термином характеризуют методы доказательства теорем и/или методы вывода, которые гарантируют, что будут получены лишь допустимые конструкции.

sound type system
система правильного типа
Система типов языка программирования, в которой гарантируется, что значение переменной во время исполнения будет только того типа, который задан во время компиляции. Другими словами, гарантируется отсутствие ошибок одного из множества типов.

source language
исходный язык
Язык, на котором написана программа. Ср. целевой язык .

start symbol
начальный символ
«Родовой» нетерминал грамматики, порождающей данный язык. Как правило, обозначается буквой S.

static analysis
статический анализ
Анализ программы, выполняемый без реального ее запуска.

static data
статические данные
Данные, расположение которых в памяти не меняется во время исполнения программы. Как правило, память под статические данные выделяет компилятор, так что ее не нужно запрашивать у системы, а затем возвращать ее.

static type checking
статическая проверка типа
Проверка или определение типа переменной во время компиляции. Это сильно быстрее динамической проверки , но ограничивает возможности языка: тип переменной должен быть фиксированным.

storage alignment
выравнивание памяти
Многие процессоры нуждаются в том, чтобы адреса данных были четными. Некоторые программы управления динамической памятью умеют выделять ее лишь блоками по 16 байтов. В подобных случаях добавляют неиспользуемые кусками, достигая, таким образом, требуемого выравнивания.

straight-line code
линейный отрезок кодов
Последовательность инструкций, куда не входят никакие переходы или условия.

string
строка; цепочка
Последовательность литер, или символов.

strong typing
сильная типизация
Статическая проверка типов, которая требует, чтобы все переменные были объявлены перед использованием. Это позволяет компилятору гарантировать корректное обращение с переменными.

structural equivalence
структурная эквивалентность
Один из способов определить эквивалентность типов: должны совпадать их компоненты.
Ср. эквивалентность по имени .

substring
подстрока; подцепочка
Смежная часть цепочки .

suffix
суффикс
Подцепочка , стоящая в конце строки.

syntax analysis
синтаксический анализ
Фаза работы компилятора: входной поток литер разбивается на осмысленные куски, которые и являются входом для парсера .

syntax directed parsing
синтаксически управляемый разбор
Подход к построению парсеров, основанный на теории формальных языков, где изобретены алгоритмы, которые позволяют автоматически построить парсер по грамматике языка, представленной в формализованном виде.
Поскольку алгоритмы разбора довольно сложны, сложными оказываются и программы, их реализующие. поскольку, кроме того, языки эволюционируют, а грамматику, как правило, читать и анализировать легче, чем программу, автоматически сгенерированные парсеры легче сопровождать.
Следует, однако, отметить, что подготовка грамматики языка остается и, видимо, в обозримом будущем останется искусством. Средства же тестирования и отладки грамматик практически не разработаны, так что удачный язык программирования и адекватная грамматики для него – плоды опыта и удачи.

syntax directed translation
синтаксически ориентированная трансляция
См. синтаксически ориентированный транслятор .

syntax directed translator
синтаксически ориентированный транслятор
Компилятор, управляемый формально описанной грамматикой.

synthesized attribute
синтезированный атрибут
Атрибут фразы языка, который выведен из значений атрибутов составляющих ее частей. Например, сумма двух строк также является строкой.

synthesized translation
трансляция с синтезом
Метод компиляции, при котором трансляция фразы составляется из трансляций ее компонент.
См. синтезированный атрибут .

systems programmer
системный программист
Классическое значение: программист, который пишет системные программы типа компиляторов и операционных систем.
Неклассическое: программист, который ничего не знает систематически и потому может лишь сопровождать/корежить какую-нибудь систему. Что-нибудь типа администратора сети или хакера (в современном понимании этого слова неспециалистами).

tagged architecture
теговая архитектура
Архитектура компьютера, в которой каждый тип данных сопровождается специальной пометкой (собственно, tag field = теговое поле). Обработка данных, по крайней мере, частично базируется на этих пометках.

temporal logic
временная логика
Один из видов математической логики, в которых кванторы (=существует и=любой) могут относиться к переменной, значения которой интерпретируются как моменты времени. Это позволяет говорить о том, что одно событие предшествует другому, а также о том, что событие непременно наступит, хотя при этом и не всегда удается указать, когда именно.
С ней связывались большие надежды: считалось, что она окажется полезной при анализе правильности программ.

terminal token
terminal symbol
терминальный символ; терминал
Цепочка, которая в грамматике с фразовой структурой (а только они и рассматриваются) является «окончательной» частью фразы языка, описываемого этой грамматикой. Подобная цепочка, конечно же, не может встретиться в левой части продукции.
Ср. нетерминал, нетерминальный символ .

termination
завершение; завершимость
Завершение – нормальное окончание исполнения программы.
Завершимость – свойство программы: гарантируется ее завершение. См. корректность – тотальная и частичная .

three-address code
трехадресный код
См. тетрада .

token
лексема
Вообще-то, в современном английском термином lexeme обозначается цепочка литер, а термином token – (грамматический, т.е. осмысленный) класс таких цепочек. Например, цепочка 123 принадлежит классу число , а цепочка return обозначает лексему RETURN, представляющую терминал return .
К сожалению, русская терминология сложилась довольно давно, когда подобное различие еще не стало общим достоянием (наука о разработке компиляторов появилась, как водится, гораздо позже самих компиляторов). Поэтому, для термина token сохранился приведенный здесь перевод.
Мне очень хотелось привести русскую терминологию в соответствие с современной английской. Удержало то, что не удалось придумать удачный перевод для слова token. Жду предложений !

top-down parsing
нисходящий разбор
Вид грамматического разбора, при котором дерево разбора строится от корня (соответствующего предложению) к листьям. Пример: рекурсивный спуск .

total correctness
сугубая корректность
Свойство программы: гарантируется ее завершимость и выдача правильного результата. Ср. частичная корректность .

translator
транслятор
Принято следующее нестрогое разделение трансляторов: ассемблеры , предназначенные для трансляции с языков низкого уровня, и компиляторы для высокого. Хотя я не встречал удовлетворительного определения, практически всегда программисты отличают языки высокого уровня от низкого. ФИДОшные споры о языке Си отнесу к маргинальным.

transitive closure
транзитивное замыкание
Минимальное транзитивное отношение, содержащее заданное.

triad
триада
Один из видов промежуточного представления результатов компиляции, состоящий из оператора и двух операндов. Другое название: двухадресный код.
Любителям детективов: к китайской мафии отношения не имеет!

triple
троичный
См. триада .

two-address code
двухадресный код
См. триада .

type coercion
приведение типов
Автоматическое преобразование данных из текущего типа в тип, требуемый операцией.

type hierarchy
иерархия типов
Связывается с объектно-ориентированным подходом, хотя известно, конечно, и ранее. Скажем, тип «целые числа» является подтипом чисел действительных, которые, в свою очередь, являются частным случаем комплексных.
В ООП формируется отношением подчиненности классов, сиречь, объектов.

type signature
сигнатура типа
Спецификации типов аргументов функции и возвращаемого ею результата.

unary operator
унарный оператор
Операция, принимающая лишь один аргумент. Примеры: NOT и MINUS . Если символ операции предшествует операнду, ее называют префиксной, иначе суффиксной.

union
объединение
Объединение двух множеств А и В состоит из элементов, каждый из которых принадлежит по крайней мере одному из множеств (т.е. множеству А, или множеству В, или им обоим). Объединение нескольких множеств определяется по индукции:.
При компиляции используется, например, для задания множества литер; в этом случае объединение, как правило, обозначается литерой '+'.

union of languages
объединение языков
Язык, каждое предложение которого является членом по крайней мере одного из объединяемых языков.

union type
объединенный тип
Тип, образованный объединением нескольких типов. Член объединенного типа может иметь тип любого из составляющих типов.

unscrolling
развертка цикла
Метод оптимизации программы, согласно которому циклы при компиляции разворачиваются за счет повторения кодов. Результат, конечно, занимает больше памяти, зато исполняется, очевидно, быстрее.

volatile register
незащищенный регистр
Регистр, значения которого не сохраняются во время вызова процедур.

whetstone
whetstone
В некоторых словарях предлагается смешной перевод “тест мокрая точилка”.
Батарея тестов , используемая для проверки скорости выполнения операций с плавающей точкой. Говорят, полезно для научных задач.
Любопытна причина появления буквы ‘h’ в названиях тестов. В компьютерных жаргонариях эта буква используется для обозначения того, что слово используется нестандартным способом, как правило, иронически. Происходит из слогана 1960-х: “Bheer is the One True Ghod”. Через комиксы и хакеров получило довольно широкое распространение, так что с течением времени стало де-факто стандартом в именах батарей тестов. По-видимому, все началось с whetstone, названия лаборатории.
[Источник: “The New Hacker's Dictionary” ( http://www.tuxedo.org/~esr/jargon/jargon.html ), Eric Raymond ([email protected] )]
См. dhrystone.

YACC
YACC
Так и произносится “як”. Широко и заслуженно распространенный генератор парсеров для контекстно-свободных грамматик. Название является аббревиатурой от Yet Another Compiler-Compiler (еще один компилятор компиляторов). Имеется GNU-тый наследник под названием BISON.

Дата последней модификации: 20 октября 2000 г.