DFA

A DFA (Deterministic Finite-state Automaton) is a program whose outcome depends only initial entries and is not dependent on any event, any action by a user.
A DFA may be used to program a machine, to make a compiler.

The DFA may be conceived as a collection of states with transitions between states. It assumes a "machine", a program that moves from one state to another.

In the case of code generation, the DFA is generated by a parser from the definition of the grammar of a language. This produces a program capable of compiling source codes conform to this grammar to produce an object code.

Grammar

A grammar is an expression of the syntax of a language in the form of rules written according conventions recognized by a parser.

Example:

exp : ( id | addition )
addition: id '+' exp

These rules, which are recursive in this example, are recognized by the YACC parser.

Determinism

The outcome depends entirely on the code and the application of the rules. There was no input by the user or any kind of event that could affect the outcome.

Finite states

The number of states is finite, as well as the number of transitions between states.

These two properties imply that it is always possible to solve cases that may present a syntactically correct programm because the grammar provides all cases without ambiguity. It is not possible in a given state of the compilation to reach different results.

Synonym

This is also called Finite State Machine.

Homonym

DFA can also mean Data Flow Analysis.

DFA parsers

Bison. GNU free version.

Programming technologies Ajax - API - Cassandra - CIL - CLI - Cookie - Cover Flow - DFA - .NET - HTTP code - IDE - JavaFX - JNA - JSON - MySQL - NaCl - Protocol Buffers - Qt - REST - Servlet - Web 2.0 - WebGL - Webkit - WYSIWYG