Операции над языками

Строки и языки

Определение лексем

Вопросы

1. Что представляет собой входной алфавит следующих языков программирования: Pascal, C, Lisp?

2. Какие существуют соглашения по использованию пробелов в каждом из языков, указанных в п.1?

3. Какую роль выполняет лексический анализ в процессе компиляции?

4. Как могут быть связаны между собой лексический и синтаксический анализ?

5. Почему большинство современных компиляторов используют фазу лексического анализа, при том, что она является необязательной?

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

Алфавит, или класс символов, обозначает любое конечное множество символов. Типичным примером символов могут служить буквы или алфавитно-цифровые символы. Множество {0,1} представляет собой бинарный алфавит. ASCII является примером компьютерного алфавита.

Строка над некоторым алфавитом – это конечная последовательность символов, взятых из алфавита. В теории языков термин предложение и слово часто используются как символы термина “строка”. Длина строки s, обычно обозначаемая как │ s │, равна количеству символов в строке. Например, длина строки banana равна шести.

Пустая строка, обозначаемая как λ (или ε), представляет собой специальную строку нулевой длины.

Язык обозначает произвольное множество строк над некоторым фиксированным алфавитом. Например, {λ} ­- множество, содержащее только пустую строку.

Имеется ряд важных операций, выполняемых над языками. С точки зрения лексического анализа особое значение имеют объединение, конкатенация и замыкание (рис. 6). Можно также обобщить оператор возведения в степень для языка, определив L ⁰ как {ε}, а L ⁱ – как L ^i-1 L. Таким образом, L ⁱ представляет собой L, конкатенированный с самим собой i -1 раз [3].

Операция	Определение
Объединение L и M – L M	L M {s | sЄL или sЄМ}
Конкатенация L и M – LM	L M {s | sЄL и sЄМ}
Замыкание Клини или итерация L – L^*	L^*-обозначает “нуль или более конкатенаций L”
Позитивное замыкание L – L^+	L^+-обозначает “одна или более конкатенаций L”

Рис. 6. Определения операций над языками

Дата добавления: 2014-12-27