Математические модели, использующие представление текстов в виде цепочек символов

Совокупность языков, применяемых для описания объектов процедур, проектных процедур автоматизированного проектирования и проектных решений, а также языков написания программного обеспечения САПР и для создания различных интерфейсов

Множество правил построения допустимых конструкций (выражений) языка

Описание назначения и смысла каждой конструкции языка

В широком смысле - программа, преобразующая текст, написанный на одном языке, в текст на другом языке; в узком смысле - программа, преобразующая программу, написанную на одном (входном) языке в программу, представленную на другом (выходном) языке

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

Программа, преобразующая текст, написанный на алгоритмическом языке, в программу, состоящую из машинных команд; компилятор создает законченный вариант программы на машинном языке

Выделение простейших конструкций языка, которые называют лексическими единицами (лексемами)

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

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

Описание структуры формального языка

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

Третья стадия работы компилятора

Программа, которая каждому символу действия, поступающему на её вход, ставит в соответствие одну или несколько команд выходного языка; в качестве выходного языка могут быть использованы команды устройства, команды ассемблера, либо операторы какого-либо другого языка

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

Символы, входящие в алфавит

Последовательность, в которую могут входить любые допустимые символы грамматики (символы, принадлежащие алфавиту)

Совокупность четырех объектов: терминального и нетерминального алфавита, начального символа грамматики и множества правил вывода

Алфавит, из букв которого строятся цепочки, порождаемые грамматикой

Наборы топологических, синтаксических и семантических признаков

Алфавит, буквы которого могут входить в промежуточные цепочки, но не должны входить в результат порождения

Обозначают понятия, которые требуют дальнейшего определения, нетерминальный символ может определяться сам через себя (рекурсивное определение)

Математический аппарат, служащий для изучения синтаксиса языков

Грамматика, которая не содержит аннулирующих правил либо содержит только одно правило вида <I> → $, где <I> - начальный символ грамматики, и символ <I> не встречается в правых частях остальных правил грамматики

Конечное множество символов, неделимых в данном рассмотрении

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

Множество правил вида α→β, где α и β - цепочки, построенные из букв объединения терминального и нетерминального алфавитов

Объединение терминального и нетерминального алфавитов

Если r = τ → γ - правило грамматики, α = χ'τχ", β = χ'γχ" - цепочки символов полного алфавита, то β может быть получена из α путём применения правила r

Если для совокупности цепочек Ω=(ω0, ω1, ..., ωn) существует последовательность непосредственных выводов ω0 ⇨ ω1, ..., ωn-1 ⇨ ωn, то такую последовательность называют выводом ωn из ω0 и обозначают ω0 ⇨ *ωn

Множество конечных цепочек терминального алфавита грамматики Г, выводимых из начального символа <I>

Язык, порождаемый грамматикой Г, который не содержит ни одной конечной цепочки

Формальные грамматики, не имеющие ограничений на правила порождения и порождающие естественные языки; правила вывода имеют вид: r = η → ψ; η, ψ ∈ (Va ∪ Vt)*

Формальные грамматики, на допускающие применения любых правил; правила вывода должны иметь вид: χ1<A>χ2 → χ1ωχ2, где χ1, χ2 - цепочки, возможно пустые, из множества ( Va ∪ Vt)*, символ <A> ∈ Va, цепочка ω ∈ (Va ∪ Vt)*

Формальные грамматики, правила вывода которых имеют вид: <A> → α, где <A> ∈ Va, α ∈ (Va ∪ Vt)*, являются математическим аппаратом теории формальных грамматик, который служит основой для проведения синтаксического анализа

Формальные грамматики, правила вывода которых имеют вид: <A> → α или <A> → α<B> или <A> → <B>α, где <A>, <B> ∈ Va, α ∈ Vt, причем грамматика может иметь только правила вида <A> → α<B> либо только правила вида <A> → <B>α

Дерево, представляющее вывод любой цепочки языка

Начальный символ грамматики

Последовательность номеров правил грамматики, применение которых позволяет построить вывод рассматриваемой цепочки из начального символа грамматики

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

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

Цепочка языка, для вывода которой существует более чем одно синтаксическое дерево

Формальные грамматики, порождающие один и тот же язык

Форма задания правил грамматики, которая предусматривает использование в качестве элементов нетерминального словаря отдельных символов и стрелки в качестве разделителя правой и левой частей правила

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

форма задания правил грамматики, которая предполагает введение специальной операции, которая называется итерацией и обозначается парой фигурных скобок со звездочкой; итерация вида {a}* определяется как множество, включающее цепочки всевозможной длины, построенные с использованием символа а, и пустую цепочку

Преобразованная формальная грамматика, порождаемый язык которой соответствует необходимой структуре

Нетерминальный символ, из которого не может быть выведена конечная терминальная цепочка

