B. Глоссарий

LALR(1)

Класс контекстно-свободных грамматик, которые может обрабатывать Bison (как и большинство других генераторов анализаторов), подмножество LR(1). См. раздел 6.7 Загадочные конфликты свёртка/свёртка.

LR(1)

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

Анализатор

Функция, распознающая правильные последовательности языка путём анализа синтаксической структуры переданного ей лексическим анализатором множества лексем.

Бэкуса-Наура форма (BNF, БНФ)

Формальный метод определения контекстно-свободных грамматики. БНФ впервые была использована в сообщении о языке ALGOL-60. См. раздел 2.1 Языки и контекстно-свободные грамматики.

Входной поток

Непрерывный поток данных между устройствами или программами.

Группа

Грамматическая конструкция, которая (в общем случае) грамматически делима, например, "выражение" или "объявление" в C. См. раздел 2.1 Языки и контекстно-свободные грамматики.

Динамическое выделение

Выделение памяти, производимое во время выполнения программы, а не во время компиляции или при входе в функцию.

Инфиксная операция

Арифметическая операция, знак которой помещается между операндами, к которым она применяется.

Контекстно-свободные грамматики

Грамматики, определённые правилами, которые могут быть применены независимо Так, если есть правило, говорящее, что целое число может использоваться как выражение, целые числа допустимы где угодно, где допустимы выражения. См. раздел 2.1 Языки и контекстно-свободные грамматики.

Левая ассоциативность

Левоассоциативные операции анализируются слева направо: `a+b+c' сначала вычисляет `a+b', а затем объединяет с `c'. См. раздел 6.3 Приоритет операций.

Левая рекурсия

Правило, результирующий символ которого является также символом его первого компонента. Например: `expseq1 : expseq1 ',' exp;'. См. раздел 4.4 Рекурсивные правила.

Лексема

Базовая, грамматически неделимая единица языка. В грамматике лексему описывает терминальный символ. На вход анализатора Bison поступает последовательность лексем от лексического анализатора. См. раздел 4.2 Символы, терминальные и нетерминальные.

Лексическая увязка

Флаг, устанавливаемый действиями правил грамматики и изменяющий способ разбора лексем. См. раздел 8.2 Лексическая увязка.

Лексический анализатор (сканер)

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

Машина с конечным числом состояний

"Машина", имеющая дискретные состояния, в одном из которых она находится в каждый момент времени. По мере обработки входного текста машина переходит из состояния в состояние, что определяется логикой машины. В случае анализатора входной файл -- это разбираемый текст, а состояния соответствуют различным стадиям в правилах грамматики. См. раздел 6. Алгоритм анализатора Bison.

Начальный символ

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

Нетерминальный символ

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

Обратная польская нотация

Язык с постфиксными операциями.

Однолитерная лексема

Единственная лексема, распознаваемая и обрабатываемая сама как есть. См. раздел 2.2 От формальных правил к входному тексту Bison.

Ошибка разбора

Ошибка, произошедшая во время разбора входного потока из-за неверного синтаксиса. См. раздел 7. Восстановление после ошибок.

Постфиксная операция

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

Повторная входимость

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

Правая рекурсия

Правило, результирующий символ которого является также символом его последнего компонента. Например: `expseq1 : exp ',' expseq1;'. См. раздел 4.4 Рекурсивные правила.

Предпросмотренная лексема

Лексема, уже прочитанная, но ещё не сдвинутая. См. раздел 6.1 Предпросмотренные лексемы.

Пустая строка

Аналогично пустому множеству в теории множеств, пустая строка -- это строка литер нулевой длины.

Разбор слева направо

Разбор предложения языка путём последовательного анализа его лексем слева направо. См. раздел 6. Алгоритм анализатора Bison.

Свёртка

Замена строки нетерминалов и/или терминалов одним нетерминалом, в соответсвии с правилом грамматики. См. раздел 6. Алгоритм анализатора Bison.

Сдвиг

Говорят, что анализатор производит сдвиг, когда он принимает решение анализировать дальнейший входной поток вместо того, чтобы выполнить немедленную свёртку по какому-либо уже распознанному правилу. См. раздел 6. Алгоритм анализатора Bison.

Семантика

В компьютерных языках семантика определяется действиями, предпринимаемыми для каждого текста на языке, т.е., смыслом каждого оператора. См. раздел 4.5 Определение семантики языка.

Строковая лексема

Лексема, состоящая из двух или более фиксированных литер. См. раздел 4.2 Символы, терминальные и нетерминальные.

Таблица символов

Структура данных, где во время разбора хранятся имена символов и связанные данные, чтобы дать возможность распознавания и использования существующей информации при повторном использовании символа. См. раздел 3.5 Многофункциональный калькулятор: mfcalc.

Терминальный символ

Символ грамматики, для которого в грамматике не существует правил, и поэтому грамматически неделимый. Представляемый им кусок текста является лексемой. См. раздел 2.1 Языки и контекстно-свободные грамматики.

Языковая конструкция

Одна из типичных исползуемых в языке схем. Например, одной из конструкций языка C является оператор if. См. раздел 2.1 Языки и контекстно-свободные грамматики.