清华大学：《编译原理》课程教学资源_（英文译文）Chapter 2.4 From Regular Expression To DFAs

COMPILER CONSTRUCTION Principles and practice Kenneth C. Louden

COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden

2. Scanning Lexical Analysis) PART TWO

2. Scanning (Lexical Analysis) PART TWO

Contents PART ONE 2. 1 The Scanning Process 2.2 Regular Expression 2.3 Finite automata PART TWO 2. 4 From Regular expressions to dFas Open 2.5 Implementation of a TINY Scanner Open 2.6 Use of Lex to Generate a Scanner Automatically Openl

Contents PART ONE 2.1 The Scanning Process 2.2 Regular Expression 2.3 Finite Automata PART TWO 2.4 From Regular Expressions to DFAs [Open] 2.5 Implementation of a TINY Scanner [Open] 2.6 Use of Lex to Generate a Scanner Automatically [Open]

2. 4 From Regular expression To DFAS

2.4 From Regular Expression To DFAs

Main purpose Study an algorithm Translating a regular expression into a dfa via NFA Regular NFA DFA Program Expression

Main Purpose • Study an algorithm: – Translating a regular expression into a DFA via NFA. Regular Expression NFA DFA Program

Contents From a regular expression to an NFA more From an nfa to a dfa more Simulating an NFA using Subset Construction ore Minimizing the number of states in a dFa more

Contents • From a Regular Expression to an NFA [More] • From an NFA to a DFA [More] • Simulating an NFA using Subset Construction [More] • Minimizing the Number of States in a DFA [More]

2.4.1 From a Regular expression to an nfa

2.4.1 From a Regular Expression to an NFA

The Idea of Thompson’s Construction Use￡- transitions to"glue together" the machine of each piece of a regular expression to form a machine that corresponds to the whole expression Basic regular expression The NFAs for basic regular expression of the form a, c, or (p

The Idea of Thompson’s Construction • Use ε-transitions – to “glue together” the machine of each piece of a regular expression – to form a machine that corresponds to the whole expression • Basic regular expression – The NFAs for basic regular expression of the form a, ε,or φ a 

The Idea of Thompson’s Construction Concatenation: to construct an nfa equal to rs To connect the accepting state of the machine of r to the start state of the machine of s by ane-transition The start state of the machine of r as its start state and the accepting state of the machine of s as its accepting state This machine accepts L(rs)=l(rl(s)and so corresponds to the regular expression rs

The Idea of Thompson’s Construction • Concatenation: to construct an NFA equal to rs – To connect the accepting state of the machine of r to the start state of the machine of s by anε-transition. – The start state of the machine of r as its start state and the accepting state of the machine of s as its accepting state. – This machine accepts L(rs) = L(r)L(s) and so corresponds to the regular expression rs. … r  … s

The Idea of Thompson’s Construction Choice among alternatives: To construct an nfa equal to rIs To add a new start state and a new accepting state and connected them as shown usinge-transitions Clearly, this machine accepts the language L(rs FL(TUL (s), and so corresponds to the regular expression rls

The Idea of Thompson’s Construction • Choice among alternatives: To construct an NFA equal to r | s – To add a new start state and a new accepting state and connected them as shown usingε-transitions. – Clearly, this machine accepts the language L(r|s) =L(r )UL ( s), and so corresponds to the regular expression r|s. … r  … s   