Finite Automata A recognizer for a language is a program that takes a string x,and answers "yes"if x is a sentence of that language,and "no"otherwise. We call the recognizer of the tokens as a finite automaton. A finite automaton can be:deterministic(DFA)or non-deterministic (NFA) This means that we may use a deterministic or non-deterministic automaton as a lexical analyzer. Both deterministic and non-deterministic finite automaton recognize regular sets ·Which one? deterministic-faster recognizer,but it may take more space non-deterministic-slower,but it may take less space Deterministic automatons are widely used lexical analyzers. First,we define regular expressions for tokens;Then we convert them into a DFA to get a lexical analyzer for our tokens. Algorithm1:Regular Expression>NFA>DFA (two steps:first to NFA,then to DFA) Algorithm2:Regular Expression>DFA (directly convert a regular expression into a DFA) CS308 Compiler TheoryFinite Automata • A recognizer for a language is a program that takes a string x, and answers “yes” if x is a sentence of that language and is a sentence of that language, and “no” otherwise otherwise. • We call the recognizer of the tokens as a finite automaton. • A finite automaton can be: deterministic( ) DFA or non-deterministic ( ) NFA • This means that we may use a deterministic or non-deterministic automaton as a lexical analyzer. • B hd i i i d Both deterministic and non-d i i i fi i i l deterministic finite automaton recognize regular sets. • Which one? – deterministic – faster recog, y p nizer, but it may take more space – non-deterministic – slower, but it may take less space – Deterministic automatons are widely used lexical analyzers. • First we define regular expressions for tokens; Then we convert them into a DFA to First, we define regular expressions for tokens; Then we convert them into a DFA to get a lexical analyzer for our tokens. – Algorithm1: Regular Expression Î NFA Î DFA (two steps: first to NFA, then to DFA) Al ith 2: Re l E e i Î DFA (di e tl e t e l e e i i t DFA) 9 – Algorithm2: Regular Expression Î DFA (directly convert a regular expression into a DFA) CS308 Compiler Theory