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

Алгоритм синтаксического анализа

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

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

  • Сканирование (из исходного текста строятся лексемы, реализуется в виде конечного автомата)

    • построение эквивалентного детерминированного автомата (поскольку по теореме для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный).(Шаг 1).

    • строится таблица переходов для полученного конечного автомата.(Шаг 2).

    • поток символов интерпретируется в выходной поток лексем (обработка потока символов в соответствии с заданной автоматной грамматикой).(Шаг 3).

  • Оценка (конструируются токены, проход по символам лексемы для получения значения токена).(Шаг 4).

  • Построение дерева разбора (результат синтаксического анализа).(Шаг 5).

Рассмотрим работу алгоритма на двух примерах.

Пример 1

Рассмотрим алгоритм построения по недетерминированному конечному автомату эквивалентного ему детерминированного автомата на Примере 1.

Конечный автомат в Примере 1 распознает цепочки языка (а+bb)(a+b)*. Это недетерминированный конечный автомат. Построим для него эквивалентный автомат без ε-переходов,заменив состояния автомата ε-замыканием.

Таблица переходов для эквивалентного детерминированного автомата.

a

b

po={qo;q1}

p2

p1

p1={q2}

p2

p2={q2;q3}

p3

p2

p3={qo;q1;q2;q3}

p3

p2

(Шаг 1 + Шаг 2).

Построим автоматную грамматику для языка из Примера 1.(Шаг 3).

Po->bP1|aP2; P2->bP2|aP3; P3->bP2|aP3; P1->bP2

Рассмотрим пример вывода цепочки bbab: (Шаг 4). Po->bP1->bbP2->bbaP3->bbabP2.

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

(Шаг 5).

Пример 2

Рассмотрим пример построения по синтаксической диаграмме детерминированного конечного автомата. Конечный автомат в Примере 2 распознает цепочки языка b+(а+bb)(b+ab)*a. Синтаксическая диаграмма для данного автомата представлена на рисунке.

Построим детерминированный конечный автомат по алгоритму, описанному выше.

Эквивалентный автомат без ε-переходов.

Таблица переходов для эквивалентного автомата из Примера 2.

a

b

p1{1}

p3

p2

p2{2;6}

p3

p3{3;4;7}

p2

p3

Эквивалентный детерминированный автомат. (Шаг 1 + Шаг 2).

Построим автоматную грамматику для языка из Примера 2.(Шаг 3).

P1->bP2|aP3; P2->bP3; P3->bP3|aP2;

Рассмотрим пример вывода цепочки bbab:(Шаг 4). P1->bP2->bbP3->bbaP2->bbabP3.

Построение дерева разбора для цепочки bbab, распознаваемой автоматом Приме

ра 2. (Шаг 5)

.

106