Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Конспект лекций СПО 31-8-13.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
970 Кб
Скачать
☆

Синтаксический и лексический анализатор

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

Конечным автоматом-распознавателем называется следующий набор объектов А={S,X,So,δ,F}, где:

  1. S – конечное непустое множество состояний

  2. Х – конечное непустое множество входных сигналов(входной алфавит)

  3. So – начальное состояние

  4. δ:S*X→S – функция переходов

  5. F – множество заключительных состояний

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

Регулярные множества и автоматные языки

Рассмотрим класс множеств цепочек над конечным словарем. Эти множества называются регулярными. Пусть V1,V2 – множества цепочек.Тогда операции над этими множествами:

  • V1 U V2 (операция объединения);

  • V1V2 (операция конкатенации или склеивания);

  • V*=V0 U V1 U V2 U… (итерация);

Класс регулярных выражений над конечным словарем:

  • Ǿ и ε

  • {a} для любого а из V

  • если R1 ,R2 регулярные, то:

  1. R1+R2;

  2. R1R2;

  3. R1*,R2* ;

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

Построение автомата по заданной грамматике

Теорема Клини: Классы регулярных множеств и автоматных языков совпадают.

Детерминированные и недетерминированные автоматы

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

Теорема 3: Для любого недетерминированного конечноавтоматного распознавателя существует эквивалентный ему детерминированный.

Алгоритм построения эквивалентного детерминированного конечного автомата.

  • Приведение недетерминированного автомата к автомату без ε-переходов.

Определение: ε-замыканием состояния s называется множество всех состояний, которые достижимы из s без подачи входного сигнала. Множеством состояний полученного автомата являются ε-замыкания состояний автомата с ε-переходами.

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