COMPILER CONSTRUCTION Principles and practice Kenneth C. Louden
COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden
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]
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]
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