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 Theory 16
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 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) 16 – Algorithm2: Regular Expression Î DFA (directly convert a regular expression into a DFA) CS308 Compiler Theory
Non-Deterministic Finite Automaton (NFA) A non-deterministic finite automaton (NFA)is a mathematical model that consists of: -S-a set of states ->-a set of input symbols (alphabet) move-a transition function move to map state-symbol pairs to sets of states. So -a start(initial)state F-a set of accepting states(final states) 8-transitions are allowed in NFAs.In other words,we can move from one state to another one without consuming any symbol. A NFA accepts a string x,if and only if there is a path from the starting state to one of accepting states such that edge labels along this path spell out x. CS308 Compiler Theory 17
Non-Deterministic Finite Automaton (NFA) • A non-deterministic finite automaton (NFA) is a mathematical model that consists of: that consists of: – S - a set of states – Σ - a set of in p y (p ) ut s ymbols (al phabet ) – move – a transition function move to map state-symbol pairs to sets of states. – s0 - a start (initial) state – F – a set of accepting states (final states) a set of accepting states (final states) • ε - transitions are allowed in NFAs In other words we can move from transitions are allowed in NFAs. In other words, we can move from one state to another one without consuming any symbol. • A NFA accepts a string x if and only if there is a path from the starting A NFA accepts a string x, if and only if there is a path from the starting state to one of accepting states such that edge labels along this path spell out x. CS308 Compiler Theory 17