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

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

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

Одной из особенностей такого подхода к разбору строк является то, что анализ выполняется по мере считывания символов, с использованием информации о текущем символе и символах, прочитанных ранее.
Синтаксический анализатор — это программа или часть программы, выполняющая синтаксический анализ, на первом шаге которого выполняется лексический анализ, разбор лексем.
Лексема - это минимальная структурная единица языка, имеющая смысл. Конструкции, распознаваемые лексическим анализатором описываются автоматной грамматикой и регулярными выражениями. На первом этапе лексического анализа происходит построение конечного автомата по регулярному выражению, затем строится таблица переходов для конечного автомата, а далее входной поток символов интерпретируется анализатором в выходной поток лексем.
Определим понятие конечного автомата.
Конечным автоматом-распознавателем называется следующий набор объектов А={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 без подачи входного сигнала. Множеством состояний полученного автомата являются ε-замыкания состояний автомата с ε-переходами.

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

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

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

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

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

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

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

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

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

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

Эквивалентный детерминированный автомат.

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

[править] Ссылки

• Карпов Ю.Г.Теория автоматов. — СПб.: Питер, 2002. С. 224. ISBN 5-318-00537-3

[править] См. также

• Минимизация конечных автоматов
• Эквивалентность детерминированных и недетерминированных конечных автоматов