На рис. 6 изображен конечный автомат – распознаватель множества целых констант [1].
Рис. 6. Конечный автомат – распознаватель целых констант
Допустимые символы в начальном состоянии: ‘+’, ‘–‘, ‘0..9’. Если приходит другой символ («Иначе»), то автомат переходит в т. н. «незаключительное» состояние, сигнализирующее о том, что лексема не относится к целым константам. Если после анализа очередной порции символов автомат окажется в «заключительном» состоянии, значит, лексема распознана и является целым числом.
Синтаксический анализ выполняется с помощью более сложных методов, поэтому возможностей обычных конечных автоматов недостаточно и используют автоматы с магазинной памятью (память стекового типа).
Системы связи. Уже довольно давно автоматы применяются в системах телекоммуникаций, в частности для спецификации протоколов компьютерных сетей. В этих спецификациях используются диаграммы Харела, основанные на графах переходов.
Дэвид Харел в 1987 году предложил свои диаграммы (названные им «State charts» – «карты состояний») для формального описания сложных систем [1, 9, 13, 14]. Эти диаграммы расширяют возможности графов переходов конечных автоматов за счет некоторых улучшений. Например, наряду с обычными состояниями могут использоваться гиперсостояния (или суперсостояния), объединяющие несколько состояний, имеющих идентичную реакцию на одно и то же событие. С состояниями могут быть ассоциированы действия: при входе в состояние (в соответствующей вершине помечается словом entry), при выходе из него (помечается словом exit) и при нахождении в состоянии (помечается словом do). Также введено историческое псевдосостояние (обозначается буквой Н), которое не является реальным состоянием и служит для запоминания вершины в гиперсостоянии, в которой система находилась в последний раз.
Loading ...