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

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

Статья не полностью соответствует правилам Википедии или рекомендациям по оформлению статей. Желательно:

проставить интервики
викифицировать

Содержание

1 Введение. Понятие конечного автомата
2 Регулярные множества и выражения
3 Детерминированные и недетерминированные автоматы
- 3.1 Пример 1
- 3.2 Пример 2
4 Ссылки
5 См. также

[править] Введение. Понятие конечного автомата

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

S – конечное непустое множество состояний
Х – конечное непустое множество входных сигналов(входной алфавит)
So – начальное состояние
δ:S*X→S – функция переходов
F – множество заключительных состояний

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

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

Рассмотрим класс множеств цепочек над конечным словарем. Эти множества называются регулярными. Пусть 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

Рассмотрим алгоритм построения по недетерминированному конечному автомату эквивалентного ему детерминированного автомата на Примере 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

[править] Пример 2

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