Курс Основы построения трансляторов


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


Пониманию сущности конечного автомата может в значительной степени помочь ДИАГРАММА СОСТОЯНИЙ-ПЕРЕХОДОВ. Каждому состоянию автомата, которое на диаграмме отображается кружочком, соответствует “поведение” конечного автомата. Например, если автомат распознает константу как последовательность цифр, то он должен иметь состояние, которое можно назвать как “ожидание очередной цифры”.  Переход автомата из одного состояния в другое отображается направленной дугой. Условие, при котором происходит этот переход, а также действие, которое осуществляет конечный автомат при переходе, подписываются над дугой. В лексическом анализаторе условием перехода является значение очередного символа строки, который анализируется, а неявным действием является продвижение к очередному символу в строке.

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

 


 

 

Используя диаграмму состояний-переходов, можно напрямую написать программу ЛА, опираясь на приведенный выше пример реализации автомата, обрабатывающего текст:

- основной цикл программы представляет собой последовательный просмотр строки;

- программа имеет переменную состояния, по которой в теле цикла организуется переключение;

- каждой ветке переключателя соответствует одно состояние КА и один узел диаграммы состояний, в ней программируется “поведение” КА для данного состояния - анализируется текущий символ и по нему определяется новое состояние КА и производимое действие;




Начало  Назад  Вперед



Книжный магазин