Дизайн компилятора - конечные автоматы
Конечные автоматы - это конечный автомат, который принимает на вход строку символов и соответственно меняет свое состояние. Конечные автоматы - это распознаватель регулярных выражений. Когда строка регулярного выражения вводится в конечный автомат, она меняет свое состояние для каждого литерала. Если входная строка успешно обработана и автомат достигает своего конечного состояния, она принимается, т. Е. Только что введенная строка считается действительным токеном используемого языка.
Математическая модель конечных автоматов состоит из:
- Конечный набор состояний (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 , δ}