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

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

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

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

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

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

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

  • States: Состояния FA представлены кружками. Имена государств написаны внутри кружков.

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

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

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

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

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