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

Материал из Википедии — свободной энциклопедии

Для улучшения статьи желательно^?:

Викифицировать статью

Содержание

1 Введение. Синтаксический и лексический анализатор
2 Регулярные множества и автоматные языки
3 Детерминированные и недетерминированные автоматы
4 Алгоритм синтаксического анализа
- 4.1 Пример 1
- 4.2 Пример 2
5 Ссылки
6 См. также

[править] Введение. Синтаксический и лексический анализатор

Одной из особенностей такого подхода к разбору строк является то, что анализ выполняется по мере считывания символов, с использованием информации о текущем символе и символах, прочитанных ранее.
Синтаксический анализатор — это программа или часть программы, выполняющая синтаксический анализ, на первом шаге которого выполняется лексический анализ, далее строится дерево разбора. Синтаксический анализатор входит в структуру транслятора.
Конструкции, распознаваемые лексическим анализатором описываются автоматной грамматикой и регулярными выражениями. На первом этапе лексического анализа происходит построение конечного автомата по регулярному выражению, затем строится таблица переходов для конечного автомата, а далее входной поток символов интерпретируется анализатором в выходной поток лексем.
Определим понятие конечного автомата.
Конечным автоматом-распознавателем называется следующий набор объектов $A=\{S,\ X,\ S_0,\ \delta,\ F\}$ , где:

$S\,$ – конечное непустое множество состояний
$X\,$ – конечное непустое множество входных сигналов(входной алфавит)
$S_0\,$ – начальное состояние
$\delta:S*X\longrightarrow S$ – функция переходов
$F\,$ – множество заключительных состояний

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

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

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

V1 U V2 (операция объединения);
V1V2 (операция конкатенации или склеивания);
V*=V0 U V1 U V2 U… (итерация);

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

Ǿ и ε
{a} для любого а из V
если R1 ,R2 регулярные, то:

R1+R2;
R1R2;
R1*,R2* ;

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

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

[править] Детерминированные и недетерминированные автоматы

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

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

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

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

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

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

[править] Алгоритм синтаксического анализа

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

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

Сканирование (из исходного текста строятся лексемы, реализуется в виде конечного автомата)
- построение эквивалентного детерминированного автомата (поскольку по теореме для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный).(Шаг 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. Синтаксическая диаграмма для данного автомата представлена на рисунке.