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

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

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

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

1. Строится эквивалентный данному детерминированный автомат (это возможно, поскольку по теореме для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный).
2. Строится таблица переходов для полученного конечного автомата.
3. Поток символов интерпретируется в выходной поток лексем (производится обработка потока символов в соответствии с заданной автоматной грамматикой).
4. Конструируются токены, выполняется проход по символам лексемы для получения значения токена.
5. Строится дерево разбора (результат синтаксического анализа).

Пример

Работу алгоритма можно проиллюстрировать следующим примером.

Конечный автомат распознает цепочки языка (а+bb)(a+b)*. Это недетерминированный конечный автомат. Построим для него эквивалентный автомат без ε-переходов, заменив состояния автомата ε-замыканием.	Недетерминированный конечный автомат
Таблица переходов для эквивалентного детерминированного автомата. a b p0={q0;q1} p2 p1 p1={q2} p2 p2={q2;q3} p3 p2 p3={q0;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

Ссылки

• Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. С. 224. ISBN 5-318-00537-3
• Синтаксический разбор строк и конечные автоматы [1]

---

См. также

• Конечный автомат
• Эквивалентность детерминированных и недетерминированных конечных автоматов
• Контекстно-свободная грамматика
• Регулярные выражения
• Формальный язык
• Формальная грамматика