編譯原理英文版課件：Chapter2 Scanning (Lexical Analysis)2

1、2. Scanning (Lexical Analysis)PART TWOContentsPART ONE2.1 The Scanning Process 2.2 Regular Expression2.3 Finite AutomataPART TWO2.4 From Regular Expressions to DFAs Open2.4 From Regular Expression To DFAs Main PurposeThe process of constructing a scanner: Regular expressions represent a pattern, tha

2、t are used as token descriptions DFAs represent algorithms that accept strings according to a pattern described in regular expressionTranslating a regular expression into a DFA via NFA.Regular ExpressionNFADFAProgramContents From a Regular Expression to an NFA MoreFrom an NFA to a DFA More Minimizin

3、g the Number of States in a DFA More2.4.1 From a Regular Expression to an NFAThe Idea of Inductive MethodIt follows the structure of the definition of a regular expressionConstruct NFA for each basic regular expression2 NFA that is equivalent to regular expression 3 NFA that is equivalent to regular

4、 expression a,a 1 NFA that is equivalent to regular expression yxyxyxaConstruct NFA for complex regular expressions2 Break up the NFA basing on the following three operations until the arrowed line is labeled by only characters 1 The NFA for regular expression “e” ise1Xye=e1|e2e2X1e1ye2e=e1e2X1ye1e=

5、e1*yxeExample: translate (a|b)*abb into an NFAX(a|b)*abbYX (a|b)* 1a 2bb 3 YX 4 1 b 3 a 2 b a|b YX 4 1 b 3 a 2 b a b YRET2.4.2 From an NFA to a DFAGoals and Methods(1) Eliminating -transitions -closure: the set of all states reachable by -transitions from a state or statesijkmaban（a）i,jmkaabn（b）Goal

6、s and Methods(2) Eliminating multiple transitions from a state on a single input character.Keeping track of the set of states that are reachable by matching a single character0123aabc（a）01,23abc（b）Goals and MethodsBoth these processes lead us to consider sets of states instead of single state. Thus,

7、 it is not surprising that the DFA we construct has sets of states of the original NFA as its states.The Algorithm Called Subset ConstructionThe -closure of a Set of states:The -closure of a single state s is the set of states reachable by a series of zero or more -transitions, and we write this set

8、 as_closure of a state always contain the state itself a2314ExampleThe -closure of a set of states: the union of the -closure of each individual state.The Subset Construction Algorithmto obtain the start state of MConstructing a DFA M from a given NFA Maa1,2,42,3,4Examples of Subset Constructiona231

9、4S1,2,42,3,42,3,42,3,4Examples of Subset Construction4a32b18567aS1,2,63,7,4,83,4,7,85, 85,81,2,6b3,4,7,85,8aRET2.4.4 Minimizing the Number of States in a DFAWhy need Minimizing?The process of deriving a DFA algorithmically from a regular expression has the unfortunate property that the resulting DFA

10、 may be more complex than necessaryThe derived DFA for the regular expression a* and an equivalent DFAaaaan Important Result from Automata Theory for MinimizingGiven any DFA, there is an equivalent DFA containing a minimum number of states, and, that this minimum-state DFA is unique It is also possi

11、ble to directly obtain this minimum-state DFA from any given DFA. Algorithm obtaining Mini-States DFAEquivalent StatesIf s and t are two states, they are equivalent if and only if:s and t are both accepting states or both non-accepting states.For each character a, s and t have transitions on a to th

12、e equivalent statesExample of Equivalent StatesC and F are all accepting states. They have transitions on a to C and have transitions on b to E, so they are equivalent states S is a non-accepting state and C is an accepting state. They are not equivalent statesaCDBAEFSbaaaaabbbbbabAlgorithm obtainin

13、g Mini-States DFASplit the set of states into some disjoint sets, so states in one set are equivalent to each other, while any two states of different sets are distinguishable.Algorithm obtaining Mini-States DFAIt begins with the most optimistic assumption possible：createing two sets, one consisting

14、 of all the accepting states and the other consisting of all the non-accepting states. 2. Consider the transitions on each character a of the alphabet for each subset, determine whether all the states in the subset are equivalent or the subset should be split Algorithm obtaining Mini-States DFA(1) I

15、f there are two states s and t in one subset that have transitions on a that land in different sets, we say that a distinguishes the states s and t(2) The set of states under consideration must be split according to where their a-transitions landAlgorithm obtaining Mini-States DFA(3)Error transition

16、s to an error state that is non-accepting. If there are two states s and t such that s has an a-transition to another states, while t has no a-transition at all (i.e., an error transition), then a distinguishes s and t.If s and t both have no a-transition, then they cant be distinguished by aAlgorit

17、hm obtaining Mini-States DFA3. Continue this process until either all sets contain only one element (in which case, we have shown the original DFA to be minimal) or until no further splitting of sets occurs.Example: The regular expression letter(letter|digit)* 10letter23letterdigitletterdigitletterdigitThe accepting sets 1,2,3The nonaccepting sets0letterdigit1letter0Example: the regular expression (a| )b*a distinguishes state 1 from states 2 and 3, and we must