Нетерминальный символ, из которого может быть выведена конечная терминальная цепочка

Символ Х ∈ (Va ∪ Vt) в КС-грамматике, который не появляется ни одной выводимой цепочке

Символ Х ∈ (Va ∪ Vt) в КС-грамматике, который появляется хотя бы в одной выводимой цепочке

Символ Х ∈ (Va ∪ Vt) в КС-грамматике, который является недостижимым или непроизводящим

КС-грамматика, которая не содержит бесполезных символов

Правило вида: <A> → α<A>, где <A> ∈ Va, α ∈ (Va ∪ Vt)*

Правило вида: <A> → <A>α, где <A> ∈ Va, α ∈ (Va ∪ Vt)*

Правило грамматики вида <A>→<B>, где A, B ∈ Va

Правило грамматики с пустой правой частью

Нетерминал аннулирующих правил

По заданной цепочке необходимо определить принадлежит ли она заданному языку

Совокупность семи объектов: входного алфавита Р, алфавита состояний S, начального состояния So ∈ S, множества конечных состояний F ⊂ S, алфавита магазинных символов, маркер дна магазина ho ∈ H и функции переходов f

Позиция, находящаяся в рассматриваемый момент времени под головкой вспомогательной ленты

Начало вспомогательной ленты (магазина) магазинного автомата

Может перемещаться только в одну сторону - вправо или оставаться на месте, т. е. она может выполнять только чтение

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

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

Включают в себя все арифметические выражения, а также описания алгебраических функций

Объединение алгебраических выражений и логических функций

Операции с одним операндом

Операции с двумя операндами

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

Определяет старшинство выполняемых операций и связывает последовательность действий алгебраических и арифметических выражений

Представление арифметических, алгебраических и логических выражений выражений в виде <оператор><операнд1><операнд2><результат> - для бинарных операций и <оператор><операнд>< ><результат> - для унарных

Взять два верхних операнда из стека, произвести над ними операцию ξ и новый операнд (результат) поместить на вершину стека

Взять операнд с именем i и отправить его на вершину стека, перейти к просмотру следующего символа

Отправить пришедший символ на вершину стека и читать следующий символ

Выполнить операцию над двумя операндами, результат занести на вершину стека и читать следующий символ

При прочтении символа ')' удалить ')' с вершины стека и читать следующий символ (действие удаления скобки)

Взять два операнда, выполить над ними команду kξ и повторить чтение входного символа

Форма записи бесскобочных арифметических выражений , в которой порядок действий задается порядком знаков операций в выражении

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

Проблемно-ориентированный язык (для генератора лексических анализаторов)

Наименьшая автономная часть языка программирования; программа обычно состоит из последовательности инструкции длиной один и более

Слово, зарезервированное в алфавите для определенных целей

Определенное в программе и неизменяемое число

Целочисленная константа, представленная символом

Имя переменной

В языке Си - инструкции, записанные в тексте программы, и выполняемые до трансляции программы; позволяют изменить текст программы, например, заменить некоторые лексемы в тексте, вставить текст из другого файла, запретить трансляцию части текста и т.п.; все директивы препроцессора начинаются со знака #

Определяет множество значений и операций, которые могут быть применены к этим значениям

Характеристика переменной, которая определяет способ ее хранения

Инструментальное средство, предоставляемое для автоматизации проектирования лексических анализаторов операционной системой OS UNIX

Выполняемый модуль генератора LEX; расположен в каталоге /usr/bin файловой системы OS UNIX

Библиотека объектных модулей стандартных функций генератора LEX; расположена в каталоге /usr/lib файловой системы OS UNIX

Исходные данные для генератора LEX; имеет формат текстового файла, который может быть подготовлен в текстовом редакторе и сохранен под произвольным именем, обычно с расширением .l, в любом доступном каталоге файловой системы OS UNIX

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

Определяет возможные последующие состояния по входному символу и текущему состоянию

Состояние, в котором конечный автомат-распознаватель может находиться в начале обработки лексем входного потока

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

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

Генератор LEX автоматически конструирует ДКА для лексического анализатора на основе построения синтаксических деревьев регулярных выражений, которые заданы во входном файле спецификации лексем разработчиком лексического анализатора

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

Определяет последовательность переходов конечного автомата

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

Входит в базовый операционный набор для конструирования регулярных выражений; предоставляет возможность выбора слов по любой из двух альтернатив

Операции объединения, конкатенации и итерации; образуют базовый операционный набор для конструирования регулярных выражений

Входит в базовый операционный набор для конструирования регулярных выражений; используется для слияния слов, когда одно слово приписывается к другому справа

Входит в базовый операционный набор для конструирования регулярных выражений; обеспечивает повторение слова произвольное число или ноль раз

В настоящее время широко используется в различных операционных средах для поиска информации в текстовых файлах на основе заданного регулярного выражения

