Дизайн компилятора - конечные автоматы

Конечные автоматы - это конечный автомат, который принимает строку символов в качестве входных данных и соответственно изменяет свое состояние. Конечные автоматы - это распознаватель регулярных выражений. Когда строка регулярного выражения подается в конечные автоматы, она меняет свое состояние для каждого литерала. Если входная строка успешно обработана и автоматы достигают своего конечного состояния, она принимается, т. Е. Только что переданная строка считается допустимым токеном языка в руке.

Математическая модель конечных автоматов состоит из:

  • Конечный набор состояний (Q)
  • Конечный набор входных символов (Σ)
  • Одно стартовое состояние (q0)
  • Набор конечных состояний (qf)
  • Функция перехода (δ)

Функция перехода (δ) отображает конечный набор состояний (Q) в конечный набор входных символов (Σ), Q × Σ ➔ Q

Конечные Автоматы Констракшн

Пусть L (r) регулярный язык, распознаваемый некоторыми конечными автоматами (FA).

  • Состояния : состояния ФА представлены кружками. Названия штатов пишутся внутри кружков.

  • Начальное состояние : состояние, из которого начинается автомат, называется начальным состоянием. Стартовое состояние имеет стрелку, направленную на него.

  • Промежуточные состояния : все промежуточные состояния имеют как минимум две стрелки; один указывает на другого, а другой указывает на них.

  • Конечное состояние : если входная строка успешно проанализирована, ожидается, что автоматы находятся в этом состоянии. Конечное состояние представлено двойными кружками. Он может иметь любое нечетное количество стрелок, указывающих на него, и четное количество стрелок, указывающих на него. Количество нечетных стрелок на единицу больше четного, то есть нечетное = четное + 1 .

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

Пример : мы предполагаем, что FA принимает любые трехзначные двоичные значения, заканчивающиеся цифрой 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}

Конечная конструкция автоматов