Знаки регулярных операций

Текстовые символы

Изменение исходного смысла символа

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

Метасимволы ^ и $, используемые в регулярных выражениях для поиска слов в начале и в конце строки

В алгебре регулярных выражений эта регулярная операция обеспечивает выбор любой из возможных альтернатив

Набор символов, которые могут находиться в определенной позиции входной строки, в регулярном выражении задаётся внутри метасимволов []

Задается перечислением допустимые символов класса внутри квадратных скобок

Применяется, когда коды ASCII символов класса образуют непрерывную возрастающую последовательность; в этом случае класс символов можно задать в форме интервала, где первый и последний символы разделяет дефис, который в таком контексте становится метасимволом класса

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

Интерпретация метасимволовз ависит от контекста, в котором они используются в регулярном выражении

Экранирующий символ; в классе символов сохраняет специальный смысл экранирующей металитеры для любого символа в квадратных скобках; обозначает регулярный оператор для обработки правого контекста

Регулярные операторы, которые позволяют специфицировать в регулярном выражении возможность повторения символов входной строки

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

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

Обозначает, что во входном потоке может находиться любое, в том числе равное нулю, количество экземпляров предшествующего ему символа регулярного выражения

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

Специальная мета-последовательность, которая позволяет конкретно задавать наименьшее обязательное и наибольшее допустимое число экземпляров повторений; состоит из самого символа и двух пределов его повторения в фигурных скобках

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

Специфицируется в форме алфавитно-цифровой метки предусловия, которая указывается в угловых скобках <> перед регулярным выражением

Позволяют изменять естественный приоритет операций; обычно используются с целью ограничения области действия регулярных операций с низким приоритетом или группировки фрагментов регулярных выражений для применения к ним регулярных операций с высоким приоритетом

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

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

Формальные языки, множества слов которых не могут быть специфицированы с помощью аппарата регулярных выражений

Все, что находится в файле спецификации лексем генератора LEX до первой разделительной пары знаков процента %%

Служебной директивой секции описаний; после неё должны быть объявлены все необходимые метки предусловий этой секции

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

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

Инструкции правил. огранченные фигурными скобками в соответствие с синтаксисом языка программирования Cи

Встроенная переменная генератора LEX; имеет тип указателя на символы (char *) и используется в блоке действия правила для адресации внешнего одномерного символьного массива, составленного из символов входного потока, которые удовлетворяют регулярному выражению данного правила

Символьный массив генератора LEX; применяется, когда в блоке действий необходимо преобразовать или посимвольно обработать входной текст, соответствующий регулярному выражению правила

Стандартная функция генератора LEX; добавляет к текущему содержимому массива yytext следующую последовательность символов входного потока

Стандартная функция генератора LEX; применяется, когда возникает потребность сохранить в массиве yytext не все, а только необходимое число символов распознанной последовательности

Стандартная функция генератора LEX; обеспечивает принудительный переход к обработке полученных символов входного потока по следующему подходящему правилу

Оператор действий; введен для сокращенной записи стандартного вывода содержимого массива yytext. В исходном тексте лексического анализатора оператор ECHO определяется директивой #define препроцессора системы программирования Cи

Оператор действий; устанавливает состояние лексического анализатора, которое обозначено меткой STATE. После его выполнения становятся активными все правила с меткой <STATE> в левом контексте их регулярных выражений

Несколько правил, которым соответствует входная последовательность символов во время лексического анализа входного потока

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

Стандартная функция генератора LEX; содержит инструкции всех действий секции правил, обеспечивая обработку лексем, распознаваемых во входном потоке, и управление процедурой лексического анализа

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

Стандартная функция генератора LEX; автоматически вызывается лексическим анализатором при достижении конца входного потока стандартного ввода; эта функция не имеет аргументов и должна возвращать целочисленное значение 0 или 1, оценка которого предусмотрена в программе лексического анализатора

Команда, которую предоставляет генератор LEX для формирования исходного кода лексического анализатора на языке программирования Cи; ее выполняемый модуль располагается в каталоге /usr/bin файловой системы OS UNIX

Параметр командной строки вызова генератора LEX, который позволяет получить исходный код лексического анализатора в файле с заданным именем

Параметр командной строки для получения исполняемого модуля лексического анализатора, который гарантирует компоновку объектных модулей стандартной библиотеки libl.a или libl.so генератора LEX, располагающихся в каталоге /usr/lib файловой системы OS UNIX

Текстовый файл с исходным кодом проектируемого лексического анализатора, создаваемый при вызове lex с одним аргументом, который обозначает имя файла спецификации лексем

Объектный файл генератора LEX; обычно компонуется с объектным модулем синтаксического анализатора

Инструментальное средство, предоставляемое для автоматизации проектирования синтаксических анализаторов операционной системой OS UNIX